## Exercises about LL and LR

### LL(1) languages

#### Exercise 1

The following languages are LL(1). For each of them:

• write a pushdown automaton (PDA) to recognize the language,
• write a context-free grammar,
• prove that the grammar you have written is LL(1). In other words, compute the lookahead set for each production rule and check that they are disjoint.

Note that the difficulty level of these exercises is not increasing. Furthermore, for some languages writing the PDA might be easy and the grammar might be difficult, or vice versa.

1. { anbmcn | m, n >= 0 }
2. { anbn | n >= 0 } + { a }
3. { anbm+nam | m, n >= 0 }

#### Exercise 2

Give the lookahead sets for each nonterminal and rule of the following grammars. Which of them are LL(1)?

1. ``````S -> ABab | bAcc
A -> a | c
B -> b | c | ε``````
2. ``````S -> aS | A
A -> ab | b``````
3. ``````S -> AB | ab
A -> aA | ε
B -> bB | ε``````
4. ``````S -> aAbBc
A -> aA | cA | ε
B -> bBc | bc``````

### LR(0) languages

Build the LR(0) machine for the following grammars. The grammars have already been extended with an end-of-string symbol `\$`. Are there any conflicts? If so, of which type?

1. ``````S' -> S \$
S  -> A B
A  -> a A | b
B  -> b B | a``````
2. ``````S' -> S \$
S  -> B A A b
A  -> ε
B  -> b``````
3. ``````S' -> S \$
S  -> a A b | a B
A  -> A a | ε
B  -> A c``````
4. ``````E' -> E \$
E  -> T | E + T
T  -> F | T * F
F  -> i | ( E )``````
5. ``````S' -> S \$
S  -> B B
B  -> a B | c``````
6. ``````S -> E \$
E -> ( L ) | ( ) | i
L -> L , E | E``````
7. ``````S -> E \$
E -> L = R | R
L -> * R | i
R -> L``````

For most of the solutions, you can check this website (check also the Next link).

### Solution of exercise 2.3

Here is the grammar we work with:

``````S -> AB | ab
A -> aA | ε
B -> bB | ε``````

#### Phase 1: computation of `empty`

Start with all set to `False`.

``````empty₀ S = False
empty₀ A = False
empty₀ B = False``````

Let’s compute the first iteration. Each `empty₁` is computed as the disjunction of the `emptyRhs₁` of the production rules.

``````empty₁ S = (emptyRhs₁ AB) or (emptyRhs₁ ab)
= -- emptyRhs₁ ab = False because it starts with a terminal
(empty₀ A and empty₀ B) or False
= (False and False) or False
= False
empty₁ A = (emptyRhs₁ aA) or (emptyRhs₁ ε)
= False or True
= True
empty₁ B = (emptyRhs₁ bB) or (emptyRhs₁ ε)
= False or True
= True``````

We see that `empty₁` is different from `empty₀`, so we keep iterating.

``````empty₂ S = (emptyRhs₂ AB) or (emptyRhs₂ ab)
= (empty₁ A and empty₁ B) or False
= (True and True) or False
= True or False
= True
-- No changes in A or B, as they don't need empty₁
empty₂ A = True
empty₂ B = True``````

If we do one more iteration, we see that `empty₃ = empty₂`, so we are done. `empty X = True` for every non-terminal `X` in the grammar.

#### Phase 2: computation of `first`

``````first₀ S = { }
first₀ A = { }
first₀ B = { }``````

Now we apply the compute the definitions for each right-hand side:

``````Rule S : firstRhs₁ AB = (first₀ A) union (if empty A then firstRhs₁ B else { })
= (first₀ A) union (firstRhs₁ B)
= (first₀ A) union (first₀ B) union (if empty ε then firstRhs₁ ε else { })
= (first₀ A) union (first₀ B) union (firstRhs₁ ε)
= { } union { } union { }
= { }
firstRhs₁ ab = { a }
first₁ S = { } union { a } = { a }

Rule A : firstRhs₁ aA = { a }
firstRhs₁ ε  = { }
first₁ A = { a } union { } = { a }

Rule B : firstRhs₁ bB = { b }
firstRhs₁ ε  = { }
first₁ B = { b } union { } = { b }``````

The new iteration does not match the previous one, so we keep going.

``````Rule S : firstRhs₂ AB = ...
= (first₁ A) union (first₁ B) union (firstRhs₂ ε)
= { a } union { b } union { }
= { a, b }
firstRhs₂ ab = { a }
first₂ S = { a, b } union { a } = { a, b }

Rule A : firstRhs₂ aA = { a }
firstRhs₂ ε  = { }
first₂ A = { a } union { } = { a }

Rule B : firstRhs₂ bB = { b }
firstRhs₂ ε  = { }
first₂ B = { b } union { } = { b }``````

Once again, after doing one iteration we see that `first₃ = first₂`, so our final computation is:

``````first₂ S = { a, b }
first₂ A = { a }
first₂ B = { b }``````

#### Phase 3: computation of `follow`

``````follow₀ S = { }
follow₀ A = { }
follow₀ B = { }``````

Remember that in `follow` the union is made over all right-hand sides of production rules which contain the corresponding non-terminal. That is:

• For `S` there is no rule to consider, since no right-hand side mentions it;
• For `A` we have to consider the rules `S -> AB` and `A -> aA`;
• For `B` we have to consider the rules `S -> AB` and `B -> bB`.

Furthermore, the `followRhs` function is called with the left-hand side of the rule, and the remainder of the rule after the non-terminal we are trying to compute.

``````follow₁ S = { }  -- no rule

followRhs₁ S B = (firstRhs B) union (if emptyRhs B then follow₀ S else { })
= (first B) union (if empty B then follow₀ S else { })
= { b } union (follow₀ S)
= { b } union { }
= { b }

followRhs₁ A ε = (firstRhs ε) union (if emptyRhs ε then follow₀ A else { })
= { } union (follow₀ A)
= { } union { }
= { }

follow₁ A = (followRhs₁ S B) union (followRhs₁ A ε)
= { b } union { }
= { b }

followRhs₁ S ε = (firstRhs ε) union (if emptyRhs ε then follow₀ S else { })
= { } union (follow₀ S)
= { } union { }
= { }

followRhs₁ B ε = (firstRhs ε) union (if emptyRhs ε then follow₀ B else { })
= { } union (follow₀ B)
= { } union { }
= { }

follow₁ B = { } union { }
= { }``````

Let’s do it one more time:

``````follow₂ S = { }  -- no rule

followRhs₂ S B = ...
= { b } union (follow₁ S)
= { b } union { }
= { b }

followRhs₂ A ε = ...
= { } union (follow₁ A)
= { } union { }
= { b }

follow₂ A = (followRhs₁ S B) union (followRhs₁ A ε)
= { b } union { b }
= { b }

followRhs₂ S ε = ...
= { } union (follow₁ S)
= { } union { }
= { }

followRhs₂ B ε = ...
= { } union (follow₁ B)
= { } union { }
= { }

follow₂ B = { } union { }
= { }``````

And we are done!

#### Phase 4: computation of `lookAhead` of each rule

``````lookAhead (S -> AB) = followRhs S AB
= (firstRhs AB) union (if emptyRhs AB then follow S else { })
= { a, b } union (follow S)
= { a, b }

lookAhead (S -> ab) = followRhs S ab
= (firstRhs ab) union (if emptyRhs ab then follow S else { })
= { a } union { }
= { a }

lookAhead (A -> aA) = followRhs A aA
= (firstRhs aA) union (if emptyRhs aA then follow A else { })
= { a } union { }
= { a }

lookAhead (A -> ε)  = followRhs A ε
= (firstRhs ε) union (if emptyRhs ε then follow A else { })
= { } union (follow A)
= { } union { b }
= { b }

lookAhead (B -> bB) = ... = { b }

lookAhead (B -> ε)  = (firstRhs ε) union (if emptyRhs ε then follow B else { })
= { } union (follow B)
= { } union { }
= { }``````

Looking at this results, we see that the grammar is not LL(1) for two reasons:

• The rules for `S` have not disjoint lookahead sets.
• The rules for `B` neither, since the second one has an empty lookahead set.