Re: Bactracking/lookahead parser generators?

jamz@my-dejanews.com wrote:


> Also look at the completely rewritten ANTLR 2 available from
> www.antlr.org. It works bascially the same as PCCTS, using syntactic
> predicates, but these predicates are no longer hoisted to referencing
> rules.


Jamz is referring to the semantic predicate hoisting idea rather than
the syntactic predicate (infinite lookahead) notion for which Adrian
has asked for info. I found that idea insanely kewl, but alas many
folks didn't quite grok it in 1.xx, hence, it was removed from the
2.xx spec; John Mitchell is currently beating me up pretty badly about
putting hoisting back in.


Both ANTLR 1.xx and ANTLR 2.xx employ backtracking for infinite
lookahead. ANTLR 1.xx used longjmp if I remember whereas ANTLR 2.xx
uses exceptions in Java. Note that even when you specify infinite
lookahead, ANTLR-generated parsers don't always backtrack--they check
the static lookahead first to see if it's obvious which way to go.


Don't forget to look at JavaCC, which uses rule return values (error
codes) to implement backtracking rather than using exceptions. That
is faster for an individual backtrack than an exception, but results
in messier code IMHO with all the result checking. In the overall
parse, however, ANTLR-generated parsers perform similarly given their
"only when necessary" approach.


Hope this helps,
Terence

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