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.