Island Grammar-based Parsing using GLL and Tom

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.
Type de document :
Communication dans un congrès
SLE 2012 - 5th International Conference on Software Language Engineering, Sep 2012, Dresden, Germany. Springer, Lecture Notes in Computer Science, pp.224-243, 2012, SLE 2012: Software Language Engineering. 〈10.1007/978-3-642-36089-3_13〉
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00722878
Contributeur : Jean-Christophe Bach <>
Soumis le : mardi 11 septembre 2012 - 08:45:40
Dernière modification le : mardi 12 juin 2018 - 09:54:02
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 11:58:55

Fichier

camera_ready_version.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Ali Afroozeh, Jean-Christophe Bach, Mark Van den Brand, Adrian Johnstone, Maarten Manders, et al.. Island Grammar-based Parsing using GLL and Tom. SLE 2012 - 5th International Conference on Software Language Engineering, Sep 2012, Dresden, Germany. Springer, Lecture Notes in Computer Science, pp.224-243, 2012, SLE 2012: Software Language Engineering. 〈10.1007/978-3-642-36089-3_13〉. 〈hal-00722878v2〉

Partager

Métriques

Consultations de la notice

470

Téléchargements de fichiers

755