Re: Left and Right recursive non-terminals

<cowboy@vnet.ibm.com> wrote:
>> 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 <bart@cs.uoregon.edu> 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) .


Ciao,
Perle
--
Frank Wilde | perle@cs.TU-Berlin.DE | +49 30 3454141
--

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