Some Aspects of Parsing Expression Grammar

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

Abstrakty

EN

Parsing Expression Grammar (PEG) is a new way to specify syntax, by means of a top-down process with limited backtracking. It can be directly transcribed into a recursive-descent parser. The parser does not require a separate lexer, and backtracking removes the usual LL(1) constraint. This is convenient for many applications, but there are two problems: PEG is not well understood as a language specification tool, and backtracking may result in exponential processing time. The paper consists of two parts that address these problems. The first part is an attempt to find out the language actually defined by a given parsing expression. The second part reports measurements of backtracking activity in a PEG-derived parser for the programming language C.

Słowa kluczowe

EN

parsing expression grammar

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 85, nr 1-4
• Strony: 441--454
• Opis fizyczny: bibliogr. 21 poz., tab., wykr.

Twórcy

autor

Redziejowski R.R.

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

Bibliografia

• [1] Aho, A. V., Sethi, R., Ullman, J. D.: Compilers, Principles,Techniques, and Tools, Addison-Wesley, 1987.
• [2] Aho, A. V., Ullman, J. D.: The Theory of Parsing, Translation and Compiling, Vol. I, Parsing, Prentice Hall, 1972.
• [3] Birman, A.: The TMG Recognition Schema, Ph.D. Thesis, Princeton University, February 1970.
• [4] Birman, A., Ullman, J. D.: Parsing Algorithms with Backtrack, Information and Control, 23, 1973, 1-34.
• [5] Brooker, P., Morris, D.: Some Proposals for the Realization of a Certain Assembly Program, The Computer Journal, 3(4), 1961, 220-231.
• [6] Ford, B.: Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking, Master Thesis, Massachusetts Institute of Technology, September 2002.
• [7] Ford, B.: Packrat Parsing: Simple, Powerful, Lazy, Linear Time, Proceedings of the 2002 International Conference on Functional Programming, October 2002.
• [8] Ford, B.: Parsing Expression Grammars: A Recognition-Based Syntactic Foundation, Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (N. D. Jones, X. Leroy, Eds.), ACM, Venice, Italy, 14-16 January 2004.
• [9] GNU: Bison parser generator, http://www.gnu.org/software/bison.
• [10] GNU: M4 macro processor, http://www.gnu.org/software/m4.
• [11] Gosling, J., Joy, B., Steele, G., Bracha, G.: Java Language Specification, The 3rd Edition, Addison-Wesley, 2005.
• [12] Hopgood, F. R. A.: Compiling Techniques, MacDonalds, 1969.
• [13] Lucas, P.: The Structure of Formula-Translators, ALGOL Bulletin Supplement, 16, September 1961, 1-27.
• [14] Mariano, A.: GNU units 1.86, http://ftp.gnu.org/gnu/units.
• [15] McClure, R. M.: TMG - a syntax directed compiler, Proceedings of the 20th ACM National Conference (L. Winner, Ed.), ACM, 24-26 August 1965.
• [16] Michie, D.: Memo Functions and Machine Learning, Nature, 218, April 1968, 19-22.
• [17] Noll, L. C.: Calc: C-style arbitrary precision system, http://sourceforge.net/projects/calc.
• [18] Redziejowski, R. R.: Computing with units - User's Manual, http://units-in-java.sourceforge.net/UnitsDoc.htm.
• [19] Redziejowski, R. R.: Parsing Expression Grammar as a Primitive Recursive-Descent Parser with Backtracking, Fundamenta Informaticae, 79(3-4), 2007, 513-524.
• [20] Rosen, S.: A Compiler-Building System Developed by Brooker and Morris, Communications of the ACM, 7(7), July 1964, 403-414.
• [21] Schmitz, S.: Modular Syntax Demands Verification, Technical Report I3S/RR-2006-32-FR, Laboratoire I3S, Universit´e de Nice - Sophia Antipolis, October 2006.