Re: Problem with top down parsing

> 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
http://www.cs.rhul.ac.uk/research/languages/index.shtml.


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


                                                  Adrian


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

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