The Usability of Ambiguity Detection Methods for Context-Free Grammars | Zendy

H.J.S. Basten | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The Usability of Ambiguity Detection Methods for Context-Free Grammars

Author(s) -

H.J.S. Basten

Publication year - 2009

Publication title -

electronic notes in theoretical computer science

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.242

H-Index - 60

ISSN - 1571-0661

DOI - 10.1016/j.entcs.2009.09.039

Subject(s) - computer science , undecidable problem , ambiguity , context free grammar , rule based machine translation , usability , programming language , generator (circuit theory) , context (archaeology) , theoretical computer science , grammar , algorithm , natural language processing , human–computer interaction , decidability , linguistics , paleontology , power (physics) , physics , philosophy , quantum mechanics , biology

One way of verifying a grammar is the detection of ambiguities. Ambiguities are not always unwanted, but they can only be controlled if their sources are known. Unfortunately, the ambiguity problem for context-free grammars is undecidable in the general case. Various ambiguity detection methods (ADMs) exist, but they can never be perfect. In this paper we explore three ADMs to test whether they still can be of any practical value: the derivation generator AMBER, the LR(k) test and the Noncanonical Unambiguity test. We benchmarked their implementations on a collection of ambiguous and unambiguous grammars of different sizes and compared their practical usability. We measured the accuracy, termination and performance of the methods, and analyzed how their accuracy could be traded for performance

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research