Re: Automatic Transformation of CFG to LL/LR

bart@cs.uoregon.edu (Barton Christopher Massey) writes
>I'll check the ref, but note that detecting, much less eliminating, CFG
>ambiguity is undecidable, which is sufficient to show that converting an
>arbitrary CFG to a necessarily unambiguous LL(1) or LR(1) grammar is
>undecidable. My conjectures thus were limited to unambiguous CFGs -- it


Could you elaborate on how the ambiguity problem can be reduced to that of
transforming a CFG to LL grammar. I certainly see one of the directions,
i.e. if transformation is successful, then the original grammar is not
ambiguous. How does the converse follow, i.e. if there is does not exist a
transformation, how can you conclude that CFG is ambiguous?


On a separate note, your conjecture when limited to unambiguous CFGs to LL
seem to be false, given the following exercise from the book on theory of
parsing by Aho and Ullman (exercise 5.2.13, pp. 397):


"Show that it is undecidable whether an LR(k) grammar is an LL grammar."


Ramki Thurimella
--

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