ANSWERS

Directions: You may write on the exam or use extra paper or both. You should probably use a separate sheet for the answer to 4. You cannot expect the proctor to answer questions about this exam, so you should give the best answer you can that fully answers the question. You are not allowed to use anything except the exam sheets. (No crib sheets, no notes, no calculator, no cell phone. Um, writing instruments are OK.) (20) Show that the grammar below is ambiguous by finding a sentence that has two different parse trees or two different leftmost derivations. Write down the sentence, the two distinct parse trees, and the two distinct leftmost derivations. E ---> E + E E ---> E * E E ---> ( E ) E ---> id 1st: E 2nd: E /|\ /|\ E + E E * E / /|\ /|\ \ id / * \ E + E id id id / \ id id 1st: E ==> E + E ==> id + E ==> id + E * E ==> id + id * E ==> id + id * id 2nd: E ==> E * E ==> E + E * E ==> id + E * E ==> id + id * E ==> id + id * id (15) (a) Translate the following ordinary arithmetic expression into Reverse Polish Notation (RPN): (5+4)*2^3$. [You can use any method and can give the final answer without showing work, but the order of the digits in the answer should be the same as in the original. One method is to work from a small "skeleton" parse tree.] E | T | +--------+-----+ | | | T | | | | | S | | | | | F | | | | | +-----+-----+ | | | | | | | | E | | | | | | | | | +--+--+ | | | | | | | | | | | E | | | | S | | | | | | | | T | T | | +--+--+ | | | | | | | | | | S | S | | | | S | | | | | | | | | | F | F | | F | F | | | | | | | | | ( 5 + 4 ) * 2 ^ 3 E | T /|\ / | \ / * S / /|\ T / | \ | F ^ S S | | | 2 F F | /|\ 3 / | \ ( E ) /|\ / | \ E + T | | T S | | S F | | F 4 | 5 Working our way up from the bottom, we would successively output: 5 4 +   (followed by) 2 3 ^   (followed by) *   (or altogether) 5 4 + 2 3 ^ * $   (the answer) The most common error was to write: 5 4 + 2 * 3 ^ $ which is a translation of ( ( 5 + 4 ) * 2 ) ^ 3 $ (or else perhaps assuming that ^ has lower precedence than *, but in fact ^ has the highest precedence of these operators ). (b) Evaluate the following RPN expression and show your work, step-by-step (not just a final answer): 342+5**$. [Here "evaluate" means to find the final single integer value of the expression.] Evaluate 342+5**$ from left to right: push(3); push(4); push(2); 2=pop(); 4=pop(); push(4+2=6); push(5); 5=pop(); 6=pop(); push(6*5=30); 30=pop(); 3=pop(); push(3*30=90); stack contains only 90. (20) Consider the following grammar and the sentence to the right of it. Is this grammar ambiguous? (Just Yes or No.) Write out a leftmost derivation and a parse tree for this sentence. Is there more than one parse tree for the sentence? (Just Yes or No.) E ---> E + T | T T ---> T * F | F F ---> ( E ) | id    ( id + id ) * id E | T | +----------+---+ | | | T | | | | | F | | | | | +-----+------+ | | | | | | | | E | | | | | | | | | +--+--+ | | | | | | | | | | | E | | | | | | | | | | | | | T | T | | | | | | | | | | | F | F | | F | | | | | | | ( id + id ) * id E | T /|\ / | \ T * F | | F id /|\ / | \ ( E ) /|\ / | \ E + T | | T F | | F id | id E ==> T ==> T * F ==> F * F ==> ( E ) * F ==> ( E + T ) * F ==> ( T + T ) * F ==> ( F + T ) * F ==> ( id + T ) * F ==> ( id + F ) * F ==> ( id + id ) * F ==> ( id + id ) * id (35) Consider the grammar on the left and the corresponding parse table for shift-reduce parsing on the right below. Use the table to carry out a shift-reduce parse of the sentence: $ id + id ^ id * id $ . [You must carry this out as we did in the course, step-by-step, showing the stack, current symbol, rest of the input, and action (if "r" give the grammar rule used).] Grammar: Arithmetic Expressions P ---> E E ---> E + T | E - T | T T ---> T * S | T / S | S S ---> F ^ S | F F ---> ( E ) | id    Parser: Shift-Reduce Table | id| ^ | */| +-| ( | ) | $ | ---+---+---+---+---+---+---+---+ P | | | | | | |acc| E | | | | s | | s | r | T | | | s | r | | r | r | S | | r | r | r | | r | r | F | | s | r | r | | r | r | id | | r | r | r | | r | r | ^ | s | | | | s | | | */ | s | | | | s | | | +- | s | | | | s | | | ( | s | | | | s | | | ) | | r | r | r | | r | r | $ | s | | | | s | | | ---+---+---+---+---+---+---+---+ Shift-Reduce Actions Stack Curr Rest of Input Action (top at right) Sym -------------------------------------------------------------------------- $ id + id ^ id * id $ s $ id + id ^ id * id $ r: F --> id $ F + id ^ id * id $ r: S --> F $ S + id ^ id * id $ r: T --> S $ T + id ^ id * id $ r: E --> T $ E + id ^ id * id $ s $ E + id ^ id * id $ s $ E + id ^ id * id $ r: F --> id $ E + F ^ id * id $ s $ E + F ^ id * id $ s $ E + F ^ id * id $ r: F --> id $ E + F ^ F * id $ r: S --> F $ E + F ^ S * id $ r: S --> F ^ S $ E + S * id $ r: T --> S $ E + T * id $ s $ E + T * id $ s $ E + T * id $ - r: F --> id $ E + T * F $ - r: S --> F $ E + T * S $ - r: T --> T * S $ E + T $ - r: E --> E + T $ E $ - r: P --> E $ P $ - acc By far the most common mistake was not reducing the three items "F ^ S" together to "S" (shown in purple above) but instead reducing the "S" on top to "T". This mistake made it impossible to complete the parse properly. (10) With syntax-directed translation, one carries out semantic actions as the parse tree is traversed. Inheritance refers to passing information down the parse tree (from the root at the top). With a recursive-descent parser, how would you carry this out. Send information in parameters of the function called to go down the tree. Synthesis refers to moving information up the parse tree toward the root. Again with a recursive-descent parser, how would you carry this out? Use the return value of the function that went down to a node to send information back up.