License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ICCSW.2012.142
URN: urn:nbn:de:0030-drops-37788
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3778/
Vasudevan, Naveneetha ;
Tratt, Laurence
Search-Based Ambiguity Detection in Context-Free Grammars
Abstract
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.
BibTeX - Entry
@InProceedings{vasudevan_et_al:OASIcs:2012:3778,
author = {Naveneetha Vasudevan and Laurence Tratt},
title = {{Search-Based Ambiguity Detection in Context-Free Grammars}},
booktitle = {2012 Imperial College Computing Student Workshop},
pages = {142--148},
series = {OpenAccess Series in Informatics (OASIcs)},
ISBN = {978-3-939897-48-4},
ISSN = {2190-6807},
year = {2012},
volume = {28},
editor = {Andrew V. Jones},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3778},
URN = {urn:nbn:de:0030-drops-37788},
doi = {10.4230/OASIcs.ICCSW.2012.142},
annote = {Keywords: Ambiguity, Parsing}
}
Keywords: |
|
Ambiguity, Parsing |
Collection: |
|
2012 Imperial College Computing Student Workshop |
Issue Date: |
|
2012 |
Date of publication: |
|
09.11.2012 |