I'm in an undergraduate class where we're studying formal grammars right now. I asked my teacher if there was any known set of rules for creating context free grammars thatWas guaranteed to produce an unambiguous grammar. Allows for the creation of any possible unambiguous grammar.I am well aware that determining whether a grammar is ambiguous is undecidable. I'm not sure if the above stated idea is reducible to that, but after fiddling around with it a bit, I couldn't think of a method for making such a reduction. That said I'm really no expert at reductions or grammars. I tried googling for a while, but I only found pages about undecidability. Does anyone know?
Method for Creating Any Unambiguous Grammar?
context free;formal grammars;ambiguity
No, and there is indeed a reduction to the undecidability of ambiguity.First, note that ambiguity is (for context-free grammars) semi-decidable: just keep generating words by different left-derivations and say ambiguous! when you first find a word you've seen before.Now, the method you are proposing allows to semi-decide unambiguity. You effectively look for a computable enumeration of all unambiguous grammars. You just generate grammars until you find your given grammar and answer unambiguous!.Since semi-decidability and co-semi-decidability imply decidability, this contradicts what you already know. Hence, there can be no set of rules as you propose.