The exercises of Chapter Three

3.2 Given the grammar A →AA|(A)|ε

a. Describe the language it generates;

b. Show that it is ambiguous.

[Solution]:

a. Generates a string of balanced parenthesis, including the empty string.

b. parse trees of ():

3.3 Given the grammar

exp → exp addop term | term

addop → + | -

term → term mulop factor| factor

mulop → *

factor → ( exp ) | number

Write down leftmost derivations, parse trees, and abstract syntax trees for the following expression:

a. 3+4*5-6

b. 3*(4-5+6)

c. 3-(4+5*6)

[Solution]: a. The leftmost derivations for the expression

3+4*5-6:

Exp => exp addop term =>exp addop term addop term =>term addop term addop term=> factor addop term addop term

=>3 addop term addop term => 3 + term addop term

=>3+term mulop factor addop term =>3+factor mulop factor addop term

=>3+4 mulop factor addop term => 3+4* factor addop term A ( ) ε A A

A A A ( ) ε ε