Re: Problem with top down parsing

A Johnstone <>
24 Nov 2006 08:20:55 -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: A Johnstone <>
Newsgroups: comp.compilers
Date: 24 Nov 2006 08:20:55 -0500
Organization: Janet Usenet Reading Service.
References: 06-10-094
Keywords: parse
Posted-Date: 24 Nov 2006 08:20:55 EST

> 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. Here's an extract question:

By tracing through the steps of a top-down parser (with backtrack)
which tries the alternate aSa before aa, show that S succeeds on 2, 4, or
8 a's but not on 6 a's

The trick here is to realise that many backtracking parsers use what
we call a singleton match strategy, in which as soon as the parse
function for a rule finds a match, it returns. In general, parse
functions need to return a set of putative matches. Just try working
it through, and you'll see that a singelton match parser misses some
of the possible derivations.

Sadly, there are real parser generators our there that claim to be
general but which exhibit this behaviour. They usually have a getout,
which says something like 'rules must be ordered by longest
match'. This turns out to be impossible in general: there are grammars
for which different orderings are required for different strings in
the language. (See our paper, below, for an example.) Backtrack
parsers? Caveat emptor.

If you want a fuller expostion, see chapter 6 of 'The theory of
parsing, translation and compiling', Alfred V Aho and Jeffrey
D. Ullman, Prentice-Hall, 1972. For a compact exposition which includes
singleton match and truly general backtrack top down parser, see our paper

'Generalised recursive descent parsing and follow determinism', Adrian
Johnstone and Elizabeth Scott, in: Kai Koskimies ed, Proc. 7th
Intnl. Conf. Compiler Construction (CC'98), Lecture Notes in Computer
Science, 1383, Springer-Verlag, Berlin 16-30 (1998)

There's a journal paper by the same authors that might appear
sometime. If it does, you'll be able to get it from our web pages at

Now, I hope that wasn't a homework question...


Dr Adrian Johnstone, Senior Lecturer in Computing, Computer Science Dep,
Royal Holloway, University of London, Egham, Surrey, TW20 0EX, England.
Email Tel:+44(0)1784 443425 Fax:+44(0)1784 439786

Post a followup to this message

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