Concepts / Parser Generators Compared With Hand-Written Parsers

Parser Generators Compared With Hand-Written Parsers

A recursive descent parser models every BNF grammar rule as a subroutine, so the structure of the program follows the structure of the grammar.

  • Programming

Predicting the Calls for a Nested Phrase

Before a program can do anything with a piece of text, something has to read that text and recognize its structure. That work is done by a parser. This article introduces one 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. Its usefulness is that it is the method best suited for writing compilers by hand, instead of generating the parser with a parser generator program.

What do you think happens?

Consider the input (4) under a grammar where an expression is a term, and a term is either a number or an opening parenthesis, an expression, and a closing parenthesis. Starting from expression(), which subroutines are called, and in what order?

  • expression() calls number() directly and then returns

  • expression() calls term(), term() calls expression() inside the parentheses, and that second expression() calls term() and then number()

  • term() is never called because the parenthesis is handled by the parser itself

Reveal answer
Answer:

expression() calls term(). Because the next item is an opening parenthesis, term() chooses the parenthesized alternative, consumes the parenthesis, and calls expression(). That second expression() calls term() again, which now sees the digit 4 and calls number(). After the digit is consumed, control returns up the chain and the outer term() consumes the closing parenthesis.

The source describes exactly this sequence: each grammar rule is a subroutine, and nested grammar rules show up as nested subroutine calls. The rest of this article explains why each choice is made and how control moves back up.

Grammar Rules Become Subroutines

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 which subroutines to write, and reading the subroutines tells you which grammar rules they follow.

To make this concrete, this article uses a small illustrative grammar, invented for teaching purposes. 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.

Pattern
expression ::= term
term ::= number | '(' expression ')'
number ::= digit-based number

The diagram shows the mapping for this grammar. The term rule refers back to the expression rule inside its parenthesized alternative, so the term() subroutine calls expression(), and expression() calls term() in return. This back-and-forth is the reason the method is called recursive. Each rule's subroutine calls the subroutines for the rules it mentions, and those calls can nest as deeply as the input nests.

The One-Item Lookahead Requirement

Not every BNF grammar can be parsed this way. The grammar must have a specific property. While the parser is in the middle of parsing a phrase, it must be possible to tell which syntactic category comes next by looking only at the next item in the input. The parser does not get to guess, backtrack through alternatives, or read far ahead to decide. It has to choose the right subroutine from one item of lookahead.

Key point

A grammar suits recursive descent parsing when the next input item alone reveals the next syntactic category. The parser makes its choice immediately, from that one item, without guessing or backtracking.

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 at once. The flowchart below shows this branching.

Tracing the Phrase (4)

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 the subroutine for the top rule, expression(). That subroutine hands the work to term(). The diagram below shows which subroutine is active at each point, and how calls and returns are ordered.

Worked example

Parsing (4) step by step

Parse the input (4) using expression(), term(), and number() under the illustrative grammar.

  1. 1
    Start at the top rule

    Parsing begins by calling expression(), the subroutine for the top rule. expression() hands the work to term().

  2. 2
    Choose the parenthesized alternative

    term() looks at the next item, which is an opening parenthesis. That single item decides the alternative, so term() consumes the parenthesis.

  3. 3
    Nested expression call

    The grammar says an expression goes inside the parentheses, so term() calls expression() again.

  4. 4
    Choose the number alternative

    The second term() call sees the digit 4, not an opening parenthesis, so it chooses the number alternative and calls number().

  5. 5
    Return up the chain

    Once the digit is consumed, control returns up through the chain of calls. The closing parenthesis is then consumed by the outer term() call, which was waiting for it.

Result

The phrase (4) is recognized. The calls were expression(), term(), expression(), term(), number(), followed by returns that unwind the nesting.

Skipping Blanks Before Lookahead

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.

The reason for the call is that the lookahead decision in term() depends on seeing the next character. 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.

Before

input: ( 4 ) peek at next character: space term() asks: is it an opening parenthesis? no wrong alternative chosen

Lookahead runs while a space is still the next character, so the decision sees a blank rather than the syntactic item it needs.

After

input: ( 4 ) skipBlanks() moves past the space peek at next character: opening parenthesis term() asks: is it an opening parenthesis? yes parenthesized alternative chosen

skipBlanks() has moved past the whitespace, so the lookahead sees the real next item and the decision is correct.

Mistakes When Hand-Writing the Parser

Because a hand-written recursive descent parser relies on lookahead decisions and on skipping blanks at the right moments, a few mistakes are easy to make. The items below follow directly from the principles above.

  • Common mistake

    Looking ahead before skipping blanks

    What it looks like

    Input ( 4 ) with a space right after the opening parenthesis. The lookahead inspects the space instead of the next real item.

    Why it fails

    The lookahead decision depends on seeing the next character. A blank in that position hides the item the decision needs.

    Do this instead

    Call TextIO.skipBlanks() before each lookahead, so the parser examines the next non-blank character or the end of the line.

  • Common mistake

    Consuming input inside a lookahead check

    What it looks like

    A subroutine reads the next item to test it and then advances the input pointer, so the subroutine that should handle that item finds the input already gone.

    Why it fails

    The source's central requirement is that the next item only reveals the next syntactic category. The choosing step is supposed to peek, and the chosen subroutine is supposed to consume. When the peek also consumes, the input pointer no longer points at the start of the phrase the chosen rule expects.

    Do this instead

    Let the decision inspect the next item without advancing the input. Only the subroutine for the chosen rule should consume the items that belong to its rule.

  • Common mistake

    Writing a grammar that needs guessing

    Why it fails

    Recursive descent cannot backtrack or read far ahead. If the next item does not determine the alternative, the method does not apply to that grammar as written.

    Do this instead

    Check that each choice can be made from one item of lookahead. If it cannot, the grammar lacks the required property and must be changed before this method works.

Checking Your Understanding of the Parse

MEDIUM

Under the illustrative grammar, trace the parse of the input ( ( 4 ) ) with spaces between items. List, in order, each subroutine that is called, and state for each term() call which alternative it chooses and what single input item made that choice.

Hints
  • Start with expression(), then follow term() and the first parenthesis.
  • Each term() call should check the next non-blank item after calling skipBlanks().
  • A term() call that sees an opening parenthesis calls expression() inside it; a term() call that sees the digit calls number().

Key Takeaways

  • In recursive descent parsing, every BNF grammar rule becomes a subroutine, so the program structure mirrors the grammar structure.
  • The grammar must let the parser tell which syntactic category comes next by looking only at the next input item, because the parser cannot guess, backtrack, or read far ahead.
  • Nested grammar rules appear as nested subroutine calls, and control returns back up the chain once a nested phrase is finished.
  • The parser calls TextIO.skipBlanks() before looking ahead, so whitespace does not hide the next item that the lookahead decision needs.
  • A common hand-writing mistake is to consume input during a lookahead check, or to look ahead before skipping blanks.

Related Topics