BNF Grammars and Syntax Rules

Before a program can do anything with a piece of text, something has to read that text and recognize its structure. That work belongs to a parser. This article introduces one popular method for writing a parser by hand, called recursive descent parsing. It is not the only way to parse, and it is not the most efficient one. What makes it useful is that it is the method best suited for writing compilers by hand, instead of generating the parser with a parser generator program.

The answer follows from the central idea of the method: the structure of the program mirrors the structure of the grammar. The rest of this article shows how that mirroring works, what the grammar must satisfy for it to work, and how the parser behaves while it runs.

The central idea of recursive descent parsing is a direct correspondence. In a recursive descent parser, every rule of the BNF grammar becomes a subroutine. If the grammar has a rule for an expression, the parser has a subroutine that handles expressions. If the grammar has a rule for a term that sits inside an expression, the parser has a separate subroutine for terms. The structure of the program therefore mirrors the structure of the grammar. Reading the grammar tells you what subroutines to write, and reading the subroutines tells you which grammar rules they follow.

To make this concrete, consider a small illustrative grammar that is invented for this article. An expression is a term. A term is either a single digit-based number, or an opening parenthesis followed by an expression and a closing parenthesis. Each of these three rules gets its own subroutine, and the subroutines call one another in the same pattern that the rules refer to one another. The rule for expression refers to term, so expression() calls term(). The rule for term refers to expression inside its parenthesized alternative, so term() calls expression(). The rule for number is a separate subroutine that term() calls when it chooses the number alternative.

The sketch above is only a shape to study, not a finished parser. Its purpose is to show that each grammar rule has a matching subroutine and that the calls between subroutines match the references between rules.

In the illustrative grammar, this property holds. When term() is running, the parser only needs to see whether the next character is an opening parenthesis. If it is, the phrase must be a parenthesized expression. If it is not, the phrase must be a number. The next input item alone determines which rule applies, so term() can make its decision immediately. The flowchart below shows this single branching decision.

The clearest way to see the mechanism is to follow a parse of a short nested phrase. Take the input (4) under the illustrative grammar. Parsing starts by calling expression(). That subroutine hands the work to term(). The term() subroutine looks at the next item, which is an opening parenthesis, so it chooses the parenthesized alternative. It consumes the parenthesis and calls expression() again, because the grammar says an expression goes inside the parentheses.

The second expression() call again calls term(), which now sees the digit 4 and chooses the number alternative, calling number(). Once the digit is consumed, control returns up through the chain of calls, and the closing parenthesis is consumed by the outer term() call. The call stack diagram below shows which subroutine is active at each step.

The BNF rules say nothing about spaces between items, yet a person writing input usually wants to put spaces between items wherever they like. A recursive descent parser handles this with a convention. Before it looks ahead to see what is coming up next in the input, it calls TextIO.skipBlanks(). That call skips past any whitespace, such as spaces and tabs. It stops when the next character is either a non-blank character or the end-of-line character.

Because the lookahead decision in term() depends on seeing the next character, skipping blanks first is what makes that decision reliable. If the input is written as ( 4 ), the spaces would otherwise stand between the parser and the character it needs to examine. Calling skipBlanks() before each lookahead lets the same grammar accept the input with or without spaces, without the grammar rules themselves having to mention spaces.

Hand-written recursive descent parsers are easy to get subtly wrong, because the rules are simple to state but the order of operations matters. The mistakes below all involve the lookahead and the input position.