Languages and Compilers - Exercises about LL and LR

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.

{ aⁿb^mcⁿ | m, n >= 0 }
{ aⁿbⁿ | n >= 0 } + { a }
{ aⁿb^m+na^m | m, n >= 0 }

Exercise 2

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

S -> ABab | bAcc
A -> a | c
B -> b | c | ε

```
S -> aS | A
A -> ab | b
```
```
S -> AB | ab
A -> aA | ε
B -> bB | ε
```
The solution can be found at the end of this page.

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?

S' -> S $
S  -> A B
A  -> a A | b
B  -> b B | a

S' -> S $
S  -> B A A b
A  -> ε
B  -> b

S' -> S $
S  -> a A b | a B
A  -> A a | ε
B  -> A c

E' -> E $
E  -> T | E + T 
T  -> F | T * F
F  -> i | ( E )

```
S' -> S $
S  -> B B
B  -> a B | c
```

S -> E $
E -> ( L ) | ( ) | i
L -> L , E | E

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`

Start with all set to the empty set:

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`

Start with all set to the empty set:

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.