Faster ambiguity detection by grammar filtering

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

    Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

    12 Citaten (Scopus)


    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.
    Originele taal-2Engels
    TitelProceedings of the Tenth Workshop on Language Descriptions, Tools and Applications (LDTA'10), March 28-29, 2010, Paphos, Cyprus
    RedacteurenC. Braband, P.-E. Morfeau
    Plaats van productieNew York NY
    UitgeverijAssociation for Computing Machinery, Inc
    ISBN van geprinte versie978-1-4503-0063-6
    StatusGepubliceerd - 2010
    Evenement10th Workshop on Language Descriptions, Tools and Applications (LDTA 2010) - Paphos, Griekenland
    Duur: 27 mrt. 201028 mrt. 2010
    Congresnummer: 10


    Workshop10th Workshop on Language Descriptions, Tools and Applications (LDTA 2010)
    Verkorte titelLDTA 2010
    Ander10th Workshop on Language Descriptions, Tools and Applications
    Internet adres


    Duik in de onderzoeksthema's van 'Faster ambiguity detection by grammar filtering'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit