dmg

package module
v0.0.0-...-462ea48 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: May 22, 2015 License: GPL-3.0 Imports: 1 Imported by: 0

README

This project has been abandoned. It's left here for historic purposes.

dmg

Simple and Fast (Generalized) Parsing for Go

Package dmg (pronounced "demagogue") is a parser combinator library for the Go programming language. It is fast, has full support for left-recursive and right-nullable grammars and stands out for its simplicity in design.

Full documentation can be found on http://godoc.org/github.com/thwd/dmg.

It's not quite ready for prime-time yet but it works, and works well so far. There will be more added features in the near future. I'm working on finishing a stable API and will promote it to beta then.

This project contains some original research of mine, built upon the following articles and theses:

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

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func Dissect

func Dissect(p Parser, r Remnant) chan State

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 AnyParser

type AnyParser struct{}

AnyParser is a Parser that accepts any one rune

func (AnyParser) Parse

func (p AnyParser) Parse(bs Remnant) StateSet

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.

func (NotParser) Parse

func (p NotParser) Parse(r Remnant) StateSet

type Parser

type Parser interface {
	Parse(Remnant) StateSet
}

func NewAlternationParser

func NewAlternationParser(ps ...Parser) Parser

NewAlternationParser returns a new AlternationParser. It panics if called with zero arguments.

func NewAnyParser

func NewAnyParser() Parser

func NewEpsilonParser

func NewEpsilonParser() Parser

func NewKleeneParser

func NewKleeneParser(p Parser) Parser

NewKleeneParser returns a Parser that accepts whatever its first argument accepts zero or many times.

func NewLiteralParser

func NewLiteralParser(l string) Parser

func NewMappingParser

func NewMappingParser(p Parser, m func(interface{}) interface{}) Parser

func NewMaybeParser

func NewMaybeParser(p Parser) Parser

NewMaybeParser returns a Parser that accepts either whatever its first argument accepts or the empty string.

func NewMutuallyRecursiveParsers

func NewMutuallyRecursiveParsers(n int, f func([]Parser) []Parser) []Parser

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 NewNotParser(p Parser) Parser

func NewPlusParser

func NewPlusParser(p Parser) Parser

NewPlusParser returns a Parser that accepts whatever its first argument accepts one or many times.

func NewPrependParser

func NewPrependParser(r interface{}, p Parser) Parser

func NewRangeParser

func NewRangeParser(min, max rune) Parser

func NewRecursiveParser

func NewRecursiveParser(f func(Parser) Parser) Parser

NewRecursiveParser passes a pointer to a RecursiveParser to its first argument and defines said RecursiveParser as the result of this operation.

func NewSequenceParser

func NewSequenceParser(ps ...Parser) Parser

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 Remnant

type Remnant []byte

A Remnant represents an input to a 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.

func Accept

func Accept(v interface{}, r Remnant) State

Accept returns a accepted state with Value v and Remnant r

func Continue

func Continue(p Parser, r Remnant) State

Continue returns a continued state with Parser p and Remnant r

func Reject

func Reject(v interface{}, r Remnant) State

Reject returns a rejected state with Value v and Remnant r

func (State) Accepted

func (s State) Accepted() bool

Accepted reports wether a State is accepted.

func (State) Continued

func (s State) Continued() bool

Continued reports wether a State is continued.

func (State) Reduce

func (s State) Reduce() StateSet

Reduce applies a State's Parser to it's Remnant and returns the resulting StateSet.

func (State) Rejected

func (s State) Rejected() bool

Rejected reports wether a State is rejected.

type StateSet

type StateSet struct {
	// contains filtered or unexported fields
}

A StateSet represents a set of States.

func NewStateSet

func NewStateSet(s ...State) StateSet

NewStateSet returns a new StateSet, containing all States optionally passed to it.

func (StateSet) Add

func (s StateSet) Add(n State)

Add adds a State to a StateSet

func (StateSet) Len

func (s StateSet) Len() int

Len reports the amount of elements in a StateSet.

func (StateSet) Map

func (s StateSet) Map(m func(State) State) StateSet

Map executes a mapping function for every State in a StateSet and returns a new StateSet containing the aggregated results of this operation.

func (StateSet) Next

func (s StateSet) Next() State

Next returns the next State in a StateSet.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL