CS 3721
Programming Languages  
Fall 2014
Homework 7. R-D Parsers
Week 9: Oct 20 - 24

Submit following directions at: submissions and rules at: rules. Deadlines are:
  • 2014-10-29  23:59:59 (that's Wed,   29 Oct 2014, 11:59:59 pm) for full credit.
  • 2014-11-03  23:59:59 (that's Mon, 03 Oct 2014, 11:59:59 pm) for 75% credit.

Note: In the grammar below, I've dropped the prefix unary plus and minus operators.

Recursive Descent Parsing: Study the page:

  1. Write Parser for More Complex Language: You are to extend the parser for the simple grammar at the link above to work for the more complex grammar at that link. The grammar is reprinted below:

    More Complex Language: REs
    P ---> E '$'
E ---> T { ( '+' | '-' ) T }
T ---> S { ( '*' | '/' ) S }
S ---> F '^' S | F
F ---> '(' E ')' | digit | letter

    Just a little extra code is needed to do this. In addition to the regular data, you should also use new test data from ae.txt, which has 11 new correct items. You don't need to worry about erroneous items.

  2. Translate to RPN: Consider the parser given Problem 1. 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+$.

    While this step may be conceptually confusing, the additions to the parser should be simple, almost minimal: As you program goes through the parse, it spits out the RPN code. In fact, these additions are essentially the same as those made to the shift-reduce parser in order to output RPN: see the page Semantic.

    In your code for this you can store the RPN in a string as it is created, or simply output them as you go along.

    You must run the 11 test cases in the same test file ae.txt used in Problem 1 above, 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.

  3. Parser for the "Odd" Language: Consider the grammar that you saw in Homework 6:

    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 in the program code to identity errors, and the test data includes cases that caused each of these errors for my program (several of them more than once, so there are more that 6 errors in the data).]

      Note: Problem 3 above has 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. Some additional output would help, but the output of the "debug" parser above is probably excessive, and may create more problems that solving them. About half the data inputs are erroneous.

  4. Evaluate the RPN (Extra Credit!) For modest extra credit, you can tack on the RPN evaluator from Homework 6, so that you have a program that starts with an AE, translates it to RPN, and then evaluates the RPN. In other words, this combination evaluates an input AE.

    Use the leftmost column from the table in Homework 6: which is in the file dae.txt.

    If you do this part and include your source program, then you can leave off the source programs in both Problems 1 and 2 above.

What to turn in: If you finish Problem 2 above and turn in the source code and runs producing RPN, then you don't need to give the source for Problem 1. In fact, the correct RPN translations do a good job of verifying that the parser is correct.

Without Problem 2, you should turn in the source for Problem 1.

Problem 3 is very important. Be sure to include the source code and results of runs with the data given. About half of these data items are in error.

Don't do Problem 4 until you've finished Problem 3. You should try to make your evaluation program a separate module. [As I mentioned above, if you do this part and include all the source programs, then you don't need the source programs for Problems 1 and 2 above. You only need to submit one copy of the parser.]

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