CS 3721 Programming Languages   Spring 2013
Recitation 4.   S-R Parsers
Week 4: Feb 04-Feb 08

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

---

1. The first page on grammars gives a formal grammar describing a float constant. Give the exact ways in which this differs from our definition of a double. (Something in addition to not having a lower-case 'e'.)

   ---

2. 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.

      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.

   ---

3. 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. Besides you did these in Recitation 2.)

      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 order. You don't have to write out the semantic actions.)

   ---

4. Suppose you have a language like C or Java with an if statement with an optional else. Below is a fragment of a grammar, where L stands for a logical expression (with further rules describing it) and S stands for a statement (with further rules describing other statements). Below the grammar on the left is a sentence in this grammar, and on the right are two distinct parse trees. (Technically, this string contains non-terminals, so it is called a sentential form.)

   Grammar: if with optional else	Two distinct ways to complete the upper part of the parse trees
   S ---> if ( L ) S S ---> if ( L ) S else S S ---> ... (more rules for statements) L ---> ... (more rules defining L)	S | +--+-+-+--------+----------+---+ | | | | | | | | | | | S | | | | | | | | | | | | | +--+-+-+---+ | | | | | | | | | | | | | if ( L ) if ( L ) S else S /|\ /|\ /|\ /|\ . . . . . . . . . . . . S | +--+-+-+--------+ | | | | | | | | | S | | | | | | | | | +--+-+-+---+----+---+ | | | | | | | | | | | if ( L ) if ( L ) S else S /|\ /|\ /|\ /|\ . . . . . . . . . . . .
   Middle portion of parse tree for a sentential form in the language
   if ( L ) if ( L ) S else S /|\ /|\ /|\ /|\ . . . . . . . . . . . .

   1. What does is mean that there are two different parse trees for a complex if-else statement? (What kind of a problem does this cause?)

   2. This is how C and Java are actually described, except the description adds an extra rule. What is the rule? Which parse tree above is correct and which one is wrong? (You find the answer in any text describing if-else.)

   3. Suppose this was being handled by an S-R parser. In this case, if an S-R table were generated, when S is the top of the stack and else is the current symbol, the algorithm building the table would try to put in for the entry under S and else, both an r and an s. That is, we have a schizophrenic, split personality table that is demanding both a "shift" and a "reduce". Which of these two should be chosen and which ignored?