Looking for a tutorial on Recursive Descent Parsing.

Question

I am trying to parse some data to no success. Can anyone recommend a good introduction with a lot of examples to Recursive Descent Parsing? I haven't been able to find any.

Answer 1

I think this is a pretty good tutorial. He uses the Python programming language.

http://effbot.org/zone/simple-top-down-parsing.htm

Answer 2

Instead of rolling your own you could also use a parser generator:

• C: lex & yacc (the classic)

• C++: Take a look at spirit in the boost-library. If unsuitable use lex & yacc.

• Antlr has support for a variety of target languages

Answer 3

Here are three tutorials that I found useful when I was teaching myself the same:

1. Recursive Descent Parsing
2. Parsing Expressions by Recursive Descent
3. Creating a Recursive Descent Parser

And the Google Query that found them. =)

Answer 4

The most hands on text for recursive descent parsing (and compiling) is Jack Crenshaw's online book/tutorial "Let's write a compiler". It has 16 chapters. You can find it here:

• http://compilers.iecc.com/crenshaw

The example code is written in Turbo-Pascal. You can use the free FreePascal compiler to compile and run them. You can find it at:

• http://www.freepascal.org

Once you have worked through Jack Crenshaw's text, if you are still hungry for more, I'd recommend the following book for it is very easy to read and hands-on as well:

• Brinch Hansen on Pascal compilers, ISBN 0130830984

If it is more examples you're after I have a grammar parser written in C and it is well commented. The tool is still work in progress but the parser is already done. You can browse the sources at:

• http://bitbucket.org/trijezdci/ebnftool/src