|Problem with top down parsing email@example.com (2006-10-24)|
|Re: Problem with top down parsing firstname.lastname@example.org (Ujjwal) (2006-11-22)|
|Re: Problem with top down parsing email@example.com (A Johnstone) (2006-11-24)|
|Re: Problem with top down parsing firstname.lastname@example.org (Sylvain Schmitz) (2006-11-24)|
|From:||A Johnstone <email@example.com>|
|Date:||24 Nov 2006 08:20:55 -0500|
|Organization:||Janet Usenet Reading Service.|
|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 firstname.lastname@example.org Tel:+44(0)1784 443425 Fax:+44(0)1784 439786
Return to the
Search the comp.compilers archives again.