Recursive descent parser

Incomputer science,arecursive descent parseris a kind oftop-down parserbuilt from a set ofmutually recursiveprocedures (or a non-recursive equivalent) where each suchprocedureimplements one of thenonterminalsof thegrammar.Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.

Apredictive parseris a recursive descent parser that does not requirebacktracking.Predictive parsing is possible only for the class ofLL(k)grammars, which are thecontext-free grammarsfor which there exists some positive integerkthat allows a recursive descent parser to decide which production to use by examining only the nextktokens of input. The LL(k) grammars therefore exclude allambiguous grammars,as well as all grammars that containleft recursion.Any context-free grammar can be transformed into an equivalent grammar that has no left recursion, but removal of left recursion does not always yield an LL(k) grammar. A predictive parser runs inlinear time.

Recursive descent with backtracking is a technique that determines whichproductionto use by trying each production in turn. Recursive descent with backtracking is not limited to LL(k) grammars, but is not guaranteed to terminate unless the grammar is LL(k). Even when they terminate, parsers that use recursive descent with backtracking may requireexponential time.

Although predictive parsers are widely used, and are frequently chosen if writing a parser by hand, programmers often prefer to use a table-based parser produced by aparser generator,either for an LL(k) language or using an alternative parser, such asLALRorLR.This is particularly the case if a grammar is not inLL(k)form, as transforming the grammar to LL to make it suitable for predictive parsing is involved. Predictive parsers can also be automatically generated, using tools likeANTLR.

Predictive parsers can be depicted using transition diagrams for each non-terminal symbol where the edges between the initial and the final states are labelled by the symbols (terminals and non-terminals) of the right side of the production rule.

Example parser

The followingEBNF-likegrammar(forNiklaus Wirth'sPL/0programming language, fromAlgorithms + Data Structures = Programs) is inLL(1)form:

program=block".".

block=
["const"ident"="number{","ident"="number}";"]
["var"ident{","ident}";"]
{"procedure"ident";"block";"}statement.

statement=
ident":="expression
|"call"ident
|"begin"statement{";"statement}"end"
|"if"condition"then"statement
|"while"condition"do"statement.

condition=
"odd"expression
|expression("="|"#"|"<"|"<="|">"|">=")expression.

expression=["+"|"-"]term{("+"|"-")term}.

term=factor{("*"|"/")factor}.

factor=
ident
|number
|"("expression")".

Terminalsare expressed in quotes. Eachnonterminalis defined by a rule in the grammar, except foridentandnumber,which are assumed to be implicitly defined.

C implementation

What follows is an implementation of a recursive descent parser for the above language inC.The parser reads in source code, and exits with an error message if the code fails to parse, exiting silently if the code parses correctly.

Notice how closely the predictive parser below mirrors the grammar above. There is a procedure for each nonterminal in the grammar. Parsing descends in a top-down manner until the final nonterminal has been processed. The program fragment depends on a global variable,sym,which contains the current symbol from the input, and the functionnextsym,which updatessymwhen called.

The implementations of the functionsnextsymanderrorare omitted for simplicity.

typedefenum{ident,number,lparen,rparen,times,slash,plus,
minus,eql,neq,lss,leq,gtr,geq,callsym,beginsym,semicolon,
endsym,ifsym,whilesym,becomes,thensym,dosym,constsym,comma,
varsym,procsym,period,oddsym}Symbol;

Symbolsym;
voidnextsym(void);
voiderror(constcharmsg[]);

intaccept(Symbols){
if(sym==s){
nextsym();
return1;
}
return0;
}

intexpect(Symbols){
if(accept(s))
return1;
error("expect: unexpected symbol");
return0;
}

voidfactor(void){
if(accept(ident)){
;
}elseif(accept(number)){
;
}elseif(accept(lparen)){
expression();
expect(rparen);
}else{
error("factor: syntax error");
nextsym();
}
}

voidterm(void){
factor();
while(sym==times||sym==slash){
nextsym();
factor();
}
}

voidexpression(void){
if(sym==plus||sym==minus)
nextsym();
term();
while(sym==plus||sym==minus){
nextsym();
term();
}
}

voidcondition(void){
if(accept(oddsym)){
expression();
}else{
expression();
if(sym==eql||sym==neq||sym==lss||sym==leq||sym==gtr||sym==geq){
nextsym();
expression();
}else{
error("condition: invalid operator");
nextsym();
}
}
}

voidstatement(void){
if(accept(ident)){
expect(becomes);
expression();
}elseif(accept(callsym)){
expect(ident);
}elseif(accept(beginsym)){
do{
statement();
}while(accept(semicolon));
expect(endsym);
}elseif(accept(ifsym)){
condition();
expect(thensym);
statement();
}elseif(accept(whilesym)){
condition();
expect(dosym);
statement();
}else{
error("statement: syntax error");
nextsym();
}
}

voidblock(void){
if(accept(constsym)){
do{
expect(ident);
expect(eql);
expect(number);
}while(accept(comma));
expect(semicolon);
}
if(accept(varsym)){
do{
expect(ident);
}while(accept(comma));
expect(semicolon);
}
while(accept(procsym)){
expect(ident);
expect(semicolon);
block();
expect(semicolon);
}
statement();
}

voidprogram(void){
nextsym();
block();
expect(period);
}

Examples

Some recursive descent parser generators:

• TMG– an early compiler-compiler used in the 1960s and early 1970s
• JavaCC
• Coco/R
• ANTLR
• Spirit Parser Framework– a C++ recursive descent parser generator framework requiring no pre-compile step
• parboiled (Java)– a recursive descentPEGparsing library forJava

See also

• Parser combinator– a higher-order function used in combinatory parsing, a method of factoring recursive descent parser designs
• Parsing expression grammar– another form representing recursive descent grammar
• Recursive ascent parser
• Tail recursive parser– a variant of the recursive descent parser

References

General references

• Compilers: Principles, Techniques, and Tools,first edition, Alfred V Aho, Ravi Sethi, and Jeffrey D Ullman, in particular Section 4.4.
• Modern Compiler Implementation in Java, Second Edition,Andrew Appel, 2002,ISBN0-521-82060-X.
• Recursive Programming Techniques,W.H. Burge, 1975,ISBN0-201-14450-6
• Crafting a Compiler with C,Charles N Fischer and Richard J LeBlanc, Jr, 1991,ISBN0-8053-2166-7.
• Compiling with C# and Java,Pat Terry, 2005,ISBN0-321-26360-X,624
• Algorithms + Data Structures = Programs,Niklaus Wirth, 1975,ISBN0-13-022418-9
• Compiler Construction,Niklaus Wirth, 1996,ISBN0-201-40353-6

External links

• Jack W. Crenshaw:Let's Build A Compiler(1988-1995),inPascal,withassembly languageoutput, using a "keep it simple" approach