Fall 98, CSE 468: Assignment 4

Distributed: Published on the web on Oct 26.
Due: Nov 6 (in class).
Total maximum score: 100 points.
The purpose of this assignment is to to provide experience with parsing of context-free languages.

Please write your solutions as clearly and concisely as possible.


Consider the following grammar G defining the language of regular expression without * on the alphabet {a,b,c} 
   E -> Lambda | Emptyset | a | b | c | E+E | EE | (E)
Note that Lambda and Emptyset here are just symbols in the alphabet of G, used to represent particular regular expressions.

Consider the language L' obtained by putting a symbol "." (end-of-string) at the end of each string in L(G). Write a program which recognizes the language L'. You can use your favourite programming language among the following: C, C++, Java, Pascal and ML.

Hint: You can use either the top-down method or the bottom-up method:
Top-down method. Define an equivalent LL(1) grammar G', and then apply the Look-Ahead method described in 7.6.1 of Martin's book. You can either use a stack (thus simulating a pushdown automata) or recursion (recursive-descent parsing).
Bottom-up method. Define an equivalent unambiguous grammar G'', and then apply the method described in 7.6.2 of Martin's book.

In both cases, you are free to choose the conventions you prefer about the precedence and associativity of the operators (but state explicitly which ones are you using).

The solution will consist of the program, and the answers of the program on the following strings (the dot at the end is part of the string):

  1. a+b+c.
  2. (a(b+c)(a+c)+b)a.
  3. (((a))).
  4. (ab+bc)++c.
  5. (ab=bc)+c.
  6. +ab.
  7. (((+))).
  8. ((a))).

Please write down which of the above methods (top-down parsing with a stack, recursive-descent parsing, or bottom-up parsing) your program is based upon. If you use a stack, then please write down also the transition table, so to help me understanding your program.

Please keep the file with the program: I might need to test it.