CS416: Compiler Design
Compilers Design: LL parser
Spring 2007
Programming Assignment 2
Due Date: June 20, 2007
You are going to write a LL(1) parser (you should write an LL(1) parser, not another parser in this assignment) for a toy programming language whose grammar is defined below. The grammar of this toy programming language:
program ( compoundstmt
stmt ( decl | ifstmt | whilestmt | assgstmt | compoundstmt
compoundstmt ( { stmts }
stmts ( stmt stmts | (
ifstmt ( if ( boolexpr ) then stmt else stmt
whilestmt ( while ( boolexpr ) stmt
assgstmt ( ID = arithexpr ;
decl( type list;
type( int | real
list( ID list1
list1(, list | (
boolexpr ( arithexpr boolop arithexpr
boolop ( < | > | <= | >= | ==
arithexpr ( multexpr arithexprprime
arithexprprime ( + multexpr arithexprprime | – multexpr arithexprprime | (
multexpr ( simpleexpr multexprprime
multexprprime ( * simpleexpr multexprprime | / simpleexpr multexprprime | (
simpleexpr ( ID | NUM | ( arithexpr )
In this grammar, program is the start symbol. You may assume that each token is separated with at least one white space character (for simple reading). ID and NUM are also tokens (you do not have use actual identifier or numbers, just use these names). You should make sure that this grammar is suitable for the LL(1) parsing (I think it is. If it is not, you should solve the problem).
Before you create the parser, you should create the LL(1) parsing table of the grammar above. Your parser should read a program, and it should create and print the parse table of that program if it is a correct program. If the program is incorrect (contains syntax errors), it should print syntax error messages (together with line numbers). Your program should be able to recover after a syntax error, and continue to parsing.
Test your LL(1) parser with correct and incorrect programs. The output of a test with a correct program should be the parse table of that program; and the output of a test with an incorrect program should be a sequence of error messages (together with line numbers). For example, the output of your parser for the following correct program
{ ID = NUM ; }
can be the following parse tree:
program
compoundstmt
{
stmts
stmt
assgstmt
ID
=
arithexpr
multexpr
simpleexpr
NUM
multexprprime
(
arithexprprime
(
;
stmts
(
}
You should hand-in:
· Your source program
· The LL(1) parsing table of the grammar
· Some test runs of your program with correct and incorrect programs
· Above all email to xmju@sei.ecnu.edu.cn.
DO IT YOURSELF – CHEATING WILL BE PUNISHED