parser

Documentation

Overview

Package grammar provides data types and algorithms for building parsers.

A parser generally relies on a lexer (also known as a lexical analyzer or scanner) to process a stream of tokens. Lexical analysis (scanning) is distinct from syntax analysis (parsing): lexical analysis deals with regular languages and grammars (Type 3), while syntax analysis deals with context-free languages and grammars (Type 2).

Index

• Variables
• func Traverse(n Node, order generic.TraverseOrder, visit generic.VisitFunc1[Node]) bool
• type InternalNode
  • func (n *InternalNode) Annotate(val any)
  • func (n *InternalNode) Annotation() any
  • func (n *InternalNode) DOT() string
  • func (n *InternalNode) Equal(rhs Node) bool
  • func (n *InternalNode) Pos() lexer.Position
  • func (n *InternalNode) String() string
  • func (n *InternalNode) Symbol() grammar.Symbol
• type LeafNode
  • func (n *LeafNode) Annotate(val any)
  • func (n *LeafNode) Annotation() any
  • func (n *LeafNode) Equal(rhs Node) bool
  • func (n *LeafNode) Pos() lexer.Position
  • func (n *LeafNode) String() string
  • func (n *LeafNode) Symbol() grammar.Symbol
• type Node
• type ParseError
  • func (e *ParseError) Error() string
  • func (e *ParseError) Unwrap() error
• type Parser
• type ProductionFunc
• type TokenFunc

Variables

var (
	EqNode = func(lhs, rhs Node) bool {
		return lhs.Equal(rhs)
	}
)

Functions

func Traverse

func Traverse(n Node, order generic.TraverseOrder, visit generic.VisitFunc1[Node]) bool

Traverse performs a depth-first traversal of an abstract syntax tree (AST), starting from the given root node. It visits each node according to the specified traversal order and passes each node to the provided visit function. If the visit function returns false, the traversal is stopped early.

Valid traversal orders for an AST are VLR, VRL, LRV, and RLV.

Types

type InternalNode

type InternalNode struct {
	NonTerminal grammar.NonTerminal
	Production  *grammar.Production
	Children    []Node
	// contains filtered or unexported fields
}

InternalNode represents an internal node in an abstract syntax tree (AST). An InternalNode represents a non-terminal symbol and its associated production rule.

func (*InternalNode) Annotate

func (n *InternalNode) Annotate(val any)

Annotate associates an annotation with this internal node. An annotation often represents the node in a different context or type.

Common use cases include:

• Storing the result of a type conversion (e.g., converting a string to a number).
• Capturing the outcome of evaluating the right-hand side of a production rule (e.g., performing an arithmetic operation like addition).
• Adding metadata or auxiliary information related to the node.

func (*InternalNode) Annotation

func (n *InternalNode) Annotation() any

Annotation returns the annotation associated with this internal node. An annotation is a context-specific value of any type, set using the Annotate method.

The caller should cast the returned value to the original type used when annotating.

func (*InternalNode) DOT

func (n *InternalNode) DOT() string

DOT generates and returns a representation of an internal node and all its descendants in DOT format. This format is commonly used for visualizing graphs with Graphviz tools.

func (*InternalNode) Equal

func (n *InternalNode) Equal(rhs Node) bool

Equal determines whether or not two internal nodes are the same. Annotations are excluded from the equality check.

func (*InternalNode) Pos

func (n *InternalNode) Pos() lexer.Position

Pos returns the position of the first child of this internal node.

func (*InternalNode) String

func (n *InternalNode) String() string

String returns a string representation of an internal node.

func (*InternalNode) Symbol

func (n *InternalNode) Symbol() grammar.Symbol

Symbol returns the non-terminal symbol associated with this internal node (the left-hand side of the production rule represented by the node).

type LeafNode

type LeafNode struct {
	Terminal grammar.Terminal
	Lexeme   string
	Position lexer.Position
	// contains filtered or unexported fields
}

LeafNode represents a leaf node in an abstract syntax tree (AST). A LeafNode represents a terminal symbol.

func (*LeafNode) Annotate

func (n *LeafNode) Annotate(val any)

Annotate associates an annotation with this leaf node. An annotation often represents the node in a different context or type.

Common use cases include:

• Storing the result of a type conversion (e.g., converting a string to a number).
• Associating a reference to a symbol table entry for an identifier.
• Adding metadata or auxiliary information related to the node.

func (*LeafNode) Annotation

func (n *LeafNode) Annotation() any

Annotation returns the annotation associated with this leaf node. An annotation is a context-specific value of any type, set using the Annotate method.

The caller should cast the returned value to the original type used when annotating.

func (*LeafNode) Equal

func (n *LeafNode) Equal(rhs Node) bool

Equal determines whether or not two leaf nodes are the same. Annotations are excluded from the equality check.

func (*LeafNode) Pos

func (n *LeafNode) Pos() lexer.Position

Pos returns the position of the substring represented by this leaf node in the input string.

func (*LeafNode) String

func (n *LeafNode) String() string

String returns a string representation of a leaf node.

func (*LeafNode) Symbol

func (n *LeafNode) Symbol() grammar.Symbol

Symbol returns the terminal symbol associated with this leaf node.

type Node

type Node interface {
	fmt.Stringer
	generic.Equaler[Node]

	// Symbol returns the grammar symbol associated with this node.
	// For internal nodes, this is a non-terminal symbol
	// (the left-hand side of the production rule represented by the node).
	// For leaf nodes, this is a terminal symbol.
	Symbol() grammar.Symbol

	// Pos returns the leftmost position in the input string that this node represent.
	Pos() lexer.Position

	// Annotate associates an annotation with this node.
	// An annotation often represents the node in a different context or type.
	//
	// Common use cases include:
	//
	//   - Storing the result of a type conversion (e.g., converting a string to a number).
	//   - Capturing the outcome of evaluating the right-hand side of a production rule
	//     (e.g., performing an arithmetic operation like addition).
	//   - Associating a reference to a symbol table entry for an identifier.
	//   - Adding metadata or auxiliary information related to the node.
	Annotate(any)

	// Annotation returns the annotation associated with this node.
	// An annotation is a context-specific value of any type, set using the Annotate method.
	//
	// The caller should cast the returned value to the original type used when annotating.
	Annotation() any
}

Node represents a node in an abstract syntax tree (AST) derived from an input string allowed based on a context-free grammar.

Each node can be either:

• An internal node: representing a non-terminal symbol and its associated production rule.
• A leaf node: representing a terminal symbol.

type ParseError

type ParseError struct {
	Description string
	Cause       error
	Pos         lexer.Position
}

ParseError represents an error encountered when parsing an input string.

func (*ParseError) Error

func (e *ParseError) Error() string

Error implements the error interface. It returns a formatted string describing the error in detail.

func (*ParseError) Unwrap

func (e *ParseError) Unwrap() error

Unwrap implements the unwrap interface.

type Parser

type Parser interface {
	// Parse analyzes a sequence of input tokens (terminal symbols) provided by a lexical analyzer.
	// It attempts to parse the input according to the production rules of a context-free grammar,
	// determining whether the input string belongs to the language defined by the grammar.
	//
	// The Parse method invokes the provided functions each time a token or a production rule is matched.
	// This allows the caller to process or react to each step of the parsing process.
	//
	// An error is returned if the input fails to conform to the grammar rules, indicating a syntax issue,
	// or if any of the provided functions return an error, indicating a semantic issue.
	Parse(TokenFunc, ProductionFunc) error

	// ParseAndBuildAST analyzes a sequence of input tokens (terminal symbols) provided by a lexical analyzer.
	// It attempts to parse the input according to the production rules of a context-free grammar,
	// constructing an abstract syntax tree (AST) that reflects the structure of the input.
	//
	// If the input string is valid, the root node of the AST is returned,
	// representing the syntactic structure of the input string.
	//
	// An error is returned if the input fails to conform to the grammar rules, indicating a syntax issue.
	ParseAndBuildAST() (Node, error)
}

Parser defines the interface for a syntax analyzer that processes input tokens.

type ProductionFunc

type ProductionFunc func(*grammar.Production) error

ProductionFunc is a function that is invoked each time a production rule is matched or applied during the parsing process of an input string. It executes the actions associated with the matched production rule, such as semantic processing, constructing abstract syntax trees (AST), or performing other custom logic required for the parsing process.

The function may return an error, indicating an issue during production rule processing. Whether the parser stops immediately or continues parsing while accumulating errors depends on the parser's implementation.

type TokenFunc

type TokenFunc func(*lexer.Token) error

TokenFunc is a function that is invoked each time a token is matched and removed from an input string during parsing. It executes the actions associated with the matched token, such as semantic processing, constructing abstract syntax trees (AST), or performing other custom logic required for the parsing process.

The function may return an error, indicating an issue during token processing. Whether the parser stops immediately or continues parsing while accumulating errors depends on the parser's implementation.