Consider the following grammar.

expr ::= expr + expr | expr expr | (expr ) | number number ::= numberdigit | digit digit::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

1. Redefine the grammar in a way that numbers are defined by regular expressions. That is, remove two grammar rules for number and digit nonterminals, and replace them with a single regular expres- sions for numbers.
2. Modify the grammar to define assignment statements with a syntax similar to C/C++, where ex- pressions are assigned to identifiers. Here are the steps:

(a) Add identifier token ID to the CFG. You may define it with regular expressions (since identi- fiers are tokens). We have already seen how to define identifiers with regular expressions, in previous sessions.

(b) Consider a nonterminal for assignment. Lets call this nonterminal assignment. You need to define a CFG rule that defines assignment . An assignment in C/C++ grammatically consists of an identifier (defined in previous step), followed by equality symbol (a terminal), followed by an expression (an already defined nonterminal). This sequence of terminals and nonterminals should be given in the RHS of your CFG rule.

2 Derivations

Consider the following CFG.

expr ::= expr # term | term

term ::= factor @ term | factor

factor ::= (expr) | 0 | 1

expr is the starting nonterminal. Moreover, (, ), 0, 1, #, and @ are terminals. Give derivations for the following expressions:

1. 1 @ 1 # 1 2. 0 @ 0 @ 0 3. 0 @ (0 # 1)