module Peggy
Peggy
packrat parster for Ruby
ast.rb - Abstract Syntax Tree
Copyright © 2006 Troy Heninger
Peggy
is copyrighted free software by Troy Heninger. You can redistribute it and/or modify it under the same terms as Ruby.
Peggy
is a packrat parsing engine. Packrat parsers memoize every production so that parses can happen in linear time. No production needs to be processed more than once for a given position of the source. See pdos.csail.mit.edu/~baford/packrat/ for more details.
Peggy
also incorporates Parsing Expression Grammar (PEG) as proposed by Bryan Ford, as one of several input grammars. PEG is a formalized grammar specification needing no separate lexer/scanner step. See pdos.csail.mit.edu/~baford/packrat/popl04/
As good as packrat parsers are, they have a few limitations. They cannot handle left recursion of a production, meaning a production cannot reference itself as the first element in a sequence. Also memoizing of production results means than memory consumption increasses with the size of the source being parsed. This is not usually a concern, execpt when attempting to parse multi-megabyte source files, such as a huge XML database.
Constants
- IN_USE
Used to prevent infinite (left) recursions
- NO_MATCH
Returned when a production did not match