How to Build a Recursive Descent Parser

Updated on 2020-03-14

Learn how to implement recursive descent parsers, with examples for JSON and an integer expression evaluator

• Download source - 85.3 KB

Introduction

Recursive descent parsing is probably the most common form of parsing. It is the standard choice for implementing hand rolled parsers. This article aims to teach you how to build them.

Conceptualizing this Mess

Parsing is used in countless software products, and involves breaking up structured text into meaningful "phrases" which are used by your code to implement some sort of functionality. What functionality that is depends on what you're parsing. In our examples, we have a JSON parser whose functionality involves building a tree of normalized JSON data, as well as an expression parser, whose functionality involves evaluating an integer expression at runtime and returning the result.

The Design Phase: Building the Grammar and Planning the Parser

There are several steps to implementing a parser, from planning to implementation. The first step is to design the "grammar" for what you'll be parsing. It can be helpful to define it using EBNF or a variant thereof. I use XBNF which is my own variant of EBNF in order to write the grammar, but it doesn't matter what form you use as long as it's understandable. We'll then use this grammar as our design template, which we'll use to guide us through the creation of the parser.

EBNF

Our grammar for the JSON parser is as follows:

Json<start>= Object | Array;
Object= "{" [ Field { "," Field } ] "}";
Field= string ":" Value;
Array= "[" [ Value { "," Value } ] "]";
Value<collapsed>= string |
    number    |
    Object    |
    Array     |
    Boolean   |
    null      ;
Boolean= true|false;
number= '\-?(0|[1-9][0-9]*)(\.[0-9]+)?([Ee][\+\-]?[0-9]+)?';
string= '"([^\n"\\]|\\([btrnf"\\/]|(u[A-Fa-f]{4})))*"';
true= "true";
false= "false";
null= "null";
lbracket<collapsed>= "[";
rbracket<collapsed>= "]";
lbrace<collapsed>= "{";
rbrace<collapsed>= "}";
colon<collapsed>= ":";
comma<collapsed>= ",";
whitespace<hidden>= '[\n\r\t ]+

Meanwhile, our grammar for the expression parser is as follows:

Term<start,type="int">= Factor { ("+"|"-") Factor };
Factor<type="int">= Unary { ("*"|"/") Unary };
Unary<type="int">= ("+"|"-") Unary | Leaf;
Leaf<type="int">= integer | "(" Term ")";
add="+";
sub="-";
mul="*";
div="/";
lparen="(";
rparen=")";
integer='[0-9]+';
whitespace<hidden>='\s+';

The JSON grammar should be fairly obvious if you understand EBNF and possibly XBNF. You can read about XBNF at any of my previous parser generator projects, which all use XBNF as their input format. Unlike my other parser projects, we will not be machine generating code for an XBNF grammar. We'll be implementing it ourselves once again simply using the grammar as a guide to help us code it.

parser generator projects

Note above I've labeled the non-terminal elements of the grammar with TitleCase names and the terminal elements with camelCase names. If you don't understand terminals versus non-terminals, it doesn't matter much here. Basically, non-terminals are composed of terminals and other non-terminals, while terminals just represent individual "flat" lexemes in the input stream. Non-Terminals are divisible into their component parts, while a terminal is atomic/indivisible. Again, you don't really need to understand this part, but it's nice if you do.

After we have the grammar, the next step should be to decide whether we'll be using a tokenizer/scanner or whether we'll be implementing a scannerless parser. Using a tokenizer/scanner can make it easier to parse, but requires either additional handwritten code or an additional build step in order to generate the scanner code.

You may be wondering what exactly a tokenizer/scanner does. Briefly it takes an input stream of text and finds patterns in it. Each different pattern has "symbol id" associated with it that tells you what pattern it is (e.g., is it a number, a string, or an opening or closing parenthesis, etc?) This information is returned as a series of "tokens" which hold the symbol id, the value of the text that was matched, and the line, column and position info of the token within the input stream. The parser then uses those symbol ids to decide what to parse next. Parsers don't really care about the token values, just the token symbol ids. To recap, the value is the literal text that was matched, while the symbol id is the numeric "code" associated with that type of text fragment.

Why should we use a tokenizer/scanner? A tokenizer/scanner can drastically ease parsing by separating the lexical analysis and syntax analysis as separate steps. Without a tokenizer/scanner, both steps are combined together in the parse routines, which can complicate them.

Why not use a tokenizer/scanner? Tokenizers/scanners don't have any context information so they cannot conditionally return different symbols for the same text depending on where it appears in the input. Because of this their matching power is less than it could be for a scannerless parser. Realistically however, this is almost never a problem. It's very rare that you'll run into a need to distinguish terminal tokens based on context. However, you will run into it with grammars like Python because of significant versus insignificant whitespace in that language's grammar. In these cases, you can either still hand write a separate tokenizer/scanner, or simply integrate the scanner portions directly into the parsing code itself. The other reason you might not want to use one is in the case of very simple grammars.

Provided in the code for this article is a scannerless JSON parser as well as an integer expression parser, the latter of which does use a tokenizer. We could have just as easily used a scanner/tokenizer for JSON but I wanted to demonstrate both techniques.

If you decide to use a tokenizer, it is generally much easier to generate one using a tool like Rolex rather than write one by hand. I've include the Rolex binary in the solution folder so that the ExpressionParser project can be rebuilt from the scanner/tokenizer specification file.

Rolex

The JSON Parser

The JSON parser is a simple parser that reads JSON input and parses it into an object model, using IDictionary<string, object> to represent a JSON object and IList