Introduction to Compilers

Spring 2002

**due: **Monday, February 18, in class

- Write an unambiguous grammar for each of the following languages:
a) Strings of a's followed by b's which have twice more a's than b's

b) Strings of a's and b's with the same number of a's and b's - a) Calculate nullable, FIRST, FOLLOW for the following gramar:
`S -> u B D z`

B -> B v | w

D -> E F

E -> y | e

F -> x | eb) Construct the LL(1) parsing table and give evidence that this grammar is not LL(1)

d) Give an LL(1) grammar which accepts the same language and build the LL(1) parsing table for that grammar

- Consider the following grammar:
- Show that this grammar is LALR(1), but not SLR:
`S -> A a | b A c | d c | b d a`

A -> d - Show that the following grammar is LR(1), but not
LALR(1):
`S -> A a | b A c | B c | b B a`

A -> d

B -> d

```
E -> E + E |
E * E | ( E ) | num
```

This is an ambiguous
grammar. We would like an unambiguous grammar where multiplication (*) has
higher precedence over addition (+).

a) write an LL(1) grammar
which accepts the same language and respects the desired operator precedence

b) show the derivation tree for the expression 1+2*3*4+5

c) write an LR(1) grammar which accepts the same language, respects the desired
operator precedence, and is such that multiplication is left-associative, and
addition is right-associative.