# LL1 parsing algorithm for strings generated by a given grammar

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$

• What conflict do you see? Did you compute first and follow for the rules? Nov 6 '17 at 17:55
• @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
– Jack
Nov 6 '17 at 18:00
• @Jack: And in what context exactly might you have to choose between predicting a B and predicting a C?
– rici
Nov 6 '17 at 20:29
• 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! Nov 6 '17 at 21:26
• 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. Nov 6 '17 at 22:23

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$$.