Wed, 3 Feb 1993 21:24:52 GMT

Related articles |
---|

Top-Down Parser Construction Conjectures bart@cs.uoregon.edu (1993-01-18) |

Automatic Transformation of CFG to LL/LR ramki@cs.du.edu (1993-01-29) |

Re: Automatic Transformation of CFG to LL/LR bart@cs.uoregon.edu (1993-02-02) |

Re: Automatic Transformation of CFG to LL/LR ramki@cs.du.edu (1993-02-03) |

Newsgroups: | comp.compilers |

From: | ramki@cs.du.edu (Ramki Thurimella) |

Keywords: | parse, theory |

Organization: | Compilers Central |

References: | 93-01-122 93-02-023 |

Date: | Wed, 3 Feb 1993 21:24:52 GMT |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.