Re: Left and Right recursive non-terminals

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)


--

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