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 ¶
- Variables
- func ExpectedToken(types ...string) error
- func UnexpectedToken(tok *lexer.Token, types ...string) error
- func UnknownTokenType(tok *lexer.Token, types ...string) error
- type AnnotatedNode
- type BaseState
- type BinaryOperator
- type Entry
- type ExprFirst
- type ExprNext
- type IPushBackLexer
- type Node
- type Parser
- type PushBackLexer
- type State
- type Statement
- type Table
- type TokenNode
- type UnaryOperator
Constants ¶
This section is empty.
Variables ¶
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.
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 ¶
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 ¶
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 ¶
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.
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 ¶
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
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 ¶
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
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
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
BinaryFactory is a factory function that may be passed to Infix or InfixR, and which constructs a BinaryOperator 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 (*Parser) Expression ¶
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.
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 ¶
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 ¶
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
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.
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.
Source Files ¶
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. |