2026-07-26T00:33:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3778 2024-03-06T10:29:10Z ddc:004 open_access

Search-Based Ambiguity Detection in Context-Free Grammars Vasudevan, Naveneetha Tratt, Laurence Ambiguity Parsing Context Free Grammars (CFGs) can be ambiguous, allowing inputs to be parsed in more than one way, something that is undesirable for uses such as programming languages. However, statically detecting ambiguity is undecidable. Though approximation techniques have had some success in uncovering ambiguity, they can struggle when the ambiguous subset of the grammar is large. In this paper, we describe a simple search-based technique which appears to have a better success rate in such cases. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Naveneetha Vasudevan and Laurence Tratt 2012 Is Part Of OASIcs, Volume 28, 2012 Imperial College Computing Student Workshop InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ICCSW.2012.142 urn:nbn:de:0030-drops-37788 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICCSW.2012.142 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode