How to describe a $\operatorname{LL(1)}$ parsing algorithm for strings generated by a given grammar?

I have to design a parser for a specific grammar. Let $G$ be the grammar described as:

$$S \rightarrow aBC $$ $$B \rightarrow bB \mid cC $$ $$C \rightarrow c \mid S $$

My approach

1. Test if the grammar is $\operatorname{LL(1)}$

First I have to determine if the grammar is $\operatorname{LL(1)}$ or not. It seems that G is $\operatorname{LL(1)}$ because:

$\operatorname{FIRST}(aBC) \cap \operatorname{FIRST}(bB \mid cC) \cap \operatorname{FIRST}(c \mid S) = \{a\} \cap \{b,c\} \cap \{c,a\} = \emptyset $

2. Write a string generated by G

$s = abccaccc$

3. Design the algorithm for parsing strings

I'm getting stuck here

4. Test the algorithm for a given string

Lets test the algorithm for a given string $s = abccaccc$

  • $\begingroup$ What conflict do you see? Did you compute first and follow for the rules? $\endgroup$ – Hendrik Jan Nov 6 '17 at 17:55
  • $\begingroup$ @HendrikJan First(B) = {b,c} ; First(C) = {c, a} . So First(B) $\cap$ First(C) = {c} then G is not LL(1). I don't have to compute follow because i don't see epsilon $\endgroup$ – Jack Nov 6 '17 at 18:00
  • $\begingroup$ @Jack: And in what context exactly might you have to choose between predicting a B and predicting a C? $\endgroup$ – rici Nov 6 '17 at 20:29
  • $\begingroup$ Instead you must distinguish the first of "$bB$" vs. the first of "$cC$" to see whether the two productions for $B$ are used in different situations! $\endgroup$ – Hendrik Jan Nov 6 '17 at 21:26
  • $\begingroup$ A language is a set of strings: it does not generate them, but a grammar does. Why jump on LL(1) parsing rather than some other technique: if it is a requirement of the problem, it should be stated in the question, not in the answer. $\endgroup$ – babou Nov 6 '17 at 22:23

Here's a possibly useful quote from Aho, Lam et al ("the Dragon Book"). (Emphasis added.)

A grammar $G$ is $LL(1)$ if and only if whenever $a \to \alpha | \beta$ are two distinct productions of $G$, the following conditions hold:

  1. For no terminal $a$ do both $\alpha$ and $\beta$ derive strings beginning with $a$.

| cite | improve this answer | |
  • $\begingroup$ thanks! But do you know how to design the algorithm? $\endgroup$ – Jack Nov 7 '17 at 12:40
  • $\begingroup$ See that book or some other textbook on compiler construction. Better still, use a parser generator (and you won't be restricted to LL(1) in most cases). Your question is to broad for this site, I think. $\endgroup$ – reinierpost Feb 5 '18 at 21:25

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.