====== Exercises about grammars ====== 1) Consider the following **unambiguous** grammar: <code> expr -> expr add term | term term -> term mul factor | factor factor -> ID | NUM | '(' expr ')' add -> '+' | '-' sub -> '*' | '/' </code> 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: <code> expr -> expr op expr | '(' expr ')' | ID op -> '+' | '*' | '-' | '/' </code> 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)