Search-Based Ambiguity Detection in Context-Free Grammars

Authors Naveneetha Vasudevan, Laurence Tratt



PDF
Thumbnail PDF

File

OASIcs.ICCSW.2012.142.pdf
  • Filesize: 0.53 MB
  • 7 pages

Document Identifiers

Author Details

Naveneetha Vasudevan
Laurence Tratt

Cite AsGet BibTex

Naveneetha Vasudevan and Laurence Tratt. Search-Based Ambiguity Detection in Context-Free Grammars. In 2012 Imperial College Computing Student Workshop. Open Access Series in Informatics (OASIcs), Volume 28, pp. 142-148, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/OASIcs.ICCSW.2012.142

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.
Keywords
  • Ambiguity
  • Parsing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail