Introduction to Syntax/Exercise 1

The Problem

Consider the following grammar: <text> bexpr -> bexpr or bexpr | bterm bterm -> bterm and bterm | bfactor bfactor -> not bfactor | ( bexpr ) | true | false </text>

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 )