CS 3721 Programming Languages   Fall 2013
Recitation 5.   Recursive Descent Parsers
Week 5: Sept 23 - 27

Submit following directions at: submissions and rules at: rules. Deadlines are: 2013-10-04  23:59:59 (that's Fri,   04 Oct 2013, 11:59:59 pm) for full credit. 2013-10-07  23:59:59 (that's Mon, 07 Oct 2013, 11:59:59 pm) for 75% 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. Your submission only needs to show the changes made to the parser.]

   ---

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. The following link contains MIPS assembly code to calculate the sum of the series: Σ 1/(n^2): The Euler Series. This series converges slowly to π²/6 = 1.644934066848226
   1. Copy/paste the MIPS file and run it on a machine in the Linux lab, using 20 as the input value. [If you name your file "euler.s", and then enter "spim euler.s" at the command line on a Linux machine, this will execute this file. Of course you'll have to type in "20 return". The sum of 20 terms rounds to 1.6, not very accurate.]

   2. Make one tiny addition to the Mips code: where the program calculates n*n, patch in an additional multiply instruction, to multiply what is in register $f6 by itself and leave the result in $f6. This will square n*n, so it will calculate the sum: Σ 1/(n^4). Again calculate the first 20 terms of this series, which converges more rapidly. [20 terms will give 4 significant digits of the correct sum, and 50 terms will give 6 significant digits. The sum of the infinite series starts out: 1.08...]