Re: Backtracking yacc

> Has anybody seen such a thing as backtracking yacc? What I had in mind
> was a LALR parser that resolves ambiquity by backtracking to the point
> where it had multiple routes to go. It would parse the input until it
> encounters a dead end, and after that it would try an alternative path.


For some reason, I have only seen four replies to the original posting, so
I hope this remark has not been posted already.


I would like to add to the discussion that backtracking could lead to very
inefficient behaviour; the number of `dead ends' can increase
exponentially in the number of steps taken since the first `wrong' choice.
In practice, Near linear-time results (don't ask me to explain what near
linear means) can be reached using the parsing methods in the work of B.
Lang, M. Tomita, R. Leermakers and J. Rekers. Until recently, the latter
was a member of the same research group as I at CWI.


The methods have in common that they reuse the useful work done on the
path leading to a dead end. Jan Rekers has developed a parser generator in
Lisp that generates parsers using this parsing method.


However, as far as I know, attaching semantic actions to the parsers
described in this work is still a problem.


Literature:


B. Lang. Deterministic techniques for efficient non-deterministic parsers.
In J. Loeckx, editor, Proceedings of the Second Colloquium on Automata,
Languages and Programming, volume 14 of LNCS, 1974


R. Leermakers. Non-deterministic Recursive Ascent Parsing. In the
proceedings of the Fifth Conference of the European Chapter of the
Association for Computational Linguistics, 9-11 April 1990.


J. Rekers. Parser Generation for Interactive Environments. PhD thesis
University of Amsterdam, 1992. CWI, Kruislaan 413, Amsterdam, The
Netherlands, Department AP3.


M. Tomita. Efficient Parsing for Natural Languages. Kluwer Academic
Publishers, 1985
--

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