Homework 2 Solutions

(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 points)

Stack                       Input          | Production
---------------------------------------------------------
$                        <  (a,((a,a),a))$ |
$ <(                     <   a,((a,a),a))$ |
$ <( <a                  >    ,((a,a),a))$ | S --> a
$ <( S                   <    ,((a,a),a))$ |
$ <( <S ,                <     ((a,a),a))$ |
$ <( <S , <(             <      (a,a),a))$ |
$ <( <S , <( <(          <       a,a),a))$ |
$ <( <S , <( <( <a       >        ,a),a))$ | S --> a
$ <( <S , <( <( S        <        ,a),a))$ |
$ <( <S , <( <( <S ,     <         a),a))$ |
$ <( <S , <( <( <S , <a  >          ),a))$ | S --> a
$ <( <S , <( <( <S , S   >          ),a))$ | L --> L,S
$ <( <S , <( <( L        =          ),a))$ |
$ <( <S , <( <( =L )     >           ,a))$ | S --> (L)
$ <( <S , <( S           <           ,a))$ |
$ <( <S , <( <S ,        <            a))$ |
$ <( <S , <( <S , =a     >             ))$ | S --> a
$ <( <S , <( <S , S      >             ))$ | L --> L,S
$ <( <S , <( L           =             ))$ |
$ <( <S , <( =L )        >              )$ | S --> (L)
$ <( <S , S              >              )$ | L --> L,S
$ <( L                   =              )$ |
$ <( =L )                >               $ | S --> (L)
$ S                                      $ |
Successful parse.

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 points) Assuming we have a function max() which returns the maximum of its two arguments, we may use the following:
```
S --> S1 S2 {S.maxdepth <- max(S1.maxdepth, S2.maxdepth)}
    | ( S1 ) {S.maxdepth <- S1.maxdepth + 1}
    | ( ) {S.maxdepth <- 1}
```
2. Now give an equivalent syntax-directed translation scheme based on the LL(1) grammar.
  (2 points) We may proceed by first transforming the above augmented grammar to match the non-left-recursive intermediate grammar:
```
S --> ( S1 ) S2 {S.maxdepth <- max(S1.maxdepth + 1, S2.maxdepth)}
    | ( ) S2 {S.maxdepth <- max(1, S2.maxdepth)}
    | ( S1 ) {S.maxdepth <- S1.maxdepth + 1}
    | ( ) {S.maxdepth <- 1}
```
  Now we just need to factor these productions as before, modifying the semantic actions so that they apply to both cases when two productions are merged:
```
S --> ( T {S.maxdepth <- T.maxdepth}
T --> S ) U {T.maxdepth <- max(S.maxdepth + 1, U.maxdepth)}
    | ) U {T.maxdepth <- max(1, U.maxdepth)}
U --> S {U.maxdepth <- S.maxdepth}
    | e {U.maxdepth <- 0}
```
  If we are willing to introduce inherited attributes, then the factoring step may be performed in a semi-automatic fashion by noting that when two productions have a common prefix factored out into a single nonterminal, the two productions that result for that nonterminal just need to have passed in to them whatever was computed in the common prefix. Thus, another solution is
```
S --> ( T {S.maxdepth <- T.maxdepth}
T --> S ) {U.i <- S.maxdepth + 1} U {T.maxdepth <- U.maxdepth}
    | ) {U.i <- 1} U {T.maxdepth <- U.maxdepth}
U --> S {U.maxdepth <- max(U.i, S.maxdepth)}
    | e {U.maxdepth <- U.i}
```

(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

Give a syntax-directed translation scheme to determine the type of each subexpression.

(2 points)

E --> E1 + T {if E1.t = int and T.t = int}
             {then E.t <- int            }
             {else E.t <- real           }
    | T {E.t <- T.t}
T --> num . num {T.t <- real}
    | num {T.t <- int}

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.

(2 points) If we write s @ t for the concatenation of the strings s and t, then the following translation scheme synthesizes the correct string representation in the attribute E.v:

E --> E1 + T {if E1.t = int and T.t = int                  }
             {then E.t <- int;                             }
             {     E.v <- E1.v @ " " @ T.v @ " +"          }
             {else if E1.t = int                           }
             {then E.t <- real;                            }
             {     E.v <- E1.v @ " inttoreal " @ T.v @ " +"}
             {else if T.t = int                            }
             {then E.t <- real;                            }
             {     E.v <- E1.v @ " " @ T.v @ " inttoreal +"}
             {else E.t <- real;                            }
             {     E.v <- E1.v @ " " @ T.v @ " +"          }
    | T {E.t <- T.t;  E.v <- T.v}
T --> num1 . num2 {T.t <- real;                          }
                  {T.v <- num1.lexval @ "." @ num2.lexval}
    | num {T.t <- int;  T.v <- num.lexval}

A clever solution which prints as it parses (suggested by several students) has this for E:

E --> E1 + T {if E1.t = int and T.t = int                    }
             {then E.t <- int;  Print(T.v, "+")              }
             {else if E1.t = int                             }
             {then E.t <- real;  Print("inttoreal", T.v, "+")}
             {else if T.t = int                              }
             {then E.t <- real;  Print(T.v, "inttoreal", "+")}
             {else E.t <- real;  Print(T.v, "+")             }
    | T {E.t <- T.t;  Print(T.v)}

Eliminate left recursion from this extended translation scheme.

(2 points) Here are the changed productions for E:

 E --> T {E'.it <- T.t;  E'.iv <- T.v}
         E' {E.t <- E'.t;  E.v <- E'.v}
E' --> + T {if E'.it = int and T.t = int                     }
           {then E'1.it <- int;                              }
           {     E'1.iv <- E'.iv @ " " @ T.v @ " +"          }
           {else if E'.it = int                              }
           {then E'1.it <- real;                             }
           {     E'1.iv <- E'.iv @ " inttoreal " @ T.v @ " +"}
           {else if T.t = int                                }
           {then E'1.it <- real;                             }
           {     E'1.iv <- E'.iv @ " " @ T.v @ " inttoreal +"}
           {else E'1.it <- real;                            }
           {     E'1.iv <- E'.iv @ " " @ T.v @ " +"          }
         E'1 {E'.t <- E'1.t;  E'.v <- E'1.v}
     | e {E'.t <- E'.it;  E'.v <- E'.iv}