{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T03:26:25Z","timestamp":1779333985986,"version":"3.51.4"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2007,8,4]],"date-time":"2007-08-04T00:00:00Z","timestamp":1186185600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2007,9,20]]},"DOI":"10.1007\/s00236-007-0054-z","type":"journal-article","created":{"date-parts":[[2007,8,3]],"date-time":"2007-08-03T11:23:20Z","timestamp":1186140200000},"page":"427-461","source":"Crossref","is-referenced-by-count":32,"title":["BRNGLR: a cubic Tomita-style GLR parsing algorithm"],"prefix":"10.1007","volume":"44","author":[{"given":"Elizabeth","family":"Scott","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adrian","family":"Johnstone","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rob","family":"Economopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,8,4]]},"reference":[{"key":"54_CR1","doi-asserted-by":"crossref","unstructured":"Aycock, J., Horspool, N.: Faster generalised LR parsing. In: Compiler Construction, 8th International Conference, CC\u201999, vol. 1575 of Lecture Notes in Computer Science, pp. 32\u201346. Springer, Heidelberg (1999)","DOI":"10.1007\/978-3-540-49051-7_3"},{"issue":"8","key":"54_CR2","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1007\/PL00013319","volume":"37","author":"J. Aycock","year":"2001","unstructured":"Aycock J., Nigel Horspool R., Janousek J., Melichar B. (2001). Even faster generalized LR parsing. Acta Informatica 37(8): 633\u2013651","journal-title":"Acta Informatica"},{"key":"54_CR3","volume-title":"Compilers: principles, techniques and tools","author":"A.V. Aho","year":"1986","unstructured":"Aho A.V., Sethi R., Ullman J.D. (1986). Compilers: principles, techniques and tools. Addison-Wesley, Reading"},{"issue":"11","key":"54_CR4","doi-asserted-by":"crossref","first-page":"1263","DOI":"10.1002\/spe.4380251106","volume":"25","author":"P.T. Breuer","year":"1995","unstructured":"Breuer P.T., Bowen J.P. (1995). A PREttier Compiler-Compiler: Generating higher-order parsers in C. Softw. Pract. Exp. 25(11): 1263\u20131297","journal-title":"Softw. Pract. Exp."},{"key":"54_CR5","doi-asserted-by":"crossref","unstructured":"Billot, S., Lang, B.: The structure of shared forests in ambiguous parsing. In: Proceedings of the 27th conference on Association for Computational Linguistics, pp. 143\u2013151. Association for Computational Linguistics (1989)","DOI":"10.3115\/981623.981641"},{"key":"54_CR6","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1006\/jcom.1997.0438","volume":"13","author":"D. Coppersmith","year":"1997","unstructured":"Coppersmith D. (1997). Rectangular matrix multiplication revisited. J. Complex. 13: 42\u201349","journal-title":"J. Complex."},{"key":"54_CR7","unstructured":"Dodd, C., Maslov, V.: http:\/\/www.siber.com\/btyacc. June (2002)"},{"key":"54_CR8","unstructured":"Donnelly, C., Stallman, R.: Bison, the YACC compatible parser generator. Version 2.1 manual., September (2005)"},{"issue":"2","key":"54_CR9","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1145\/362007.362035","volume":"13","author":"J. Earley","year":"1970","unstructured":"Earley J. (1970). An efficient context-free parsing algorithm. Commun. ACM 13(2): 94\u2013102","journal-title":"Commun. ACM"},{"key":"54_CR10","unstructured":"Eggert, P.: http:\/\/compilers.iecc.com\/comparch\/article\/03-01-042 (2003)"},{"key":"54_CR11","unstructured":"JAVACC home page http:\/\/www.metamata.com\/JavaCC, 2000."},{"key":"54_CR12","doi-asserted-by":"crossref","unstructured":"Johnson, M.: The computational complexity of GLR parsing. In: Masaru, T. (ed.) Generalized LR parsing, pp. 35\u201342. Kluwer, The Netherlands (1991)","DOI":"10.1007\/978-1-4615-4034-2_3"},{"key":"54_CR13","unstructured":"Johnstone, A.: bool\u2014a boolean function minimiser. Technical Report CSD\u2013TR\u201393\u201325, Computer Science Department, Royal Holloway, University of London, London (1993)"},{"key":"54_CR14","doi-asserted-by":"crossref","unstructured":"Johnstone, A., Scott, E.: rdp\u2014an iterator based recursive descent parser generator with tree promotion operators. SIGPLAN notices, 33(9) (1998)","DOI":"10.1145\/290229.290240"},{"key":"54_CR15","doi-asserted-by":"crossref","unstructured":"Johnstone, A., Scott, E.: Generalised regular parsers. In: Gorel, H. (ed.) Compiler Construction, 12th International Conference CC\u201903, vol. 2622 of Lecture Notes in Computer Science, pp. 232\u2013246. Springer, Berlin (2003)","DOI":"10.1007\/3-540-36579-6_17"},{"key":"54_CR16","unstructured":"Johnstone, A., Scott, E.: RHUL compiler group home page. http:\/\/www.cs.rhul.ac.uk\/research\/languages\/ (2006)"},{"key":"54_CR17","doi-asserted-by":"crossref","unstructured":"Johnstone, A., Scott, E., Economopoulos, G.: Generalised parsing: some costs. In: Evelyn, D. (ed.) Compiler Construction, 13th International Conference CC\u201904, vol. 2985 of Lecture Notes in Computer Science, pp. 89\u2013103. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-24723-4_7"},{"key":"54_CR18","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.entcs.2004.06.008","volume":"110","author":"A. Johnstone","year":"2004","unstructured":"Johnstone A., Scott E., Economopoulos G. (2004). The grammar tool box: a case study comparing GLR parsing algorithms. Electron. Notes Theoret. Comput. Sci. 110: 97\u2013133","journal-title":"Electron. Notes Theoret. Comput. Sci."},{"key":"54_CR19","doi-asserted-by":"crossref","unstructured":"Johnstone, A., Scott, E., Economopoulos, G.: The GTB and PAT tools. In: Gorel, H., Eric Van, W. (eds.) Proceedings of the 4th Workshop on Language Descriptions, Tools and Applications LDTA2004. INRIA (2004)","DOI":"10.1016\/j.entcs.2004.06.003"},{"key":"54_CR20","doi-asserted-by":"crossref","unstructured":"Kipps, J.R.: GLR parsing in time O(n 3). In: Masaru, T. (ed.) Generalized LR parsing, pp. 43\u201359. Kluwer, The Netherlands (1991)","DOI":"10.1007\/978-1-4615-4034-2_4"},{"key":"54_CR21","unstructured":"Kernighan, B.W., Ritchie, D.M.: The C Programming Language, second edition. Prentice-Hall, Englewood Cliffs (1988)"},{"key":"54_CR22","doi-asserted-by":"crossref","unstructured":"Lang, B.: Deterministic techniques for efficient non-deterministic parsers. In: Automata, Lanugages and Programming: 2nd Colloquium, vol. 14 of Lecture Notes in Computer Science, pp. 255\u2013269. Springer, Heidelberg (1974)","DOI":"10.1007\/978-3-662-21545-6_18"},{"key":"54_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/505241.505242","volume":"49","author":"L. Lee","year":"2002","unstructured":"Lee L. (2002). Fast context-free grammar parsing requires fast boolean matrix multiplication. J. ACM 49: 1\u201315","journal-title":"J. ACM"},{"issue":"15","key":"54_CR24","doi-asserted-by":"crossref","first-page":"1395","DOI":"10.1002\/spe.423","volume":"31","author":"R. L\u00e4mmel","year":"2001","unstructured":"L\u00e4mmel R., Verhoef C. (2001). Semi-automatic Grammar Recovery. Softw. Pract. Exp. 31(15): 1395\u20131438","journal-title":"Softw. Pract. Exp."},{"key":"54_CR25","doi-asserted-by":"crossref","unstructured":"McPeak, S., Necula, G.: Elkhound: a fast, practical GLR parser generator. In: Evelyn, D. (ed.) Compiler Construction, 13th International Conference CC\u201904, Lecture Notes in Computer Science. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-24723-4_6"},{"key":"54_CR26","doi-asserted-by":"crossref","unstructured":"Nozohoor-Farshi, R.: GLR parsing for \u03b5-grammars. In: Masaru, T. (ed.) Generalized LR Parsing, pp. 60\u201375. Kluwer, The Netherlands (1991)","DOI":"10.1007\/978-1-4615-4034-2_5"},{"key":"54_CR27","unstructured":"Parr, T.: ANTLR home page. http:\/\/www.antlr.org, Last visited: Dec (2004)"},{"key":"54_CR28","unstructured":"Rekers, J.G.: Parser generation for interactive environments. PhD thesis, Universty of Amsterdam (1992)"},{"key":"54_CR29","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1007\/s00236-004-0137-z","volume":"40","author":"E. Scott","year":"2004","unstructured":"Scott E., Johnstone A. (2004). Reducing non-determinism in right nulled GLR parsers. Acta Informatica 40: 459\u2013489","journal-title":"Acta Informatica"},{"key":"54_CR30","doi-asserted-by":"crossref","unstructured":"Scott, E., Johnstone, A.: Right nulled GLR parsers. ACM Trans. Program. Lang. Syst. pp. 1\u201343 (2006)","DOI":"10.1145\/1146809.1146810"},{"key":"54_CR31","unstructured":"Scott, E.A., Johnstone, A.I.C., Economopoulos, G.R.: BRN-table based GLR parsers. Technical Report TR-03-06, Computer Science Department, Royal Holloway, University of London, London (2003)"},{"key":"54_CR32","unstructured":"Scott, E., Johnstone, A., Hussain, S.S.: Tomita-style generalised LR parsers. Updated Version. Technical Report TR-00-12, Computer Science Department, Royal Holloway, University of London, London, December (2000)"},{"key":"54_CR33","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(75)80046-8","volume":"10","author":"L. Valiant","year":"1975","unstructured":"Valiant L. (1975). General context-free recognition in less than cubic time. J. Comput. Syst. Sci. 10: 308\u2013315","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"54_CR34","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1145\/567097.567099","volume":"24","author":"M.G.J. van den Brand","year":"2002","unstructured":"van den Brand M.G.J., Heering J., Klint P., Olivier P.A. (2002). Compiling language definitions: the ASF+SDF compiler. ACM Trans. Program. Lang. Syst. 24(4): 334\u2013368","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"54_CR35","unstructured":"Visser, E.: Syntax definition for language prototyping. PhD thesis, Universty of Amsterdam (1997)"},{"issue":"2","key":"54_CR36","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/S0019-9958(67)80007-X","volume":"10","author":"D.H. Younger","year":"1967","unstructured":"Younger D.H. (1967). Recognition of context-free languages in time n 3. Inform. Control 10(2): 189\u2013208","journal-title":"Inform. Control"}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-007-0054-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-007-0054-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-007-0054-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T09:41:54Z","timestamp":1558690914000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-007-0054-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8,4]]},"references-count":36,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2007,9,20]]}},"alternative-id":["54"],"URL":"https:\/\/doi.org\/10.1007\/s00236-007-0054-z","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8,4]]}}}