Re: Backtracking yacc

Tom Harwood <harwood@progress.com> writes:
|> Backtracking yacc? Ahh, this takes me back to the bad old days; I once
|> debugged such a beast (we were using it to parse 5-10K line COBOL
|> programs). A few observations from experience:
|>
|> - The parse is still reasonably efficient. The parser really doesn't
|> backtrack all that often.


I have to observe (or maybe confess?) that our parser backtracks
*frequently* in parsing C++. This is because there are some pretty
general and frequently ecountered contexts in which the ambiguity can
arise. However, even so, it is true that the parse is still pretty
efficient since the "secondary" parses are usuallly quite short, and
saving and restoring states is pretty quick.


Keep in mind that the approach I have taken is *not* to build backtracking
into yacc, but to modify yacc in such a way that it can be used to
accomplish backtracking. This allows me a bit more control over when and
how the backtracking takes place.


|> - Semantic actions are not a bad problem, *as long as their side effects
|> can be undone when the parser backtracks*.


Mostly I just shut 'em off. However, this is not a solution in the
general case.


|> - Error handling is a total pain. Imagine what happens when the parser
|> encounters a dead end deep within an expression... and backtracks
|> to <start block>, or like high-level rule. You won't like it.


I think this is generalizeable to "Error handling in yacc is a total
pain." However, it's more of a pain if you permit some kind of
backtracking. Currently our parser issues some pretty puzzling error
diagnostics if it encounters a syntax error in an ambiguous construct
(i.e., *none* of the possibilities pans out). I'm leaning toward a "best
fit" approach here in which the parser will assume that the user intended
the type of construct that allows the parse to proceed the farthest.


|> - Did I mention that the company that developed this parser went
|> out of business? ;-)


Thanks a lot. I can always go back to teaching philosophy.
--
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.