CS 3721 Programming Languages   Spring 2013
Recitation 5.   Recursive Descent Parsers
Week 5: Feb 11-Feb 15

Submit following directions at: submissions and rules at: rules. Deadlines are: Only one due date, for FULL credit. 2013-02-22  23:59:59 (that's Fri, 22 Feb 2013, 11:59:59 pm) for 100% (FULL) credit.

---

1. Consider the "Bare" Parser given as part of the Recursive Descent Parser page. Add extra code to this parser so that it translates an ordinary arithmetic expression into RPN form. Thus a+b*c$ should be translated to abc*+$ and a*b+c$ to ab*c+$. Test this translator with the inputs: Rec5.1 Test Data. [This should be easy. You only need to include the code you changed in your submission.]

   ---

2. Consider the grammar that you saw in Recitation 4:

   Grammar: Odd language
   P ---> S $ (P = start) S ---> b M b M ---> ( L | a L ---> M a )

   Write a recursive descent parser for the language defined by this grammar. Test your parser with the inputs: Rec5.2 Test Data. The test cases include a number of strings to accept and a number to reject. [My own parser identified 6 separate places for errors, and the test data includes cases that caused each of these errors for my program.]

   [Note that this problem has nothing to do with shift-reduce parsing. This should be fairly short and simple code. One common problem has to do with the use of scan(), too many, too few, in the wrong place.]

   ---

3. This problem starts work on the language we will implement: Tiny®. First we doing a simplified version. The hardest parts of the grammar below are already covered as arithmetic expressions, so you will mostly be adding to the "Bare" Parser.

   Simplified Tiny® Grammar
   M ---> { S } '$' S ---> A | P | C | G A ---> lower-case '=' E ';' P ---> '<' E ';' C ---> '<' upper-case ';' G ---> '>' lower-case ';' E ---> T {('+' | '-') T} T ---> U {('*' | '/' | '%') U} U ---> F '^' U | F F ---> '(' E ')' | lower-case | digit

   Important Note: The program on the right below is a Tiny® program that might read values for variables a, b, and c. Then the program calculates the two roots r and s of the equation a*x^2 + b*x + c = 0. Finally it outputs these two roots. This program assumes an implementation of Tiny® that works with doubles. Initially we will be working with ints, and may or may not do modifications to have all variables be doubles. Also, we probably won't implement the '^' operator for doubles.

   Fibonacci #s f = 5 + 8; g = f + 8; h = f + g; < h; < N; $;

   Roots of quadratic equation > a; > b; > c; d = ( b^2 - 4*a*c ) ^ ( 1/2 ); r = ( 0 - b + d ) / ( 2*d ); s = ( 0 - b - d ) / ( 2*d ); < r; < s; $

   For this assignment, you are to use the two programs above as inputs to your parser. In order to convince yourself (and me) that your parser is working correctly, you must have some debug output statements, especially in procedure A, for example stating that you are entering it, and stating that you are leaving it. (You don't need as much output as is produced by the Debug Runs.) At every point where there are choices, you must include a call to an error routine if all the choices fail. It is permissible to collapse some of the functions in the parser, say, if you put the body of the function S into the function M (or even into main in C). Other reasonable variations are also OK.