Cut Points in PEG

• Autorzy: Redziejowski R. R.

Identyfikatory

DOI

10.3233/FI-2016-1308

• Języki publikacji: EN

Abstrakty

EN

Parsing Expression Grammar (PEG) encodes a recursive-descent parser with limited backtracking. It has been recently noticed that in the situation when the parser is to explore several alternatives one after another, no further alternatives need to be explored after the parser reached certain ”cut point”. This fact can be used to save both processing time and storage. The subject of the paper is identification of cut points, which can also help in producing better diagnostics.

Słowa kluczowe

EN

parsing; expression; backtrack programming; recursive functions; data analysis

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 143, nr 1/2
• Strony: 141--149
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Redziejowski R. R.

• Ceremonimästarvägen 10, SE-181 40 Lidingö, Sweden

Bibliografia

• [1] 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.
• [2] 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.
• [3] 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.
• [4] Hobbelt, G.: Breaking the Mizushima(2010) cut operator, PEG Archives, July 2014, https://lists.csail.mit.edu/pipermail/peg/2014-July/000629.html.
• [5] Maidl, A. M., Medeiros, S., Mascarenhas, F., Ierusalimschy, R.: Error reporting in Parsing Expression Grammars, Technical report, PUC-Rio, UFRJ Rio de Janeiro, UFRN Natal, Brazil, 2014, http://arxiv.org/pdf/1405.6646v1.pdf.
• [6] Mascarenhas, F., Medeiros, S., Ierusalimschy, R.: On the Relation between Context-Free Grammars and Parsing Expression Grammars, Science of Computer Programming, 89, 2014, 235–250.
• [7] 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.
• [8] 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.
• [9] Redziejowski, R. R.: More about converting BNF to PEG, Fundamenta Informaticae, 133(2-3), 2014, 177–191.