On the relation between context-free grammars and parsing expression grammars

Science of Computer Programming - Tập 89 - Trang 235-250 - 2014
Fabio Mascarenhas1, Sérgio Medeiros2, Roberto Ierusalimschy3
1Department of Computer Science, UFRJ, Rio de Janeiro, Brazil
2School of Science and Technology, UFRN, Natal, Brazil
3Department of Computer Science, PUC-Rio, Rio de Janeiro, Brazil

Tài liệu tham khảo

Ford, 2004, Parsing expression grammars: a recognition-based syntactic foundation, 111 Birman, 1973, Parsing algorithms with backtrack, Inf. Control, 23, 1, 10.1016/S0019-9958(73)90851-6 Aho, 1972 Parr, 1995, Antlr: a predicated-LL(k) parser generator, Softw. Pract. Exp., 25, 789, 10.1002/spe.4380250705 Kahn, 1987, Natural semantics, 22 Winskel, 1993 Clark Grune, 1991 Knuth, 1971, Top-down syntax analysis, Acta Inform., 1, 79, 10.1007/BF00289517 Hopcroft, 1979 Nijholt, 1980, LL-regular grammars, Int. J. Comput. Math., 8, 303, 10.1080/00207168008803216 Jarzabek, 1975, LL-regular grammars, Inf. Process. Lett., 4, 31, 10.1016/0020-0190(75)90009-5 Nijholt, 1982, From LL-regular to LL(1) grammars: Transformations, covers and parsing, RAIRO Theor. Inform. Appl., 16, 387, 10.1051/ita/1982160403871 de Medeiros, 2010 Redziejowski, 2009, Applying classical concepts to parsing expression grammar, Fundam. Inform., 93, 325, 10.3233/FI-2009-0105 Redziejowski, 2008, Some aspects of parsing expression grammar, Fundam. Inform., 85, 441 Redziejowski, 2013, From EBNF to PEG, Fundam. Inform., 128, 177, 10.3233/FI-2013-940 Schmitz, 2006 Parr, 1994, Adding semantic and syntactic predicates to LL(k): pred-LL(k), 263 Parr, 2011, LL(*): the foundation of the ANTLR parser generator, 425 Scott, 2013, GLL parse-tree generation, Sci. Comput. Program., 78, 1828, 10.1016/j.scico.2012.03.005 Johnstone, 2011, Modelling GLL parser implementations, vol. 6563, 42 Tomita, 1988, Graph-structured stack and natural language parsing, 249 Scott, 2010, Gll parsing, Electron. Notes Theor. Comput. Sci., 253, 177, 10.1016/j.entcs.2010.08.041 Scott, 2007, BRNGLR: a cubic Tomita-style GLR parsing algorithm, Acta Inform., 44, 427, 10.1007/s00236-007-0054-z Knuth, 1965, On the translation of languages from left to right, Inf. Control, 8, 607, 10.1016/S0019-9958(65)90426-2 DeRemer, 1971, Simple LR(k) grammars, Commun. ACM, 14, 453, 10.1145/362619.362625 Medeiros, 2012, Left recursion in parsing expression grammars, 27