Re: YACC with infinite lookahead

Daniele Benegiamo wrote:


> Someone know if there exists a version of YACC with infinite lookahead?
>
> Daniele "kafumanto" Benegiamo | mailto:Daniele.Benegiamo@aleph.it
> | http://www.aleph.it/~benegiamo
> [I doubt it. There have been versions of yacc that can back up and try
> again, which are nearly essential if you want to parse C++. Give one of
> them a try. -John]


I don't have production software to do this - I didn't implement beyond
proof of concept as there seems to be little interest.


Some time ago, I worked out some theory on how to look-ahead at
non-terminals instead of terminals in the parsing process. This
requires a better parsing automata that the PDA. I used 2 stacks
(i.e. the parser allows parsed look-ahead non-terminals to be pushed
back into the "input stack" and avoids any re-parsing of arbitrary
look-ahead. The parser is still efficient (O(N)), detects errors
immediately, etc. The generator produces an LR(1) parser for an LR(1)
grammar (which can be reduced to LALR(1) as a separate optimisation
process). The technique has some interesting capabilities for error
recover, too. There were a few papers published a few years ago.


I believe the technique is practical for a number of painful parsing
problems, e.g. it allows the lexical and parsing phases to be unified.


The technique cannot "look ahead" over an arbitrary bunch of brackets
to see what is coming next, so it probably doesn't help with problems
parsing C++.


          regards
          Bob Buckley

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