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?

  • 1
    $\begingroup$ There are (computable) characterisations of LL(1) grammars. Have you checked those? See also here. $\endgroup$
    – 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.

  • $\begingroup$ 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. $\endgroup$ Dec 15 '14 at 14:56

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.