|Left and Right recursive non-terminals firstname.lastname@example.org (1996-12-14)|
|Re: Left and Right recursive non-terminals email@example.com (1996-12-15)|
|Re: Left and Right recursive non-terminals firstname.lastname@example.org (David L Moore) (1996-12-15)|
|Re: Left and Right recursive non-terminals email@example.com (1996-12-18)|
|Re: Left and Right recursive non-terminals firstname.lastname@example.org (1996-12-20)|
|Re: Left and Right recursive non-terminals email@example.com (Horst von Brand) (1996-12-26)|
|From:||firstname.lastname@example.org (Frank Wilde)|
|Date:||18 Dec 1996 00:12:14 -0500|
|Organization:||Technical University of Berlin, Germany|
>> I'm sure I read somewhere that a non-terminal that is both left and right
>> recursive renders the grammar ambiguous (I think for any k).
Barton C. Massey <email@example.com> wrote:
>Consider a such nonterminal A, with production
> A -> A b A
>where b is any string of terminals and nonterminals (need a
>Greek keyboard :-).
>Now, for there to be any finite-length strings recognizable by A, it
>must be that it is possible to derive the empty sentence e from A.
Non sequitur. There must be another production for A for a derivation
of A to be able to terminate, but you only have to be able to derive some
terminal string from it; it does not neccessarily have to be empty.
Of course, this says nothing about abiguousity, because
A b A b A can obviously be (A b A) b A or A b (A b A) .
Frank Wilde | perle@cs.TU-Berlin.DE | +49 30 3454141
Return to the
Search the comp.compilers archives again.