View source for Introduction to Syntax/Exercise 1

== 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 ==

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

2. The following trees are possible for true and false and true (an analogous analysis could be done for '''or''')

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 analysis considers the grammar defined in 3.



[[category:Compilers]]
[[category:Teaching]]