I'm trying to solve some exercises for the upcoming Compilers' exam. Teacher gave us some sheets from previous exams to practice with - no answers provided.

Let $\mathcal{G}$ be the following context-free grammar: $$ \begin{aligned} A &\to BC \\ B &\to aD\; |\; bD \\ C &\to BCC \; | \; aCd \; | \; \epsilon \\ D &\to aD \; | \; bD \; | \;\epsilon \end{aligned} $$ Provide the LL(1) parsing table for $\mathcal{G}$.

Ok. Before rushing into the construction of the table, I've asked myself: is this really a LL(1) grammar? A quick look at the definition of the grammar is already telling me that probably it is not. The dragon book gives the following criteria for establishing whether a cfg is LL(1):

A grammar $\mathcal{G}$ is LL(1) if and only if whenever A → α | β are two distinct productions of $\mathcal{G}$, the following conditions hold:

  1. FIRST(α) and FIRST(β) are disjoint sets;
  2. if ε is in FIRST(β), then FIRST(α) and FOLLOW(A) are disjoint sets;
  3. likewise if ε is in FIRST(α).

What caught me first was the production rules for nonterminal $C$, so I computed the first sets involved in them:

$$ \begin{aligned} \mathrm{FIRST}(BCC) &= \mathrm{FIRST}(B) = \lbrace a, b \rbrace \\ \mathrm{FIRST}(aCd) &= \lbrace a \rbrace \\ \mathrm{FIRST}(\epsilon) &= \lbrace \epsilon \rbrace. \end{aligned} $$

Of course, at least two of these sets are not disjoint, so it follows that the grammar is not LL(1).

How shall I proceed? Does this suffice as answer, or shall I provide an equivalent LL(1) grammar with its parsing table? What would you do?

  • 3
    $\begingroup$ I would ask my teacher. $\endgroup$ – adrianN Jun 15 '16 at 14:11
  • 2
    $\begingroup$ You can still produce the table. It will have an undesirable property, but it will exist. $\endgroup$ – André Souza Lemos Jun 15 '16 at 16:13
  • $\begingroup$ @AndréSouzaLemos So I have to expect a table with multiple entries, right? $\endgroup$ – Filippo De Bortoli Jun 15 '16 at 16:28
  • $\begingroup$ There you go. Additionally, try to figure out what language is defined by this grammar. $\endgroup$ – André Souza Lemos Jun 15 '16 at 16:34
  • $\begingroup$ @adrianN you got a point on this. However, I wanted to know how other people would go on this exercise. Is it more natural to show that the grammar is not LL(1) and conclude that some of its LL(1) parsing table's entries would be multiply defined, or just build the table and highlight the interested entries? Or both of them? $\endgroup$ – Filippo De Bortoli Jun 16 '16 at 9:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.