CSE 321 Homework 12

1. Consider the following rewrite rules where <L> is the start symbol:

<L> -> <L> + <A> | <A>
<A> -> <A> * <Z> | <Z>
<Z> -> ( <L> ) | 0 | 1

a) What are the terminal symbols in these rules?
b) What are the nonterminal symbols in these rules?
c) Show the derivation (parse) tree for the string ( ( 1 + 1 ) * 0 + 1 + ( 0 + 0 ) * 1 )
d) Assume the following equalities:

0 + 0 = 1
0 + 1 = 0
1 + 0 = 0
1 + 1 = 1
0 * 0 = 0
0 * 1 = 1
1 * 0 = 1
1 * 1 = 0
(0) = 0
(1) = 1

Using these equalities and the derivation tree you created, give the value, either 1 or 0, of the string in part c above.

2. Using the following rewrite rules for arithmetic expressions, draw a derivation tree for the expression 5 * 3 + 1 + 4.

<expression>    ->  <expression> <addop> <term> |
                    <term>

<term>          ->  <term> <multop> <factor> |
                    <factor>

<factor>        ->  ( <expression> ) |
                    <digit seqnce>

<addop>         ->  + | -

<multop>        ->  * | DIV | MOD

<digit seqnce>  ->  <digit> |
                    <digit> <digit seqnce>

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

3. Using the following rewrite rules for arithmetic expressions, draw a derivation tree for the expression 5 * 3 + 1 + 4.

<expression>    ->  <term> {<addop> <term>}

<term>          ->  <factor> {<multop> <factor>}

<factor>        ->  ( <expression> ) |
                    <digit seqnce>

<addop>         ->  + | -

<multop>        ->  * | DIV | MOD

<digit seqnce>  ->  <digit> |
                    <digit> <digit seqnce>

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

Note: a pair of new special symbols ('{' and '}') is used in the rewrite rules above. The meaning of {...} is that the string of nonterminal and terminal symbols appearing between { and } can be repeated 0 or more times. For instance, the first rewrite rule:

<expression>  ->  <term> {<addop> <term>}

is equivalent to the following (infinite) set of rewrite rules:

<expression>  ->  <term>
                  <term> <addop> <term>
                  <term> <addop> <term> <addop> <term>
                  <term> <addop> <term> <addop> <term> <addop> <term>
                  ...