Documentation
¶
Overview ¶
Package dmg implements parser combinators to build simple and fast parsers. The produced parsers are recursive-descent parsers with infinite lookahead, aka. LL(k), but with support for left-recursive (in fact, any-recursive) grammars. It also supports nullability (again, anywhere).
Additionally, dmg provides a set of convenience functions to provide common building blocks for parsers such as the Kleene Closure and a Maybe-Parser, equivalent in functionality to the POSIX regular expression operators `*` and `?`, respectively.
A simple, left-recursive parser for arithmetic difference can be built as follows:
// number -> [0-9]+
number := dmg.NewPlusParser(
dmg.NewRangeParser('0', '9'),
)
// difference -> difference '-' number | number
difference := dmg.NewRecursiveParser(func(self dmg.Parser) dmg.Parser {
return dmg.NewAlternationParser(
dmg.NewSequenceParser(
self,
dmg.NewLiteralParser("-"),
number,
),
number,
)
})
The above code, when evaluated to the end of a valid input will produce a left-leaning concrete syntax tree. In order to build an abstract syntax tree, dmg provides the MappingParser, which enables you to write "actions" to manipulate matches. Following with the example:
number := dmg.NewMappingParser(number, func(m interface{}) interface{} {
return toInteger(m)
})
This package is work-in-progress and will grow. Once it reaches a Beta-state It'll get a grammar-tree optimizer which will hopefully eliminate any and all back-tracking from the parser implementation, essentially guaranteeing an O(n) time-complexity for unambiguous grammars, as well as scaling elegantly for more complex grammars.
Example ¶
// number -> [0-9]+
number := dmg.NewPlusParser(
dmg.NewRangeParser('0', '9'),
)
// difference -> difference '-' number | number
difference := dmg.NewRecursiveParser(func(self dmg.Parser) dmg.Parser {
return dmg.NewAlternationParser(
dmg.NewSequenceParser(
self,
dmg.NewLiteralParser("-"),
number,
),
number,
)
})
treec := dmg.Dissect(difference, dmg.Remnant("10-7-1"))
// print all successful matches
for {
state := <-treec
if state.Rejected() {
continue // don't care
}
fmt.Printf("%#v\n", dmg.MatchToString(state.Value))
if len(state.Remnant) == 0 {
break // we're done
}
}
Index ¶
- func Dissect(p Parser, r Remnant) chan State
- func MatchToString(m interface{}) string
- type AlternationParser
- type AnyParser
- type EpsilonParser
- type LiteralParser
- type MappingParser
- type NotParser
- type Parser
- func NewAlternationParser(ps ...Parser) Parser
- func NewAnyParser() Parser
- func NewEpsilonParser() Parser
- func NewKleeneParser(p Parser) Parser
- func NewLiteralParser(l string) Parser
- func NewMappingParser(p Parser, m func(interface{}) interface{}) Parser
- func NewMaybeParser(p Parser) Parser
- func NewMutuallyRecursiveParsers(n int, f func([]Parser) []Parser) []Parser
- func NewNotParser(p Parser) Parser
- func NewPlusParser(p Parser) Parser
- func NewPrependParser(r interface{}, p Parser) Parser
- func NewRangeParser(min, max rune) Parser
- func NewRecursiveParser(f func(Parser) Parser) Parser
- func NewSequenceParser(ps ...Parser) Parser
- type PrependParser
- type RangeParser
- type RecursiveParser
- type Remnant
- type SequenceParser
- type State
- type StateSet
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func MatchToString ¶
func MatchToString(m interface{}) string
Types ¶
type AlternationParser ¶
type AlternationParser []Parser
An AlternationParser is a Parser that will match a set of Parsers against a Remnant in no particular order and return the merged set of states again in no particular order.
func (AlternationParser) Parse ¶
func (p AlternationParser) Parse(bs Remnant) StateSet
Parse applies all branches of an alternation to a remnant in no particular order.
Returns a set of either all rejected states if all branches of the alternation were rejected, or a set containing accepted and continued states otherwise.
type EpsilonParser ¶
type EpsilonParser struct{}
EpsilonParser is a Parser that always accepts the empty string
func (EpsilonParser) Parse ¶
func (p EpsilonParser) Parse(bs Remnant) StateSet
type LiteralParser ¶
type LiteralParser string
LiteralParser is a Parser that accepts a given string
func (LiteralParser) Parse ¶
func (p LiteralParser) Parse(bs Remnant) StateSet
type MappingParser ¶
type MappingParser struct {
Parser Parser
Mapping func(interface{}) interface{}
}
MappingParser is a Parser that matches a given Parser against a Remnant and mutates the Values of all accepted States through a mapping function.
func (MappingParser) Parse ¶
func (p MappingParser) Parse(bs Remnant) StateSet
Parse delegates to the MappingParser's underlying parser and maps all matched states' values through the MappingParser's mapping function.
type NotParser ¶
type NotParser struct {
Parser Parser
}
NotParser is a Parser that accepts any input rejected by a given Parser. It rejects anything that said Parser accepts, without consuming any input.
type Parser ¶
func NewAlternationParser ¶
NewAlternationParser returns a new AlternationParser. It panics if called with zero arguments.
func NewAnyParser ¶
func NewAnyParser() Parser
func NewEpsilonParser ¶
func NewEpsilonParser() Parser
func NewKleeneParser ¶
NewKleeneParser returns a Parser that accepts whatever its first argument accepts zero or many times.
func NewLiteralParser ¶
func NewMappingParser ¶
func NewMaybeParser ¶
NewMaybeParser returns a Parser that accepts either whatever its first argument accepts or the empty string.
func NewMutuallyRecursiveParsers ¶
NewMutuallyRecursiveParsers allows the definition of mutually recursive grammar trees.
It creates an amount of RecursiveParsers equal to its first argument and passes them as a slice to its second argument. The result of this operation must be a slice of the same length (n), otherwise it panics.
It returns a slice of length n of recursive Parsers with the order corresponding to the order returned by f.
func NewNotParser ¶
func NewPlusParser ¶
NewPlusParser returns a Parser that accepts whatever its first argument accepts one or many times.
func NewPrependParser ¶
func NewRangeParser ¶
func NewRecursiveParser ¶
NewRecursiveParser passes a pointer to a RecursiveParser to its first argument and defines said RecursiveParser as the result of this operation.
func NewSequenceParser ¶
NewSequenceParser returns a new SequenceParser. It panics if called with zero arguments.
type PrependParser ¶
type PrependParser struct {
Prepend interface{}
Parser Parser
}
PrependParser is a Parser used by SequenceParser to prepend a value to the Value of each accepted State returned by a given Parser
func (PrependParser) Parse ¶
func (p PrependParser) Parse(bs Remnant) StateSet
type RangeParser ¶
type RangeParser struct {
Min, Max rune
}
RangeParser is a Parser that accepts an UTF-8 rune in the range [Min, Max] (inclusive)
func (RangeParser) Parse ¶
func (p RangeParser) Parse(bs Remnant) StateSet
type RecursiveParser ¶
type RecursiveParser struct {
Parser Parser
}
RecursiveParser is a Parser that allows the definition of recursive grammar trees. See NewRecursiveParser.
func (*RecursiveParser) Parse ¶
func (p *RecursiveParser) Parse(bs Remnant) StateSet
Parse delegates to the RecursiveParser's underlying parser.
type SequenceParser ¶
type SequenceParser []Parser
A SequenceParser is a Parser that will match a set of Parsers against a Remnant one after the other.
func (SequenceParser) Parse ¶
func (p SequenceParser) Parse(bs Remnant) StateSet
Parse applies every element in a sequence to a remnant, in order.
If all possible branches of a sequence application fail, a set of all rejected states will be returned; a set of accepted and continuead states otherwise.
type State ¶
type State struct {
Remnant Remnant
Parser Parser
Value interface{}
// contains filtered or unexported fields
}
A State represents a step in the parsing process. It can be either accepted, rejected or continued, meaning that either it matched an input, didn't match an input or has yet to match an input, respectively.
If a State is accepted or rejected, its Parser field will be nil and its Value field not nil. The opposite otherwise.
A State can be accepted or rejected even if it has a non-empty Remnant.
type StateSet ¶
type StateSet struct {
// contains filtered or unexported fields
}
A StateSet represents a set of States.
func NewStateSet ¶
NewStateSet returns a new StateSet, containing all States optionally passed to it.