# Is this $LL(1)$ grammar valid?

Is the following a valid $LL(1)$ grammar:

\begin{align} S &\rightarrow L \ \\ L &\rightarrow M L_2 \\ L_2 &\rightarrow \underline{::} L \\ L_2 &\rightarrow \epsilon \\ M &\rightarrow \underline{id} R \\ R &\rightarrow \underline{(} R_2 \\ R_2 &\rightarrow M \underline{)} \\ R_2 &\rightarrow \underline{)} \end{align} $I am not sure because of$R_2$since there are two rules I could apply to reach$\$$(bottom of stack) or do I understand something wrong here? So in the parsing table for R_2 under \$$ I have the options $R_2 \rightarrow M \underline{)}$ and $R_2 \rightarrow \underline{)}$

Could somebody clarify?

• There are (computable) characterisations of LL(1) grammars. Have you checked those? See also here. – Raphael Dec 15 '14 at 13:13

I believe you have misunderstood what the parsing table does. The parsing table tells for each pair $(A,a)$, where $A$ is a non-terminal symbol and $a$ is a terminal symbol, which grammar rule you have to use so that the next non-terminal symbol produced to the string from the left will be $a$. For example, the symbol $R_2$ produces either the symbol $id$ by the derivation $$R_2 \rightarrow M) \rightarrow idR)$$ or the symbol $)$ by $$R_2 \rightarrow )$$ Thus in the parsing table, $(R_2, id)$ points to rule "$R_2 \rightarrow M)$", and $(R_2,\textrm{'})\textrm{'})$ points to rule "$R_2 \rightarrow )$". The case $(R_2, \$)$is a parsing error, since the dollar sign cannot be reached from$R_2$without first producing either$id$or$)$. If fact, all other terminal symbols except for$id$and$)$are parsing errors. A grammar is a valid$LL(1)$grammar if for every pair$(A,a)$there is only one choice for which grammar rule to use. In our grammar the possibly problematic rules are the ones for$L_2$and$R_2$, because they have two choices. The rest of the non-terminals are clearly unambiguous, as there is only one choice. I gave the unambiguous parsing table rules$R_2$above. For$L_2$, the only symbols which do not produce a parsing error are$\epsilon$and$::$. For$\epsilon$we use the rule$L_2 \rightarrow \epsilon$, and for$::$we use the rule$L_2 \rightarrow :: L$. Therefore the parsing rules for$L_2$is also unambiguous, and in conclusion the grammar is a valid$LL(1)$grammar. • Hi! The thing is that$FOLLOW(R_2) = \{\underline{::}, \epsilon, \$\}$ if I'm not mistaken e.g. for an input $\underline{id}\underline{(}\underline{)}$ the end of stack $\$$follows after$R_2$. But this holds for both rules of$R_2\$. I think this is where my confusion begins. – displayname Dec 15 '14 at 14:56