Re: Backtracking yacc

Tom Harwood <harwood@progress.com>
Fri, 18 Sep 1992 12:02:37 GMT

          From comp.compilers
Related articles
[3 earlier articles]
Re: Backtracking yacc sasghm@unx.sas.com (Gary Merrill) (1992-09-14)
Re: Backtracking yacc ipser@solomon.technet.sg (1992-09-16)
Re: Backtracking yacc bromage@mullauna.cs.mu.OZ.AU (1992-09-17)
Re: Backtracking yacc Jasper.Kamperman@cwi.nl (1992-09-17)
Re: Backtracking yacc sasghm@unx.sas.com (1992-09-17)
Re: Backtracking yacc diamond@jit081.enet.dec.com (18-Sep-1992 1420) (1992-09-18)
Re: Backtracking yacc harwood@progress.com (Tom Harwood) (1992-09-18)
Re: Backtracking yacc ipser@solomon.technet.sg (1992-09-19)
Re: Backtracking yacc andrewd@cs.adelaide.edu.au (1992-09-21)
Re: Backtracking yacc sasghm@unx.sas.com (1992-09-21)
Re: Backtracking yacc sasghm@unx.sas.com (1992-09-23)
Re: Backtracking yacc schrod@iti.informatik.th-darmstadt.de (1992-09-23)
Re: Backtracking yacc andrewd@cs.adelaide.edu.au (1992-09-25)
[2 later articles]
| List of all articles for this month |
Newsgroups: comp.compilers
From: Tom Harwood <harwood@progress.com>
Organization: Progress Software Corp.
Date: Fri, 18 Sep 1992 12:02:37 GMT
References: 92-09-059 92-09-100
Keywords: yacc, parse, LR(1), Cobol
Posted-Date: Fri, 18 Sep 1992 12:02:37 GMT

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.


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


- An analog of the Prolog "cut" helps keep the conflict stack managable.


- 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.


- It's worth exploring a conflict before it's pushed onto the stack.
    About 75% of the conflicts we saw lead to "no hope" states.


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


Have fun.
--

Post a followup to this message

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