CS314
Assignment 3
1 LL(1) Grammar and Recursive Descent Parsing
<program ::= def <funcname <arguments : \n <block EOF
<funcname ::= f | g
<arguments ::= ( <variable <morevars )
<morevars ::= , <variable <morevars | ?
<block ::= <stmtlist
<stmtlist ::= \t <stmt <morestmts
<morestmts ::= \n <stmtlist | ?
<stmt ::= <assign | <ifstmt | <returnstmt
<assign ::= <variable = <expr
<condition ::= <variable <= <expr
<ifstmt ::= if <condition : <assign \n \t else : <assign
<returnstmt ::= return <variable
<expr ::= <term + <term
<term ::= <variable | <digit
<variable :: = a | b | c
<digit :: = 0 | 1 | 2
\n represents the “new line” terminal. \t represents the “tab” terminal.
(a) Show that the grammar above is LL(1). Use a formal argument based
on the definition of the LL(1) grammar.
(b) Show the LL(1) parse table.
1
(c) Write a recursive descent parser for the above grammar in pseudo code
in the same format as that in lecture 6.
2
