Re: Backtracking parsers

Michael Lee Finney (michael.finney@acm.org) wrote:
: I was talking to friend about a grammar, and he suggested that there were
: grammar problems that I couldn't see. It turned out to be a communication
: problem, but it raised a very interesting question. If you have a grammar
: such as:


: prod1 := (prod2 | prod3) prod4
: prod2 := ...
: prod3 := ...
: prod4 := ...


...


Backtracking parsers are _far_ trickier than is generally
recognised. In general, one must return a set of possible matches from
each sub-rule and then test each of their continuations. This is the
root of the issue that you've raised.


I've spent quite a lot of time studying the available backtracking
parsers out there and designing my own. You might like to have a look
at our paper in the 1998 Compilers Conference (Generalised Recursive
Descent Parsing and Follow determinism, Adrian Johnstone and Elizabeth
Scott in 7th International Conference on compiler 1998, Lecture Notes
in Computer Science 1382) which explains in detail how multiple
matches must be tracked via return sets, the effect of enforcing
singleton matches, and the applicability of certain match
strategies. We've also just submitted a paper to ToPLAS on the broad
issue of backtrack parsers and their failure modes which contains
practical advice as well as some theoretical results. You might also
like to look at our Web page on backtracking parsers which you can
reach via


                        http://www.cs.rhbnc.ac.uk/research/languages/


Anybody who'd like a preprint of the ToPLAS paper (which hasn't been
refereed yet) let me know.




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

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