Parser Objects
ParserObjects is a library for combinator-based parsers. Combinators are the same general algorithm as Recursive Descent, but using objects instead of functions to represent grammar production rules. Some benefits of this algorithm include:
- Dynamic: You can easily construct or dynamically modify parser object graphs at runtime (normal Recursive Descent uses method references, which are generally set at compile time)
- Declarative: Declaration of parsers can closely resemble a pseudo-BNF grammar for easy readability
The Wikipedia page on Parsing gives a good overview of parsing in general and the page on Parser Combinators cover a lot of the important topics and also point to other resources for continued reading.
Key Concepts and Abstractions
ParserObjects defines a few important abstractions.
ISequence<T>
ISequence<T>
is very similar to IEnumerable<T>
/IEnumerator<T>
. It allows you to stream items from a source one by one, but it also provides a few additional features which IEnumerable<T>
/IEnumerator<T>
don’t include:
.GetNext()
gets the next item from the stream and advances the stream one position.Peek()
returns the next item from the stream but does not advance the stream.PutBack(T item)
pushes the item onto the head of the stream. It can be retrieved again with.GetNext()
or.Peek()
, first-in, last-out..CurrentLocation
returns an approximate description of the current location in the source. If the source is a text file, for example, the location will include file name, line and column..IsAtEnd
returns true if the sequence is at the end, false otherwise
A sequence is expected to always return a result even when it is at the end. A sequence should define some kind of sentinel value that can be returned when the sequence is at the end. This sentinel is usually a default value such as null
, '\0'
or 0
.
IParseResult<T>
The IParseResult<T>
abstraction represents the result of a parser execution.
.Success
a boolean flag which says whether the parse succeeded or failed..Value
the result value of the parse. If.Success
is false, this value is invalid and should not be used..Location
the approximate location of the parse result from the input stream..Transform<T2>()
transform theIParseResult<T>
intoIParseResult<T2>
IParser<TInput, TOutput>
IParser<TInput, TOutput>
is the core parser definition. The most important methods are:
.Parse()
attempts to parse. Takes an inputISequence<TInput>
and returns aIParseResult<TOutput>
..ParseUntyped()
attempts to parse, returning anIParseResult<object>
. This is frequently implemented in terms of.Parse()
with the output cast toobject
..GetChildren()
returns all the child parsers referenced by the current parser..ReplaceChild()
returns a new parser, identical to the current parser, with one of it’s child parsers replaced (non-recursive).
Pages
See the following pages for more information and examples