{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T03:26:26Z","timestamp":1779333986519,"version":"3.51.4"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2006,7,1]],"date-time":"2006-07-01T00:00:00Z","timestamp":1151712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2006,7]]},"abstract":"<jats:p>\n            The right nulled generalized LR parsing algorithm is a new generalization of LR parsing which provides an elegant correction to, and extension of, Tomita's GLR methods whereby we extend the notion of a\n            <jats:italic>reduction<\/jats:italic>\n            in a shift-reduce parser to include\n            <jats:italic>right nulled<\/jats:italic>\n            items. The result is a parsing technique which runs in linear time on LR(1) grammars and whose performance degrades gracefully to a polynomial bound in the presence of nonLR(1) rules. Compared to other GLR-based techniques, our algorithm is simpler and faster.\n          <\/jats:p>","DOI":"10.1145\/1146809.1146810","type":"journal-article","created":{"date-parts":[[2006,7,25]],"date-time":"2006-07-25T14:14:26Z","timestamp":1153836866000},"page":"577-618","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":39,"title":["Right nulled GLR parsers"],"prefix":"10.1145","volume":"28","author":[{"given":"Elizabeth","family":"Scott","sequence":"first","affiliation":[{"name":"Royal Holloway, University of London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adrian","family":"Johnstone","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2006,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/360933.360969"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/6448"},{"key":"e_1_2_1_3_1","unstructured":"Aho A. V. and Ullman J. D. 1972. The Theory of Parsing Translation and Compiling. Series in Automatic Computation vol. 1---Parsing. Prentice-Hall Upper Saddle River N. J.   Aho A. V. and Ullman J. D. 1972. The Theory of Parsing Translation and Compiling. Series in Automatic Computation vol. 1---Parsing. Prentice-Hall Upper Saddle River N. J."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Compiler Construction, 8th International Conference CC'99","volume":"1575","author":"Aycock J."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.3115\/981623.981641"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.4380251106"},{"key":"e_1_2_1_7_1","volume-title":"eds","author":"Bunt H.","year":"1991"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/362619.362625"},{"key":"e_1_2_1_10_1","unstructured":"Dodd C. and Maslov V. 1995. http:\/\/compilers.iecc.com\/comparch\/article\/95-03-044.  Dodd C. and Maslov V. 1995. http:\/\/compilers.iecc.com\/comparch\/article\/95-03-044."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/362007.362035"},{"key":"e_1_2_1_12_1","unstructured":"Eggert P. 2003. http:\/\/compilers.iecc.com\/comparch\/article\/03-01-005.  Eggert P. 2003. http:\/\/compilers.iecc.com\/comparch\/article\/03-01-005."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-2458(08)60451-9"},{"key":"e_1_2_1_14_1","volume-title":"Parsing Techniques: A Practial Guide. Ellis Horwood","author":"Grune D.","year":"1990"},{"key":"e_1_2_1_15_1","volume-title":"Tech. Rep. MSR-TR-2003-32, Microsoft Research","author":"Hanson D. R.","year":"2003"},{"key":"e_1_2_1_16_1","volume-title":"Introductions to Computational Linguistics","author":"Hays D."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/366062.366083"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 7th International Conference on Compiler Construction (CC'98)","volume":"1383","author":"Johnstone A."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS02)","author":"Johnstone A."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Compiler Construction, 12th International Conference, CC'03, G. Hedin, ed. LNCS","volume":"2622","author":"Johnstone A."},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the Compiler Construction, 13th International Conference, CC'04, E. Duesterwald, ed. LNCS","volume":"2985","author":"Johnstone A."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2773566.2773670"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(65)90426-2"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/646230.681872"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/321466.321477"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the Compiler Construction, 13th Internationl. Conference CC'04, E. Duesterwald, ed. LNCS. Springer","author":"McPeak S."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.3115\/981732.981749"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Nederhof M.-J. and Sarbo J. J. 1996. Increasing the applicability of LR parsing. In Recent Advances in Parsing Technology H.Bunt and M. Tomita eds. Kluwer Academic Amsterdam the Netherlands 35--57.  Nederhof M.-J. and Sarbo J. J. 1996. Increasing the applicability of LR parsing. In Recent Advances in Parsing Technology H.Bunt and M. Tomita eds. Kluwer Academic Amsterdam the Netherlands 35--57.","DOI":"10.1007\/978-94-010-9733-8_3"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.3115\/981863.981895"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Nederhof M.-J. and Satta G. 2004. Tabular parsing. In Formal Languages and Applications Studies in Fuzziness and Soft Computing 148 G. C.Martin-Vide V.Mitrana eds. Springer New York 529--549.  Nederhof M.-J. and Satta G. 2004. Tabular parsing. In Formal Languages and Applications Studies in Fuzziness and Soft Computing 148 G. C.Martin-Vide V.Mitrana eds. Springer New York 529--549.","DOI":"10.1007\/978-3-540-39886-8_28"},{"key":"e_1_2_1_32_1","volume-title":"Kluwer","author":"Nozohoor-Farshi R."},{"key":"e_1_2_1_33_1","volume-title":"Language Translation Using PCCTS and C&plus;&plus;","author":"Parr T. J."},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 1961 International Conference on Machine Translation of Languages and Applied Language Analysis. 593--608","author":"Sakai I.","year":"1962"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-004-0137-z"},{"key":"e_1_2_1_37_1","volume-title":"Tech. Rep. TR-00-12, Royal Holloway","author":"Scott E.","year":"2000"},{"key":"e_1_2_1_38_1","unstructured":"Sheil B. 1976. Observations on context-free parsing. In Statistical Methods in Linguistics. 71--109.  Sheil B. 1976. Observations on context-free parsing. In Statistical Methods in Linguistics. 71--109."},{"key":"e_1_2_1_39_1","volume-title":"The Design and Evolution of C&plus;&plus;","author":"Stroustrup B."},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","volume-title":"Efficient Parsing for Natural Language","author":"Tomita M.","DOI":"10.1007\/978-1-4757-1885-0"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/362991.363001"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80046-8"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/567097.567099"},{"key":"e_1_2_1_45_1","volume-title":"Domain-Specific Program Generation, C. et al, ed. LNCS","author":"Visser E."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)80007-X"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1146809.1146810","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1146809.1146810","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T15:14:25Z","timestamp":1750259665000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1146809.1146810"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7]]},"references-count":42,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,7]]}},"alternative-id":["10.1145\/1146809.1146810"],"URL":"https:\/\/doi.org\/10.1145\/1146809.1146810","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,7]]},"assertion":[{"value":"2006-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}