Grammar

package
v0.1.5 Latest Latest
Warning

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

 Go to latest Published: Apr 25, 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 = "->"

	// 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"
)
View Source 
const (
	// EOFTokenID is the identifier of the end-of-file token.
	EOFTokenID string = "EOF"
)

Variables

This section is empty.

Functions

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 ErrNoMoreTokens added in v0.1.5 

type ErrNoMoreTokens struct{}

ErrNoMoreTokens is an error that indicates that there are no more tokens in the stream.

func NewErrNoMoreTokens added in v0.1.5 

func NewErrNoMoreTokens() *ErrNoMoreTokens

NewErrNoMoreTokens creates a new ErrNoMoreTokens error.

Returns:

  • *ErrNoMoreTokens: A pointer to the new error.

func (*ErrNoMoreTokens) Error added in v0.1.5 

func (e *ErrNoMoreTokens) Error() string

Error is a method of errors that returns the error message.

Returns:

  • string: The error message.

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.

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.

func (*Grammar) Match 

func (g *Grammar) Match(at int, b any) []MatchedResult

Match 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) AddProduction 

func (b *GrammarBuilder) AddProduction(p ...Productioner)

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

Parameters:

  • p: The production 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.

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.

func (*GrammarBuilder) String 

func (b *GrammarBuilder) String() string

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

It should only be used for debugging and logging purposes.

Returns:

  • string: A string representation of a GrammarBuilder.

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

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 struct {
	// Matched is the matched token.
	Matched Tokener

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

MatchedResult represents the result of a match operation.

func NewMatchResult 

func NewMatchResult(matched Tokener, ruleIndex int) MatchedResult

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

func (p *Production) IndexOfRhs(rhs string) int

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

Parameters:

  • rhs: The symbol to find the index of.

Returns:

  • int: The index of the symbol in the right-hand side of the production. Returns -1 if the symbol is not found.

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, b any) Tokener

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.
  • b: 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.
  • as of now, only Stack.Stacker[Tokener] is supported as the type of 'b'.

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

	// Match 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 input stream or stack to match the production against.
	//
	// Returns:
	//
	//   - Tokener: A token that matches the production in the input stream or stack.
	// 	nil if there is no match.
	//
	// 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.
	Match(at int, b any) Tokener

	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 any) Tokener

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 TokenStream added in v0.1.5 

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

TokenStream is a stream of tokens.

func NewTokenStream added in v0.1.5 

func NewTokenStream(tokens []*LeafToken) TokenStream

NewTokenStream creates a new token stream with the given tokens.

Parameters:

  • tokens: The tokens to add to the stream.

Returns:

  • TokenStream: The new token stream.

func (*TokenStream) Consume added in v0.1.5 

func (ts *TokenStream) Consume() *LeafToken

Consume consumes the next token in the stream. It panics if there are no more tokens in the stream.

Returns:

  • *LeafToken: A pointer to the consumed token.

func (*TokenStream) GetTokens added in v0.1.5 

func (ts *TokenStream) GetTokens() []*LeafToken

GetTokens returns the tokens in the stream. It ignores the end-of-file token if present.

Returns:

  • []*LeafToken: The tokens in the stream.

func (*TokenStream) IsDone added in v0.1.5 

func (ts *TokenStream) IsDone() bool

IsDone returns true if the token stream has been fully consumed.

Returns:

  • bool: True if the token stream has been fully consumed.

func (*TokenStream) IsEmpty added in v0.1.5 

func (ts *TokenStream) IsEmpty() bool

IsEmpty returns true if the token stream is empty.

Returns:

  • bool: True if the token stream is empty.

func (*TokenStream) Peek added in v0.1.5 

func (ts *TokenStream) Peek() *LeafToken

Peek returns the next token in the stream without consuming it. It panics if there are no more tokens in the stream.

Returns:

  • *LeafToken: A pointer to the next token in the stream.

func (*TokenStream) RemoveByTokenID added in v0.1.5 

func (ts *TokenStream) RemoveByTokenID(id string)

RemoveByTokenID removes tokens by their token ID.

Parameters:

  • id: The token ID to remove.

func (*TokenStream) Reset added in v0.1.5 

func (ts *TokenStream) Reset()

Reset resets the token stream to the beginning.

func (*TokenStream) SetEOFToken added in v0.1.5 

func (ts *TokenStream) SetEOFToken()

SetEOFToken sets the end-of-file token in the token stream.

If the end-of-file token is already present, it will not be added again.

func (*TokenStream) SetLookahead added in v0.1.5 

func (ts *TokenStream) SetLookahead()

SetLookahead sets the lookahead token for all the tokens in the stream.

func (*TokenStream) Size added in v0.1.5 

func (ts *TokenStream) Size() int

Size returns the number of tokens in the token stream.

Returns:

  • int: The number of tokens in the token stream.

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.