Grammar

package
v0.1.8 Latest Latest
Warning

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

 Go to latest Published: May 10, 2024 License: MIT Imports: 10 Imported by: 0

Documentation

Index

Constants

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

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

	// EndSymbolID is the identifier of the end symbol in the grammar.
	EndSymbolID string = "EOF"

	// 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"

	// RootTokenID is the identifier of the root token.
	RootTokenID string = "ROOT"
)

Variables

This section is empty.

Functions

func FilterNilProduction added in v0.1.8 

func FilterNilProduction(p Productioner) bool

FilterNilProduction filters out nil productions.

Parameters:

  • p: The production to filter.

Returns:

  • bool: True if the production is not nil, false otherwise.

func IsTerminal 

func IsTerminal(identifier string) bool

IsTerminal checks if the given identifier is a terminal. Terminals are identifiers that start with an uppercase letter.

Parameters:

  • identifier: The identifier to check.

Returns:

  • bool: True if the identifier is a terminal, false otherwise.

Types

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 returns the error message: "lhs of production rule (lhs) does not match rhs (rhs)".

Returns:

  • string: The error message.

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 returns the error message: "no production rules found".

Returns:

  • string: The error message.

type ErrUnknowToken added in v0.1.8 

type ErrUnknowToken struct {
	// Token is the unknown token.
	Token Tokener
}

ErrUnknownToken is an error that is returned when an unknown token is found.

func NewErrUnknowToken added in v0.1.8 

func NewErrUnknowToken(token Tokener) *ErrUnknowToken

NewErrUnknowToken creates a new error of type *ErrUnknowToken.

Parameters:

  • token: The unknown token.

Returns:

  • *ErrUnknowToken: The new error.

func (*ErrUnknowToken) Error added in v0.1.8 

func (e *ErrUnknowToken) Error() string

Error returns the error message: "unknown token type: (type)".

Returns:

  • string: The error message.

Behaviors:

  • If the token is nil, the error message is "token is nil".

type Grammar 

type Grammar struct {
	// Productions is a slice of Productions in the grammar.
	Productions []Productioner

	// LhsToSkip is a slice of productions to skip.
	LhsToSkip []string

	// Symbols is a slice of Symbols in the grammar.
	Symbols []string
}

Grammar represents a context-free grammar.

func NewGrammar added in v0.1.8 

func NewGrammar() *Grammar

NewGrammar is a constructor of an empty Grammar.

A context-free grammar is a set of productions, each of which consists of a non-terminal symbol and a sequence of symbols.

The non-terminal symbol is the left-hand side of the production, and the sequence of symbols is the right-hand side of the production.

The grammar also contains a set of symbols, which are the non-terminal and terminal symbols in the grammar.

Returns:

  • *Grammar: A new empty Grammar.

func (*Grammar) GetProductions added in v0.1.8 

func (g *Grammar) GetProductions() []*Production

GetProductions returns a slice of Production in the grammar.

Returns:

  • []*Production: A slice of Production in the grammar.

func (*Grammar) GetRegProductions added in v0.1.8 

func (g *Grammar) GetRegProductions() []*RegProduction

GetRegProductions returns a slice of RegProduction in the grammar.

Returns:

  • []*RegProduction: A slice of RegProduction in the grammar.

func (*Grammar) ProductionMatch added in v0.1.8 

func (g *Grammar) ProductionMatch(at int, stack *ds.DoubleStack[Tokener]) []*MatchedResult[*NonLeafToken]

ProductionMatch returns a slice of MatchedResult that match the input token.

Parameters:

  • at: The position in the input string.
  • stack: The input stream to match. Refers to Productioner.Match.

Returns:

  • []MatchedResult: A slice of MatchedResult that match the input token.

func (*Grammar) RegexMatch added in v0.1.8 

func (g *Grammar) RegexMatch(at int, b []byte) []*MatchedResult[*LeafToken]

RegexMatch returns a slice of MatchedResult that match the input token.

Parameters:

  • at: The position in the input string.
  • b: The input stream to match. Refers to Productioner.Match.

Returns:

  • []MatchedResult: A slice of MatchedResult that match the input token.

func (*Grammar) String 

func (g *Grammar) String() string

String is a method of Grammar that returns a string representation of a Grammar.

It should only be used for debugging and logging purposes.

Returns:

  • string: A string representation of a Grammar.

type GrammarBuilder 

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

GrammarBuilder represents a builder for a grammar.

The default direction of the productions is LeftToRight.

func (*GrammarBuilder) AddProductions added in v0.1.8 

func (b *GrammarBuilder) AddProductions(ps ...Productioner)

AddProductions is a method of GrammarBuilder that adds a production to the GrammarBuilder.

Parameters:

  • ps: The productions to add to the GrammarBuilder.

func (*GrammarBuilder) Build 

func (b *GrammarBuilder) Build() (*Grammar, error)

Build is a method of GrammarBuilder that builds a Grammar from the GrammarBuilder.

Returns:

  • *Grammar: A Grammar built from the GrammarBuilder.
  • error: An error if the GrammarBuilder could not build a Grammar.

func (*GrammarBuilder) FilterProductionsWithoutLHS added in v0.1.8 

func (b *GrammarBuilder) FilterProductionsWithoutLHS(lhs string) bool

FilterProductionsWithoutLHS filters out productions without the specified left-hand side.

Parameters:

  • lhs: The left-hand side to filter.

Returns:

  • bool: True if the production has the specified left-hand side, false otherwise.

func (*GrammarBuilder) Reset 

func (b *GrammarBuilder) Reset()

Reset is a method of GrammarBuilder that resets a GrammarBuilder.

func (*GrammarBuilder) SetToSkip 

func (b *GrammarBuilder) SetToSkip(lhss ...string)

SetToSkip is a method of GrammarBuilder that sets the productions to skip in the GrammarBuilder.

Parameters:

  • lhss: The left-hand sides of the productions to skip.

type LeafToken 

type LeafToken struct {
	// ID is the identifier of the token.
	ID string

	// Data is the data of the token.
	Data string

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

	// Lookahead is the next token in the input string.
	Lookahead *LeafToken
}

LeafToken represents a token that contains a single piece of data.

func NewEOFToken added in v0.1.5 

func NewEOFToken() *LeafToken

NewEOFToken creates a new end-of-file token.

Returns:

  • *LeafToken: A pointer to the new end-of-file token.

func NewLeafToken 

func NewLeafToken(id string, data string, at int) *LeafToken

NewLeafToken creates a new leaf token with the given identifier, data, and position.

Parameters:

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

Returns:

  • *LeafToken: A pointer to the new leaf token.

func NewRootToken added in v0.1.5 

func NewRootToken() *LeafToken

NewRootToken creates a new root token.

Returns:

  • *LeafToken: A pointer to the new root token.

func (*LeafToken) GetData 

func (t *LeafToken) GetData() any

GetData returns the data of the token.

Returns:

  • any: The data of the token.

func (*LeafToken) GetID 

func (t *LeafToken) GetID() string

GetID returns the identifier of the token.

Returns:

  • string: The identifier of the token.

func (*LeafToken) GetLookahead 

func (t *LeafToken) GetLookahead() *LeafToken

GetLookahead returns the next token in the input string.

Returns:

  • LeafToken: The next token in the input string.

func (*LeafToken) GetPos 

func (t *LeafToken) 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 (*LeafToken) SetLookahead 

func (t *LeafToken) SetLookahead(lookahead *LeafToken)

SetLookahead sets the next token in the input string.

Parameters:

  • lookahead: The next token in the input string.

func (*LeafToken) String 

func (t *LeafToken) String() string

String is a method of fmt.Stringer interface.

It should only be used for debugging and logging purposes.

Returns:

  • string: A string representation of the leaf token.

type MatchedResult 

type MatchedResult[T Tokener] struct {
	// Matched is the matched token.
	Matched 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 Tokener](matched 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.

func (*MatchedResult[T]) GetMatch added in v0.1.8 

func (mr *MatchedResult[T]) GetMatch() T

GetMatch returns the matched token.

Returns:

  • T: The matched token.

type NonLeafToken 

type NonLeafToken struct {
	// ID is the identifier of the token.
	ID string

	// Data is the data of the token.
	Data []Tokener

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

	// Lookahead is the next token in the input string.
	Lookahead *LeafToken
}

NonLeafToken represents a token that contains multiple pieces of data.

func NewNonLeafToken 

func NewNonLeafToken(id string, at int, data ...Tokener) *NonLeafToken

NewNonLeafToken creates a new non-leaf token with the given identifier, data, and position.

Parameters:

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

Returns:

  • *NonLeafToken: A pointer to the new non-leaf token.

func (*NonLeafToken) GetData 

func (t *NonLeafToken) GetData() any

GetData returns the data of the token.

Returns:

  • any: The data of the token.

func (*NonLeafToken) GetID 

func (t *NonLeafToken) GetID() string

GetID returns the identifier of the token.

Returns:

  • string: The identifier of the token.

func (*NonLeafToken) GetLookahead 

func (t *NonLeafToken) GetLookahead() *LeafToken

GetLookahead returns the next token in the input string.

Returns:

  • LeafToken: The next token in the input string.

func (*NonLeafToken) GetPos 

func (t *NonLeafToken) 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 (*NonLeafToken) SetLookahead 

func (t *NonLeafToken) SetLookahead(lookahead *LeafToken)

SetLookahead sets the next token in the input string.

Parameters:

  • lookahead: The next token in the input string.

func (*NonLeafToken) String 

func (t *NonLeafToken) String() string

String is a method of fmt.Stringer interface.

It should only be used for debugging and logging purposes.

Returns:

  • string: A string representation of the non-leaf token.

type Production 

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

Production represents a production in a grammar.

func NewProduction 

func NewProduction(lhs string, rhs string) *Production

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.
  • rhs: The right-hand side of the production.

Returns:

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

func (*Production) Copy 

func (p *Production) Copy() itff.Copier

Copy is a method of Production that returns a copy of the production.

Returns:

  • itff.Copier: A copy of the production.

func (*Production) Equals 

func (p *Production) Equals(other Productioner) bool

Equals is a method of Production that returns whether the production is equal to another production. Two productions are equal if their left-hand sides are equal and their right-hand sides are equal.

Parameters:

  • other: The other production to compare to.

Returns:

  • bool: Whether the production is equal to the other production.

func (*Production) GetLhs 

func (p *Production) GetLhs() string

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

Returns:

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

func (*Production) GetRhsAt 

func (p *Production) GetRhsAt(index int) (string, 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:

  • string: 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) GetSymbols 

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

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) HasRhs added in v0.1.8 

func (p *Production) HasRhs(rhs string) 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) IndicesOfRhs added in v0.1.8 

func (p *Production) IndicesOfRhs(rhs string) []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) Iterator 

func (p *Production) Iterator() itf.Iterater[string]

Iterator is a method of Production that returns an iterator for the production that iterates over the right-hand side of the production.

Returns:

  • itf.Iterater[string]: An iterator for the production.

func (*Production) Match 

func (p *Production) Match(at int, stack *ds.DoubleStack[Tokener]) (*NonLeafToken, 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:

  • Tokener: 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) ReplaceRhsAt added in v0.1.8 

func (p *Production) ReplaceRhsAt(index int, otherP *Production) (*Production, error)

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:

  • *ers.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) ReverseIterator 

func (p *Production) ReverseIterator() itf.Iterater[string]

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:

  • itf.Iterater[string]: A reverse iterator for the production.

func (*Production) Size 

func (p *Production) 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) String 

func (p *Production) String() string

String is a method of Production that returns a string representation of a Production.

Returns:

  • string: A string representation of a Production.

type Productioner 

type Productioner interface {
	// Equals returns whether the production is equal to another production.
	// Two productions are equal if their left-hand sides are equal and their
	// right-hand sides are equal.
	//
	// Parameters:
	//   - other: The other production to compare to.
	//
	// Returns:
	//   - bool: Whether the production is equal to the other production.
	Equals(other Productioner) bool

	// GetLhs returns the left-hand side of the production.
	//
	// Returns:
	//   - string: The left-hand side of the production.
	GetLhs() string

	// GetSymbols 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.
	GetSymbols() []string

	fmt.Stringer
	itff.Copier
}

Productioner is an interface that defines methods for a production in a grammar.

type RegProduction 

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

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

func NewRegProduction 

func NewRegProduction(lhs string, regex string) *RegProduction

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) Compile 

func (r *RegProduction) 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) Copy 

func (p *RegProduction) Copy() itff.Copier

Copy is a method of RegProduction that returns a copy of the production.

Returns:

  • itff.Copier: A copy of the production.

func (*RegProduction) Equals 

func (p *RegProduction) Equals(other Productioner) bool

Equals is a method of RegProduction that returns whether the production is equal to another production. Two productions are equal if their left-hand sides are equal and their right-hand sides are equal.

Parameters:

  • other: The other production to compare to.

Returns:

  • bool: Whether the production is equal to the other production.

func (*RegProduction) GetLhs 

func (p *RegProduction) GetLhs() string

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

Returns:

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

func (*RegProduction) GetSymbols 

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

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:

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

func (*RegProduction) Match 

func (p *RegProduction) Match(at int, b []byte) *LeafToken

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:

  • Tokener: A token that matches the production in the stack. nil if there is no match.

func (*RegProduction) String 

func (r *RegProduction) String() string

String is a method of fmt.Stringer that returns a string representation of a RegProduction.

It should only be used for debugging and logging purposes.

Returns:

  • string: A string representation of a RegProduction.

type Tokener 

type Tokener interface {
	// GetID returns the identifier of the token.
	//
	// Returns:
	//
	//   - string: The identifier of the token.
	GetID() string

	// GetData returns the data of the token.
	//
	// Returns:
	//
	//   - any: The data of the token.
	GetData() any

	// GetPos returns the position of the token in the input string.
	//
	// Returns:
	//
	//   - int: The position of the token in the input string.
	GetPos() int

	// GetLookahead returns the next token in the input string.
	//
	// Returns:
	//
	//   - LeafToken: The next token in the input string.
	GetLookahead() *LeafToken

	// SetLookahead sets the next token in the input string.
	//
	// Parameters:
	//
	//   - lookahead: The next token in the input string.
	SetLookahead(lookahead *LeafToken)

	fmt.Stringer
}

Tokener is an interface that defines the methods that a token must implement.

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.