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
    Commented 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
    Commented Jan 13, 2018 at 23:12

Your Answer

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

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