## Description

- (5 points) We have the following grammar with the start symbol <e>:

<e> -> <d> | <e> * <e> | <e> / <e>

<d> -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

- Show a leftmost derivation for the expression “2 * 3 * 6”.
- Show a rightmost derivation for the above expression.
- Show two different parse trees for the above expression.
- The grammar is ambiguous. Show a new grammar that removesthe ambiguity and makes “*” and “/” left-associative. Show the parse tree for “2 * 3 / 6” in your new grammar. Argue why this is the only parse tree in the new grammar.
- Show a new grammar that removes the ambiguity and makes “*”and “/” right-associative. Show the parse tree for “2 * 3 / 6” in the new grammar.

- (3 points) Consider the language consisting of strings that represent the list of numbers separated by commas. For instance, the string “10,7” and “1, 7, 5, 13” are in the language; also included in the language are lists of a single number (e.g., “12”). Write an unambiguous BNF grammar for the language. Briefly explain why your grammar is unambiguous.
- (3 points). The following grammar for arithmetic expressions allow addition, subtraction, as well as a unary operator “~” for negation; that is, “~8” is interpreted as number negative eight.

1

<e> -> <d> | <e> + <e> | <e> – <e> | ~<e>

<d> -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

The grammar is clearly ambiguous. Change the grammar so that “+” and “-” are left-associative and the precedence of “~” is higher than “+” and “-”.

- (4 points) A simplified email address has (i) an account name starting with a letter and continuing with any number of letters or digits; (ii) an @ character; (iii) a host with two or more sequences of letters or digits separated by periods; the last sequence must be a toplevel domain— either ’edu’, ’org’, or ’com’. Define a context-free grammar to model this language.
- (4 points) The following grammar discussed in class is for constructing numbers:

<n> -> <d> | <n> <d>

<d> -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Numbers with leading zeros such as 007 belong to the above grammar. Change the grammar so that numbers with leading zeros cannot be derived from the new grammar; however, number 0 itself should still be allowed. As a sanity check, make sure numbers such as 70 and 107 belong to your grammar, while numbers such as 070 do not.

- (3 points) The following E-BNF grammar is used to specify decimal numbers such as 7.9 and -10.78. Translate it into an equivalent BNF grammar.

<expr> -> [-] <int> [.<int>]

<int> -> <digit> {<digit>}

<digit> -> 0 | 1 | … | 9

2