Problem Set 4

Due: Monday, 24 March, beginning of class.

Consider the grammar given at the bottom of this page for the language SPoc (Simple Procedural languge). You are to modify the grammar so that it can be used to develop a top-down parser for SPoc. In particular, it must meet the following requirements:

1. Change the grammar so that there is no left recursion in the grammar.
2. Rewrite the grammar so that * and / have precedence over + and - and all of these operators are left associative.
3. Modify SPoc to allow a simple while loop. The loop will have the following syntax:

while [ <boolean_expr> ] { <expr> }

4. After you have completed the first three steps, write out the first set for every nonterminal. Before you do this, ensure that there are no pairwise disjointness problems.
5. General Notes.
• White space should not matter.
• Note the use of square brackets in some places and curly brackets in others. This is done to make the parsing job easier.

SPoc grammar
<SPoc>	::=	program beginD <decl> endD <SPoc_stmt_list> end
<SPoc_stmt_list>	::=	<SPoc_stmt_list> <SPoc_stmt>
<SPoc_stmt_list>	::=	<SPoc_stmt>
<SPoc_stmt>	::=	<assign> $
<SPoc_stmt>	::=	if <boolean_expr> then <SPoc_stmt> else <SPoc_stmt> $
<SPoc_stmt>	::=	if <boolean_expr> then <SPoc_stmt> $
<decl>	::=	<id_list>
<id_list>	::=	<id_list> <type> <id>
<id_list>	::=	<type> <id>
<type>	::=	int | float
<assign>	::=	<id> = <arith_expr>
<boolean_expr>	::=	<id> <bool_op> <id>
<bool_op>	::=	= | > | < | !=
<arith_expr>	::=	<arith_expr> <arith_op> <arith_expr>
<arith_expr>	::=	<id> | <number>
<arith_op>	::=	+ | - | * | /
<number>	::=	<int> | <float>
<int>	::=	<int> <digit> | <digit>
<float>	::=	<int> . <int>
<id>	::=	<id> <char> | <char>
<digit>	::=	0| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<char>	::=	a | b | c | i | j | x | y | z

Last updated on 15 Mar 2008 by John Barr