More About Converting BNF to PEG

• Autorzy: Redziejowski R. R.

Identyfikatory

DOI

10.3233/FI-2014-1075

• Języki publikacji: EN

Abstrakty

EN

Parsing Expression Grammar (PEG) encodes a recursive-descent parser with limited backtracking. The parser has many useful properties. Converting PEG to an executable parser is a rather straightforward task. Unfortunately, PEG is not well understood as a language definition tool. It is thus of a practical interest to construct PEGs for languages specified in some familiar way, such as Backus-Naur Form (BNF). The problem was attacked by Medeiros in an elegant way by noticing that both PEG and BNF can be formally defined in a very similar way. Some of his results were extended in a previous paper by this author. We continue here with further extensions.

Słowa kluczowe

EN

parsing; coding theory; computer systems; computer software; programming languages

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 133, nr 2/3
• Strony: 257--270
• Opis fizyczny: Bibliogr. 8 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 ACMSIGPLAN International 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] Mascarenhas, F., Medeiros, S., Ierusalimschy, R.: On the Relation between Context-Free Grammars and Parsing Expression Grammars, Technical report, UFRJ Rio de Janeiro, UFS Aracaju, PUC-Rio, Brazil, 2013, http://arxiv.org/pdf/1304.3177v1.
• [6] Medeiros, S.: Correspondència entre PEGs e Classes de Gramáticas Livres de Contexto, Ph.D. Thesis, Pontifıcia 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.
• [7] Redziejowski, R. R.: From EBNF to PEG, Fundamenta Informaticae, 128, 2013, 177–191.
• [8] Tremblay, J.-P., Sorenson, P. G.: The Theory and Practice of Compiler Writing, McGraw-Hill, 1985.