Saturday, 24 August 2013

Find CFG for Lisp-like expressions

Find CFG for Lisp-like expressions

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}

No comments:

Post a Comment