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/
Go to the corresponding OASIcs Volume Portal

Vasudevan, Naveneetha ; Tratt, Laurence

Search-Based Ambiguity Detection in Context-Free Grammars

pdf-format:
23.pdf (0.5 MB)

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI