• LL(1) Grammar and Recursive Descent Pars-ing
<program> ::= def <funcname> <arguments> : nn <block> EOF <funcname> ::= f j g
<arguments> ::= ( <variable> <morevars> ) <morevars> ::= , <variable> <morevars> j <block> ::= <stmtlist>
<stmtlist> ::= nt <stmt> <morestmts>
<morestmts> ::= nn <stmtlist> j
<stmt> ::= <assign> j <ifstmt> j <returnstmt>
<assign> ::= <variable> = <expr>
<condition> ::= <variable> <= <expr>
<ifstmt> ::= if <condition> : <assign> nn nt else : <assign> <returnstmt> ::= return <variable> <expr> ::= <term> + <term>
<term> ::= <variable> j <digit>
<variable> :: = a j b j c
<digit> :: = 0 j 1 j 2
nn represents the \new line" terminal. nt represents the \tab" terminal.
(a) Show that the grammar above is LL(1). Use a formal argument based on the de nition 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
