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

doi:10.1007/978-3-642-36089-3_13

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 proceeding › Conference contribution › Academic › peer-review

7 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 language	English
Title of host publication	Software Language Engineering (5th International Conference, SLE 2012, Dresden, Germany, September 26-28, 2012, Revised Selected Papers)
Editors	K. Czarnecki, G. Hedin
Place of Publication	Berlin
Publisher	Springer
Pages	224-243
ISBN (Print)	978-3-642-36088-6
DOIs	https://doi.org/10.1007/978-3-642-36089-3_13
Publication status	Published - 2013
Event	5th International Conference on Software Language Engineering (SLE 2012) - Dresden, Germany Duration: 26 Sept 2012 → 28 Sept 2012 Conference number: 5 http://www.sleconf.org/2012/

Publication series

Name	Lecture Notes in Computer Science
Volume	7745
ISSN (Print)	0302-9743

Conference

Conference	5th International Conference on Software Language Engineering (SLE 2012)
Abbreviated title	SLE 2012
Country/Territory	Germany
City	Dresden
Period	26/09/12 → 28/09/12
Internet address	http://www.sleconf.org/2012/

Access to Document

10.1007/978-3-642-36089-3_13

Cite this

Afroozeh, A., Bach, J.-C., Brand, van den, M. G. J., Johnstone, A., Manders, M. W., Moreau, P.-E., & Scott, E. (2013). Island grammar-based parsing using GLL and Tom. In K. Czarnecki, & G. Hedin (Eds.), Software Language Engineering (5th International Conference, SLE 2012, Dresden, Germany, September 26-28, 2012, Revised Selected Papers) (pp. 224-243). (Lecture Notes in Computer Science; Vol. 7745). Springer. https://doi.org/10.1007/978-3-642-36089-3_13

@inproceedings{444b899c67e44588b9c5a4d07903d687,

title = "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.",

author = "A. Afroozeh and J.-C. Bach and {Brand, van den}, M.G.J. and A. Johnstone and M.W. Manders and P.-E. Moreau and E. Scott",

year = "2013",

doi = "10.1007/978-3-642-36089-3_13",

language = "English",

isbn = "978-3-642-36088-6",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "224--243",

editor = "K. Czarnecki and G. Hedin",

booktitle = "Software Language Engineering (5th International Conference, SLE 2012, Dresden, Germany, September 26-28, 2012, Revised Selected Papers)",

address = "Germany",

note = "5th International Conference on Software Language Engineering (SLE 2012), SLE 2012 ; Conference date: 26-09-2012 Through 28-09-2012",

url = "http://www.sleconf.org/2012/",

}

Afroozeh, A, Bach, J-C, Brand, van den, MGJ, Johnstone, A, Manders, MW, Moreau, P-E & Scott, E 2013, Island grammar-based parsing using GLL and Tom. in K Czarnecki & G Hedin (eds), Software Language Engineering (5th International Conference, SLE 2012, Dresden, Germany, September 26-28, 2012, Revised Selected Papers). Lecture Notes in Computer Science, vol. 7745, Springer, Berlin, pp. 224-243, 5th International Conference on Software Language Engineering (SLE 2012), Dresden, Germany, 26/09/12. https://doi.org/10.1007/978-3-642-36089-3_13

Island grammar-based parsing using GLL and Tom. / Afroozeh, A.; Bach, J.-C.; Brand, van den, M.G.J. et al.
Software Language Engineering (5th International Conference, SLE 2012, Dresden, Germany, September 26-28, 2012, Revised Selected Papers). ed. / K. Czarnecki; G. Hedin. Berlin: Springer, 2013. p. 224-243 (Lecture Notes in Computer Science; Vol. 7745).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Island grammar-based parsing using GLL and Tom

AU - Afroozeh, A.

AU - Bach, J.-C.

AU - Brand, van den, M.G.J.

AU - Johnstone, A.

AU - Manders, M.W.

AU - Moreau, P.-E.

AU - Scott, E.

N1 - Conference code: 5

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-36089-3_13

DO - 10.1007/978-3-642-36089-3_13

M3 - Conference contribution

SN - 978-3-642-36088-6

T3 - Lecture Notes in Computer Science

SP - 224

EP - 243

BT - Software Language Engineering (5th International Conference, SLE 2012, Dresden, Germany, September 26-28, 2012, Revised Selected Papers)

A2 - Czarnecki, K.

A2 - Hedin, G.

PB - Springer

CY - Berlin

T2 - 5th International Conference on Software Language Engineering (SLE 2012)

Y2 - 26 September 2012 through 28 September 2012

ER -

Afroozeh A, Bach JC, Brand, van den MGJ, Johnstone A, Manders MW, Moreau PE et al. Island grammar-based parsing using GLL and Tom. In Czarnecki K, Hedin G, editors, Software Language Engineering (5th International Conference, SLE 2012, Dresden, Germany, September 26-28, 2012, Revised Selected Papers). Berlin: Springer. 2013. p. 224-243. (Lecture Notes in Computer Science). doi: 10.1007/978-3-642-36089-3_13

Island grammar-based parsing using GLL and Tom

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this