MOO-cows Mailing List Archive


Re: modification of parser.y

Followup to:  <4qigbi$>
By author: (H. Peter Anvin)
In newsgroup: local.moo
> >  
> > I would be equally grateful to anyone who could point me to a man page
> > for LALR.  It seems to be conveniently missing on my system, as well as
> > every man pages server I've found on the web.  (ARGH!)
> >  

Oh, by the way... LALR(1) is not a man page... the subset of all
context-free grammars that yacc can generate a parser for is called
LALR(1).  The parsing technique used is called "lookahead LR" (LALR --
LR stands for left shift, right reduction) and yacc supports one (1)
token worth of lookahead.  The one-token lookahead limit is, by the
way, the reason why you wouldn't want to implement a chevron (<<)
operator by entering '<' '<' directly into the parser.

I have occationally seen LALR(2) parser generators, but they tend be
very memory-hungry.  Similarly, an LALR(0) parser is very
memory-efficient; unfortunately too many useful languages aren't in
the LALR(0) set.

For information on how to use yacc I recommend "Lex and Yacc" by
Levine, Mason & Brown, published by O'Reilly and Associates.  The
venerable "dragon book" has a more in-depth discussion of the LALR
parsing techique.


PGP public key available - finger
"The earth is but one country, and mankind its citizens."  --  Bahá'u'lláh
Just Say No to Morden * The Shadows were defeated -- Babylon 5 is renewed!!

Follow-Ups: References:

Home | Subject Index | Thread Index