From EBNF to PEG

• Autorzy: Redziejowski R.R.
• Języki publikacji: EN

Abstrakty

EN

Parsing Expression Grammar (PEG) encodes a recursive-descent parser with limited backtracking. The parser has many useful properties, and with the use of memoization, it works in a linear time. In its appearance, PEG is almost identical to a grammar in Extended Backus-Naur Form (EBNF), but usually defines a different language. However, in some cases only minor typographical changes are sufficient to convert an EBNF grammar into its PEG parser. As recently shown by Medeiros, this is, in particular, true for LL(1) grammars. But this is also true for many non-LL(1) grammars, which is interesting because the backtracking of PEG is often a convenient way to circumvent just the LL(1) restriction. We formulate a number of conditions for EBNF grammar to become its own PEG parser, and arrive at a condition that we call LL(1p), meaning that a top-down parser can choose its next action by looking at the input within the reach of one parsing procedure (rather than by looking at the next letter). An extension to LL(kp) for k > 1 seems possible.

Słowa kluczowe

EN

language; linear systems; programming languages; computer systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2013
• Tom: Vol. 128, nr 1-2
• Strony: 177--191
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Redziejowski R.R.

• Giraf's Research

Bibliografia

• [1] Aho, A. V, Sethi, R., Ullman, J. D.: Compilers. Principles, Techniques, and Tools, Addison-Wesley, 1987.
• [2] Ford, B.: Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master Thesis, Massachusetts Institute of Technology, September 2002, http://pdos.csail.mit.edu/papers/packrat-parsing:ford-ms.pdf.
• [3] Ford, B.: Packrat parsing: simple, powerful, lazy, linear time, functional pearl, Proceedings of the Seventh ACMSIGPLANInternational Conference on Functional Programming (ICFP ’02), Pittsburgh, Pennsylvania, USA, October 4-6, 2002 (M. Wand, S. L. P. Jones, Eds.), ACM, 2002.
• [4] Ford, B. : Parsing Expression Grammars: A Recognition-Based Syntactic Foundation, Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2004 (N. D. Jones, X. Leroy, Eds.), ACM, Venice, Italy, 14-16 January 2004.
• [5] Medeiros, S.: Correspondencia entre PEGs e Classes de Gramáticas Livres de Contexto, Ph.D. Thesis, Pontificia Universidade Católica do Rio de Janeiro, August 2010, http : //www2. dbd.puc-rio . br/pergamum/tesesabertas/0611957_10_pretextual. pdf, http ://www2.dbd.puc-rio.br/pergamum/tesesabertas/0611957_10_cap_01. pdf , http ://www2.dbd.puc-rio.br/pergamum/tesesabertas/0611957_10_cap_02.pdf etc. http ://www2.dbd.puc-rio.br/pergamum/tesesabertas/0611957_10_cap_05. pdf, http ://www2.dbd.puc-rio.br/pergamum/tesesabertas/0611957_10_postextual.pdf.
• [6] Mizushima, K., Maeda, A., Yamaguchi, Y.: Packrat parsers can handle practical grammars in mostly constant space, Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, PASTE’10, Toronto, Ontario, Canada, June 5-6, 2010 (S. Lerner, A. Rountev, Eds.), ACM, 2010.
• [7] Redziejowski, R. R.: Some Aspects of Parsing Expression Grammar, Fundamenta Informaticae, 85(1-4), 2008, 441-454.
• [8] Schmitz, S.: Modular Syntax Demands Verification, Technical Report ISRNI3S/RR 2006-32-FR, Laboratoire I3S, Sophia Antipolis, October 2006.
• [9] Tremblay, J.-P., Sorenson, P. G.: The Theory and Practice of Compiler Writing, McGraw-Hill, 1985.