The Problem
Consider the following grammar:
bexpr -> bexpr or bexpr | bterm
bterm -> bterm and bterm | bfactor
bfactor -> not bfactor | ( bexpr ) | true | false
- Identify the terminal and non-terminal symbols of the grammar.
- Show that the grammar is ambiguous by deriving two different trees for the same input sequence.
- Write a non-ambiguous grammar for the same language.
- Build the tree corresponding to the analysis of the following input sequence: not ( true or false and true )
Solution
The terminal symbols are all the symbols not defined by a rule: or, and, not, (, ), true, false.