Optimization Strategies for Performance Enhancement of Packrat Parsers

Authors

  • Nikhil Mangrulkar Yeshwantrao Chavan College of Engineering, Nagpur – 441110, INDIA
  • Kavita Singh Yeshwantrao Chavan College of Engineering, Nagpur – 441110, INDIA
  • Sagar Badhiye Symbiosis Institute of Tech. Nagpur Campus, Nagpur– 440008, INDIA

Keywords:

Parsing, Parsing expression grammar, Packrat parser, Linear time parsing, Memoization

Abstract

Memoization in computing refers to storing intermediate results and referring them when same inputs appear again instead of calculating them again. Packrat parsing is a comparatively new parsing technique based on top down approach with backtracking for parsing input which uses memoization and ensures linear time parsing. Introduced in 2002 by Bryan Ford, Packrat parsing was developed with focus on computer oriented languages. The ensured linear time parsing by packrat parsers comes at a cost of huge primary memory consumption for memoization making it impractical to implement. Here we have proposed a three way approach to optimize the use of memory required for memoization. Our implementation allocates memory for memoization dynamically based on resources available. Non linear data structure eliminates the requirement of continues blocks of free memory. Using linear time searching technique it is ensured that latency is constant even in case where higher number of intermediate results are stored. The proposed implementation is a promising approach for exploiting benefits of memoization to ensure linear time parsing while avoiding burdening the system in case where primary memory is a constraint..

Downloads

Download data is not yet available.

References

B. Ford, “Parsing expression grammars: A recognition-based syntactic foundation,” Conference Record of the Annual ACM Symposium on Principles of Programming Languages, vol. 31, pp. 111–122, 2004.

M. Johnson, “Memoization of Top-down Parsing,” Computational Linguistics, vol. 21, no. 3, 1995.

B. Ford, “Packrat Parsing: Simple, Powerful, Lazy, Linear Time Functional Pearl,” in Seventh ACM SIGPLAN international conference on Functional programming (ICFP ’02), New York: Association for Computing Machinery, 2002, pp. 36–47. [Online]. Available: http://pdos.lcs.mit.edu/

B. Ford, “Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking,” Dissertation for Master of Science in Computer Science and Engineering, Massachusetts Institute of Technology, 2002.

Birman Alexander, “The TMG Recognition Schema,” Dissertation for Doctor of Philosophy, Princeton University, 1970.

R. Becket and Z. Somogyi, “DCGs + Memoing = Packrat Parsing But is it worth it?,” in Practical Aspects of Declarative Languages. PADL 2008, P. Hudak and D. S. Warren, Eds., Springer, Berlin, Heidelberg, 2008. doi: https://doi.org/10.1007/978-3-540-77442-6_13.

N. S. Mangrulkar, K. R. Singh, and M. M. Raghuwanshi, “Parsing Expression Grammar and Packrat Parsing—A Review,” 2023, pp. 377–384. doi: 10.1007/978-981-19-0095-2_36.

R. Grimm, “Practical Packrat Parsing.” [Online]. Available: http://www.cs.nyu.edu/rgrimm/xtc/.

Warth Alessandro, Douglass James R., and Millstein Todd, “Packrat Parsers Can Support Left Recursion,” Association for Computing Machinery, 2010, p. 158.

R. R. Redziejowski, “Mouse: From Parsing Expressions to a Practical Parser,” in CS&P Workshop, Jan. 2009, pp. 514–525. [Online]. Available: http://www.romanredz.se/freesoft.htm.

M. M. Goswami, M. M. Raghuwanshi, and L. Malik, “Performance Improvement of Stack Based Recursive-Descent Parser for Parsing Expression Grammar,” International Journal of Latest Trends in Engineering and Technology, vol. 6, no. 3, pp. 302–309, 2016.

K. Kuramitsu, “Packrat parsing with elastic sliding window,” Journal of Information Processing, vol. 23, no. 4, pp. 505–512, Jul. 2015, doi: 10.2197/ipsjjip.23.505.

Nikhil Mangrulkar, Kavita Singh, and Mukesh Raghuwanshi, “Packrat Parsing with Dynamic Buffer Allocation,” JOURNAL OF ADVANCED APPLIED SCIENTIFIC RESEARCH, vol. 4, no. 1, Apr. 2022, doi: 10.46947/joaasr412022227.

N. Mangrulkar and K. Singh, “Optimizing Packrat Parsing with Non-Linear Data Structures for Memoization,” in 2023 International Conference on Self Sustainable Artificial Intelligence Systems (ICSSAS), IEEE, Oct. 2023, pp. 1–4. doi: 10.1109/ICSSAS57918.2023.10331889.

Downloads

Published

23.02.2024

How to Cite

Mangrulkar, N. ., Singh, K. ., & Badhiye, S. . (2024). Optimization Strategies for Performance Enhancement of Packrat Parsers. International Journal of Intelligent Systems and Applications in Engineering, 12(17s), 781–785. Retrieved from https://ijisae.org/index.php/IJISAE/article/view/5031

Issue

Vol. 12 No. 17s (2024)

Section

Research Article

License

Creative Commons License

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

All papers should be submitted electronically. All submitted manuscripts must be original work that is not under submission at another journal or under consideration for publication in another form, such as a monograph or chapter of a book. Authors of submitted papers are obligated not to submit their paper for publication elsewhere until an editorial decision is rendered on their submission. Further, authors of accepted papers are prohibited from publishing the results in other publications that appear before the paper is published in the Journal unless they receive approval for doing so from the Editor-In-Chief.

IJISAE open access articles are licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license lets the audience to give appropriate credit, provide a link to the license, and indicate if changes were made and if they remix, transform, or build upon the material, they must distribute contributions under the same license as the original.