combinator

Documentation

Overview

Package combinator is a parser combinator library.

Index

• type Conditional
• type Error
  • func NewError(msg string, from, to int) *Error
  • func (e *Error) Error() string
  • func (e *Error) From() int
  • func (e *Error) Message() string
  • func (e *Error) To() int
• type Lexer
• type Node
• type Parser
  • func Accept(p func(Token) bool, msg string, wrp TokenWrapper) Parser
  • func And(a, b Parser) Parser
  • func Any(a Conditional) Parser
  • func Assert(p Parser) Parser
  • func Choose(choices ...Conditional) Parser
  • func Drop(p Parser) Parser
  • func Fmap(f func([]Node) []Node, p Parser) Parser
  • func Not(p Parser) Parser
  • func Ok() Parser
  • func OneOf(args ...Parser) Parser
  • func SeparatedBy(a, b Parser) Parser
  • func Seq(args ...Parser) Parser
  • func SurroundedBy(a, b, c Parser) Parser
• type RollbackLexer
• type Token
• type TokenWrapper
• type Transaction

Types

type Conditional

type Conditional struct {
	Gate      Parser // Gate gates Choose and Any from using Success if Predicate fails
	OnSuccess Parser // OnSuccess is the parser that runs after gate succeeds
}

Conditional is a pair of parsers. Once Gate succeeds we don't roll back but we are committed to parse with OnSuccess.

Conditional is meant to solve the following problem.

OneOf is much simpler and simpler to use than Choose. However in the following language there is a problem.

S -> Ax
A -> OneOf(B, C)
B -> qbcd
C -> q

qbczx is the input text, here using rule B was intended, giving the error that z doesn't match expected d. However in OneOf C matches, so in rule A there is no error. Rule S fails q (from rule C) is not followed by x, rolling back bcz part of the input. The reported error gets far from the actual error character.

Do this instead:

S -> Ax
A -> Choose( Cond{G: qb, S: cd }, Cond{ G: Ok(), S : q } )

Assuming choice rules can have identifying prefixes.

type Error

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

Error indicates an error in the input source code.

func NewError

func NewError(msg string, from, to int) *Error

func (*Error) Error

func (e *Error) Error() string

func (*Error) From

func (e *Error) From() int

From points to the starting position of the token in the buffer.

func (*Error) Message

func (e *Error) Message() string

Message describes the error.

func (*Error) To

func (e *Error) To() int

To points to the ending position of the token in the buffer.

type Lexer

type Lexer interface {
	From() int
	To() int
	Next() bool   // Is there a next token
	Err() error   // signal lexing error
	Token() Token // The next Token
}

Lexer produces a stream of tokens. Next() advances the lexer and returns true until all tokens are returned. Err() and Token() do not modify the lexer and start returning values after the first Next() call.

type Node

type Node any

Node is an AST node, with pointers to sub-tree nodes and potentially some parse information data.

type Parser

type Parser func(input RollbackLexer) ([]Node, *Error)

Parser accepts input and returns sequence of parsed nodes or error.

It's the users responsibility to combine compound nodes into one, ie. the sub-parser results can be combined into a Node that has tree pointers to the sub expressions.

func Accept

func Accept(p func(Token) bool, msg string, wrp TokenWrapper) Parser

Accept asserts the next token

given a predicate p on a lexer Token, parses successfully if the predicate is true for the next token provided by l, and then returns the node holding that token. If p is false or the lexer fails then Accept fails.

func And

func And(a, b Parser) Parser

And is sequencing two parsers

Parses with a and then continues parsing with b. Only succeeds if both a and b succeed and returns the concatenated result from both a and b.

func Any

func Any(a Conditional) Parser

Any parses with 0 or more execution of a

It tries parsing with predicate and if that succeeds it commits to go one more step with success. The predicate failing is rolled back automatically. The succeeding predicate result is concatenated with the result

If the rule doesn't have a meaningful prefix to condition on, one can place the rule in the gate, and just use Ok() for OnSuccess. This gives a behaviour where failures are rolled back.

func Assert

func Assert(p Parser) Parser

Assert asserts the given parser p would succeed without consuming input. It returns empty parse result.

func Choose

func Choose(choices ...Conditional) Parser

Choose is a choice between many parsers

It uses Conditionals, asserting that the Gate succeeds and if so it commits to parsing with OnSuccess part of choice. It rolls back a failing Predicate automatically. A succeeding predicate will be prepended to the result of success.

func Drop

func Drop(p Parser) Parser

Drop drops the result of p.

func Fmap

func Fmap(f func([]Node) []Node, p Parser) Parser

Fmap maps f : []Node -> []Node function on parser p.

Returns a modified version of p that succeeds when p succeeds but if p returns r the modified version returns f(r).

func Not

func Not(p Parser) Parser

Not asserts that the given parser p will fail.

func Ok

func Ok() Parser

Ok is a parser that doesn't do anything just returns a successful parse result.

func OneOf

func OneOf(args ...Parser) Parser

OneOf is a choice between many parsers

It tries each parser in turn, rolling back the input after each failed attempt It is meant to be used with terminal rules only, for complex language rules prefer Choose because it gives much closer syntax errors to the actual error location.

func SeparatedBy

func SeparatedBy(a, b Parser) Parser

SeparatedBy parses with a sequence of a, separated by b.

It never fails, but result might be empty. It asserts that a sequence of a is interspersed with b, the sequence not ending with b. The parse results of b are thrown away, it returns the sequenced results of a.

func Seq

func Seq(args ...Parser) Parser

Seq is sequencing many parsers

Parses with a sequence of parsers, returns the concatenated result from all if all are successful. Fails if any of the parsers fail.

func SurroundedBy

func SurroundedBy(a, b, c Parser) Parser

SurroundedBy parses with a sequence of a, b, c but returns the parse result of b only

It fails if any of a, b, c fails. Useful for asserting parenthesis style rules.

type RollbackLexer

type RollbackLexer interface {
	Lexer
	Transaction
}

type Token

type Token interface {
	From() int
	To() int
}

Token represents a lexeme from a lexer.

type TokenWrapper

type TokenWrapper interface {
	Wrap(Token) Node
}

TokenWrapper wraps a token in a single AST node containing the token.

type Transaction

type Transaction interface {
	Snapshot() // Push current state on a stack so it can be recovered
	Rollback() // Recover last state that was pushed
	// Commit state. After commit the previous snapshot point is removed, the
	// next Rollback returns to the snapshot prior to that
	Commit()
}

It's expected to be stack based just like a database transaction.