Ambiguity Detection Using Approximation Techniques

Abstract

One way to verifying a grammar is the detection of ambiguity. Unfortunately, ambiguity problem for context-free grammars is un decidable. Ambiguity in context-free grammars is a recurring problem in language design and parser generation, as well as in applications where grammars are used as models of real-world physical structures. Context-free grammars are widely used but still hindered by ambiguity. It was observe that there is simple linguistic characterization of the grammar ambiguity problem .This problem divided into form of horizontal and vertical ambiguity. We show the conservative approximation for ambiguity problem. 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. In this thesis the available techniques have been compared. A new approach has been proposed. This approach work on Chomsky Normal form(CNF) of the Grammar because Chomsky Normal Form of the Context free Grammar construct a polynomial-time algorithm to decide whether or not a given string is in the language generated by that grammar. A Grammar is a simple structure, and that makes it easy to parse. In an arbitrary CFG, there is no a priori bound on the length of a derivation of an input word. The experimental results demonstrate that proposed approach can effectively detect the ambiguity in Context free Grammar.