CS 3721 Programming Languages   Fall 2013
Recitation 4.   S-R Parsers
Week 4: Sep 16-Feb 20

Submit following directions at: submissions and rules at: rules. Deadlines are: 2013-09-27  23:59:59 (that's Fri, 27 Sep 2013, 11:59:59 pm) for full credit. 2013-09-30  23:59:59 (that's Mon, 30 Sep 2013, 11:59:59 pm) for 75% credit.

1. Consider the sentence a * b + c. Using the unambiguous grammar of the middle link above, construct the top-down leftmost derivation, and the bottom-up (backwards) rightmost derivation for this sentence. (These are shown for a + b * c in the two boxes at the right in the two examples at the end of the middle link above.)

2. Do the same for the sentence a * ( b + c ). (Again, produce two derivations, one leftmost, and one rightmost backwards.)

---

1. Consider the following grammar, with corresponding shift-reduce table. (This language is almost designed to be confusing, so that the easiest way to parse is to follow the rules in the table.)

   Grammar: Odd language S ---> b M b (S = start symbol) M ---> ( L M ---> a L ---> M a )

   Parser: Shift-Reduce Table | b | a | ( | ) | $ | -----+-----+-----+-----+-----+-----+ S | | | | | acc | (s means "shift") M | s | s | | | | L | r | r | | | | (r means "reduce") b | | s | s | | r | a | r | r | | s | | (acc means "accept") ( | s | s | s | | | ) | r | r | | | | $ | s | | | | | -----+-----+-----+-----+-----+-----+

   1. Carry out the shift-reduce parse of the following sentence, showing the stack, current symbol, remaining symbols, and next action to take at each stage. (You should follow the form given in Shift-Reduce Parsers.)

      Input sentence
      $ b ( ( a a ) a ) b $

   2. Draw the parse tree for the sentence (just a crude and quick drawing, since such trees are annoying to draw text-only. You will need to draw parse trees on exams.)

   3. Give a sentence in the grammar of this language that is longer than the one above.

   ---

2. Consider the following grammar:

   Grammar: Arithmetic Expressions P ---> E (P = start symbol) 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 | | | -----+-----+-----+-----+-----+-----+-----+-----+

   1. As in problem 2, carry out the shift-reduce parse of the following sentences, showing the stack, current symbol, remaining symbols, and next action to take at each stage. (Be prepared to produce the two parse trees for an exam, but don't put them in this submission. Again you should follow the form given in Shift-Reduce Parsers.)

      Input sentence
      $ id ^ id ^ id $ $ id + id * id ^ id $ | | | | a b c d

   2. Study the last example on the page Semantic Actions. Using the same semantic actions given there (along with obvious ones involving the operator '^'), give step-by-step the translation of the second sentence above ($ id + id * id ^ id $) to intermediate code. (Assume the four ids are tagged with a, b, c, and d, in that order. You don't have to write out the semantic actions.)