Paper Info
Title
A parsing machine for PEGs
Abstract
Parsing Expression Grammar (PEG) is a recognition-based foundation for describing syntax that renewed interest in top-down parsing approaches. Generally, the implementa- tion 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 pattern- matching tool. We give an operational semantics of PEGs used for pat- tern matching, then describe our parsing machine and its semantics. We show how to transform PEGs to parsing ma- chine programs, and give a correctness proof of our trans- formation.
Year
DOI
Venue
2008
10.1145/1408681.1408683
Dynamic Languages Symposium
Keywords
Field
DocType
parsing expression grammars,new program,virtual parsing machine,top-down parsing approach,virtual machine,parsing machine program,parsing expression grammar,operational semantics,new approach,pattern matching,parsing machine,scripting languages,scripting language,top down
Top-down parsing language,Programming language,Computer science,Theoretical computer science,Natural language processing,Artificial intelligence,Top-down parsing,S-attributed grammar,Bottom-up parsing,Parsing expression grammar,Parsing,Parser combinator,Memoization
Conference
Citations 
PageRank 
References 
11
0.81
8
Authors
2
Name
Order
Citations
PageRank
Sérgio Medeiros1283.31
Roberto Ierusalimschy246354.25