Re: Left and Right recursive non-terminals

bart@time.cirl.uoregon.edu (Barton C. Massey)
15 Dec 1996 16:19:01 -0500

          From comp.compilers

Related articles
Left and Right recursive non-terminals cowboy@cv.lexington.ibm.com (1996-12-14)
Re: Left and Right recursive non-terminals bart@time.cirl.uoregon.edu (1996-12-15)
Re: Left and Right recursive non-terminals dlmoore@ix.netcom.com (David L Moore) (1996-12-15)
Re: Left and Right recursive non-terminals perle@cs.tu-berlin.de (1996-12-18)
Re: Left and Right recursive non-terminals bart@time.cirl.uoregon.edu (1996-12-20)
Re: Left and Right recursive non-terminals vonbrand@inf.utfsm.cl (Horst von Brand) (1996-12-26)
| List of all articles for this month |

From: bart@time.cirl.uoregon.edu (Barton C. Massey)
Newsgroups: comp.compilers
Date: 15 Dec 1996 16:19:01 -0500
Organization: University of Oregon
References: 96-12-089
Keywords: parse, theory

<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).


A reachable non-terminal that is both left and right recursive and
which derives any nonempty string of terminals renders a grammar
ambiguous, yes. I don't know a reference, but the proof is pretty
easy...


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.
Assume further that there is a nonempty sentence s such that s is
derivable from b (this is informal, but you get the idea).


Consider parsing the sentence s s s with A. We can parse this
as
    A -> A b A -> (A b A) b A -> ((A b A) b A) b A -*-> ((s) s) s
or as
    A -> A b A -> (A b A) b A -> (A b A) b (A b A) -*-> (s) s (s)


In other words, we can have at least two parse trees for the
sentence s s s


    s s
      \ / \
        s s s
          \
            s


Finally, we note that by the definition of A, A must recognize the
sentence s s s , therefore A is ambiguous.


Hope this helps, (and that I didn't just do your homework for you :-)!


Bart Massey
bart@cs.uoregon.edu
--


Post a followup to this message

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