Re: YACC with infinite lookahead

Bob Buckley <bbuckley@ozemail.com.au>
20 May 1999 01:46:07 -0400

          From comp.compilers

Related articles
YACC with infinite lookahead daniele.benegiamo@aleph.it (Daniele Benegiamo) (1999-05-16)
Re: YACC with infinite lookahead bbuckley@ozemail.com.au (Bob Buckley) (1999-05-20)
Re: YACC with infinite lookahead cfc@world.std.com (Chris F Clark) (1999-05-20)
Re:YACC with infinite lookahead scavadini@hotmail.com (Salvador V. Cavadini) (1999-05-20)
Re: YACC with infinite lookahead demaille@solo.enst.fr (Akim Demaille) (1999-05-21)
Re: YACC with infinite lookahead vmakarov@cygnus.com (Vladimir Makarov) (1999-05-21)
Re: YACC with infinite lookahead bromage@cs.mu.OZ.AU (1999-05-27)
| List of all articles for this month |

From: Bob Buckley <bbuckley@ozemail.com.au>
Newsgroups: comp.compilers
Date: 20 May 1999 01:46:07 -0400
Organization: Infuse Pty Ltd
References: 99-05-072
Keywords: parse

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


Post a followup to this message

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