Description
This programming assignment is to be done individually. It is the continuation of Assignment
Three. You are required to write a predictive parser for the Simple Language (SL) based on the
tokens obtained from Assignment Three.
The grammar for SL is as follows:
PROG PROG_BODY .
PROG_BODY var ID_LIST; STATEMENT_LIST
ID_LIST ID_LIST , id | id
STATEMENT_LIST begin STATEMENT end
STATEMENT STATEMENT id =E; | STATEMENT STATEMENT_LIST | id=E;
E E+E | E–E | E*E | E/E | (E) | num | id
In the grammar, “var”, “begin”, “end”, “id”, “num”, “.”, “,”, “;” , “ (”, “)” , “+”, “-“, “*”,
“/”, “=” are terminals, which you should treat as the corresponding tokens defined in
Assignment Three in the program.
You need to do the following:
1. Check the grammar for SL and determine whether it is suitable for predictive parsing
(recursive descent parsing without backtracking). If not, perform grammar
transformations and, if necessary, rewrite the grammar. (10%)
2. Rewrite the scanner (lexical analyzer) in Assignment Three to make it provide a function
getNextToken(), which when called will extract the next token from the input string and
return the token. The parser will call the function whenever it needs to read the next token
for syntax analysis. (10%)
3. Write a recursive descent parser program for SL (You can use C, C++, and Java to
implement it. (70%)
4. Test the syntax analyzer with some example programs written in SL. A sample program
is given at the end of this document (10%).
Your syntax analyzer should produce two outputs depending on whether it can successfully
parse the input stream. If it is successful, the parser should output a sequence of program
constructs recognized during the parsing plus the string “Program parsed successfully.” For
example, for the following program:
var a, b, c;
begin
a = 5;
end.
Your program should output:
“Program” begins
“Program Body” begins
“Declaration” begins
“Declaration” ends
“Statement” begins
“Assignment” begins
“Assignment” ends
“Statement” ends
“Program Body” ends
“Program” ends
Program parsed successfully
In case there is a syntax error, the parser will print out “Syntax Error” and then stop.
What to Submit: A zip file includes the following:
(1) A report describing 1 and 4 with the testing results;
(2) A readme file to show how to compile and run your program;
(3) The source code file (in a separate file). The tutor will test your program based on this.
Appendix B : Sample SL Program and scanner’s output
Sample program 1:
var a, b, c;
begin
a = 5;
b = 6;
c = (a + b) / 2.0;
end.
Sample program 2:
var a;
begin
a = 5
end .