Re: Problem with top down parsing

Sylvain Schmitz <>
24 Nov 2006 19:00:41 -0500

          From comp.compilers

Related articles
Problem with top down parsing (2006-10-24)
Re: Problem with top down parsing (Ujjwal) (2006-11-22)
Re: Problem with top down parsing (A Johnstone) (2006-11-24)
Re: Problem with top down parsing (Sylvain Schmitz) (2006-11-24)
| List of all articles for this month |

From: Sylvain Schmitz <>
Newsgroups: comp.compilers
Date: 24 Nov 2006 19:00:41 -0500
Organization: Compilers Central
References: 06-10-094 06-11-099
Keywords: parse
Posted-Date: 24 Nov 2006 19:00:41 EST
X-Virus-Scanned: amavisd-new at

A Johnstone wrote:
>> S -> aSa | aa
>> It is quoted that a "top down parse with backtracking" can establish
>> the inputs with 2,4 or 8 a's but not 6 a's .... How is this possible ?
> The exercise (5.6 on page 193 of the first edition of the Dragon Book) refers
> to limited backtrack parsing.
> [...]
> If you want a fuller exposition, see chapter 6 of 'The theory of
> parsing, translation and compiling', Alfred V Aho and Jeffrey
> D. Ullman, Prentice-Hall, 1972. [...]

More references on the subject:

This limited backtrack parsing technique and the languages it allows
to recognize were investigated in a thesis by Alexander Birman (and
supervised by Jeffrey Ullman). The parsers run in linear time using
memoization techniques. The main results are also accessible in

Alexander Birman and Jeffrey D. Ullman, Parsing Algorithms with
Backtrack, Information and Control 23, 1--34 (1973).

The grammatical formalism and the corresponding parsing technique are
now better known as Parsing Expression Grammars (PEGs) and packrat
parsers after the recent work of Bryan Ford. More information is
accessible from his packrat webpage
<>, including electronic
copies of his papers and of Birman's PhD thesis.

The technique is currently implemented in a small number of parser
generators, for instance Robert Grimm's Rats!, and used in some ways in
the recent ANTLR 3 by Terence Parr.

Hopes that helps,


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.