Trying to Understand PEG

• Autorzy: Redziejowski R. R.

Identyfikatory

DOI

10.3233/FI-2018-1638

• Języki publikacji: EN

Abstrakty

EN

Parsing Expression Grammar (PEG) encodes a recursive-descent parser with limited backtracking. Its properties are useful in many applications, but it is not well understood as a language definition tool. In its appearance, PEG is almost identical to a grammar in the Extended Backus-Naur Form (EBNF), and one may expect it to define the same language. But, due to the limited backtracking, PEG may reject some strings defined by EBNF, which gives an impression of PEG being unpredictable. We note that for some grammars, the limited backtracking is “efficient”, in the sense that it exhausts all possibilities. A PEG with efficient backtracking should therefore be easy to understand. There is no general algorithm to check if the grammar has efficient backtracking, but it can be often checked by inspection. The paper outlines an interactive tool to facilitate such inspection.

Słowa kluczowe

EN

parsing; backtrack programming; syntax; computer algorithms; scanning systems

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 157, nr 4
• Strony: 463--475
• Opis fizyczny: Bibliogr. 12 poz., rys., tab.

Twórcy

autor

Redziejowski R. R.

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

Bibliografia

• [1] Lucas P. The Structure of Formula-Translators. ALGOL Bulletin Supplement, 1961;16:1-27. URL http://dl.acm.org/citation.cfm?id=1064069.1064070.
• [2] Ford B. Parsing Expression Grammars: A Recognition-Based Syntactic Foundation. In: Jones ND, Leroy X (eds.), Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2004. ACM, Venice, Italy, 2004 pp. 111-122. doi:10.1145/964001.964011.
• [3] Ford B. Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking. Master’s thesis, Massachusetts Institute of Technology, 2002. http://pdos.csail.mit.edu/papers/packrat-parsing:ford-ms.pdf.
• [4] Ford B. Packrat parsing: simple, powerful, lazy, linear time, functional pearl. In: Wand M, Jones SLP (eds.), Proceedings of the Seventh ACM SIGPLAN International Conference on Functional Programming (ICFP ’02), Pittsburgh, Pennsylvania, USA, October 4-6, 2002. ACM, 2002 pp. 36-47. doi:10.1145/581478.581483.
• [5] Mizushima K, Maeda A, Yamaguchi Y. Packrat parsers can handle practical grammars in mostly constant space. In: Lerner S, Rountev A (eds.), 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. ACM, 2010 pp. 29-36. doi:10.1145/1806672.1806679.
• [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, 2010.
• [7] Mascarenhas F, Medeiros S, Ierusalimschy R. On the Relation between Context-Free Grammars and Parsing Expression Grammars. Science of Computer Programming, 2014;89(C):235-250. URL https://doi.org/10.1016/j.scico.2014.01.012.
• [8] Redziejowski RR. From EBNF to PEG. Fundamenta Informaticae, 2013;128(1-2):177-191. doi:10.3233/FI-2013-940.
• [9] Aho AV, Sethi R, Ullman JD. Compilers, Principles, Techniques, and Tools. Addison-Wesley, 1986. ISBN:0-201-10088-6.
• [10] Tremblay JP, Sorenson PG. The Theory and Practice of Compiler Writing. McGraw-Hill, 1985. ISBN:0070651612, 9780070651616.
• [11] Redziejowski RR. PEG Explorer, 2017. URL http://mousepeg.sourceforge.net/explorer.htm.
• [12] Okhotin A. Boolean grammars. Inf. Comput., 2004. 194(1):19-48. doi:10.1016/j.ic.2004.03.006. URL https://doi.org/10.1016/j.ic.2004.03.006.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).