According to my understanding, a grammar is ambiguous if it generate strings which can be interpreted in more than one ways ( that is , more than one parse tree), but when it comes to the language itself , is there any kind of relationship between the language itself and the ambiguous nature of a particular grammar that could generate it. Also , I am having another doubt , Is it possible that there should exist,infinite number of grammars that could generate the strings of a particular language ?
$\begingroup$
$\endgroup$
5
-
$\begingroup$ Nice questions. These questions should have been answered on this site. In particular, we can classify a language according to the ambiguity of the grammars that generate it. Of course, there are infinite many grammars for any given language. For example, "dead" rules can be added arbitrarily. For example, any rule can be replaced by "delaying rules" such as $A\to somethingForIt$ can be replaced by $A\to D$ and $D\to somethingForIt$. $\endgroup$– John L.Jan 19, 2019 at 13:25
-
$\begingroup$ Since there are infinite grammars existing for a language, we cannot rule out the possibility that some of them might turn out to be ambiguous ,right ? $\endgroup$– Mathews GeorgeJan 19, 2019 at 17:05
-
$\begingroup$ Yes, there are infinitely many ambiguous grammars that generates any computable language. For example, replace $S\to something$ with $S\to S_1$ and $S\to S_2$ and $S_1\to something$ and $S_2\to something$. $\endgroup$– John L.Jan 19, 2019 at 17:33
-
$\begingroup$ Since , we can construct an ambiguous grammar for any language, can we conclude that, there is no relationship exists between the grammar being ambiguous and the language itself. $\endgroup$– Mathews GeorgeJan 19, 2019 at 17:53
-
$\begingroup$ A language could be inherently ambiguous. That is the relationship. $\endgroup$– John L.Jan 20, 2019 at 15:52
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
There exist context-free languages which have no unambiguous grammar. Such languages are called "inherently ambiguous".
On the other hand, there is no such thing as a language which does not have an ambiguous grammar; any grammar can be made ambiguous by duplicating some or all of the non-terminals.
The fact that inherently ambiguous languages exist is interesting, but they rarely if ever show up in real-life parsing problems.
