1) Consider the following unambiguous grammar:
expr -> expr add term | term
term -> term mul factor | factor
factor -> ID | NUM | '(' expr ')'
add -> '+' | '-'
sub -> '*' | '/'
a) Do a leftmost derivation for the following: x + 3 - 4 * y / 7
b) Draw the parse tree for the leftmost derivation, numbering the steps
c) Do a rightmost derivation for the same
d) Draw the parse tree for the rightmost derivation, numbering the steps
Your trees must be the same, where only the order of construction is different.
2) Consider the following ambiguous grammar:
expr -> expr op expr | '(' expr ')' | ID
op -> '+' | '*' | '-' | '/'
a) Do two different leftmost derivations for the input a*(b+c)/d-e, such that the resulting parse trees are different. Comment on which parse tree is in compliance with our general knowledge of operator precedence in arithmetic expressions.
b) Do two different rightmost derivations for the same, such that the resulting parse trees are different. Comment on which parse tree is in compliance with our general knowledge of operator precedence in arithmetic expressions.
3) Consider a language like the one in Exercise 1, but this time with the following operators: ∪ (union), ∩ (intersection), and - (difference). The precedence order is as follows: - > ∩ > ∪. Also, ∩ and ∪ are left-associative and - is right-associative.
a) Write an unambiguous grammar for this language
b) Do a leftmost derivation for the following: x - (y ∪ z) - v ∩ w
c) Draw the parse tree (no need for numbering the steps)