Ambiguity detection : scaling to scannerless

H.J.S. Basten, P. Klint, J.J. Vinju

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Citations (Scopus)

Abstract

Static ambiguity detection would be an important aspect of language workbenches for textual software languages. However, the challenge is that automatic ambiguity detection in context-free grammars is undecidable in general. Sophisticated approximations and optimizations do exist, but these do not scale to grammars for so-called "scannerless parsers", as of yet. We extend previous work on ambiguity detection for context-free grammars to cover disambiguation techniques that are typical for scannerless parsing, such as longest match and reserved keywords. This paper contributes a new algorithm for ambiguity detection in character-level grammars, a prototype implementation of this algorithm and validation on several real grammars. The total run-time of ambiguity detection for character-level grammars for languages such as C and Java is significantly reduced, without loss of precision. The result is that efficient ambiguity detection in realistic grammars is possible and may therefore become a tool in language workbenches.
Original languageEnglish
Title of host publicationProceedings of the 4th International Conference on Software Language Engineering, SLE 2011, July 3-4, 2011, Braga, Portugal, Revised Selected Papers
EditorsA. Sloane, U. Assmann
Place of PublicationBerlin
PublisherSpringer
Pages303-323
ISBN (Print)978-3-642-28829-6
DOIs
Publication statusPublished - 2012
Externally publishedYes
Event4th International Conference on Software Language Engineering (SLE 2011) - Braga, Portugal
Duration: 3 Jul 20114 Jul 2011
Conference number: 4
http://www.sleconf.org/2011/

Publication series

NameLecture Notes in Computer Science
Volume6940
ISSN (Print)0302-9743

Conference

Conference4th International Conference on Software Language Engineering (SLE 2011)
Abbreviated titleSLE 2011
CountryPortugal
CityBraga
Period3/07/114/07/11
Internet address

Fingerprint

Dive into the research topics of 'Ambiguity detection : scaling to scannerless'. Together they form a unique fingerprint.

Cite this