Re: Problem with top down parsing

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).
<http://dx.doi.org/10.1016/S0019-9958(73)90851-6>.


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
<http://pdos.csail.mit.edu/~baford/packrat/>, 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,


      Sylvain

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