Re: Left and Right recursive non-terminals

David L Moore <dlmoore@ix.netcom.com>
15 Dec 1996 16:24:14 -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: Aho and Ullman theory of parsing books adrian@dcs.rhbnc.ac.uk (1996-12-20)
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: David L Moore <dlmoore@ix.netcom.com>
Newsgroups: comp.compilers
Date: 15 Dec 1996 16:24:14 -0500
Organization: Netcom
References: 96-12-089
Keywords: parse, theory

cowboy@cv.lexington.ibm.com wrote:
>
> The recent discussions on LL(k) has reminded me of a topic I can no longer
> find...
>
> 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 grammar is ambiguous if a sentence has more than one possible parse
tree (Aho and Ullman "The Theory of Parsing Translation and
Compiling", Vol 1, page 143 [Prentice Hall 1972]). It has nothing to
do with k. An ambiguous grammar is nether LL(k) not LR(k) for any
k. This is obvious since these are deterministic parsers so they
cannot handle the situation where there are two possible parse trees.


Consider the grammar


A -> aA | b | Ac


The sentence abc can be parsed A->aA->aAc->abc or
A->Ac->aAc->abc. Hence the grammar is ambiguous. The result is easy to
generalize.


David Moore.


NOTE: YACC (and possibly other parser generators) will still produce
parsers for ambiguous grammars by throwing away alternate parses. You
just have to be careful to keep the one you want. YACC has priority
statements to guide it - see the YACC and LEX book by our esteemed
moderator (my copy is at work, so I cannot give you the exact
bibliographic information]


BTW, I only have Vol 1 of Aho and Ullman. I believe someone said here
that it is out of print. Has it been republished by any of those
companies that reprint valuable older texts. (Such as Dover - I now
have a number of texts in Dover editions which I was too poor to
purchase as a student - Dover is an ornament to civilization)


--


Post a followup to this message

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