Grammar

package
v0.1.19 Latest Latest
Warning

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

 Go to latest Published: Jul 15, 2024 License: MIT Imports: 11 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	// LeftToRight is the direction of a production from left to right.
	LeftToRight string = "->"

	// ArrowLen is the length of the arrow.
	ArrowLen int = 2

	// StartSymbolID is the identifier of the start symbol in the grammar.
	StartSymbolID string = "source"

	// EpsilonSymbolID is the identifier of the epsilon symbol in the grammar.
	EpsilonSymbolID string = "ε"
)
View Source 
const (
	// EOFTokenID is the identifier of the end-of-file token.
	EOFTokenID string = "EOF"
)

Variables

This section is empty.

Functions

func Ast added in v0.1.19 

func Ast[N Noder, T TokenTyper](f AstRecFunc[N, T], tok *Token[T]) (N, error)

Ast generates the AST.

Parameters:

  • f: The function to recursively extract sub nodes.
  • token: The token.

Returns:

  • N: The root node.
  • error: An error if the AST generation fails.

func ExtractSubNodes added in v0.1.19 

func ExtractSubNodes[N Noder, T TokenTyper](f AstRecFunc[N, T], tok *Token[T]) ([]N, bool)

ExtractSubNodes is a helper function to extract sub nodes.

Parameters:

  • f: The function to recursively extract sub nodes.
  • tok: The token.

Returns:

  • []*Node: The sub nodes. Nil if there are no sub nodes.
  • bool: True if the function succeeds. (i.e., tok.Data is a []*Token[T])

Behaviors:

  • If the function is nil or tok is nil, the function will return nil and true.

func LinkParent added in v0.1.19 

func LinkParent[T Noder](parent T, children []T)

LinkParent links the parent to the children.

Parameters:

  • parent: The parent.
  • children: The children.

func LinkSubNodes added in v0.1.19 

func LinkSubNodes[T Noder](sub_nodes []T)

LinkSubNodes links the sub nodes.

Parameters:

  • sub_nodes: The sub nodes.

Types

type AstRecFunc added in v0.1.19 

type AstRecFunc[N Noder, T TokenTyper] func(tok *Token[T]) []N

AstRecFunc is a function to recursively extract sub nodes.

Parameters:

  • tok: The token.

Returns:

  • []N: The sub nodes. Nil if there are no sub nodes.

type ErrCycleDetected added in v0.1.12 

type ErrCycleDetected struct{}

ErrCycleDetected is an error that is returned when a cycle is detected.

func NewErrCycleDetected added in v0.1.12 

func NewErrCycleDetected() *ErrCycleDetected

NewErrCycleDetected creates a new error of type *ErrCycleDetected.

Returns:

  • *ErrCycleDetected: The new error.

func (*ErrCycleDetected) Error added in v0.1.12 

func (e *ErrCycleDetected) Error() string

Error implements the error interface.

Message: "cycle detected".

type ErrLhsRhsMismatch added in v0.1.8 

type ErrLhsRhsMismatch struct {
	// Lhs is the left-hand side of the production rule.
	Lhs string

	// Rhs is the right-hand side of the production rule.
	Rhs string
}

ErrLhsRhsMismatch is an error that is returned when the lhs of a production rule does not match the rhs.

func NewErrLhsRhsMismatch added in v0.1.8 

func NewErrLhsRhsMismatch(lhs, rhs string) *ErrLhsRhsMismatch

NewErrLhsRhsMismatch creates a new error of type *ErrLhsRhsMismatch.

Parameters:

  • lhs: The left-hand side of the production rule.
  • rhs: The right-hand side of the production rule.

Returns:

  • *ErrLhsRhsMismatch: The new error.

func (*ErrLhsRhsMismatch) Error added in v0.1.8 

func (e *ErrLhsRhsMismatch) Error() string

Error implements the error interface.

Message: "lhs of production rule (lhs) does not match rhs (rhs)".

type ErrMissingArrow added in v0.1.11 

type ErrMissingArrow struct{}

ErrMissingArrow is an error that is returned when an arrow is missing in a rule.

func NewErrMissingArrow added in v0.1.11 

func NewErrMissingArrow() *ErrMissingArrow

NewErrMissingArrow creates a new error of type *ErrMissingArrow.

Returns:

  • *ErrMissingArrow: The new error.

func (*ErrMissingArrow) Error added in v0.1.11 

func (e *ErrMissingArrow) Error() string

Error implements the error interface.

Message: "missing arrow in rule".

type ErrNoLHSFound added in v0.1.11 

type ErrNoLHSFound struct{}

ErrNoLHSFound is an error that is returned when no left-hand side is found in a rule.

func NewErrNoLHSFound added in v0.1.11 

func NewErrNoLHSFound() *ErrNoLHSFound

NewErrNoLHSFound creates a new error of type *ErrNoLHSFound.

Returns:

  • *ErrNoLHSFound: The new error.

func (*ErrNoLHSFound) Error added in v0.1.11 

func (e *ErrNoLHSFound) Error() string

Error implements the error interface.

Message: "no left-hand side in rule".

type ErrNoProductionRulesFound added in v0.1.8 

type ErrNoProductionRulesFound struct{}

ErrNoProductionRulesFound is an error that is returned when no production rules are found in a grammar.

func NewErrNoProductionRulesFound added in v0.1.8 

func NewErrNoProductionRulesFound() *ErrNoProductionRulesFound

NewErrNoProductionRulesFound creates a new error of type *ErrNoProductionRulesFound.

Returns:

  • *ErrNoProductionRulesFound: The new error.

func (*ErrNoProductionRulesFound) Error added in v0.1.8 

func (e *ErrNoProductionRulesFound) Error() string

Error implements the error interface.

Message: "no production rules found".

type ErrNoRHSFound added in v0.1.11 

type ErrNoRHSFound struct{}

ErrNoRHSFound is an error that is returned when no right-hand side is found in a rule.

func NewErrNoRHSFound added in v0.1.11 

func NewErrNoRHSFound() *ErrNoRHSFound

NewErrNoRHSFound creates a new error of type *ErrNoRHSFound.

Returns:

  • *ErrNoRHSFound: The new error.

func (*ErrNoRHSFound) Error added in v0.1.11 

func (e *ErrNoRHSFound) Error() string

Error implements the error interface.

Message: "no right-hand side in rule".

type MatchedResult 

type MatchedResult[T TokenTyper] struct {
	// Matched is the matched token.
	Matched *Token[T]

	// RuleIndex is the index of the production that matched.
	RuleIndex int
}

MatchedResult represents the result of a match operation.

func NewMatchResult 

func NewMatchResult[T TokenTyper](matched *Token[T], ruleIndex int) *MatchedResult[T]

NewMatchResult is a constructor of MatchedResult.

Parameters:

  • matched: The matched token.
  • ruleIndex: The index of the production that matched.

Returns:

  • *MatchedResult: A new MatchedResult.

type Noder added in v0.1.19 

type Noder interface {
	// SetParent sets the parent.
	//
	// Parameters:
	//   - n: The parent. Never nil.
	SetParent(n Noder)

	// SetFirstChild sets the first child.
	//
	// This should also set the parent of the first child.
	//
	// Parameters:
	//   - n: The first child. Never nil.
	SetFirstChild(n Noder)

	// SetLastChild sets the last child.
	//
	// This should also set the parent of the last child.
	//
	// Parameters:
	//   - n: The last child. Never nil.
	SetLastChild(n Noder)

	// SetNextSibling sets the next sibling.
	//
	// This should also set the previous sibling of the next sibling (if any).
	//
	// Parameters:
	//   - n: The next sibling. Never nil.
	SetNextSibling(n Noder)
}

Noder is an interface for a node.

type Production 

type Production[T TokenTyper] struct {
	// contains filtered or unexported fields
}

Production represents a production in a grammar.

func NewProduction 

func NewProduction[T TokenTyper](lhs T, rhss []T) *Production[T]

NewProduction is a function that returns a new Production with the given left-hand side and right-hand side.

Parameters:

  • lhs: The left-hand side of the production.
  • rhss: The right-hand side of the production.

Returns:

  • *Production: A new Production with the given left-hand side and right-hand side.

func (*Production[T]) Copy 

func (p *Production[T]) Copy() uc.Copier

Copy implements the common.Copier interface.

func (*Production[T]) Equals 

func (p *Production[T]) Equals(other uc.Equaler) bool

Equals implements the common.Equaler interface.

Two productions are equal if their left-hand sides are equal and their right-hand sides are equal.

func (*Production[T]) GetLhs 

func (p *Production[T]) GetLhs() T

GetLhs is a method of Production that returns the left-hand side of the production.

Returns:

  • T: The left-hand side of the production.

func (*Production[T]) GetRhsAt 

func (p *Production[T]) GetRhsAt(index int) (T, error)

GetRhsAt is a method of Production that returns the symbol at the given index in the right-hand side of the production.

Parameters:

  • index: The index of the symbol to get.

Returns:

  • T: The symbol at the given index in the right-hand side of the production.
  • error: An error of type *ErrInvalidParameter if the index is invalid.

func (*Production[T]) GetSymbols 

func (p *Production[T]) GetSymbols() []T

GetSymbols is a method of Production that returns a slice of symbols in the production. The slice contains the left-hand side of the production and the right-hand side of the production, with no duplicates.

Returns:

  • []string: A slice of symbols in the production.

func (*Production[T]) HasRhs added in v0.1.8 

func (p *Production[T]) HasRhs(rhs T) bool

HasRhs is a method of Production that returns whether the right-hand side of the production contains the given symbol.

Parameters:

  • rhs: The symbol to check for.

Returns:

  • bool: Whether the right-hand side of the production contains the given symbol.

func (*Production[T]) IndicesOfRhs added in v0.1.8 

func (p *Production[T]) IndicesOfRhs(rhs T) []int

IndicesOfRhs is a method of Production that returns the indices of the symbol in the right-hand side of the production.

Parameters:

  • rhs: The symbol to find the index of.

Returns:

  • []int: The indices of the symbol in the right-hand side of the production.

func (*Production[T]) Iterator 

func (p *Production[T]) Iterator() uc.Iterater[T]

Iterator implements the common.Iterater interface.

It scans the right-hand side of the production from left to right.

func (*Production[T]) Match 

func (p *Production[T]) Match(at int, stack *ud.History[lls.Stacker[*Token[T]]]) (*Token[T], error)

Match is a method of Production that returns a token that matches the production in the given stack. The token is a non-leaf token if the production is a non-terminal production, and a leaf token if the production is a terminal production.

Parameters:

  • at: The current index in the input stack.
  • stack: The stack to match the production against.

Returns:

  • Token: A token that matches the production in the stack.

Information:

  • 'at' is the current index where the match is being attempted. It is used by the lexer to specify the position of the token in the input string. In parsers, however, it is not really used (at = 0). Despite that, it can be used to provide additional information to the parser for error reporting or debugging.

func (*Production[T]) ReplaceRhsAt added in v0.1.8 

func (p *Production[T]) ReplaceRhsAt(index int, rhs T) *Production[T]

ReplaceRhsAt is a method of Production that replaces the symbol at the given index in the right-hand side of the production with the right-hand side of another production.

Parameters:

  • index: The index of the symbol to replace.
  • otherP: The other production to replace the symbol with.

Returns:

  • *Production: A new production with the symbol at the given index replaced with the right-hand side of the other production.
  • error: An error if the index is invalid or the other production is nil.

Errors:

  • *uc.ErrInvalidParameter: If the index is invalid or the other production is nil.
  • *ErrLhsRhsMismatch: If the left-hand side of the other production does not match the symbol at the given index in the right-hand side of the production.

func (*Production[T]) ReverseIterator 

func (p *Production[T]) ReverseIterator() uc.Iterater[T]

ReverseIterator is a method of Production that returns a reverse iterator for the production that iterates over the right-hand side of the production in reverse.

Returns:

  • uc.Iterater[T]: A reverse iterator for the production.

func (*Production[T]) Size 

func (p *Production[T]) Size() int

Size is a method of Production that returns the number of symbols in the right-hand side of the production.

Returns:

  • int: The number of symbols in the right-hand side of the production.

func (*Production[T]) String 

func (p *Production[T]) String() string

String implements the fmt.Stringer interface.

func (*Production[T]) SubstituteRhsAt added in v0.1.10 

func (p *Production[T]) SubstituteRhsAt(index int, other_p *Production[T]) *Production[T]

ReplaceRhsAt is a method of Production that replaces the symbol at the given index in the right-hand side of the production with the right-hand side of another production.

Parameters:

  • index: The index of the symbol to replace.
  • otherP: The other production to replace the symbol with.

Returns:

  • *Production: A new production with the symbol at the given index replaced with the right-hand side of the other production.
  • error: An error if the index is invalid or the other production is nil.

Errors:

  • *uc.ErrInvalidParameter: If the index is invalid or the other production is nil.
  • *ErrLhsRhsMismatch: If the left-hand side of the other production does not match the symbol at the given index in the right-hand side of the production.

type RegProduction 

type RegProduction[T TokenTyper] struct {
	// contains filtered or unexported fields
}

RegProduction represents a production in a grammar that matches a regular expression.

func NewRegProduction 

func NewRegProduction[T TokenTyper](lhs T, regex string) *RegProduction[T]

NewRegProduction is a function that returns a new RegProduction with the given left-hand side and regular expression.

It adds the '^' character to the beginning of the regular expression to match the beginning of the input string.

Parameters:

  • lhs: The left-hand side of the production.
  • regex: The regular expression to match the right-hand side of the production.

Returns:

  • *RegProduction: A new RegProduction with the given left-hand side and regular expression.

Information:

  • Must call Compile() on the returned RegProduction to compile the regular expression.

func (*RegProduction[T]) Compile 

func (r *RegProduction[T]) Compile() error

Compile is a method of RegProduction that compiles the regular expression of the production.

Returns:

  • error: An error if the regular expression cannot be compiled.

func (*RegProduction[T]) Copy 

func (p *RegProduction[T]) Copy() uc.Copier

Copy implements the common.Copier interface.

func (*RegProduction[T]) Equals 

func (p *RegProduction[T]) Equals(other uc.Equaler) bool

Equals implements the common.Equaler interface.

Two productions are equal if their left-hand sides are equal and their right-hand sides are equal.

func (*RegProduction[T]) GetLhs 

func (p *RegProduction[T]) GetLhs() T

GetLhs is a method of RegProduction that returns the left-hand side of the production.

Returns:

  • T: The left-hand side of the production.

func (*RegProduction[T]) GetSymbols 

func (p *RegProduction[T]) GetSymbols() []T

GetSymbols is a method of RegProduction that returns a slice of symbols in the production. The slice contains the left-hand side of the production.

Returns:

  • []T: A slice of symbols in the production.

func (*RegProduction[T]) GoString added in v0.1.11 

func (r *RegProduction[T]) GoString() string

GoString implements the fmt.GoStringer interface.

func (*RegProduction[T]) MatchRegProd added in v0.1.19 

func (p *RegProduction[T]) MatchRegProd(at int, b []byte) (*Token[T], bool)

Match is a method of RegProduction that returns a token that matches the production in the given stack. The token is a non-leaf token if the production is a non-terminal production, and a leaf token if the production is a terminal production.

Parameters:

  • at: The current index in the input stack.
  • b: The slice of bytes to match the production against.

Returns:

  • Token: A token that matches the production in the stack.
  • bool: True if the production matches the input stack, false otherwise.

type TTInfo added in v0.1.12 

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

TTInfo is the information about the token tree.

func NewTTInfo added in v0.1.12 

func NewTTInfo(root tn.Noder) (*TTInfo, error)

NewTTInfo creates a new TTInfo.

Parameters:

  • root: The root of the token tree.

Returns:

  • *TTInfo: The new TTInfo.
  • error: An error of type *uc.ErrInvalidParameter if the root is nil.

Behaviors:

  • The depth of the root is set to 0.

func (*TTInfo) Copy added in v0.1.12 

func (tti *TTInfo) Copy() uc.Copier

Copy creates a copy of the TTInfo.

Returns:

  • uc.Copier: A copy of the TTInfo.

func (*TTInfo) GetDepth added in v0.1.12 

func (tti *TTInfo) GetDepth(Token tn.Noder) (int, bool)

GetDepth gets the depth of the Token.

Parameters:

  • Token: The Token to get the depth of.

Returns:

  • int: The depth of the Token.
  • bool: True if the depth was found. False if the Token does not have a depth.

func (*TTInfo) SetDepth added in v0.1.12 

func (tti *TTInfo) SetDepth(Token tn.Noder, depth int) bool

SetDepth sets the depth of the Token.

Parameters:

  • Token: The Token to set the depth of.
  • depth: The depth to set.

Returns:

  • bool: True if the depth was set. False if the Token already has a depth.

type Token added in v0.1.18 

type Token[T TokenTyper] struct {
	// ID is the identifier of the token.
	ID T

	// At is the position of the token in the input string.
	At int

	// Lookahead is the next token in the input string.
	Lookahead *Token[T]

	// Data is the data of the token.
	// If data is a string, it is the data of a leaf token.
	// If data is a slice of Token, it is the data of a non-leaf token.
	// any other type of data is not supported.
	//
	// Only EofToken and RootToken have nil data.
	Data any
}

Token is the information about a token.

func NewToken added in v0.1.18 

func NewToken[T TokenTyper](id T, data any, at int, lookahead *Token[T]) *Token[T]

NewToken creates a new token info with the given identifier, data, position, and lookahead token.

Parameters:

  • id: The identifier of the token.
  • data: The data of the token.
  • at: The position of the token in the input string.
  • lookahead: The next token in the input string.

Returns:

  • *Token: A pointer to the new token info. Nil if the data is nil or not a string or a slice of Token.

func (*Token[T]) Copy added in v0.1.18 

func (tok *Token[T]) Copy() uc.Copier

Copy implements common.Copier interface.

func (*Token[T]) GetData added in v0.1.18 

func (tok *Token[T]) GetData() any

GetData returns the data of the token.

Data can only be a string or a slice of Token. Unless the token is the EofToken or the RootToken, the data should not be nil.

Returns:

  • any: The data of the token.

func (*Token[T]) GetID added in v0.1.18 

func (tok *Token[T]) GetID() T

GetID returns the identifier of the token.

Returns:

  • T: The identifier of the token.

func (*Token[T]) GetLookahead added in v0.1.18 

func (tok *Token[T]) GetLookahead() *Token[T]

GetLookahead returns the next token in the input string.

Returns:

  • *Token: The next token in the input string.

func (*Token[T]) GetPos added in v0.1.18 

func (tok *Token[T]) GetPos() int

GetPos returns the position of the token in the input string.

Returns:

  • int: The position of the token in the input string.

func (*Token[T]) GoString added in v0.1.18 

func (tok *Token[T]) GoString() string

GoString is a method of fmt.GoStringer interface.

func (*Token[T]) IsLeaf added in v0.1.18 

func (tok *Token[T]) IsLeaf() bool

IsLeaf checks if the token is a leaf token.

Returns:

  • bool: True if the token is a leaf token, false otherwise.

func (*Token[T]) IsNonLeaf added in v0.1.18 

func (tok *Token[T]) IsNonLeaf() bool

IsNonLeaf checks if the token is a non-leaf token.

Returns:

  • bool: True if the token is a non-leaf token, false otherwise.

func (*Token[T]) SetLookahead added in v0.1.18 

func (tok *Token[T]) SetLookahead(lookahead *Token[T])

SetLookahead sets the next token in the input string.

Parameters:

  • lookahead: The next token in the input string.

type TokenTree added in v0.1.12 

type TokenTree struct {

	// Info is the information about the tree.
	Info *TTInfo
	// contains filtered or unexported fields
}

TokenTree is a tree of tokens.

func NewTokenTree added in v0.1.12 

func NewTokenTree(root tn.Noder) (*TokenTree, error)

NewTokenTree creates a new token tree.

Parameters:

  • root: The root of the token tree.

Returns:

  • *TokenTree: The new token tree.
  • error: An error if the token tree could not be created.

Errors:

  • *ErrCycleDetected: A cycle is detected in the token tree.
  • *uc.ErrInvalidParameter: The root is nil.
  • *ErrUnknowToken: The root is not a known token.

func (*TokenTree) DebugString added in v0.1.12 

func (tt *TokenTree) DebugString(f func(data tn.Noder) string) string

DebugString returns a string representation of the token tree.

Returns:

  • string: The string representation of the token tree.

Information: This is a debug function.

func (*TokenTree) GetAllBranches added in v0.1.12 

func (tt *TokenTree) GetAllBranches() ([][]tn.Noder, error)

GetAllBranches returns all the branches of the token tree.

Returns:

  • [][]Token: All the branches of the token tree.

func (*TokenTree) GetRoot added in v0.1.16 

func (tt *TokenTree) GetRoot() tn.Noder

GetRoot returns the root of the token tree.

Returns:

  • Token: The root of the token tree.

type TokenTyper added in v0.1.19 

type TokenTyper interface {
	// IsTerminal checks if the token type is a terminal.
	//
	// Returns:
	//   - bool: True if the token type is a terminal, false otherwise.
	IsTerminal() bool

	uc.Enumer
}

TokenTyper is an interface for a token type.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.