Recursive Descent

One day a student came to the LispMaster and said: "Please explain recursion to me, oh Master." The master looked at him and and patiently told the student the following story:

"One day a student came to the LispMaster and said: 'Please explain recursion to me'....."

A top-down parsing technique in which each non-terminal is represented by a subroutine written to match symbols that make it up. For the grammar rule

   <term> ::= <factor> ('+' | '-') <factor>

one could write (in a very simplified fashion):

   Parse_Term() : Boolean begin
      var op:token;
      if Parse_Factor() then
         case Next_Symbol() of
            '+': op := ADDITION;
            '-': op := SUBTRACTION;
            default: ERROR;
         esac
         if Parse_Factor() then
            SUCCESS;
   end

In effect, TheSourceCodeIsTheGrammar?

Or the other way around use CodeGeneration to derive the source code from the Grammar. A hand made RecursiveDescent (meta) parser could take the rule above as input and create the code as output. The benefit is once the metaparser is made it can generate RecursiveDescent parsers for as many languages as you can define rules for.

RecursiveDescent compilers work best in languages which require, at most, one symbol lookahead to resolve which construct is happening.

Tools exist to automatically generate RecursiveDescent parsers, as well as ShiftReduce? parsers. Yacc and its derivatives (such as Bison) are the most well-known (basic Yacc generates ShiftReduce? parsers only; bison can generate both).

[ Lex generates scanners, YACC generates parsers. While lex can be told to accept grammars that are mildly non-regular (via various hacks), Lex cannot be used to generate parsers for context-free grammars of any complexity. Yacc (and its cousins such as Bison) doesn't generate top-down (recursive-descent) parsers, it generates bottom-up (shift/reduce) parsers--a different category of parser altogether, and one which (unlike recursive descent) is difficult to generate by hand. Newer versions of Bison can generate recursive descent parsers. ]

See http://www.cs.uu.nl/~jeroen/article/parsers/parsers.ps for an introduction to writing recursive descent parsers in a functional language. Heady stuff.