Re: Yacc Poll

harvard!rutgers!mcnc!ece-csc!mauney (Jon Mauney)
Tue, 18 Aug 87 09:57:23 EDT

          From comp.compilers

Related articles
[2 earlier articles]
Re: Yacc poll (1987-08-11)
Re: Yacc poll ihnp4!m10ux!mncm000) (1987-08-14)
Re: Yacc poll malcolm@keilir.UUCP (1987-08-14)
Re: Yacc poll jbn@glacier.STANFORD.EDU (1987-08-16)
Re: Yacc poll decvax!utzoo!henry (1987-08-17)
Re: Yacc poll harvard!seismo!sun!tekchips!stevev (Steve Vegdahl) (1987-08-17)
Re: Yacc Poll harvard!rutgers!mcnc!ece-csc!mauney (1987-08-18)
| List of all articles for this month |

Date: Tue, 18 Aug 87 09:57:23 EDT
From: harvard!rutgers!mcnc!ece-csc!mauney (Jon Mauney)
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

Post a followup to this message

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