×

Generalized LR parsing algorithm for grammars with one-sided contexts. (English) Zbl 1379.68192

Summary: The Generalized LR parsing algorithm for context-free grammars is notable for having a decent worst-case running time (cubic in the length of the input string, if implemented efficiently), as well as much better performance on “good” grammars. This paper extends the Generalized LR algorithm to the case of “grammars with left contexts” [the authors, Inf. Comput. 237, 268–293 (2014; Zbl 1360.68531)], which augment the context-free grammars with special operators for referring to the left context of the current substring, along with a conjunction operator (as in conjunctive grammars) for combining syntactical conditions. All usual components of the LR algorithm, such as the parsing table, shift and reduce actions, etc., are extended to handle the context operators. The resulting algorithm is applicable to any grammar with left contexts and has the same worst-case cubic-time performance as in the case of context-free grammars.

MSC:

68Q42 Grammars and rewriting systems

Citations:

Zbl 1360.68531
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aizikowitz, T., Kaminski, M.: LR(0) Conjunctive grammars and deterministic synchronized alternating pushdown automata, Computer Science in Russia (CSR 2011, St. Petersburg, Russia). LNCS 6651, 345-358 (2011) · Zbl 1332.68102
[2] Aycock, J., Horspool, R.N., Janoušek, J., Melichar, B.: Even faster generalized LR parsing. Acta Informatica 37(9), 633-651 (2001) · Zbl 0973.68107
[3] Barash, M.: Programming language specification by a grammar with contexts. NCMA 2013 (Umeå, Sweden, 13-14, August 2013, 51-67 · Zbl 1286.68268
[4] Barash, M., Okhotin, A.: An extension of context-free grammars with one-sided context specifications. Inf. Comput. 237, 268-293 (2014) · Zbl 1360.68531
[5] Barash, M., Okhotin, A.: Two-sided context specifications in formal grammars. Theor. Comput. Sci. 591, 134-153 (2015) · Zbl 1408.68086
[6] Barash, M., Okhotin, A.: Linear grammars with one-sided contexts and their automaton representation. RAIRO Informatique Théorique et Applications 49(2), 153-178 (2015) · Zbl 1328.68100
[7] Clark, A., Eyraud, R., Habrard, A.: Using contextual representations to efficiently learn context-free languages. J. Mach. Learn. Res. 11, 2707-2744 (2010) · Zbl 1242.68213
[8] Economopoulos, G., Klint, P., Vinju, J.: Faster scannerless GLR parsing. Compiler Construction (CC 2009, York, United Kingdom, March 22-29, 2009) LNCS 5501, 126-141 · Zbl 1328.68100
[9] Kallmeyer, L., Maier, W.: LR Parsing for LCFRS. Human Language Technologies (NAACL HLT 2015, Denver, Colorado, USA, 31 May-5 June 2015), 1250-1255 · Zbl 1041.68054
[10] Kipps, J.R.: GLR parsing in time 𝓞(n3)\( \mathcal{O}(n^3). In\): Tomita, M. (ed.) Generalized LR Parsing, Kluwer, pp 43-59 (1991) · Zbl 1408.68086
[11] Knuth, D.E.: On the translation of languages from left to right. Inf. Control. 8, 607-639 (1965) · Zbl 0231.68027
[12] Kowalski, R.: Logic for Problem Solving. North-Holland, Amsterdam (1979) · Zbl 0426.68002
[13] Lang, B.: Deterministic techniques for efficient non-deterministic parsers. Automata, Languages and Programming (ICALP 1974, Saarbrücken, Germany, July 29-August 2, 1974), LNCS 14, 255- 269 · Zbl 0299.68020
[14] Nederhof, M.-J.: An alternative LR algorithm for TAGs. 36th Annual Meeting of the Association for Computational Linguistics (COLING-ACL’98, Montréal, Canada, 10-14 August 1998), 946-952 · Zbl 1004.68082
[15] Okhotin, A.: Conjunctive grammars. Journal of Automata, Languages and Combinatorics 6(4), 519-535 (2001) · Zbl 1004.68082
[16] Okhotin, A.: LR Parsing for conjunctive grammars. Grammars 5, 81-124 (2002) · Zbl 1041.68054
[17] Okhotin, A.: Generalized LR parsing algorithm for Boolean grammars. Int. J. Found. Comput. Sci. 17(3), 629-664 (2006) · Zbl 1098.68060
[18] Okhotin, A.: Conjunctive and Boolean grammars: the true general case of the context-free grammars. Computer Science Review 9, 27-59 (2013) · Zbl 1286.68268
[19] Okhotin, A.: Parsing by matrix multiplication generalized to Boolean grammars. Theor. Comput. Sci. 516, 101-120 (2014) · Zbl 1277.68108
[20] Okhotin, A.: Improved normal form for grammars with one-sided contexts. Theor. Comput. Sci. 588, 52-72 (2015) · Zbl 1329.68155
[21] Okhotin, A.: Input-driven languages are linear conjunctive. Theor. Comput. Sci. 618, 52-71 (2016) · Zbl 1335.68127
[22] Pereira, F.C.N., Warren, D.H.D.: Parsing as deduction. 21st Annual Meeting of the Association for Computational Linguistics (ACL 1983, Cambridge, Mass., USA, 15-17 June 1983), 137-144
[23] Prolo, C.A.: An efficient LR parser generator for tree-adjoining grammars. In: Bunt, H., Caroll, J., Satta, G. (eds.) New Developments in Parsing Technology, pp 125-155 (2005) · Zbl 1277.68108
[24] Rabkin, M.: Recognizing two-sided contexts in cubic time. Computer Science—Theory and Applications (CSR 2014, Moscow, Russia, 6-12, June 2014), LNCS 8476, 14-324 · Zbl 1408.68088
[25] Rounds, W.C.: LFP: A logic for linguistic descriptions and an analysis of its complexity. Computational Linguistics 14(4), 1-9 (1988)
[26] Scott, E., Johnstone, A.: Right nulled GLR parsers. ACM Trans. Program. Lang. Syst. 28(4), 577-618 (2006) · Zbl 1094.68045
[27] Tomita, M.: Efficient Parsing for Natural Language. Kluwer (1986) · Zbl 1360.68531
[28] Tomita, M.: An efficient augmented context-free parsing algorithm. Computational Linguistics 13(1), 31-46 (1987)
[29] Yoshinaka, R.: Learning conjunctive grammars and contextual binary feature grammars. Language and Automata Theory and Applications (LATA 2015, Nice, France, 2-6, March 2015), LNCS 8977, 623-635 · Zbl 1425.68151
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.