Module: Peggy

Defined in:

lib/parse/ast.rb,
lib/abnc.rb,
lib/parse/parser.rb,
lib/parse/builder.rb

Overview

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.

Defined Under Namespace

Modules: OneChild Classes: ABNF, AST, Alternatives, AnyNumber, AtLeastOne, Builder, Element, Literal, Multiple, Negative, Node, Optional, Parser, Positive, Predicate, Production, Reference, Sequence

Constant Summary

NO_MATCH =

Returned when a production did not match

false

IN_USE =

Used to prevent infinite (left) recursions

true