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 ( ) ε ε