Exercise 1
Consider the following context-free grammar:
--------------
S -> SASB
S -> d
A -> Aa
A -> e
B -> Bb
B -> Cc
C -> c
(a) Show that the grammar is not LL(1).
(b) Modify the grammar so that it becomes LL(1).
(c) Construct the corresponding LL(1) parse table.
(d) Write the skeleton of the corresponding recursive descent parser.
Exercise 2
Write a context free grammar with the following characteristics:
--------------
(a) The language is composed of expressions, with operators and the atomic symbol 'a';
(b) The language has the following operator precedence hierarchy:
| Precedence |
Operator |
Type |
Associativity |
| 1 |
== < > |
Binary Infix |
Left |
| 2 |
+ - |
Binary Infix |
Right |
| 3 |
× / |
Binary Infix |
Left |
| 4 |
! |
Unary Prefix |
None |
| 5 |
; |
Unary Postfix |
None |
| 6 |
( ) |
Embedding |
None |
(c) Show the derivation tree and the abstract syntax tree for the following expression:
a * a - a * !a + a / ( a; ) < a
Link to the Word Format