CS 3723 Programming Languages   Fall 2014
Homework 6. S-R Parsers
Week 6: Sep 29 - Oct 3

Submit following directions at: submissions and rules at: rules. Deadlines are: 2014-10-13  23:59:59 (that's Mon, 13 Oct 2014, 11:59:59 pm) for full credit. 2014-10-15  23:59:59 (that's Wed,  15 Oct 2014, 11:59:59 pm) for 75% credit. Note earlier part-credit deadline!

---

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):

 P  --->  E
 E  --->  E + T  |   E - T  |  T  
 T  --->  T * S  |   T / S  |  S
 S  --->  F ^ S  |   F
 F  --->  ( E )  |  id

     |  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 + id $

3. Consider arithmetic expressions in RPN form with the following conditions:
   • each operand is a single digit representing a double.

   • the operators are: +, −, *, /, and ^, each taking two operands.

   Write a Python program to evaluate such an RPN string as a double. So take the single-digit operands as doubles, and carry out the operations as doubles. Here is an evaluation algorithm from RPN:

   In general, the evaluation of RPN input can proceed as follows: Use an evaluation stack of doubles. Proceed through the RPN from left to right. Operands are pushed onto the stack, and operators pop their arguments off the stack and push the result. At the end of the input, the remainder of the stack is popped and printed. (It should be be a single value.)

   Here are 9 RPN strings for you to evaluate, along with the correct value in all but 3 cases. (The first column below, the original arithmetic expression, is just for reference.) For the operators −, /, and ^, the order of the operands makes a difference, so the operator must be applied to the next-to-the-top operand followed by the top operand, in that order.

   Arithmetic Expression	RPN	Value
   2+3	23+	5.0
   2+3*4	234*+	14.0
   3*4+5	34*5+	17.0
   (2+3)*4	23+4*	20.0
   (3*(2+4)/(5+1))-2	324+*51+/2-	1.0
   (5+3)^(2+1)^2	53+21+2^^
   2+3*4^5*6+7	2345^*6*+7+	18441.0
   ((3^2-4*1*2)^(1/2)-3)/(2*1)	32^41*2*-12/^3-21*/
   ((2-3)^((4+1)*5)/6-(2-4)*7)-8	23-41+5*^6/24-7*-8-

Python has a built-in function eval(expr) that will find the value of a Python expression expr, and a function exec(code) that will execute the Python code code. (Even if Python has some function to evaluate RPN, you are not to use it here.)

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