Considering a grammar that includes a dictionary or list with an optional terminal separator - e.g.:

$$ \begin{align} obj \to & dict \\ &\mid OTHER \\ dict \to & \{ \quad \} \\ & \mid \{ \quad pairs \quad \} \\ pairs \to & pair \quad ,? \\ & \mid pair \quad , \quad pairs \\ pair \to & PAIR \end{align} $$

My understanding is that the above is not an LL(1) grammar because there are productions with FIRST() sets crossing over.

But what if we convert it to the following:

$$ \begin{align} obj \to & dict \\ &\mid OTHER \\ dict \to & \{ \quad dictrest \\ dictrest \to & \} \\ & \mid pair \quad pairseq \quad ,? \quad \} \\ pairseq \to & \varepsilon \\ & \mid , \quad pair \quad pairseq \\ pair \to & PAIR \end{align} $$

Is this latter version LL(1)?

  • 2
    $\begingroup$ There are both methods to remove certain non-LL(1) features and to check whether a grammar is LL(1). Have you attempted either of these? Note also that the, arguably, more pressing concern is whether the new grammar describes the same language as the old one. $\endgroup$ – Raphael Aug 13 '13 at 14:17
  • $\begingroup$ The second version is my attempt to remove non-ll(1) features. I haven't tried a formal method to check for ll(1)-ness. I partly asked this hoping more eyes might spot something more obvious I have missed. Thanks. $\endgroup$ – Basel Shishani Aug 13 '13 at 14:36
  • 2
    $\begingroup$ My suggestion was: train yourself by using the tools at hand. Doing the algorithmic check (on several attempts of yours) you might spot a pattern, causing you to build intuition, causing you to become better. This is hard to simulate here. $\endgroup$ – Raphael Aug 13 '13 at 14:42

You grammar can be boiled down by removing some chain rules to this:

$\qquad\begin{align} obj &\to \{\ dict \mid OTHER \\ dict &\to\ \} \mid PAIR\ pairs\ ,\ \} \mid PAIR\ pairs\ \} \\ pairs &\to\ ,\ PAIR\ pairs \mid \varepsilon \end{align}$

Note that I expanded the $?$ which, as far as I know, is not EBNF. This introduces one source of ambiguity LL(1) can not get rid of. The version with $?$, i.e.

$\qquad\begin{align} obj &\to \{\ dict \mid OTHER \\ dict &\to\ \} \mid PAIR\ pairs\ ,?\ \} \\ pairs &\to\ ,\ PAIR\ pairs \mid \varepsilon \end{align}$

has a similar problem: while deriving $dict$ and you see $PAIR\ ,$, which alternative of $pairs$ do you choose? Impossible to decide.

Note that your basic problem is that you create a sequence of stuff from the left without knowing what the last element is going to be. Formally, you have the right-linear grammar

$\qquad A \to abA \mid ab \mid a$

which generates $(ab)^*a(b\mid\varepsilon)$, surrounded by

$\qquad S \to \{\ A\ \}$.

Selecting the very last rule is indeed problematic -- because you threw away the real end marker, the closing brace! Move that one to $A$, get rid of the ambiguity with $a$ and you are good!

$\qquad\begin{align} S &\to \{\ A \\ A &\to aB \mid\ \} \\ B &\to bA \mid \ \}\end{align}$

  • $\begingroup$ Thanks heaps for your informative answer. The '?' was wrong EBNF notation, supposed to be '[]'. $\endgroup$ – Basel Shishani Aug 25 '13 at 4:46

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.