Re: Yacc Poll

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

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