|
|
| (5 intermediate revisions by the same user not shown) |
| Line 1: |
Line 1: |
| == The Problem ==
| | #REDIRECT [[ist:Introduction to Syntax/Exercise 1]] |
| | |
| 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]]
| |