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.


Frank Wilde <perle@cs.tu-berlin.de> wrote:
> 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) .


Right you are. Further, somebody sent me e-mail pointing out that I
didn't really try to prove the theorem that was requested. I tried to
prove that a reachable *production* that is both left and right
recursive renders a grammar ambiguous. They also helped me see the
right proof.


Sooo... let's do this one more time:


case 1)


There is a production for A of the form


    A -> A b A


Assume that A derives some finite sentence a. Let the string
of symbols b derive some finite sentence s. Then if a is
nonempty, we have


    A -*-> (a s a) s a = a s a s a
    A -*-> a s (a s a) = a s a s a


otherwise my original proof is correct:


    A -*-> a s (a s (a s a)) = s (s s) = s s s
    A -*-> ((a s a) s a) s a = (s s) s = s s s


case 2)


There are productions for A of the form


    A -> b A
    A -> A c


Assume that A derives some finite sentence a. Let the string
of symbols b derive some finite sentence s, and c derive some
finite sentence t. Then if a, b, c are nonempty, we note that


    A -*-> s (a t) = s a t
    A -*-> (s a) t = s a t


We note that if a is the empty sentence, and s and t are
nonempty, then


    A -*-> s (s ((a t) t)) = s (s (t t)) = s s t t
    A -*-> ((s (s a)) t) t = ((s s) t) t = s s t t


If s or t is the empty sentence, then


    A -*-> a
    A -*-> s a = a


or


    A -*-> a
    A -*-> a t = a


Does this look better to everybody? My apologies for the online
theorem proving. I still hope I'm not doing somebody's homework :-).


Bart Massey
bart@cs.uoregon.edu
--

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