Barash, Mikhail; Okhotin, Alexander An extension of context-free grammars with one-sided context specifications. (English) Zbl 1360.68531 Inf. Comput. 237, 268-293 (2014). Summary: The paper introduces an extension of context-free grammars equipped with an operator for referring to the left context of the substring being defined. For example, a rule \(A \to a\) & \(\vartriangleleft B\) defines a symbol \(a\), as long as it is preceded by a string defined by \(B\). The conjunction operator in this example is taken from conjunctive grammars [A. Okhotin, J. Autom. Lang. Comb. 6, No. 4, 519–535 (2001; Zbl 1004.68082)], which are an extension of ordinary context-free grammars that maintains most of their practical properties, including many parsing algorithms. This paper gives two equivalent definitions of grammars with left contexts – by logical deduction and by language equations – and establishes their basic properties, including a transformation to a normal form and a cubic-time parsing algorithm, with a square-time version for unambiguous grammars. Cited in 5 ReviewsCited in 13 Documents MSC: 68Q42 Grammars and rewriting systems Keywords:context-free grammars; conjunctive grammars; contexts; context-sensitive grammars; parsing Citations:Zbl 1004.68082 Software:ALGOL 60 PDFBibTeX XMLCite \textit{M. Barash} and \textit{A. Okhotin}, Inf. Comput. 237, 268--293 (2014; Zbl 1360.68531) Full Text: DOI References: [1] Aizikowitz, T.; Kaminski, M., LR(0) conjunctive grammars and deterministic synchronized alternating pushdown automata, (Computer Science in Russia. Computer Science in Russia, CSR 2011, St. Petersburg, Russia, 14-18 June 2011. Computer Science in Russia. Computer Science in Russia, CSR 2011, St. Petersburg, Russia, 14-18 June 2011, Lect. Notes Comput. Sci., vol. 6651 (2011)), 345-358 · Zbl 1332.68102 [2] Autebert, J.; Berstel, J.; Boasson, L., Context-free languages and pushdown automata, (Rozenberg; Salomaa, Handbook of Formal Languages, vol. 1 (1997), Springer-Verlag), 111-174 [3] Barash, M., Recursive descent parsing for grammars with contexts, (SOFSEM 2013 Student Research Forum, Local Proceedings II. SOFSEM 2013 Student Research Forum, Local Proceedings II, Špindlerův Mlýn, Czech Republic, 26-31 January, 2013 (2013), Institute of Computer Science AS CR), 10-21 [4] Barash, M., Programming language specification by a grammar with contexts, (Bensch, S.; Drewes, F.; Freund, R.; Otto, F., Fifth Workshop on Non-Classical Models of Automata and Applications. Fifth Workshop on Non-Classical Models of Automata and Applications, NCMA 2013, Umeå, Sweden, 13-14 August, 2013 (2013), Österreichische Computer Gesellschaft), 51-67, books@ocg.at 294 [6] Chomsky, N., On certain formal properties of grammars, Inf. Control, 2, 2, 137-167 (1959) · Zbl 0088.10801 [7] Čulík, K.; Cohen, R., LR-regular grammars—an extension of \(LR(k)\) grammars, J. Comput. Syst. Sci., 7, 1, 66-96 (1973) · Zbl 0253.68014 [8] Ésik, Z.; Kuich, W., Boolean fuzzy sets, Int. J. Found. Comput. Sci., 18, 6, 1197-1207 (2007) · Zbl 1183.68338 [9] Ford, B., Parsing expression grammars: a recognition-based syntactic foundation, (Proceedings of POPL 2004. Proceedings of POPL 2004, Venice, Italy, January 14-16, 2004 (2004)), 111-122 · Zbl 1325.68120 [10] Ginsburg, S.; Rice, H. G., Two families of languages related to ALGOL, J. ACM, 9, 350-371 (1962) · Zbl 0196.01803 [11] Jarząbek, S.; Krawczyk, T., LL-regular grammars, Inf. Process. Lett., 4, 31-37 (1975) · Zbl 0314.68026 [12] Jeż, A., Conjunctive grammars can generate non-regular unary languages, Int. J. Found. Comput. Sci., 19, 3, 597-615 (2008) · Zbl 1155.68040 [13] Jeż, A.; Okhotin, A., Conjunctive grammars over a unary alphabet: undecidability and unbounded growth, Theory Comput. Syst., 46, 1, 27-58 (2010) · Zbl 1183.68327 [14] Joshi, A. K.; Levy, L. S.; Takahashi, M., Tree adjunct grammars, J. Comput. Syst. Sci., 10, 1, 136-163 (1975) · Zbl 0326.68053 [15] Joshi, A. K.; Vijay-Shanker, K.; Weir, D. J., The convergence of mildly context-sensitive grammatical formalisms, (Sells; Shieber; Wasow, Foundational Issues in Natural Language Processing (1991)) [16] Kasami, T.; Torii, K., A syntax-analysis procedure for unambiguous context-free grammars, J. ACM, 16, 3, 423-431 (1969) · Zbl 0175.00802 [17] Kountouriotis, V.; Nomikos, Ch.; Rondogiannis, P., Well-founded semantics for Boolean grammars, Inf. Comput., 207, 9, 945-967 (2009) · Zbl 1181.68162 [18] Kowalski, R., Logic for Problem Solving (1979), North-Holland: North-Holland Amsterdam · Zbl 0426.68002 [19] Okhotin, A., Conjunctive grammars, J. Autom. Lang. Comb., 6, 4, 519-535 (2001) · Zbl 1004.68082 [20] Okhotin, A., Conjunctive grammars and systems of language equations, Program. Comput. Softw., 28, 5, 243-249 (2002) · Zbl 1036.68063 [21] Okhotin, A., Boolean grammars, Inf. Comput., 194, 1, 19-48 (2004) · Zbl 1073.68037 [22] Okhotin, A., The dual of concatenation, Theor. Comput. Sci., 345, 2-3, 425-447 (2005) · Zbl 1079.68053 [23] Okhotin, A., Generalized LR parsing algorithm for Boolean grammars, Int. J. Found. Comput. Sci., 17, 3, 629-664 (2006) · Zbl 1098.68060 [24] Okhotin, A., Recursive descent parsing for Boolean grammars, Acta Inform., 44, 3-4, 167-189 (2007) · Zbl 1119.68101 [25] Okhotin, A., Unambiguous Boolean grammars, Inf. Comput., 206, 1234-1247 (2008) · Zbl 1328.68106 [26] Okhotin, A., Conjunctive and Boolean grammars: the true general case of the context-free grammars, Comput. Sci. Rev., 9, 27-59 (2013) · Zbl 1286.68268 [27] Okhotin, A., Parsing by matrix multiplication generalized to Boolean grammars, Theor. Comput. Sci., 516, 101-120 (2014) · Zbl 1277.68108 [28] Okhotin, A.; Reitwießner, C., Conjunctive grammars with restricted disjunction, Theor. Comput. Sci., 411, 26-28, 2559-2571 (2010) · Zbl 1203.68078 [29] Okhotin, A.; Rondogiannis, P., On the expressive power of univariate equations over sets of natural numbers, Inf. Comput., 212, 1-14 (2012) · Zbl 1263.68102 [30] Parr, T.; Fisher, K., \(LL(\ast)\): the foundation of the ANTLR parser generator, (Programming Language Design and Implementation. Programming Language Design and Implementation, PLDI 2011, San Jose, USA, 4-8 June 2011 (2011)), 425-436 [32] Rounds, W. C., LFP: A logic for linguistic descriptions and an analysis of its complexity, Comput. Linguist., 14, 4, 1-9 (1988) [33] Seki, H.; Matsumura, T.; Fujii, M.; Kasami, T., On multiple context-free grammars, Theor. Comput. Sci., 88, 2, 191-229 (1991) · Zbl 0762.68039 [34] Sikkel, K., Parsing Schemata (1997), Springer-Verlag · Zbl 0876.68071 [35] Valiant, L. G., General context-free recognition in less than cubic time, J. Comput. Syst. Sci., 10, 2, 308-314 (1975) · Zbl 0312.68042 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.