Faster ambiguity detection by grammar filtering

H.J.S. Basten, J.J. Vinju

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

    11 Citations (Scopus)

    Abstract

    Real programming languages are often defined using ambiguous context-free grammars. Some ambiguity is intentional while other ambiguity is accidental. A good grammar development environment should therefore contain a static ambiguity checker to help the grammar engineer. Ambiguity of context-free grammars is an undecidable property. Nevertheless, various imperfect ambiguity checkers exist. Exhaustive methods are accurate, but suffer from non-termination. Termination is guaranteed by approximative methods, at the expense of accuracy. In this paper we combine an approximative method with an exhaustive method. We present an extension to the Noncanonical Unambiguity Test that identifies production rules that do not contribute to the ambiguity of a grammar and show how this information can be used to significantly reduce the search space of exhaustive methods. Our experimental evaluation on a number of real world grammars shows orders of magnitude gains in efficiency in some cases and negligible losses of efficiency in others.
    Original languageEnglish
    Title of host publicationProceedings of the Tenth Workshop on Language Descriptions, Tools and Applications (LDTA'10), March 28-29, 2010, Paphos, Cyprus
    EditorsC. Braband, P.-E. Morfeau
    Place of PublicationNew York NY
    PublisherAssociation for Computing Machinery, Inc
    Pages5/1-9
    ISBN (Print)978-1-4503-0063-6
    DOIs
    Publication statusPublished - 2010
    Event10th Workshop on Language Descriptions, Tools and Applications (LDTA 2010) - Paphos, Greece
    Duration: 27 Mar 201028 Mar 2010
    Conference number: 10
    http://ldta.info/2010/

    Workshop

    Workshop10th Workshop on Language Descriptions, Tools and Applications (LDTA 2010)
    Abbreviated titleLDTA 2010
    CountryGreece
    CityPaphos
    Period27/03/1028/03/10
    OtherWorkshop held as a satellite event of the 13th European Joint Conferences on Theory and Practice of Software (ETAPS 2010)
    Internet address

    Fingerprint Dive into the research topics of 'Faster ambiguity detection by grammar filtering'. Together they form a unique fingerprint.

    Cite this