Re: Is a contextfree Grammar ambiguous ?

Martin asked:
>> Does an algorithm to decide whether a context free grammar is
>> ambiguous exist ?


Chris Clark USG <clark@quarry.zk3.dec.com> writes:
>There is a little semantic nit with this question, but for the
>question you are trying to ask is probably yes.


>The semantic nit is that by definition a context free grammar is
>unambiguous. That is, if your grammar is ambiguous it is not a
>context free grammar.


Huh? Here are the productions of an ambiguous context-free grammar:
S -> S
S -> 0
...


>There are related classes, the LL(oo) and LR(oo) grammars, that
>researchers are defining algorithms for, and in that sense still
>defining what is meant by these names.


I'm not familiar with LR(oo) -- do you have a reference? It seems to
me that infinite lookahead would imply general context-free parsing.
Do you perhaps mean LR(k, oo), which Szymanski defined in 1972 as a
generalization of Knuth's LR(k,t)?
--
M. Dennis Mickunas
Department of Computer Science 1304 W. Springfield Ave.
University of Illinois Urbana, Illinois 61801
mickunas@cs.uiuc.edu (217) 333-6351

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