Parsing Expression Grammar as a Primitive Recursive-Descent Parser with Backtracking

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

Abstrakty

EN

Two recent developments in the field of formal languages are Parsing Expression Grammar (PEG) and packrat parsing. The PEG formalism is similar to BNF, but defines syntax in terms of recognizing strings, rather than constructing them. It is, in fact, precise specification of a backtracking recursive-descent parser. Packrat parsing is a general method to handle backtracking in recursive-descent parsers. It ensures linear working time, at a huge memory cost. This paper reports an experiment that consisted of defining the syntax of Java 1.5 in PEG formalism, and literally transcribing the PEG definitions into parsing procedures (accidentally, also in Java). The resulting primitive parser shows an acceptable behavior, indicating that packrat parsing might be an overkill for practical languages. The exercise with defining the Java syntax suggests that more work is needed on PEG as a language specification tool.

Słowa kluczowe

EN

parsing expression grammar

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2007
• Tom: Vol. 79, nr 3-4
• Strony: 513--524
• Opis fizyczny: bibliogr. 13 poz., tab.

Twórcy

autor

Redziejowski R.R.

• Ceremonimästarvägen 10, S-18140 Lidingö, Sweden,

Bibliografia

• [1] Aho, A. V., Ullman, J. D.: The Theory of Parsing, Translation and Compiling, Vol. I, "Parsing", Prentice Hall, 1972.
• [2] Birman, A.: The TMG Recognition Schema, Ph.D. Thesis, Princeton University, February 1970.
• [3] Birman, A., Ullman, J. D.: Parsing Algorithms with Backtrack, Information and Control, 23, 1973, 1-34.
• [4] Christopher, T.: A Strong LL(k) Parser Generator That Accepts Non-LL Grammars and Generates LL(1) Tables: Extended Abstract, Dept. of Computer Science, Illinois Institute of Technology, http://www.iit.edu/_tc/llkppr.ps.
• [5] Conway, D.: The man (1) of descent, The Perl, 3(4), 1998, 46-58, http://search.cpan.org/src/DCONWAY/Parse-RecDescent-1.94/tutorial/tutorial.html.
• [6] 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.
• [7] 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.
• [8] Gosling, J., Joy, B., Steele, G., Bracha, G.: Java Language Specification, The 3rd Edition, Addison-Wesley, 2005, http://java.sun.com/docs/books/jls/third edition/html/j3TOC.html.
• [9] Grimm, R.: Practical Packrat Parsing, Technical Report TR2004-854, Dept. of Computer Science, New York University,March 2004, http://www.cs.nyu.edu/rgrimm/papers/tr2004-854.pdf.
• [10] Lucas, P.: The Structure of Formula-Translators, ALGOL Bulletin Supplement, 16, September 1961, 1-27.
• [11] Parr, T., Quong, R.: ANTLR: A Predicated-LL(k) Parser Generator, Software: Practice and Experience, 25(7), 1995, 789-810, http://www.antlr.org/article/1055550346383/antlr.pdf.
• [12] Rosen, S.: A Compiler-Building System Developed by Brooker and Morris, Communications of the ACM, 7(7), July 1964, 403-414.
• [13] Schmitz, S.: Modular Syntax Demands Verification, Technical Report I3S/RR-2006-32-FR, Laboratoire I3S, Université de Nice - Sophia Antipolis, October 2006, http://www.i3s.unice.fr/_mh/RR/2006/RR-06.32-S.SCHMITZ.pdf.