Find CFG for Lisp-like expressions

1k Views Asked by At

All Lisp-like expressions.

A Lisp expression may be an unsigned integer or a list. A list, enclosed by left and right parentheses, consists of one operator ($+$, $-$, $*$, $/$, $\max$, $\min$) followed by a sequence of at least one Lisp expression. For instance, $13$, $(- \;8)$, $(*\; 9\; 3)$, $(+\; (*\; 2\; 2)\; 4)$, and $(\min\; (\max\; 3\; 1\; 4) (\max\; 2\; 7\; 1))$ are Lisp expressions.

This is my solution:

\begin{gather} S \to X \mid Y \\ X \to 0\text{–}9 X \mid \epsilon \\ Y \to ( E )\mid \epsilon \\ E \to +,-,*,/,\max,\min YX \end{gather}