Unambiguity proofs for CFG's

Last year I posted a query as to whether it was possible to determine if a
grammar is unambiguous. The answer is that it is not, the proof being the
Post Correspondence Problem. But further reflection has yielded the
intuition that if "ambiguity" is equivalent to "can produce more than one
parse tree for some input", then wouldn't it be enough to show that for a
given grammar any input could still only produce one parse tree? Can you
do that, perhaps by induction?


Matt
--

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