Revision as of 13:05, 8 April 2008

The Problem

Consider the following grammar:

 bexpr   -> bexpr or bexpr | bterm
 bterm   -> bterm and bterm | bfactor
 bfactor -> not bfactor | ( bexpr ) | true | false

1. Identify the terminal and non-terminal symbols of the grammar.
2. Show that the grammar is ambiguous by deriving two different trees for the same input sequence.
3. Write a non-ambiguous grammar for the same language.
4. Build the tree corresponding to the analysis of the following input sequence: not ( true or false and true )

Solution