parser

package
v0.5.0 Latest Latest
Warning

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

Go to latest
Published: Oct 31, 2020 License: Apache-2.0 Imports: 6 Imported by: 0

Documentation

Overview

Package parser is a subpackage of ptk that contains the Parser, which implements parsing using the Pratt recursive descent technique, along with related support types and code such as Node. A parser can be queried to extract expressions and statements from a lexer; generally, a parser takes a lexer and builds up an abstract syntax tree from the tokens generated by the lexer.

Index

Constants

This section is empty.

Variables

View Source
var (
	ErrExpectedToken    = errors.New("No tokens available")
	ErrUnknownTokenType = errors.New("Unknown token type")
	ErrUnexpectedToken  = errors.New("Unexpected token")
	ErrNoTable          = errors.New("Programming error: Parse table missing")
)

Simple errors that may be generated within the package.

View Source
var Literal = ExprFirst(literal)

Literal is an ExprFirst function for literal tokens. It may be used directly to initialize a First field in an Entry. The implementation of Literal is trivial: it simply returns the token wrapped in a TokenNode.

Functions

func ExpectedToken

func ExpectedToken(types ...string) error

ExpectedToken constructs and returns an ErrExpectedToken. Its optional arguments are a list of token types, which are expressed as strings; these will be used to generate an error message explaining what token types are expected.

func UnexpectedToken

func UnexpectedToken(tok *lexer.Token, types ...string) error

UnexpectedToken cunstructs and returns an ErrUnexpectedToken, given a token. It may also be passed additional arguments, which are interpreted as token types; these will be used to generate an error message explaining what token types are expected.

func UnknownTokenType

func UnknownTokenType(tok *lexer.Token, types ...string) error

UnknownTokenType constructs and returns an ErrUnknownTokenType, given a token. It may also be passed additional arguments, which are interpreted as token types; these will be used to generate an error message explaining what token types are expected.

Types

type AnnotatedNode added in v0.5.0

type AnnotatedNode struct {
	Node       Node   // The wrapped node
	Annotation string // The annotation text
}

AnnotatedNode is a wrapper for Node that implements Node. The Location and String calls are proxied through, but the String method includes a specified annotation. This is used to allow attaching annotations to the string representations of nodes for the purposes of visualizing the AST.

func NewAnnotatedNode added in v0.5.0

func NewAnnotatedNode(node Node, annotation string) *AnnotatedNode

NewAnnotatedNode returns a new AnnotatedNode wrapping a given node with the specified annotation.

func (*AnnotatedNode) Children added in v0.5.0

func (an *AnnotatedNode) Children() []Node

Children returns a list of child nodes.

func (*AnnotatedNode) Location added in v0.5.0

func (an *AnnotatedNode) Location() scanner.Location

Location returns the node's location range.

func (*AnnotatedNode) String added in v0.5.0

func (an *AnnotatedNode) String() string

String returns a string describing the node. This should include the location range that encompasses all of the node's tokens.

type BaseState added in v0.5.0

type BaseState struct {
	Tab Table // The table for the parse
}

BaseState is a basic implementation of the State interface. It assumes a fixed Table for the lifetime of the parser's operation.

func (*BaseState) Table added in v0.5.0

func (bs *BaseState) Table() Table

Table must return the parser table to use. It is safe for the application to return different Table implementations depending on the parser state.

type BinaryOperator added in v0.5.0

type BinaryOperator struct {
	Loc scanner.Location // The location of the expression
	Op  *lexer.Token     // The unary operator
	L   Node             // The left-hand side expression
	R   Node             // The right-hand side expression
}

BinaryOperator is a Node implementation that describes the use of a binary operator, e.g., "*".

func (*BinaryOperator) Children added in v0.5.0

func (b *BinaryOperator) Children() []Node

Children returns a list of child nodes.

func (*BinaryOperator) Location added in v0.5.0

func (b *BinaryOperator) Location() scanner.Location

Location returns the node's location range.

func (*BinaryOperator) String added in v0.5.0

func (b *BinaryOperator) String() string

String returns a string describing the node. This should include the location range that encompasses all of the node's tokens.

type Entry

type Entry struct {
	Power int       // The binding power of the token type
	First ExprFirst // The function to call for an initial token
	Next  ExprNext  // The function to call for the next token
	Stmt  Statement // The function to call for statement tokens
}

Entry is an entry in the parser table. The Pratt technique is table driven, based on the token type; objects of this type contain a single entry from the table.

type ExprFirst

type ExprFirst func(parser *Parser, power int, tok *lexer.Token) (Node, error)

ExprFirst functions are called to process the first token in an expression. Functions of this type are typically declared on literal tokens or prefix operators.

func Prefix added in v0.5.0

func Prefix(factory func(p *Parser, op *lexer.Token, exp Node) (Node, error), power int) ExprFirst

Prefix constructs an ExprFirst function for prefix operators, e.g., "+" or "-" when used directly before a token--that is, not in a binary operator context. For example, "+123" or "-12". The Prefix function should be passed a "factory" function that constructs a Node; this function will be called with the token representing the operator and the expression to the right of the operator. It should also be called with a binding power; typically, this binding power will be higher than the binding power for the same operator as a binary operator, which is why it is separate from the Entry.

type ExprNext

type ExprNext func(parser *Parser, power int, left Node, tok *lexer.Token) (Node, error)

ExprNext functions are called to process the subsequent tokens in an expression. Functions of this type are typically declared with a "left binding power" (a measure of how tightly an operator binds to its operands), and are used with binary operators.

func Infix added in v0.5.0

func Infix(factory func(p *Parser, l, r Node, op *lexer.Token) (Node, error)) ExprNext

Infix constructs an ExprNext function for infix-style binary operators, e.g., "+", "*", etc. These operators are left-associative; that is, an expression like "1 + 2 + 3" is equivalent to "(1 + 2) + 3". The Infix function should be passed a "factory" function that constructs a Node; this function will be called with the left and right nodes and the token representing the operator.

func InfixR added in v0.5.0

func InfixR(factory func(p *Parser, l, r Node, op *lexer.Token) (Node, error)) ExprNext

InfixR is identical to Infix, with the exception that it is used for right-associative operators, e.g., "**". In this case, an expression like "1 ** 2 ** 3" is equivalent to "1 ** (2 ** 3)". The InfixR should be passed a factory function, which will be called with the left and right nodes and the token representing the operator.

type IPushBackLexer added in v0.5.0

type IPushBackLexer interface {
	lexer.ILexer

	// PushBack pushes a token back into the lexer.  This token
	// will be returned on the next call to the Next method.
	PushBack(tok *lexer.Token)
}

IPushBackLexer is an interface for a lexer supporting push-back of tokens. A token that is pushed back will be returned by the next call to the objects Next method.

type Node added in v0.5.0

type Node interface {
	// Location returns the node's location range.
	Location() scanner.Location

	// Children returns a list of child nodes.
	Children() []Node

	// String returns a string describing the node.  This should
	// include the location range that encompasses all of the
	// node's tokens.
	String() string
}

Node describes one node in an abstract syntax tree.

func BinaryFactory added in v0.5.0

func BinaryFactory(p *Parser, l, r Node, op *lexer.Token) (Node, error)

BinaryFactory is a factory function that may be passed to Infix or InfixR, and which constructs a BinaryOperator node.

func UnaryFactory added in v0.5.0

func UnaryFactory(p *Parser, op *lexer.Token, exp Node) (Node, error)

UnaryFactory is a factory function that may be passed to Prefix, and which constructs a UnaryOperator node.

type Parser

type Parser struct {
	Lexer IPushBackLexer // The lexer providing the tokens
	State State          // The state of the parser
}

Parser is the object that performs parsing; it assembles a sequence of tokens, as presented by the lexer, into an abstract syntax tree.

func New

func New(l lexer.ILexer, state State) *Parser

New constructs a new Parser using the provided lexer and state.

func (*Parser) Expression

func (p *Parser) Expression(rbp int) (Node, error)

Expression parses a single expression from the token stream provided by the lexer. The method will be called with a "right binding power", which should be 0 for consumers of the parser, but will be non-zero when called recursively.

func (*Parser) Statement

func (p *Parser) Statement() (Node, error)

Statement parses a single statement from the token stream provided by the lexer.

type PushBackLexer added in v0.5.0

type PushBackLexer struct {
	Lexer lexer.ILexer // The source lexer
	// contains filtered or unexported fields
}

PushBackLexer is an implementation of lexer.ILexer that includes token push-back capability. A PushBackLexer wraps another lexer.ILexer, but provides an additional method for pushing back tokens that will be returned later.

func NewPushBackLexer added in v0.5.0

func NewPushBackLexer(l lexer.ILexer) *PushBackLexer

NewPushBackLexer wraps another lexer in a PushBackLexer.

func (*PushBackLexer) Next added in v0.5.0

func (pbl *PushBackLexer) Next() *lexer.Token

Next returns the next token. At the end of the lexer, a nil should be returned.

func (*PushBackLexer) PushBack added in v0.5.0

func (pbl *PushBackLexer) PushBack(tok *lexer.Token)

PushBack pushes a token back into the lexer. This token will be returned on the next call to the Next method.

type State

type State interface {
	// Table must return the parser table to use.  It is safe for
	// the application to return different Table implementations
	// depending on the parser state.
	Table() Table
}

State represents the parser state. This is passed to instantiate a new Parser.

type Statement

type Statement func(parser *Parser, tok *lexer.Token) (Node, error)

Statement functions are called to process a statement. They're called with the first token of the statement, and should read in additional tokens.

type Table

type Table map[string]Entry

Table is a table of entries by their token type. The Pratt technique is table driven, based on the token type; objects of this type contain the table.

type TokenNode added in v0.5.0

type TokenNode struct {
	*lexer.Token
}

TokenNode is an implementation of Node that wraps lexer.Token. It provides a default implementation of Children that returns an empty list of child nodes.

func (*TokenNode) Children added in v0.5.0

func (tn *TokenNode) Children() []Node

Children returns a list of child nodes.

type UnaryOperator added in v0.5.0

type UnaryOperator struct {
	Loc scanner.Location // The location of the expression
	Op  *lexer.Token     // The unary operator
	Exp Node             // The expression acted upon
}

UnaryOperator is a Node implementation that describes the use of a unary operator, e.g., "~".

func (*UnaryOperator) Children added in v0.5.0

func (u *UnaryOperator) Children() []Node

Children returns a list of child nodes.

func (*UnaryOperator) Location added in v0.5.0

func (u *UnaryOperator) Location() scanner.Location

Location returns the node's location range.

func (*UnaryOperator) String added in v0.5.0

func (u *UnaryOperator) String() string

String returns a string describing the node. This should include the location range that encompasses all of the node's tokens.

Directories

Path Synopsis
Package visualize contains a Visualize function that may be used to generate a printable tree representation of a nested set of Node instances.
Package visualize contains a Visualize function that may be used to generate a printable tree representation of a nested set of Node instances.

Jump to

Keyboard shortcuts

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