# Figuring out whether LL(1) grammar has an $\varepsilon$-free variant

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.

$$\begin{array} \\ S & \rightarrow & (EP\\ P & \rightarrow & (EP \\ & | & \varepsilon \\ E & \rightarrow &iE \\ & | &sE \\ & | &nE \\ & | &(EE \\ & | &) \end{array}$$
• 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. – setun-90 Dec 31 '17 at 18:47