CS 3721 Programming Languages   Spring 2014
Recitation 4.   Recursive Descent Parsers
Week 4: Feb 4 - 6

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

---

1. Translate to RPN: 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: Test Data. [This should be very easy. Your submission must carefully show the changes you made to the parser, although you don't have to show the whole program. You must also run the 8 test cases, showing the source data and output data for each case. There are no errors in this input data. And, hey, now you have a translator from arithmetic expressions to RPN.]

   ---

   Notes: Problems 2 and 3 below have nothing to do with shift-reduce parsing. The code should be fairly short and simple, but it may be conceptually difficult for some students. One common problem has to do with the use of scan(), too many, too few, in the wrong place. Thus the scanning can produce annoying and tricky bugs. Remember: the simplest scanning strategy (while not the best) is to scan for the next token immediately after making a decision based on the current token.

   To help with debugging, you should have more output than just "accept" or "reject". Often you don't have to do error-checking in this course, but in this case your program should detect all possible errors, and handle the error, perhaps as in the examples above. Some additional output would help, but the output of the "debug" parser above is probably excessive, and may create more problems that solving them. In each problem, about half the data inputs were erroneous.

   As always, you must include the parser code, along with output of runs with each of the given inputs.

   ---

2. Parser for Python Dictionaries: Here we want to recognize a simplified (almost trivial) class of Python Dictionary types. For us here, a dictionary is has the following intuitive syntax: "it consists of a sequence of one or more items, each separated from the next by a comma, enclosed in curly brackets. Each item is a digit followed by a colon followed by a letter." All whitespace is ignored. Examples are { 3:a } and { 2:b , 4:d , 3:e }. To get a precise definition of the syntax, use the following grammar:

   Grammar: Simplified Dictionary
   D --> '{' L '}' L --> I { ',' I } I --> digit ':' letter

   Above "digit" stands for any single digit, and "letter" stands for any single letter (all our examples will be lower-case). The non-terminal D is for "Dictionary", L is for "List of Items", and I is for "Item".

   The objective of this problem is for you to practice writing a R-D parser. The program would probably be easier for you to write if you did it from scratch without thinking about parsers at all. Thus you must have functions named D, L, and I, whose code mirrors the grammar rule. You are expected to imitate the "bare" parser at the first link above, and if you do, this problem is greatly simplified.

   Use the following input data to test your parser: Test Data. You can handle the input all at once or as separate runs, whichever you want.

   ---

3. Parser for the "Odd" Language: Consider the grammar that you saw in Recitation 2:

   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: 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.]