# Representing grammar for list/dictionary with optional end separator as LL(1)

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)?

• 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. – Raphael Aug 13 '13 at 14:17
• 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. – Basel Shishani Aug 13 '13 at 14:36
• 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. – 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}

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