Parser Generator for Parsing Expression Grammar

Authors

  • Tota M Vivekananda Institute of Technology and Science, Karimnagar (A.P), India
  • Kumar PP Vivekananda Institute of Technology and Science, Karimnagar (A.P), India

Keywords:

PEG, memorization, lexer, backtracking, CFG

Abstract

In the field of formal languages apart from context free grammar (CFG) a new approach is developed i.e. Parsing Expression Grammar (PEG). Parsing Expression Grammar (PEG) is a new way to specify recursive-descent parsers with limited backtracking. The use of backtracking lifts the LL(1) restriction usually imposed by top-down parsers. In addition, PEG can directly define the structures that usually require a separate “lexer” or “scanner”. The parser has many useful properties, and with the use of memorization, it works in a linear time. This paper reports an experiment that consisted of defining PEG formalism, and literally transcribing the PEG definitions into parsing procedures.

References

Ford, B. Packrat parsing: a practical linear-time algorithm with backtracking. Master’s thesis, Massachusetts Institute of Technology, September 2002.

Ford, B. Parsing expression grammars: A recognition-based syntactic foundation. In Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2004 (Venice, Italy, 14–16 January 2004), N. D. Jones and X. Leroy, Eds., ACM, pp.

Gosling, J., Joy, B., Steele, G., and Bracha, G. Java Language Speci_cation, The 3rd Edi-tion. Addison-Wesley, 2005. http://java.sun.com/docs/books/jls/thirdedition/html/j3TOC.html.

Grimm, R. Practical packrat parsing. Tech. Rep. TR2004-854, Dept. of Computer Science,New York University, March 2004. http://www.cs.nyu.edu/rgrimm/papers/tr2004-854.pdf.

Redziejowski, R. R.: Parsing Expression Grammar as a Primitive Recursive-Descent Parser with Backtracking, Fundamenta Informaticae, 79(3–4), 2007, 513–524.

Redziejowski, R. R.: Some Aspects of Parsing Expression Grammar, Fundamenta Informaticae, 85(1–4), 2008, 441–454.

Ford, B. Packrat parsing: Simple, powerful, lazy, linear time. In Proceedings of the 2002 International Conference on Functional Programming (October 2002).

Redziejowski, R. R. Applying classical concepts to Parsing Expression Grammar. Fundamenta Informaticae 93, 1–3 (2009), 325–336.

Mizushima, K., Maeda, A., and Yamaguchi, Y. Packrat parsers can handle practical grammars in mostly constant space. In 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 (2010), S. Lerner and A. Rountev, Eds., ACM, pp. 29–36.

Aho, A. V., Sethi, R., and Ullman, J. D. Compilers. Principles, Techniques, and Tools. Addison- Wesley, 1987.

Downloads

Published

2024-02-26

How to Cite

Tota, M., & Kumar, P. P. (2024). Parser Generator for Parsing Expression Grammar. COMPUSOFT: An International Journal of Advanced Computer Technology, 2(07), 188–192. Retrieved from https://ijact.in/index.php/j/article/view/35

Issue

Vol. 2 No. 07 (2013): July

Section

Original Research Article

License

Copyright (c) 2013 COMPUSOFT: An International Journal of Advanced Computer Technology

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

©2023. COMPUSOFT: AN INTERNATIONAL OF ADVANCED COMPUTER TECHNOLOGY by COMPUSOFT PUBLICATION is licensed under a Creative Commons Attribution 4.0 International License. Based on a work at COMPUSOFT: AN INTERNATIONAL OF ADVANCED COMPUTER TECHNOLOGY. Permissions beyond the scope of this license may be available at Creative Commons Attribution 4.0 International Public License.