×

The computational power of parsing expression grammars. (English) Zbl 1432.68211

Summary: We study the computational power of parsing expression grammars (PEGs). We begin by constructing PEGs with unexpected behaviour, and surprising new examples of languages with PEGs, including the language of palindromes whose length is a power of two, and a binary-counting language. We then propose a new computational model, the scaffolding automaton, and prove that it exactly characterises the computational power of parsing expression grammars (PEGs). Several consequences will follow from this characterisation: (1) we show that PEGs are computationally “universal”, in a certain sense, which implies the existence of a PEG for a P-complete language; (2) we show that there can be no pumping lemma for PEGs; and (3) we show that PEGs are strictly more powerful than online Turing machines which do \(o(n/(\log n)^2)\) steps of computation per input symbol.

MSC:

68Q42 Grammars and rewriting systems
68Q09 Other nonclassical models of computation

Software:

TRX
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ford, B., Parsing expression grammars: a recognition-based syntactic foundation, (ACM SIGPLAN Notices, vol. 39 (2004), ACM), 111-122 · Zbl 1325.68120
[2] Birman, A.; Ullman, J. D., Parsing algorithms with backtrack, (11th Annual Symposium on Switching and Automata Theory (1970), IEEE), 153-174
[3] Birman, A., The TMG Recognition Schema (1970), Princeton, Ph.D. thesis
[4] Aho, A. V.; Ullman, J. D., The Theory of Parsing, Translation, and Compiling, vol. 1 (1972), Prentice-Hall
[5] Chida, N.; Kuramitsu, K., Linear parsing expression grammars, (LATA. LATA, LNCS, vol. 10168 (2017)), 275-286 · Zbl 1485.68126
[6] Garnock-Jones, T.; Eslamimehr, M.; Warth, A., Recognising and generating terms using derivatives of parsing expression grammars, CoRR
[7] Henglein, F.; Rasmussen, U. T., PEG parsing in less space using progressive tabling and dynamic analysis, (PEPM (2017), ACM), 35-46
[8] Mizushima, K.; Maeda, A.; Yamaguchi, Y., Packrat parsers can handle practical grammars in mostly constant space, (PASTE (2010), ACM), 29-36
[9] Moss, A., Derivatives of parsing expression grammars, (AFL, vol. 252 (2017)), 180-194 · Zbl 1483.68150
[10] Redziejowski, R. R., From EBNF to PEG, Fundam. Inform., 128f, 1-2, 177-191 (2013) · Zbl 1285.68077
[11] Redziejowski, R. R., Cut points in PEG, Fundam. Inform., 143, 1-2, 141-149 (2016) · Zbl 1358.68159
[12] Redziejowski, R. R., Trying to understand PEG, Fundam. Inform., 157, 4, 463-475 (2018) · Zbl 1386.68081
[13] Becket, R.; Somogyi, Z., DCGs + memoing = packrat parsing but is it worth it?, (PADL, vol. 4902f (2008)), 182-196
[14] Grimm, R., Better extensibility through modular syntax, ACM SIGPLAN Not., 41, 6, 38-51 (2006)
[15] Ierusalimschy, R., A text pattern-matching tool based on parsing expression grammars, Softw. Pract. Exp., 39, 3, 221-258 (2009)
[16] Koprowski, A.; Binsztok, H., TRX: a formally verified parser interpreter, Log. Methods Comput. Sci., 7f, 2 (2011) · Zbl 1260.68194
[17] Kuramitsu, K., Fast, flexible, and declarative construction of abstract syntax trees with PEGs, J. Inf. Process., 24, 1, 123-131 (2016)
[18] Laurent, N.; Mens, K., Parsing expression grammars made practical, (SLE (2015), ACM), 167-172
[19] Maidl, A. M.; Mascarenhas, F.; Medeiros, S.; Ierusalimschy, R., Error reporting in parsing expression grammars, Sci. Comput. Program., 132, 129-140 (2016)
[20] Matsumura, T.; Kuramitsu, K., A declarative extension of parsing expression grammars for recognizing most programming languages, J. Inf. Process., 24, 2, 256-264 (2016)
[21] Medeiros, S.; Ierusalimschy, R., A parsing machine for PEGs, (DLS (2008)), 2
[22] Ford, B., The packrat parsing and parsing expression grammars page, online at
[23] Steele, G. L., Growing a language, High.-Order Symb. Comput., 12, 3, 221-236 (1999)
[24] Flood, C., Fortress: a next-generation programming language brought to you by Sun Labs, (Java One Developer Conference (2008))
[25] Bar-Hillel, Y.; Perles, M.; Shamir, E., On formal properties of simple phrase structure grammars, (Bar-Hillel, Y., Language and Information: Selected Essays on Their Theory and Application. Language and Information: Selected Essays on Their Theory and Application, Series in Logic (1964), Addison-Wesley), 116-150 · Zbl 0158.25307
[26] Li, M.; Vitányi, P., A new approach to formal language theory by Kolmogorov complexity, SIAM J. Comput., 24, 2, 398-410 (1995) · Zbl 0827.68057
[27] Hayashi, T., On derivation trees of indexed grammars: an extension of the uvwxy-theorem, Publ. Res. Inst. Math. Sci., Kyoto Univ., 9, 61-92 (1973) · Zbl 0319.68043
[28] Yu, S., A pumping lemma for deterministic context-free languages, Inf. Process. Lett., 31, 1, 47-51 (1989) · Zbl 0672.68041
[29] Amarilli, A.; Jeanmougin, M., A proof of the pumping lemma for context-free languages through pushdown automata (2012)
[30] Greibach, S. A., The hardest context-free language, SIAM J. Comput., 2, 4, 304-310 (1973) · Zbl 0278.68073
[31] Hartmanis, J.; Stearns, R. E., On the computational complexity of algorithms, Trans. Am. Math. Soc., 117, 285-306 (1965) · Zbl 0131.15404
[32] Ford, B., Packrat parsing: simple, powerful, lazy, linear time, functional pearl, (Wand, M.; Jones, S. L.P., ICFP’02 (2002), ACM), 36-47 · Zbl 1322.68040
[33] Ford, B., Packrat Parsing: A Practical Linear-Time Algorithm With Backtracking (2002), Massachusetts Institute of Technology
[34] Hopcroft, J. E.; Motwani, R.; Ullman, J. D., Introduction to automata theory, languages, and computation, ACM SIGACT News, 32, 1, 60-65 (2001) · Zbl 0980.68066
[35] Balcázar, J. L.; Dıaz, J.; Gabarró, J., Structural Complexity I (1988), Springer · Zbl 0638.68040
[36] Arora, S.; Barak, B., Computational Complexity: A Modern Approach (2009), Cambridge University Press · Zbl 1193.68112
[37] Johnson, D. S., A catalog of complexity classes, (Algorithms and Complexity (1990), Elsevier), 67-161 · Zbl 0900.68246
[38] Sipser, M., Introduction to the Theory of Computation (2012), Cengage Learning
[39] Rosenberg, A., Real-time definable languages, J. ACM, 14, 4, 645-662 (1967) · Zbl 0153.00902
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.