Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!hao!ames!ucbcad!ucbvax!decvax!ima!johnl
From: johnl@ima.UUCP
Newsgroups: comp.compilers
Subject: Re: Yacc Poll
Message-ID: <668@ima.ISC.COM>
Date: Tue, 18-Aug-87 09:57:23 EDT
Article-I.D.: ima.668
Posted: Tue Aug 18 09:57:23 1987
Date-Received: Thu, 20-Aug-87 05:34:46 EDT
Sender: johnl@ima.ISC.COM
Reply-To: harvard!rutgers!mcnc!ece-csc!mauney (Jon Mauney)
Lines: 31
Approved: compilers@ima.UUCP
Posted-Date: Tue, 18 Aug 87 09:57:23 EDT


> ...My gut feeling is that the bottom-up nature of LALR parsing gives
> you rather less information about what's going on, perhaps enough to make
> the idea impractical.  My LALR is rusty enough that I'm not sure of this,
> though.  Certainly it's harder to do than the top-down version.

The LALR parser contains all the information about what's going on,
but since it is cleverly encoded in the states, one must go to some
trouble to extract it.  Bernard Dion showed how it can be done

 %A Bernard A. Dion
 %T Locally least-cost error correctors for context-free and
    context-sensitive parsers
 %D 1982
 %I UMI Research Press
 %C Ann Arbor
 %O Ph.D. Thesis, University of Wisconsin-Madison, 1978

With enough invariant-preserving transformation, Dion's algorithm can be
brought to a point that some may consider practical. Dion extracts a lot of
information, though. If you are willing to settle for less, more efficient
extractors are possible. If you just want to know what the possibilities are
for the next symbol, that's easy; it is just the symbols that can be shifted
by the current state, or by some state lower on the stack in the case that
this state can reduce.

            Jon Mauney    ...!mcnc!ece-csc!mauney or mauney@ece-csc.ncsu.edu
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.ARPA
Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | cca}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers.  Meta-mail to ima!compilers-request