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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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} $$

Improve this answer
$\endgroup$
2
  • $\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, 2017 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, 2018 at 23:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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