A Survey of Packrat Parser

Authors

  • Amit Vishwakarma  Department of CSE, Rajiv Gandhi College of Engineering and Research, Nagpur, India
  • Manish M. Goswami  Department of IT, Rajiv Gandhi College of Engineering and Research, Nagpur, India
  • Priyanka Gonnade  Department of CSE, Rajiv Gandhi College of Engineering and Research, Nagpur, India

Keywords:

PEG; Recursive Descent Parser; Packrat Parser; TDPL

Abstract

Two recent developments in the field of formal languages are Parsing Expression Grammar (PEG) and packrat parsing. The PEG formalism is similar to BNF, but defines syntax in terms of recognizing strings, rather than constructing them. It is, in fact, precise specification of a backtracking recursive-descent parser. Packrat parsing is a general method to handle backtracking in recursive descent parsers. It ensures linear working time, at a huge memory cost. This paper begins with discussion of PEG and packrat parsing introduced by Bryan Ford Followed by various approaches over improvement of packrat parsing to reduce the memory requirement. This paper also describes the approaches to handle the left-recursion problem for PEG. The described Approaches handle the direct and indirect left-recursion problem for PEG. The paper concludes with the application of packrat parsing and throws a light on future scope in packrat parsing.

References

  1. B. Ford. Packrat parsing: Simple, powerful, lazy, linear time.In Proceedings of the 2002 International Conference on Functional Programming, October 2002.
  2. B. Ford. Parsing expression grammars: A recognition-based syntactic foundation. In Symposium on Principles of Programming Languages, January 2004.
  3. Redziejowski, R.R.: Parsing Expression Grammar as a primitive recursive-descent parser with backtracking.Fundamenta Informaticae 79,3-4, (2007) pages 513-524.
  4. R. Redziejowski. Some aspects of parsing expression grammar. In Fundamenta Informaticae 85, 1-4, pages 441–454, 2008.
  5. R. Redziejowski. Applying classical concepts to parsing expression grammar. In Fundamenta Informaticae 93, 1-3, pages 325–336, 2009.
  6. S. Medeiros and R. Lerusalimschy : A Parsing Machine for PEGs. In Proc. PEPM, ACM (January 2009) 105-110.
  7. R. Grimm. Better extensibility through modular syntax. In Proceedings of the ACM SIGPLAN 2006 Conference on Programming Language Design and Implementation, pages 19–28, 2006.
  8. K. Mizushima, A. Maeda, and Y. Yamaguchi. Improvement technique of memory efficiency of packrat parsing. In IPSJ Transaction on Programming Vol.49 No. SIG 1(PRO 35) (in Japanese), pages 117–126, 2008.
  9. Mizushima, K., Maeda, A., Yamaguchi, Y.: Packrat parsers can handle practical grammars in mostly constant space. In PASTE'10: Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on program analysis for software tools and engineering, Toronto, Ontario, ACM (2010) 29-36.
  10. R. Becket and Z. Somogyi. Dcgs + memoing = packrat parsing but is it worth it? In Practical Aspects of Declarative Languages, January 2008.
  11. Warth, A., Douglass, J., Millstein, T.: Packrat parsers can support left recursion. In: Proc. PEPM, ACM (January 2008) 103-110.
  12. Warth, A., Piumarta, I.: OMeta: an object-oriented language for pattern matching. In: Proc. Dynamic Languages Symposium, ACM (2007) 11-19.
  13. R. Redziejowski. Mouse: from parsing expressions to a practical parser. In Concurrency Specification and Programming Workshop,September 2009.
  14. R. Redziejowski. Parsing Expression Grammar for Java 1.5. http://www.romanredz.se/papers/PEG.Java.1.5.txt.
  15. Adam Koprowski and Henri Binsztok. TRX: A formally veri_ed parser interpreter. In Proceedings of the 19th European Symposium on Programming (ESOP '10), volume 6012 of Lecture Notes in Computer Science, pages 345-365, 2010.
  16. Lucas, P. The structure of formula-translators. ALGOL Bulletin Supplement 16 (September 1961), 1-27.
  17. Hopgood, F. R. A. Compiling Techniques. MacDonalds, 1969.
  18. Brooker, P., and Morris, D. Some proposals for the realization of a certain assembly program. The Computer Journal 3, 4 (1961), 220-231.
  19. Rosen, S. A compiler-building system developed by Brooker and Morris. Commun. ACM 7, 7 (July 1964), 403-414.
  20. McClure, R. M. Tmg - a syntax directed compiler. In Proceedings of the 20th ACM National Conference (24{26 August 1965), L. Winner, Ed., ACM, pp. 262-274.
  21. Birman, A. The TMG Recognition Schema. PhD thesis, Princeton University, February 1970.
  22. Birman, A., and Ullman, J. D. Parsing algorithms with backtrack. Information and Control 23(1973), 1-34.
  23. Aho, A. V., and Ullman, J. D. The Theory of Parsing, Translation and Compiling, Vol. I, Parsing. Prentice Hall, 1972.
  24. Earley, J.: An e_cient context-free parsing algorithm. Communications of the ACM 13(2) (February 1970).
  25. Tratt, L.: Domain specific language implementation via compile-time metaprogramming. TOPLAS 30(6) (2008) 1-40.
  26. J. R. Levine. lex & yacc. O’Reilly, Oct. 1992.
  27. C. Braband, M. I. Schwartzbach, and M. Vanggaard. The METAFRONT system: Extensible parsing and transformation. Technical Report BRICS RS-03-7, BRICS, Aarhus, Denmark, Feb. 2003.
  28. O. Enseling. Build your own languages with JavaCC.JavaWorld, Dec. 2000. Available at http://www.javaworld.com/javaworld/jw-12-2000/ jw-1229-cooltools.html.
  29. T. J. Parr and R. W. Quong. ANTLR: A predicated-LL(k) parser generator. Software—Practice and Experience, 25(7):789–810, July 1995.
  30. Alexander Birman. PhD thesis, 1970.
  31. Alexander Birman and Jeffrey D. Ullman. Parsing algorithms with backtrack.Information and Control, 23, 1973.
  32. Daniel J. Salomon and Gordon V. Cormack. Scannerless NSLR(1) parsing of programming languages. In Proceedings of the ACM SIGPLAN’89 Conference on Programming Language Design and Implementation (PLDI), pages 170–178, Jul 1989.
  33. Terence John Parr. Obtaining practical variants of LL(k) and LR(k) for k > 1 by splitting the atomic k-tuple. PhD thesis, Purdue University, Apr 1993.
  34. Terence J. Parr and RussellW. Quong. ANTLR: A predicated-LL(k) parser generator. Software Practice and Experience, 25(7):789–810, 1995.
  35. Bjarne Stroustrup. The C++ Programming Language. Addison-Wesley, 3rd edition, June 1997.
  36. Simon Peyton Jones and John Hughes (editors). Haskell 98 Report, 1998. http://www.haskell.org.
  37. Laurence Tratt. Direct Left-Recursive Parsing Expression Grammars: Technical report EIS-10-01 Middlesex University, The Burroughs, London, NW4 4BT, United Kingdom (2010).
  38. R. Grimm. Practical packrat parsing. New York University Technical Report, Dept. of Computer Science, TR2004-854, 2004.

International Journal of Scientific Research in Science, Engineering and Technology

Downloads

Published

2015-10-25

Issue

Volume 1, Issue 5, September-October-2015

Section

Research Articles

License

Copyright (c) IJSRSET

Creative Commons License

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

How to Cite

[1]
Amit Vishwakarma, Manish M. Goswami, Priyanka Gonnade, " A Survey of Packrat Parser, International Journal of Scientific Research in Science, Engineering and Technology(IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 1, Issue 5, pp.324-329, September-October-2015.