Loading...
Please wait, while we are loading the content...
A parsing machine for pegs (2008).
| Content Provider | CiteSeerX |
|---|---|
| Author | Ierusalimschy, Roberto Medeiros, Sérgio |
| 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. |
| File Format | |
| Publisher Date | 2008-01-01 |
| Access Restriction | Open |
| Subject Keyword | Recursive-descent Parser Scripting Language New Program Parsing Machine Pattern Matching Patternmatching Tool New Approach Machine Program Top-down Parsing Approach Correctness Proof Memoization Algorithm Recognition-based Foundation Operational Semantics Corresponding Program Virtual Parsing Machine Expression Grammar Virtual Machine |
| Content Type | Text |
