On Tue, 16 Jul 2002, Shlomi Fish wrote:
> > Another thing that got me stuck, is the list-like recursion, such as
> > (yacc!):
> >
> > chunk: { $$ = ""; }
> > | item chunk { $$ = $1.$2; }
> > ;
> >
> > Now, note the first line, representing that "chunk" could be nothing. It
> > also says that nothing should be nothing (that is, $$ = "")! It took me
> > some time to find out that the $$="" is necessary, otherwise we get
> > previous garbage in $$, and I mean GARBAGE.
> >
> > Now, I guess that the compiler freaks among us will notice, that I made
> > a "right recursion", as opposed to the glorious "left recursion", which
> > would be saying "chunk item { $$ = $1.$2; }". (Right recursion forces
> > the parser to read all the chunk into the stack before starting to
> > chew).
> >
> > The reason I stayed with right recursion is that left recursion didn't
> > work :(. I got empty strings. Anyone got any idea of why?
>
> I think Yacc imposes some limitations on its grammar and does not accept
> left-recursive grammars. Better check the Dragon Book to be sure.
to be exact, yacc will accept any grammar you give it, but is guranteed to
work properly only for LALR(1) grammars. the reason that us 'compiler
freaks' use left-recursions, is because this usually solves conflicts with
the grammar that make it non-LALR(1) grammar. yacc is not capable of
properly handling all context-free grammars - only the LALR(1) subset.
ofcourse, if you want to know what the hell LALR(1) stands for (its
pronounced El-Ei-El-Ar-One, btw) - indeed, get yourself a dragon, and read
chapters 1-4 (or just chapter 4, which i think deals with grammar-based
parsers, and with yacc specifically). you'll learn to appreciate handles
;)
--
guy
"For world domination - press 1,
or dial 0, and please hold, for the creator." -- nob o. dy
--------------------------------------------------------------------------
Haifa Linux Club Mailing List (http://linuxclub.il.eu.org)
To unsub send an empty message to [EMAIL PROTECTED]
