1
$\begingroup$

This question arose out of a concrete problem I had, which was to find an $\varepsilon$-free variant of the following LL(1) grammar $G_0$ that I developed for a Lisp-like language $L$ (I found a monotone LR(0) variant):

$$ \begin{array} \\ P & \rightarrow & (EP \\ & | & \varepsilon \\ E & \rightarrow &iE \\ & | &sE \\ & | &nE \\ & | &(EE \\ & | &) \end{array} $$ where the start symbol is $P$. With this grammar, the leftmost derivation of $\omega = (i()sn)(inn)$ is $$ \begin{array} \\ P & \Rightarrow_L (EP \\ & \Rightarrow_L (iEP \\ & \Rightarrow_L (i(EEP \\ & \Rightarrow_L (i()EP \\ & \Rightarrow_L (i()sEP \\ & \Rightarrow_L (i()snEP \\ & \Rightarrow_L (i()sn)P \\ & \Rightarrow_L (i()sn)(EP \\ & \Rightarrow_L (i()sn)(iEP \\ & \Rightarrow_L (i()sn)(inEP \\ & \Rightarrow_L (i()sn)(innEP \\ & \Rightarrow_L (i()sn)(inn)P \\ & \Rightarrow_L (i()sn)(inn) \end{array} $$ My problem is that the parser generated by this grammar accepts the empty string, and I would like to exclude that.
So I am looking for an $\varepsilon$-free LL(1) grammar $G_1$ that generates $L-\{\varepsilon\}$. I have tried several times without success, leading me to doubt whether $L-\{\varepsilon\}$ is simple deterministic.

$\endgroup$
0
$\begingroup$

The solution is to simply start in a slightly different starting state before starting the main recursion:

$$ \begin{array} \\ S & \rightarrow & (EP\\ P & \rightarrow & (EP \\ & | & \varepsilon \\ E & \rightarrow &iE \\ & | &sE \\ & | &nE \\ & | &(EE \\ & | &) \end{array} $$

$\endgroup$
  • $\begingroup$ Not monotone due to $P \rightarrow \varepsilon$, but it at least generates $L - \{\varepsilon\}$ (and even contains the original grammar), so a point for that. $\endgroup$ – setun-90 Dec 31 '17 at 18:47
  • $\begingroup$ Now that I have researched a bit, the simple deterministic languages contain the languages which have an end marker, which is obviously not the case of this language, so I believe it's highly unlikely it's simple deterministic, making this grammar the best one. $\endgroup$ – setun-90 Jan 13 '18 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.