Revision as of 23:54, 2 April 2010

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

1. The terminal symbols are all the symbols not defined by a rule: or, and, not, (, ), true, false.

2. The following trees are possible for true and false and true (an analogous analysis could be done for or). Terminals are in blue and non-terminals in black.

3. The following grammar selects left associativity for the binary operators (and and or):

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

4. The following analysis considers the grammar defined in 3 (again, terminals are in blue and non-terminals in black).