Island grammar-based parsing using GLL and Tom

A. Afroozeh, J.-C. Bach, M.G.J. Brand, van den, A. Johnstone, M.W. Manders, P.-E. Moreau, E. Scott

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

    3 Citations (Scopus)
    2 Downloads (Pure)

    Abstract

    Extending a language by embedding within it another language presents significant parsing challenges, especially if the embedding is recursive. The composite grammar is likely to be nondeterministic as a result of tokens that are valid in both the host and the embedded language. In this paper we examine the challenges of embedding the Tom language into a variety of general-purpose high level languages. Tom provides syntax and semantics for advanced pattern matching and tree rewriting facilities. Embedded Tom constructs are translated into the host language by a preprocessor, the output of which is a composite program written purely in the host language. Tom implementations exist for Java, C, C#, Python and Caml. The current parser is complex and difficult to maintain. In this paper, we describe how Tom can be parsed using island grammars implemented with the Generalised LL (GLL) parsing algorithm. The grammar is, as might be expected, ambiguous. Extracting the correct derivation relies on our disambiguation strategy which is based on pattern matching within the parse forest. We describe different classes of ambiguity and propose patterns for resolving them.
    Original languageEnglish
    Title of host publicationSoftware Language Engineering (5th International Conference, SLE 2012, Dresden, Germany, September 26-28, 2012, Revised Selected Papers)
    EditorsK. Czarnecki, G. Hedin
    Place of PublicationBerlin
    PublisherSpringer
    Pages224-243
    ISBN (Print)978-3-642-36088-6
    DOIs
    Publication statusPublished - 2013
    Event5th International Conference on Software Language Engineering (SLE 2012) - Dresden, Germany
    Duration: 26 Sep 201228 Sep 2012
    Conference number: 5
    http://www.sleconf.org/2012/

    Publication series

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

    Conference

    Conference5th International Conference on Software Language Engineering (SLE 2012)
    Abbreviated titleSLE 2012
    CountryGermany
    CityDresden
    Period26/09/1228/09/12
    Internet address

    Fingerprint

    Dive into the research topics of 'Island grammar-based parsing using GLL and Tom'. Together they form a unique fingerprint.

    Cite this