A parsing machine for PEGs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A parsing machine for PEGs

Full text

Pdf (238 KB)

Source

Dynamic Languages Symposium archive
Proceedings of the 2008 symposium on Dynamic languages table of contents

Paphos, Cyprus

Article No. 2

Year of Publication: 2008

ISBN:978-1-60558-270-2

Authors

Sérgio Medeiros	PUC-Rio, Rio de Janeiro, Brazil
Roberto Ierusalimschy	PUC-Rio, Rio de Janeiro, Brazil

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 106, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1408681.1408683 What is a DOI?

ABSTRACT

Parsing Expression Grammar (PEG) is a recognition-based foundation for describing syntax that renewed interest in top-down parsing approaches. Generally, the implementation of PEGs is based on a recursive-descent parser, or uses a memoization algorithm.

We present a new approach for implementing PEGs, based on a virtual parsing machine, which is more suitable for pattern matching. Each PEG has a corresponding program that is executed by the parsing machine, and new programs are dynamically created and composed. The virtual machine is embedded in a scripting language and used by a patternmatching tool.

We give an operational semantics of PEGs used for pattern matching, then describe our parsing machine and its semantics. We show how to transform PEGs to parsing machine programs, and give a correctness proof of our transformation.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	B. Ford. Packrat parsing:: simple, powerful, lazy, linear time, functional pearl. SIGPLAN Not., 37(9):36--47, 2002.
	2	B. Ford. Parsing expression grammars: a recognition-based syntactic foundation. In POPL '04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 111--122, New York, NY, USA, 2004. ACM.
	3	D. P. Friedman, C. T. Haynes, and M. Wand. Essentials of programming languages (2nd ed.). Massachusetts Institute of Technology, Cambridge, MA, USA, 2001.
	4	R. Grimm. Better extensibility through modular syntax. In PLDI '06: Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, pages 38--51, New York, NY, USA, 2006. ACM.
	5	G. Hutton and E. Meijer. Monadic Parsing in Haskell. Journal of Functional Programming, 8(4):437--444, July 1998.
	6	R. Ierusalimschy. Programming in Lua, Second Edition. Lua.Org, 2006.
	7	R. Ierusalimschy. A Text Pattern-Matching Tool based on Parsing Expression Grammars. Software - Practice and Experience, 2008 (to appear).
	8	R. Ierusalimschy, L. H. de Figueiredo, and W. C. Filho. Lua - an extensible extension language. Software - Practice and Experience, 26(6):635--652, 1996.
	9	D. E. Knuth. Top-down syntax analysis. Acta Inf., 1:79--110, 1971.
	10	D. J. P. Leijen and H. J. M. Meijer. Parsec: Direct style monadic parser combinators for the real world. Technical Report UU-CS-2001-35, Department of Information and Computing Sciences, Utrecht University, 2001.
	11	LPEG: Parsing Expression Grammars For Lua. Available at http://www.inf.puc-rio.br/~roberto/lpeg,2008. Visited on April 2008.
	12	peg/leg - recursive-descent parser generators for C. Available at http://piumarta.com/software/peg/, 2008. Visited on June 2008.
	13	R. R. Redziejowski. Parsing expression grammar as a primitive recursive-descent parser with backtracking. Fundamenta Informaticae, 3--4(79):513--524, 2007.
	14	K. Thompson. Programming techniques: Regular expression search algorithm. Commun. ACM, 11(6):419--422, 1968.
	15	A. Warth and I. Piumarta. Ometa: an object-oriented language for pattern matching. In DLS '07: Proceedings of the 2007 symposium on Dynamic languages, pages 11--19, New York, NY, USA, 2007. ACM.