Exploring the Problem of Ambiguity in Context-free Grammars

Abstract

The general problem of ambiguity detection is unsolvable. Some context-free languages are inherently ambiguous. There is no algorithm that can detect the ambiguity of context-free grammars (CFG) in general since it is a provably unsolvable problem. The objective of this thesis is to study the notion of ambiguity in context-free grammars and grammars in general. The areas of this study include ambiguity in CFGs, ambiguity in other classes of grammars, and a number of algorithms for finding ambiguous strings and grammars. Also, an algorithm that finds ambiguous strings in a subset of context-free grammars is presented. This algorithm is based on the observation that ambiguity in strings cannot be induced by mere repetitions of applications of productions unless ambiguous strings can be generated without exhibiting the self-embedding property.Ambiguity in different classes of formal languages and in some programming languages was studied. The problem of ambiguity detection in context-free grammars was studied in depth. An algorithm was designed and implemented to detect ambiguous strings generated by a subset of context-free grammars. The algorithm works successfully for all grammars in the test suite of grammars which are known to be either ambiguous or unambiguous. It was observed that checking the sentential forms for ambiguity instead of checking only the sentences, and applying the productions of the proper grammar instead of the CNF grammar to derive the sentential forms are promising techniques to keep the execution time low. It was also observed that the time in which ambiguity was detected in the grammars in the test suite was largely independent of factors such as the productivity of a grammar (the number of strings that can be generated without exhibiting the self-embedding property), the degree of ambiguity of a string, and the lengths of strings generated.