{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T12:01:38Z","timestamp":1758628898374,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2023,7,19]],"date-time":"2023-07-19T00:00:00Z","timestamp":1689724800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/I032509\/1"],"award-info":[{"award-number":["EP\/I032509\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"PLanCompS: Programming Language Components and Specifications"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2023,9,30]]},"abstract":"<jats:p>This article introduces two new approaches in the areas of lexical analysis and context-free parsing. We present an extension, MGLL, of generalised parsing which allows multiple input strings to be parsed together efficiently, and we present an enhanced approach to lexical analysis which exploits this multiple parsing capability. The work provides new power to formal language specification and disambiguation, and brings new techniques into the historically well-studied areas of lexical and syntax analysis. It encompasses character-level parsing at one extreme and the classical LEX\/YACC style division at the other, allowing the advantages of both approaches.<\/jats:p>","DOI":"10.1145\/3594734","type":"journal-article","created":{"date-parts":[[2023,5,3]],"date-time":"2023-05-03T12:27:35Z","timestamp":1683116855000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Multiple Input Parsing and Lexical Analysis"],"prefix":"10.1145","volume":"45","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5907-8513","authenticated-orcid":false,"given":"Elizabeth","family":"Scott","sequence":"first","affiliation":[{"name":"Royal Holloway, University of London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9446-9701","authenticated-orcid":false,"given":"Adrian","family":"Johnstone","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6533-5050","authenticated-orcid":false,"given":"Robert","family":"Walsh","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,7,19]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Alfred V. Aho Monica S. Lam Ravi Sethi and Jeffrey D. Ullman.2006. Compilers: Principles Techniques and Tools (2nd ed.). Addison-Wesley."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/6448"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/spe.390"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.3115\/981623.981641"},{"key":"e_1_3_3_6_2","first-page":"10","volume-title":"ECAI 1996: 12th European Conference on Artificial Intelligence","author":"Chanod J.-P.","year":"1996","unstructured":"J.-P. Chanod and P. Tapananeinen. 1996. A non deterministic tokeniser for finite-state parsing. In ECAI 1996: 12th European Conference on Artificial Intelligence, W. Wahlster (Ed.). JohnWiley & Sons, Ltd., 10\u201312."},{"key":"e_1_3_3_7_2","first-page":"72","volume-title":"Extended Finite State Models of Languages","author":"Chanod J.-P.","year":"1999","unstructured":"J.-P. Chanod and P. Tapananeinen. 1999. Finite state based reductionist parsing for French. In Extended Finite State Models of Languages, A. Kornai (Ed.). Cambridge University Press, 72\u201385."},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/362007.362035"},{"key":"e_1_3_3_9_2","doi-asserted-by":"crossref","unstructured":"Bryan Ford. 2004. Parsing expression grammars: A recognition-based syntactic foundation. In Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL\u201904) . ACM New York NY 111\u2013122.","DOI":"10.1145\/964001.964011"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.5555\/560667"},{"key":"e_1_3_3_11_2","volume-title":"The Java Language Specification (Java SE 18 ed.)","author":"Gosling James","year":"2022","unstructured":"James Gosling, Bill Joy, Guy Steele, Gilad Bracha, Alex Bucklkey, Daniel Smith, and Gavin Bierman. 2022. The Java Language Specification (Java SE 18 ed.). Oracle America. https:\/\/docs.oracle.com\/javase\/specs\/jls\/se18\/jls18.pdf."},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","unstructured":"Adrian Johnstone and Elizabeth Scott. 2011. Modelling GLL parser implementations. In Software Language Engineering . Lecture Notes in Computer Science Vol. 6563. Springer 42\u201361.","DOI":"10.1007\/978-3-642-19440-5_4"},{"key":"e_1_3_3_13_2","doi-asserted-by":"crossref","unstructured":"Adrian Johnstone and Elizabeth Scott. 2011. Translator generation using ART. In Software Language Engineering . Lecture Notes in Computer Science Vol. 6563. Springer 306\u2013315.","DOI":"10.1007\/978-3-642-19440-5_20"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2013.09.012"},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","unstructured":"Ali Afroozeh Jean-Christophe Bach Mark van den Brand Adrian Johnstone Maarten Manders Pierre-Etienne Moreau and Elizabeth Scott. 2013. Island grammar-based parsing using GLL and Tom. In Software Language Engineering . Lecture Notes in Computer Science Vol. 7745. Springer 224\u2013243.","DOI":"10.1007\/978-3-642-36089-3_13"},{"key":"e_1_3_3_16_2","first-page":"108","volume-title":"Source Code Analysis and Manipulation","author":"Klint P.","year":"2009","unstructured":"P. Klint, T. van der Storm, and J. Vinju. 2009. Rascal: A domain specific language for source code analysis and manipulation. In Source Code Analysis and Manipulation. IEEE, Los Alamitos, CA, 108\u2013177."},{"key":"e_1_3_3_17_2","unstructured":"M. E. Lesk and E. Schmidt. 1990. Lex\u2014A lexical analyzer generator. In UNIX . Vol. II. W. B. Saunders Philadelphia PA 375\u2013387."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993548"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/1146809.1146810"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/jentcs.2010.08.041"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2009.07.001"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2012.03.005"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2016.04.003"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.scico.2018.06.001"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357766.3359532"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-007-0054-z"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.5555\/537456"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.5555\/532747"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/567097.567099"},{"key":"e_1_3_3_30_2","volume-title":"Scannerless Generalised-LR Parsing","author":"Visser Eelco","year":"1997","unstructured":"Eelco Visser. 1997. Scannerless Generalised-LR Parsing. Technical Report P9707. University of Amsterdam."},{"key":"e_1_3_3_31_2","volume-title":"Syntax Definition for Language Prototyping","author":"Visser Eelco","year":"1997","unstructured":"Eelco Visser. 1997. Syntax Definition for Language Prototyping. Ph.D. Dissertation. University of Amsterdam."},{"key":"e_1_3_3_32_2","doi-asserted-by":"crossref","unstructured":"Eelco Visser. 2004. Program transformation with Stratego\/XT: Rules strategies tools and systems in StrategoXT-0.9. In Domain-Specific Program Generation . Lecture Notes in Computer Science Vol. 3016. Springer 216\u2013238.","DOI":"10.1007\/978-3-540-25935-0_13"},{"key":"e_1_3_3_33_2","unstructured":"R. M. Walsh. 2015. Adapting Compiler Front Ends for Generalised Parsing . Ph.D. Thesis. Royal Holloway University of London."}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3594734","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3594734","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:51Z","timestamp":1750178271000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3594734"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,19]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,9,30]]}},"alternative-id":["10.1145\/3594734"],"URL":"https:\/\/doi.org\/10.1145\/3594734","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[2023,7,19]]},"assertion":[{"value":"2022-01-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-07-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}