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.
>
> I know this would not solve much. Resolving the the conflicts 'the wrong
> way' can still result to an errorless parsing, but I would like to know if
> there have been any study about this approach. Is this a completely dead
> idea ?


Our C++ parser uses a yacc-generated parser that is recursively callable
in order to resolve the ambiguities in C++. I have modified a version of
Berkeley yacc in several (not very complicated) ways to support this
approach. The underlying yacc parser will of course not correctly parse a
non-LR(k) grammar by itself, but given the added features and using a
technique of "trial parsing" (such as that hinted at in the above
posting), it is possible to parse the desired ambiguities -- and more
generally, it is possible to parse non-LR(k) grammars. A paper describing
the implementation of the changes to yacc, the technique of trial parsing,
the role of the lexical analyzer, techniques required in constructing the
yacc grammar, and examples of parsing ambiguities in C++ has been
submitted to a journal. I suppose I could make draft copies of this
available on an individual basis to those interested.


Having done all this, I am still rather uncertain as to its value. (The
paper explains briefly why I went this route, and the reasons pertained
largely to practical concerns, scheduling, etc. rather than to technical
issues.) The approach certainly seems to work. It is quite powerful.
But I think if I had it to do over again I would use a recursive descent
parser.
---
Gary H. Merrill [Principal Systems Developer, C Compiler Development]
SAS Institute Inc. / SAS Campus Dr. / Cary, NC 27513 / (919) 677-8000
sasghm@theseus.unx.sas.com ... !mcnc!sas!sasghm
--

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