Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Vasudevan, Naveneetha; Tratt, Laurence License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-37788


Search-Based Ambiguity Detection in Context-Free Grammars



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

  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 =		{},
  URN =		{urn:nbn:de:0030-drops-37788},
  doi =		{},
  annote =	{Keywords: Ambiguity, Parsing}

Keywords: Ambiguity, Parsing
Seminar: 2012 Imperial College Computing Student Workshop
Related Scholarly Article:
Issue date: 2012
Date of publication: 2012

DROPS-Home | Fulltext Search | Imprint Published by LZI