CS 3721
Programming Languages  
Spring 2014
Recitation 2.   S-R Parsers
Week 2: Jan 21-23

Submit following directions at: submissions and rules at: rules. Deadlines are:
  • 2014-01-28  23:59:59 (that's Tue, 28 Jan 2014, 11:59:59 pm) for full credit.
  • 2014-01-31  23:59:59 (that's Fri,    31 Jan 2014, 11:59:59 pm) for 75% credit.

Shift-Reduce Parsers (Bottom-Up): Study the pages:

  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
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. Here it's easier to type answers where you can do cutting and pasting.)

      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 (just a beefed-up version of the "standard" grammar with three extra operators):

    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  |     |     |
−−−−−+−−−−−+−−−−−+−−−−−+−−−−−+−−−−−+−−−−−+−−−−−+

    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. (Be prepared to produce the parse trees for an exam, but don't put it in this submission.) Again you should follow the form given in Shift-Reduce Parsers.)

    Input sentence
    $ id + id * id ^ id $

  3. Consider the following arithmetic expression, which is the same as the input of Problem 2 above, but using integers instead of identifiers:
    Input sentence
    $ 7 + 5 * 4 ^ 3 $

    1. Translate this sentence by hand to RPN. (Use any method or just "fake" the translation to come up with the correct answer.) In the result the four integer operands should have the same order in the original arithmetic expression. Of course the answer has no parentheses.

    2. Show step-by-step how you can use a stack to evaluate the RPN above, to obtain the final value.

    3. Do steps a and b above for the following input. (Your RPN must retain all the operands and operators as given, without any simplifications.)

      Input sentence
      $ 6 * (4 + 3) ^ (2 + 1) + 5 $

Revision date: 2014-01-21. (Please use ISO 8601, the International Standard.)