Recursive descent parsing with BNF grammars

(This is a modified repost of a post I recently put up on our company's wiki, explaining a very old CS concept/approach which seems to be rather neglected lately in production use.)

Introduction

If you're implementing any sort of miniature language as part of some software (query language, scripting capability) or even just attempting to parse structured input of some kind, using the full-boogie compiler-builder tools like YACC, bison, and friends can seem like overkill. If you just try to write a completely ad-hoc parser off-the-cuff, however, you'll find it laborious, painful, and likely find the result to be full of bugs and nasty corner cases. However, there's a happy medium, which is recursive descent parsing. I'm going to give you a quick hand-wavy explanation of how to use it.

Overview of Recursive Descent Parsing

Recursive Descent Parsing (RDP) is a powerful technique for implementing
languages or parsing inputs conforming to some syntax, as long as the syntax can be expressed in BNF (Backus-Naur form) or EBNF (Extended Backus-Naur Form). Recursive descent parsers are sometimes described as LL(k) grammars, where k defines the number of tokens of look-ahead needed, usually 1.

Until the advent of "compiler-compiler" tools like YACC, essentially all compilers were written by hand using recursive descent parsers, and it's still not a terribly onerous task because the translation from the grammar to a recursive parser is extremely straightforward, almost mechanical. Given a grammar in BNF or EBNF, you can translate it to a slightly simpler BNF form which obeys certain constraints. Once you have the BNF there will be a single routine corresponding to each left-hand-side (LHS) item or "production" in the grammar, which will end up calling the routines corresponding to each entry on its right-hand-side (RHS).

Example of BNF conversion to RDP

Let's assume we're trying to parse a simple "calculator" input, with integer expressions combined with +,-,*,/ and possibly grouped with parentheses. This is simple enough to explain in a brief example.

EBNF grammar for simple integer expressions:

Expr := Term | Term '+' Term | Term '-' Term
Term := Factor | Factor '*' Factor | Factor '/' Factor

Factor := RealNum | '-' RealNum | '(' Expr ')'

RealNum := Digit +

Note: In reality, for practicality's sake we'd probably match RealNum as a token with a pattern-matching rule rather than in EBNF.

BNF left-factorized simplification of EBNF grammar:

To convert the grammar to a parser, begin by converting it to the simpler BNF form, which eliminates any use of optional elements ([ ] or ?), any use of repetition operators (*) and any use of parenthesis operators for grouping. This can always be done at the expense of a slightly longer simple BNF form.
We also must transform the grammar (which again may introduce some new non-terminal symbols) so that there is never a self-recursive or recursive derivation of a given symbol on the left side of a rule, and left-factor it, i.e. modify it so that whenever a given symbol appears as the first element in two or more possible derivations of a given symbol, it gets "factored out" for common processing, by splitting it into two sub-rules. This gives us:

Expr := Term ExprTail
ExprTail := nil | '+' Term | '-' Term

Term := Factor TermTail 

TermTail := nil | '*' Factor | '/' Factor

Factor := RealNum | '-' RealNum | '(' Expr ')' 

RealNum := Digit RestOfNum

RestOfNum := nil | Digit RestOfNum

Simplified parser code corresponding to BNF grammar:

Translating this quite mechanically into very simplified code, assuming we have a TokenSource type with "peekToken" and "nextToken" methods, gives us code something like the following:

void ParseExpr( TokenSource t ) {
    ParseTerm( t );

    ParseExprTail( t );

}

void ParseExprTail( TokenSource t ) {

    string s = t.peekToken();

    if ( s == '+' ) {

        s = t.nextToken();

        ParseTerm( t );

    }

    else if ( s == '-' ) {

        s = t.nextToken();

        ParseTerm( t );

    }

    else {

       // nil

    }

}

void ParseTerm( TokenSource t ) {

    ParseFactor( t );

    ParseTermTail( t );

}

void ParseTermTail( TokenSource t ) {

    string s = t.peekToken();

    if ( s == '*' ) {

        s = t.nextToken(); 

        ParseFactor( t );

    }

    else if ( s == '/' ) {

        s = t.nextToken();

        ParseFactor( t );

    }

    else {

       // nil

    }

etc. As you can see, it's a very mechanical process. It almost takes less time to write the code than it does to format this blog post. I've slightly glossed over the need for the parser to do something and return its results; in a real parser, the routines would be returning a pointer to the expression tree it had built thus far, or perhaps evaluating it on the fly and returning a real.

Web links:

General information on BNF and EBNF

BNF and EBNF: What are they and how do they work?

Wikipedia on Backus-Naur form

Recursive Descent Parsers for .Net programmers

I found an interesting blog entry from a teacher at the IT University of Copenhagen, Denmark with a note about how to write scanners and parsers in C#. If you're interested in learning more, it has a good introductory explanation of the relationship between grammars (productions) and parsing, as well as more detailed examples of parsing code in C#. You should find it easy to apply this approach in any language.