RECURSIVE DESCENT PARSER
Design a recursive descent parser for the following grammar.
Axiom ::= Expr Axiom
eof
| λ
Expr ::= Expr + Term
| Expr – Term
| Term
Term ::= Term * Factor
| Term / Factor
| Factor
Factor ::= (Expr)
|
num
1
F irst, we need to remove left recursion and left factor the grammar to obtain:
A ::= E A eof
| λ
E
::= T E’
E’
::= + T E’
| - T E’
| λ
T
::= F T’
T’
::= * F T’
| / F T’
| λ
F
::= (E)
|
num
ow that we have a good grammar to start working with, let’s calculate FIRST and FOLLOW
N
sets:
Nullable FIRST FOLLOW
A Yes
λ
, num, (
$, eof
E No num, ( num, eof, ( , )
E’ Yes
λ
, +, -
num, eof, (, )
T No num, ( num, eof, (, ), +, -
T’ Yes
λ
, *, /
num, eof, (, ), +, -
F No num, ( num, eof, (, ), *, /, +, -
on-terminalsA,E’andT’arenullable,buttheydonotoverlapintheirFIRSTand FOLLOW
N
sets,soourgrammarisLL(1).Wecanbuildarecursivedescentparsertorecognizeit.Wewill
makeuseofthefunction match_tokenasdefinedbelow.Itisimportanttonoticethat this
function, as it is implemented, asks the lexical analyzer to provide the next token
(lookahead), so we need to take that into account when using it.
void match_token (int expected) {
if (lookahead != expected) {
// lookahead is a globalvariable
printf (“syntax error”) ;
exit (0) ;
} else {
lookahead = rd_lex () ;
// read the next token
}
}
2
The implementation (in pseudo code) of the recursive descent parser would be as follows:
void Parse_A () {
//nullable A ::= E A eof | lambda
if (lookahead∈
FOLLOW (A)) {
return ;
// λ
} else if (lookahead∈
FIRST (E)) { // E is not nullable
!
Parse_E () ;
Parse_A () ;
match_token (EOF) ;
} else {
printf (“syntax error”);
exit (0) ;
}
}
void Parse_E () {
// E ::= T E’
if (lookahead∈
FIRST (T)) { // T is not nullable
!
Parse_T ();
Parse_E’ ();
} else {
printf (“syntax error”);
exit (0) ;
}
}
void Parse_E’ () {
//nullable
E’ ::= + T E’ | -
T E’ | lambda
if (lookahead∈
FOLLOW (E’)) {
return ;
// λ
} else if (lookahead == PLUS) {
match_token (PLUS) ;
Parse_T () ;
Parse_E’ () ;
} else if (lookahead == MINUS) {
match_token (MINUS) ;
Parse_T () ;
Parse_E’ () ;
} else {
printf (“syntax error”) ;
exit (0) ;
}
}
3
void Parse_T () {
// T ::= F T’
if (token∈
FIRST (F)) { // F is not nullable !
Parse_F () ;
Parse_T’ () ;
} else {
printf (“syntax error”) ;
exit (0) ;
}
}
void Parse_T’ () {
//nullable T’ ::= * F T’
| /
F T’ | lambda
if (lookahead∈
FOLLOW (T’)) {
return ;
// λ
} else if (lookahead == MULT) {
match_token (MULT) ;
Parse_F () ;
Parse_T’ () ;
} else if (lookahead == DIV) {
match_token (DIV) ;
Parse_F () ;
Parse_T’ () ;
} else {
printf (“syntax error”) ;
exit (0) ;
}
}
void Parse_F () {
// F ::= ( E ) | num
if (lookahead == L_PAREN) {
match_token (L_PAREN) ;
Parse_E () ;
match_token (R_PAREN) ;
} else if (lookahead == NUM) {
match_token (NUM) ;
} else {
printf (“syntax error”) ;
exit (0) ;
}
}
4
