Homework 2

Due Friday, November 4 at the start of class. Late homeworks will be accepted, with a 20% penalty, until the corrected papers are returned to the class. You may discuss the problems with other students, but your submitted work should be done independently.

1. (Aho, Sethi, and Ullman 4.24) The table below shows operator-precedence relations for the following grammar:

   S --> ( L )
       | a
   B --> L , S
       | S

   Using these precedence relations, parse the sentence (a,((a,a),a)).

      | a | ( | ) | , | $
   -----------------------
    a |   |   | > | > | >
    ( | < | < | = | < |
    ) |   |   | > | > | >
    , | < | < | > | > |
    $ | < | < |   |   |

2. We may convert the grammar

   S --> S S
       | ( S )
       | ( )

   into LL(1) form by first substituting the non-left-recursive productions for the left S in the first production, yielding

   S --> ( S ) S
       | ( ) S
       | ( S )
       | ( )

   (note that this removes the ambiguity of the original grammar, which had two distinct derivations of the string ()()(), by forcing the recursion to go to the right); this grammar may then be factored into

   S --> ( T
   T --> S ) U
       | ) U
   U --> S
       | e

   which may easily be seen to be LL(1).
   1. Show how to augment the original grammar with semantic actions which synthesize the attribute S.maxdepth, which counts the maximum nesting of parentheses in the string produced from S. For example, in the derivation of (())(), the maxdepth attribute of the start symbol should be 2.
   2. Now give an equivalent syntax-directed translation scheme based on the LL(1) grammar.
3. (Aho, Sethi, and Ullman 5.6 & 11) The following grammar generates expressions formed by applying an arithmetic operator + to integer and real constants. When two integers are added, the resulting type is integer, otherwise, it is real.

   E --> E + T
       | T
   T --> num . num
       | num

   1. Give a syntax-directed translation scheme to determine the type of each subexpression.
   2. Extend this translation scheme to translate expressions into postfix notation as well as determining types. Use the unary operator inttoreal to convert an integer value into an equivalent real value, so that both operands of + in the postfix form have the same type.
   3. Eliminate left recursion from this extended translation scheme.