Re: Backtracking yacc

The moderator comments:
>[That might help for conflicts in an unambiguous grammar that needs more than
>one token lookahead, but not for the more common case that a conflict is due
>to a truly ambiguous grammar. Besides, isn't there a theorem that says that
>any LR(k) grammar can be rewritten as LR(1)? -John]


Such theorems are rarely of practical value; in practice you will find
that rewriting an LR(k) grammar to be LR(1) (or whatever) will involve
contorting the original syntax in ways that are perverse. While such a
contortion might be acceptable for parsing alone, attempting to add simple
semantic actions or, worse, trying to maintain the grammar for an evolving
language can lead to premature greying. The Roskind C++ grammar is a
notorious example.


As for backtracking, there are additional problems: again, what about
semantic processing? If you are merely parsing or constructing a parse
tree, you can get away with throwing away an incorrect guess. But as soon
as you introduce side effects of even the simplest nature, you are left
with the task of figuring out how to undo actions associated with the
wrong guess. Even for a language as simle as Ansi C, you must perform
certain semantic actions just to parse and C++ is even worse.


A far better approach is to have available a set of tools which allow the
disambiguation at the point where it is first encountered. LADE, for
example, allows context-sensitive tests to be performed. These can be used
to either a) test arbitrary semantic information to decide on a path to
take, or b) parse ahead in parse-only mode to find some disambiguating
symbol, then return and resume normal, action-associated, parsing. While b
approaches a back-tracking capability, it is not, in fact, backtracking
since it returns to the originating point regardless of what symbols were
found in the scan- ahead.


(For information on LADE please contact xorian@solomon.technet.sg)
--

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