{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,5]],"date-time":"2026-04-05T00:35:39Z","timestamp":1775349339267,"version":"3.50.1"},"reference-count":41,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2016,8,27]],"date-time":"2016-08-27T00:00:00Z","timestamp":1472256000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>LR parsing is a popular parsing strategy for variants of Context-Free Grammar (CFG). It has also been used for mildly context-sensitive formalisms, such as Tree-Adjoining Grammar. In this paper, we present the first LR-style parsing algorithm for Linear Context-Free Rewriting Systems (LCFRS), a mildly context-sensitive extension of CFG which has received considerable attention in the last years in the context of natural language processing.<\/jats:p>","DOI":"10.3390\/a9030058","type":"journal-article","created":{"date-parts":[[2016,8,29]],"date-time":"2016-08-29T10:18:38Z","timestamp":1472465918000},"page":"58","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["LR Parsing for LCFRS"],"prefix":"10.3390","volume":"9","author":[{"given":"Laura","family":"Kallmeyer","sequence":"first","affiliation":[{"name":"Department for Computational Linguistics, Institute for Language and Information, Heinrich-Heine Universit\u00e4t D\u00fcsseldorf, Universit\u00e4tsstr. 1, 40225 D\u00fcsseldorf, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wolfgang","family":"Maier","sequence":"additional","affiliation":[{"name":"Department for Computational Linguistics, Institute for Language and Information, Heinrich-Heine Universit\u00e4t D\u00fcsseldorf, Universit\u00e4tsstr. 1, 40225 D\u00fcsseldorf, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2016,8,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Vijay-Shanker, K., Weir, D., and Joshi, A.K. (1987, January 6\u20139). Characterising structural descriptions used by various formalisms. Proceedings of the 25th Annual Meeting of the Association for Computational Linguistics, Stanford, CA, USA.","DOI":"10.3115\/981175.981190"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Dowty, D., Karttunen, L., and Zwicky, A. (1985). Natural Language Processing: Theoretical, Computational and Psychological Perspectives, Cambridge University Press.","DOI":"10.1017\/CBO9780511597855"},{"key":"ref_3","unstructured":"Brants, S., Dipper, S., Hansen, S., Lezius, W., and Smith, G. (2002, January 13\u201314). The TIGER treebank. Proceedings of the 1st Workshop on Treebanks and Linguistic Theories, Sofia, Bulgaria."},{"key":"ref_4","unstructured":"Maier, W., and Lichte, T. (2009, January 25\u201326). Characterizing discontinuity in constituent treebanks. Proceedings of the 14th International Conference, Bordeaux, France."},{"key":"ref_5","first-page":"313","article-title":"Building a large annotated corpus of english: The penn treebank","volume":"19","author":"Marcus","year":"1993","journal-title":"Comput. Linguist."},{"key":"ref_6","unstructured":"Evang, K., and Kallmeyer, L. (2011, January 5\u20137). PLCFRS parsing of english discontinuous constituents. Proceedings of the 12th International Conference on Parsing Technologies (IWPT 2011), Dublin, Ireland."},{"key":"ref_7","unstructured":"Haider, H., and Rosengren, I. (1998). Scrambling, Sprache und Pragmatik."},{"key":"ref_8","first-page":"1","article-title":"Dependency parsing","volume":"1","author":"McDonald","year":"2009","journal-title":"Synth. Lect. Hum.Lang. Technol."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1162\/COLI_a_00125","article-title":"Mildly non-projective dependency grammar","volume":"39","author":"Kuhlmann","year":"2013","journal-title":"Comput. Linguist."},{"key":"ref_10","unstructured":"Skut, W., Krenn, B., Brants, T., and Uszkoreit, H. (April, January 31). An annotation scheme for free word order languages. Proceedings of the 5th Applied Natural Language Processing Conference."},{"key":"ref_11","unstructured":"Ranta, A. (2011). Grammatical Framework: Programming with Multilingual Grammars, CSLI Publications."},{"key":"ref_12","unstructured":"Ljungl\u00f6f, P. (2004). Expressivity and Complexity of the Grammatical Framework. [Ph.D. Thesis, G\u00f6teborg University]."},{"key":"ref_13","first-page":"377","article-title":"TuLiPA-Parsing extensions of TAG with range concatenation grammars","volume":"58","author":"Kallmeyer","year":"2010","journal-title":"Bull. Pol. Acad. Sci."},{"key":"ref_14","unstructured":"Kallmeyer, L., and Parmentier, Y. (2008, January 13\u201319). On the relation between multicomponent tree adjoining grammars with tree tuples (TT-MCTAG) and range concatenation grammars (RCG). Proceedings of the Second International Conference on Language and Automata Theory and Applications (LATA 2008), Tarragona, Spain."},{"key":"ref_15","unstructured":"Dada, A., and Ranta, A. (2007). Perspectives on Arabic Linguistics: Papers from the Annual Symposium on Arabic Linguistics, John Benjamins Publishing."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Botha, J.A., and Blunsom, P. (2013, January 18\u201321). Adaptor grammars for learning non-concatenative morphology. Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, Washington, DC, USA.","DOI":"10.18653\/v1\/D13-1034"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Melamed, I.D., Satta, G., and Wellington, B. (2004, January 21\u201326). Generalized multitext grammars. Proceedings of the 42nd Meeting of the Association for Computational Linguistics (ACL\u201904), Barcelona, Spain.","DOI":"10.3115\/1218955.1219039"},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Kaeshammer, M. (2015, January 17\u201318). Hierarchical machine translation with discontinuous phrases. Proceedings of the Tenth Workshop on Statistical Machine Translation, Lisbon, Portugal.","DOI":"10.18653\/v1\/W15-3028"},{"key":"ref_19","unstructured":"Kaeshammer, M. (2013, January 13). Synchronous linear context-free rewriting systems for machine translation. Proceedings of the Seventh Workshop on Syntax, Semantics and Structure in Statistical Translation, Atlanta, GA, USA."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0304-3975(91)90374-B","article-title":"On multiple context-free grammars","volume":"88","author":"Seki","year":"1991","journal-title":"Theor. Comput. Sci."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Burden, H., and Ljungl\u00f6f, P. (2005, January 9\u201310). Parsing linear context-free rewriting systems. Proceedings of the Ninth International Workshop on Parsing Technology, Vancouver, BC, Canada.","DOI":"10.3115\/1654494.1654496"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Kallmeyer, L., and Maier, W. (2009, January 7\u20139). An incremental earley parser for simple range concatenation grammar. Proceedings of the 11th International Conference on Parsing Technologies (IWPT\u201909), Paris, France.","DOI":"10.3115\/1697236.1697247"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Villemonte de la Clergerie, E. (2002, January 26\u201330). Parsing mildly context-sensitive languages with thread automata. Proceedings of the COLING 2002: The 19th International Conference on Computational Linguistics, Taipei, Taiwan.","DOI":"10.3115\/1072228.1072256"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1162\/COLI_a_00136","article-title":"Data-driven parsing using probabilistic linear context-free rewriting systems","volume":"39","author":"Kallmeyer","year":"2013","journal-title":"Comput. Linguist."},{"key":"ref_25","unstructured":"Van Cranenburgh, A. (2012, January 23\u201327). Efficient parsing with linear context-free rewriting systems. Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, Avignon, France."},{"key":"ref_26","doi-asserted-by":"crossref","unstructured":"Angelov, K., and Ljungl\u00f6f, P. (2014, January 26\u201330). Fast statistical parsing with parallel multiple context-free grammars. Proceedings of the 14th Conference of the European Chapter of the Association for Computational Linguistics, Gothenburg, Sweden.","DOI":"10.3115\/v1\/E14-1039"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1016\/S0019-9958(65)90426-2","article-title":"On the translation of languages from left to right","volume":"8","author":"Knuth","year":"1965","journal-title":"Inf. Control"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Tomita, M. (1984, January 2\u20136). LR parsers for natural languages. Proceedings of the COLING 1984: The 10th International Conference on Computational Linguistics, Stanford, CA, USA.","DOI":"10.3115\/980431.980564"},{"key":"ref_29","first-page":"31","article-title":"An efficient augmented context-free parsing algorithm","volume":"13","author":"Tomita","year":"1987","journal-title":"Comput. Linguist."},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Nederhof, M.J. (1998, January 10\u201314). An alternative LR algorithm for TAGs. Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics and 17th International Conference on Computational Linguistics, Montreal, QC, Canada.","DOI":"10.3115\/980691.980725"},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Prolo, C.A. (2003). LR Parsing for Tree Adjoining Grammars and Its Application to Corpus-Based Natural Language Parsing. [Ph.D. Thesis, Department of Computer and Information Science, University of Pennsylvania].","DOI":"10.3115\/1118693.1118707"},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Aizikowitz, T., and Kaminski, M. (2011, January 14\u201318). LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata. Proceedings of the 6th International Computer Science Symposium on Computer Science, Theory and Applications, St. Petersburg, Russia.","DOI":"10.1007\/978-3-642-20712-9_27"},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1142\/S0129054106004029","article-title":"Generalized LR parsing algorithm for boolean grammars","volume":"17","author":"Okhotin","year":"2006","journal-title":"Int. J. Found. Comput. Sci."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Barash, M., and Okhotin, A. (2016). Generalized LR parsing algorithm for grammars with one-sided contexts. Theory Comput. Syst.","DOI":"10.1007\/s00224-016-9683-3"},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Kallmeyer, L., and Maier, W. (June, January 31). LR parsing for LCFRS. Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Denver, CO, USA.","DOI":"10.3115\/v1\/N15-1134"},{"key":"ref_36","unstructured":"Boullier, P. (1998). Proposal for a Natural Language Processing Syntactic Backbone, INRIA-Rocquencourt. Research Report 3342."},{"key":"ref_37","unstructured":"Weir, D. (1988). Characterizing Mildly Context-Sensitive Grammar Formalisms. [Ph.D. Thesis, University of Pennsylviania]."},{"key":"ref_38","doi-asserted-by":"crossref","unstructured":"Kracht, M. (2003). The Mathematics of Language, Mouton de Gruyter.","DOI":"10.1515\/9783110895667"},{"key":"ref_39","doi-asserted-by":"crossref","unstructured":"Kallmeyer, L. (2010). Parsing beyond Context-Free Grammar, Springer.","DOI":"10.1007\/978-3-642-14846-0"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Grune, D., and Jacobs, C. (2008). Parsing Techniques. A Practical Guide, Springer. [2nd ed.]. Monographs in Computer Science.","DOI":"10.1007\/978-0-387-68954-8"},{"key":"ref_41","unstructured":"Nederhof, M.J. (1997, January 25\u201328). Solving the correct-prefix property for TAGs. Proceedings of the Fifth Meeting on Mathematics of Language, Schloss Dagstuhl, Germany."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/3\/58\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T19:29:25Z","timestamp":1760210965000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/9\/3\/58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,27]]},"references-count":41,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2016,9]]}},"alternative-id":["a9030058"],"URL":"https:\/\/doi.org\/10.3390\/a9030058","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,8,27]]}}}