ConflictSolver

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: 15 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var GlobalDebugMode bool = true

Functions

func FilterNonTerminalLeaf added in v0.1.10 

func FilterNonTerminalLeaf[T gr.TokenTyper](n tn.Noder) bool

FilterNonTerminalLeaf filters out non-terminal leaf nodes.

Parameters:

  • tn: The tree node to filter.

Returns:

  • bool: False if the tree node is a terminal leaf, true otherwise.

func FilterTerminalLeaf 

func FilterTerminalLeaf[T gr.TokenTyper](tn *HelperNode[T]) bool

FilterTerminalLeaf filters out terminal leaf nodes.

Parameters:

  • tn: The tree node to filter.

Returns:

  • bool: True if the tree node is a terminal leaf, false otherwise.

func MatchAction added in v0.1.10 

func MatchAction[T gr.TokenTyper](a Actioner[T], top *gr.Token[T], stack *ud.History[lls.Stacker[*gr.Token[T]]]) error

Match matches the action with the top of the stack.

Parameters:

  • a: The action to match.
  • top: The top of the stack.
  • stack: The stack.

Returns:

  • error: An error if the action does not match the top of the stack.

Types

type ActAccept 

type ActAccept[T gr.TokenTyper] struct {
	*Action[T]

	// Rule is the Rule to reduce by.
	Rule *gr.Production[T]

	// Original is the Original rule to reduce by.
	// this should never be modified.
	Original *gr.Production[T]
}

ActAccept represents an accept action.

func NewActAccept added in v0.1.19 

func NewActAccept[T gr.TokenTyper](rule *gr.Production[T]) *ActAccept[T]

NewActAccept creates a new accept action.

Parameters:

  • rule: The rule to reduce by.

Returns:

  • *ActAccept: A pointer to the new reduce action. Nil if the rule is nil.

func (*ActAccept[T]) Copy 

func (a *ActAccept[T]) Copy() uc.Copier

Copy implements the common.Copier interface.

func (*ActAccept[T]) String 

func (a *ActAccept[T]) String() string

String implements the Actioner interface.

type ActReduce 

type ActReduce[T gr.TokenTyper] struct {
	*Action[T]

	// Rule is the Rule to reduce by.
	Rule *gr.Production[T]

	// Original is the Original rule to reduce by.
	// this should never be modified.
	Original *gr.Production[T]
}

ActReduce represents a reduce action.

func NewActReduce 

func NewActReduce[T gr.TokenTyper](rule *gr.Production[T]) *ActReduce[T]

NewActReduce creates a new reduce action.

Parameters:

  • rule: The rule to reduce by.

Returns:

  • *ActReduce: A pointer to the new reduce action. Nil if the rule is nil.

func (*ActReduce[T]) Copy 

func (a *ActReduce[T]) Copy() uc.Copier

Copy implements the common.Copier interface.

func (*ActReduce[T]) String 

func (a *ActReduce[T]) String() string

String implements the Actioner interface.

type ActShift 

type ActShift[T gr.TokenTyper] struct {
	*Action[T]
}

ActShift represents a shift action.

func NewActShift 

func NewActShift[T gr.TokenTyper]() *ActShift[T]

NewActShift creates a new shift action.

Returns:

  • *ActShift: A pointer to the new shift action.

func (*ActShift[T]) Copy 

func (a *ActShift[T]) Copy() uc.Copier

Copy implements the common.Copier interface.

func (*ActShift[T]) String 

func (a *ActShift[T]) String() string

String implements the Actioner interface.

type Action added in v0.1.10 

type Action[T gr.TokenTyper] struct {
	// contains filtered or unexported fields
}

Action represents an action in a decision table.

func (*Action[T]) ActionSize added in v0.1.19 

func (a *Action[T]) ActionSize() int

ActionSize returns the size of the right-hand side tokens.

Returns:

  • int: The size of the right-hand side tokens.

func (*Action[T]) AppendRhs added in v0.1.10 

func (a *Action[T]) AppendRhs(rhs T)

AppendRhs appends a right-hand side token to the action.

Parameters:

  • rhs: The right-hand side token to append.

func (*Action[T]) Copy added in v0.1.19 

func (a *Action[T]) Copy() uc.Copier

Copy implements the common.Copier interface.

func (*Action[T]) GetLookahead added in v0.1.10 

func (a *Action[T]) GetLookahead() (T, bool)

GetLookahead implements the Actioner interface.

func (*Action[T]) Iterator added in v0.1.10 

func (a *Action[T]) Iterator() uc.Iterater[T]

Iterator implements the Iterators.Iterater interface.

func (*Action[T]) SetLookahead added in v0.1.10 

func (a *Action[T]) SetLookahead(lookahead *T)

SetLookahead sets the lookahead token ID for the action.

Parameters:

  • lookahead: The lookahead token ID to set.

func (*Action[T]) String added in v0.1.10 

func (a *Action[T]) String() string

String implements the Actioner interface.

type Actioner 

type Actioner[T gr.TokenTyper] interface {
	// GetLookahead returns the lookahead token ID for the action.
	//
	// Returns:
	//   - T: The lookahead token ID.
	//   - bool: True if there is a lookahead token ID.
	GetLookahead() (T, bool)

	// ActionSize returns the size of the right-hand side tokens.
	//
	// Returns:
	//   - int: The size of the right-hand side tokens.
	ActionSize() int

	fmt.Stringer

	uc.Iterable[T]
}

Actioner represents an action that the parser will take.

type CMPerSymbol 

type CMPerSymbol[T gr.TokenTyper] map[T]uc.Pair[[]*HelperNode[T], int]

CMPerSymbol is a type that represents conflicts per symbol.

type ConflictSolver 

type ConflictSolver[T gr.TokenTyper] struct {
	// contains filtered or unexported fields
}

ConflictSolver solves conflicts in a decision table.

func NewConflictSolver 

func NewConflictSolver[T gr.TokenTyper](symbols []T, rules []*gr.Production[T]) *ConflictSolver[T]

NewConflictSolver is a constructor of ConflictSolver.

Parameters:

  • symbols: The symbols in the decision table.
  • rules: The rules in the decision table.

Returns:

  • *ConflictSolver: The pointer to the new ConflictSolver.
  • error: An error if the operation failed.

Errors:

  • *ErrCannotCreateItem: If an item cannot be created.
  • *uc.ErrInvalidParameter: If the item is nil.

func SolveConflicts 

func SolveConflicts[T gr.TokenTyper](symbols []T, rules []*gr.Production[T]) (*ConflictSolver[T], error)

SolveConflicts solves conflicts in a decision table.

Parameters:

  • symbols: The symbols in the decision table.
  • rules: The rules in the decision table.

Returns:

  • map[string][]*Helper: The elements in the decision table with conflicts solved.
  • error: An error if the operation failed.

func (*ConflictSolver[T]) FString 

func (cs *ConflictSolver[T]) FString(trav *ffs.Traversor, opts ...ffs.Option) error

FString returns a formatted string representation of the decision table multilined with a specific indentation level.

Parameters:

  • indentLevel: The level of indentation.

Returns:

  • []string: A formatted string representation of the decision table.

func (*ConflictSolver[T]) FindConflicts 

func (cs *ConflictSolver[T]) FindConflicts() CMPerSymbol[T]

FindConflicts is a method that finds conflicts for a specific symbol.

Parameters:

  • symbol: The symbol to find conflicts for.

Returns:

  • CMPerSymbol: The conflicts per symbol.

func (*ConflictSolver[T]) GetElemsWithLhs 

func (cs *ConflictSolver[T]) GetElemsWithLhs(rhs T) []*HelperNode[T]

GetElemsWithLhs is a method that returns all elements with a specific LHS.

Parameters:

  • rhs: The RHS to find elements for.

Returns:

  • []*Helper: The elements with the specified LHS.

func (*ConflictSolver[T]) MakeExpansionForests 

func (cs *ConflictSolver[T]) MakeExpansionForests(index int, next_rhs map[*HelperNode[T]]T) (map[*HelperNode[T]][]T, error)

MakeExpansionForests creates a forest of expansion trees rooted at the next symbol of the conflicting rules.

Parameters:

  • index: The index of the conflicting rules.
  • nextRhs: The next symbol of the conflicting rules.

Returns:

  • map[*Helper][]*ExpansionTree: The forest of expansion trees.
  • error: An error of type *ErrHelper if the operation failed.

func (*ConflictSolver[T]) Match 

func (cs *ConflictSolver[T]) Match(stack *ud.History[lls.Stacker[*gr.Token[T]]]) ([]HelperElem[T], error)

Match is a method that matches the top of the stack with the elements in the decision table.

Parameters:

  • stack: The stack to match the elements with.

Returns:

  • []HelperElem: The elements that match the top of the stack.
  • error: An error if the operation failed.

func (*ConflictSolver[T]) Solve 

func (cs *ConflictSolver[T]) Solve() error

SolveConflicts is a method that solves conflicts in a decision table.

Returns:

  • error: An error if the operation failed.

func (*ConflictSolver[T]) SolveAmbiguous 

func (cs *ConflictSolver[T]) SolveAmbiguous(index int, conflicts []*HelperNode[T]) (bool, error)

SolveAmbiguous is a method that solves ambiguous conflicts in a decision table.

Parameters:

  • index: The index of the conflicting rules.
  • conflicts: The conflicting rules.

Returns:

  • bool: A boolean value indicating if the operation was successful.
  • error: An error if the operation failed.

func (*ConflictSolver[T]) SolveAmbiguousShifts 

func (cs *ConflictSolver[T]) SolveAmbiguousShifts() error

SolveAmbiguousShifts is a method that solves ambiguous shifts in a decision table.

Returns:

  • error: An error if the operation failed.

Errors:

  • *ErrHelpersConflictingSize: If the helpers have conflicting sizes.
  • *ErrHelper: If there is an error appending the right-hand side to the helper.

type Err0thRhsNotSet 

type Err0thRhsNotSet struct{}

Err0thRhsNotSet is an error that is returned when the 0th right-hand side is not set.

func NewErr0thRhsNotSet 

func NewErr0thRhsNotSet() *Err0thRhsNotSet

NewErr0thRhsNotSet creates a new error of type *Err0thRhsNotSet.

Returns:

  • *Err0thRhsNotSet: A pointer to the new error.

func (*Err0thRhsNotSet) Error 

func (e *Err0thRhsNotSet) Error() string

Error implements the error interface.

Message: "0th RHS not set".

type ErrHelper 

type ErrHelper[T gr.TokenTyper] struct {
	// Elem is the helper that caused the error.
	Elem *HelperNode[T]

	// Reason is the reason for the error.
	Reason error
}

ErrHelper is an error that is returned when something goes wrong with a helper.

func NewErrHelper 

func NewErrHelper[T gr.TokenTyper](elem *HelperNode[T], reason error) *ErrHelper[T]

NewErrHelper creates a new error of type *ErrHelper.

Parameters:

  • elem: The helper that caused the error.
  • reason: The reason for the error.

Returns:

  • *ErrHelper: A pointer to the new error.

func (*ErrHelper[T]) Error 

func (e *ErrHelper[T]) Error() string

Error implements the error interface.

Messages:

  • "something went wrong with helper (no helper)" if Elem is nil.
  • "helper (Elem) error: Reason" if Reason is not nil.

type ErrHelpersConflictingSize 

type ErrHelpersConflictingSize struct{}

ErrHelpersConflictingSize is an error that is returned when helpers have conflicting sizes.

func NewErrHelpersConflictingSize 

func NewErrHelpersConflictingSize() *ErrHelpersConflictingSize

NewErrHelpersConflictingSize creates a new error of type *ErrHelpersConflictingSize.

Returns:

  • *ErrHelpersConflictingSize: A pointer to the new error.

func (*ErrHelpersConflictingSize) Error 

func (e *ErrHelpersConflictingSize) Error() string

Error implements the error interface.

Message: "helpers have conflicting sizes".

type ExpansionTree 

type ExpansionTree[T gr.TokenTyper] struct {
	// contains filtered or unexported fields
}

ExpansionTree is a tree of expansion helpers.

func NewExpansionTreeRootedAt 

func NewExpansionTreeRootedAt[T gr.TokenTyper](cs *ConflictSolver[T], h *HelperNode[T]) (*ExpansionTree[T], error)

NewExpansionTree creates a new expansion tree where the root is h and every node is a helper whose LHS is the 0th RHS of the parent node. However, the leaves of the tree are helpers whose 0th RHS is a terminal symbol.

Parameters:

  • cs: The conflict solver.
  • h: The root of the expansion tree.

Returns:

  • *ExpansionTree: The new expansion tree.
  • error: An error if the operation failed.

Errors:

  • *ers.Err0thRhsNotSet: The 0th RHS of the root is not set.
  • *ers.ErrInvalidParameter: The root is nil.

func (*ExpansionTree[T]) Collapse 

func (et *ExpansionTree[T]) Collapse() []T

Collapse collapses the expansion tree into a slice of strings that are the 0th RHS of the terminal leaves.

Returns:

  • []T: The collapsed expansion tree.

func (*ExpansionTree[T]) PruneNonTerminalLeaves 

func (et *ExpansionTree[T]) PruneNonTerminalLeaves()

PruneNonTerminalLeaves prunes the non-terminal leaves of the expansion tree.

func (*ExpansionTree[T]) Size 

func (et *ExpansionTree[T]) Size() int

Size returns the size of the expansion tree.

Returns:

  • int: The size of the expansion tree.

type HelperElem added in v0.1.10 

type HelperElem[T gr.TokenTyper] interface {
	// SetLookahead sets the lookahead of the action.
	//
	// Parameters:
	//   - lookahead: The lookahead to set.
	SetLookahead(lookahead *T)

	// AppendRhs appends a symbol to the right-hand side of the action.
	//
	// Parameters:
	//   - symbol: The symbol to append.
	AppendRhs(symbol T)

	Actioner[T]

	fmt.Stringer
	uc.Copier
}

type HelperNode added in v0.1.19 

type HelperNode[T gr.TokenTyper] struct {
	Parent, FirstChild, NextSibling, LastChild, PrevSibling *HelperNode[T]

	// Item is the item of the helper.
	*Item[T]

	// Action is the action of the helper.
	// This can never be nil.
	Action HelperElem[T]
}

HelperNode is a node in a tree.

func NewHelperNode added in v0.1.19 

func NewHelperNode[T gr.TokenTyper](item *Item[T], action HelperElem[T]) *HelperNode[T]

NewHelperNode creates a new node with the given data.

Parameters:

  • item: The item of the helper.
  • action: The action of the helper.

Returns:

  • *HelperNode[T]: A pointer to the newly created node. Nil if item or action is nil.

func (*HelperNode[T]) ActionSize added in v0.1.19 

func (h *HelperNode[T]) ActionSize() int

ActionSize returns the size of the helper.

Returns:

  • int: The size of the helper.

func (*HelperNode[T]) AddChild added in v0.1.19 

func (tn *HelperNode[T]) AddChild(child treenode.Noder)

AddChild adds a new child to the node. If the child is nil or it is not of type *HelperNode[T], it does nothing.

This function clears the parent and sibling pointers of the child and so, it does not add relatives to the child.

Parameters:

  • child: The child to add.

func (*HelperNode[T]) AddChildren added in v0.1.19 

func (tn *HelperNode[T]) AddChildren(children []*HelperNode[T])

AddChildren is a convenience function to add multiple children to the node at once. It is more efficient than adding them one by one. Therefore, the behaviors are the same as the behaviors of the HelperNode.AddChild function.

Parameters:

  • children: The children to add.

func (*HelperNode[T]) AppendRhs added in v0.1.19 

func (h *HelperNode[T]) AppendRhs(symbol T)

AppendRhs appends a symbol to the right-hand side of the action.

Parameters:

  • symbol: The symbol to append.

func (*HelperNode[T]) Cleanup added in v0.1.19 

func (tn *HelperNode[T]) Cleanup()

Cleanup implements the treenode.Noder interface.

This is expensive as it has to traverse the whole tree to clean up the nodes, one by one. While this is useful for freeing up memory, for large enough trees, it is recommended to let the garbage collector handle the cleanup.

Despite the above, this function does not use recursion and is safe to use (but make sure goroutines are not running on the tree while this function is called).

Finally, it also logically removes the node from the siblings and the parent.

func (*HelperNode[T]) Copy added in v0.1.19 

func (tn *HelperNode[T]) Copy() common.Copier

Copy implements the treenode.Noder interface.

It never returns nil and it does not copy the parent or the sibling pointers.

func (*HelperNode[T]) DeleteChild added in v0.1.19 

func (tn *HelperNode[T]) DeleteChild(target treenode.Noder) []treenode.Noder

DeleteChild implements the treenode.Noder interface.

No nil nodes are returned.

func (*HelperNode[T]) EvaluateLookahead added in v0.1.19 

func (h *HelperNode[T]) EvaluateLookahead() error

EvaluateLookahead evaluates the lookahead of the action.

Returns:

  • error: An error if the evaluation failed.

func (*HelperNode[T]) ForceLookahead added in v0.1.19 

func (h *HelperNode[T]) ForceLookahead(lookahead T)

ForceLookahead forces the lookahead of the action.

Parameters:

  • lookahead: The lookahead to force.

func (*HelperNode[T]) GetAction added in v0.1.19 

func (h *HelperNode[T]) GetAction() HelperElem[T]

GetAction returns the action of the helper.

Returns:

  • Actioner: The action of the helper.

func (*HelperNode[T]) GetAncestors added in v0.1.19 

func (tn *HelperNode[T]) GetAncestors() []treenode.Noder

GetAncestors implements the treenode.Noder interface.

This is expensive since ancestors are not stored and so, every time this function is called, it has to traverse the tree to find the ancestors. Thus, it is recommended to call this function once and then store the ancestors somewhere if needed.

Despite the above, this function does not use recursion and is safe to use.

Finally, no nil nodes are returned.

func (*HelperNode[T]) GetChildren added in v0.1.19 

func (tn *HelperNode[T]) GetChildren() []treenode.Noder

GetChildren returns the immediate children of the node.

The returned nodes are never nil and are not copied. Thus, modifying the returned nodes will modify the tree.

Returns:

  • []treenode.Noder: A slice of pointers to the children of the node.

func (*HelperNode[T]) GetFirstChild added in v0.1.19 

func (tn *HelperNode[T]) GetFirstChild() treenode.Noder

GetFirstChild implements the treenode.Noder interface.

func (*HelperNode[T]) GetFirstSibling added in v0.1.19 

func (tn *HelperNode[T]) GetFirstSibling() *HelperNode[T]

GetFirstSibling returns the first sibling of the node. If it has a parent, it returns the first child of the parent. Otherwise, it returns the first sibling of the node.

As an edge case, if the node has no parent and no previous sibling, it returns the node itself. Thus, this function never returns nil.

Returns:

  • *HelperNode[T]: A pointer to the first sibling.

func (*HelperNode[T]) GetLastSibling added in v0.1.19 

func (tn *HelperNode[T]) GetLastSibling() *HelperNode[T]

GetLastSibling returns the last sibling of the node. If it has a parent, it returns the last child of the parent. Otherwise, it returns the last sibling of the node.

As an edge case, if the node has no parent and no next sibling, it returns the node itself. Thus, this function never returns nil.

Returns:

  • *HelperNode[T]: A pointer to the last sibling.

func (*HelperNode[T]) GetLeaves added in v0.1.19 

func (tn *HelperNode[T]) GetLeaves() []treenode.Noder

GetLeaves implements the treenode.Noder interface.

This is expensive as leaves are not stored and so, every time this function is called, it has to do a DFS traversal to find the leaves. Thus, it is recommended to call this function once and then store the leaves somewhere if needed.

Despite the above, this function does not use recursion and is safe to use.

Finally, no nil nodes are returned.

func (*HelperNode[T]) GetLookahead added in v0.1.19 

func (h *HelperNode[T]) GetLookahead() (T, bool)

GetLookahead returns the lookahead of the action.

Returns:

  • T: The lookahead token ID.
  • bool: True if the lookahead is set, false otherwise.

func (*HelperNode[T]) GetParent added in v0.1.19 

func (tn *HelperNode[T]) GetParent() treenode.Noder

GetParent implements the treenode.Noder interface.

func (*HelperNode[T]) HasChild added in v0.1.19 

func (tn *HelperNode[T]) HasChild(target *HelperNode[T]) bool

HasChild returns true if the node has the given child.

Because children of a node cannot be nil, a nil target will always return false.

Parameters:

  • target: The child to check for.

Returns:

  • bool: True if the node has the child, false otherwise.

func (*HelperNode[T]) IsChildOf added in v0.1.19 

func (tn *HelperNode[T]) IsChildOf(target *HelperNode[T]) bool

IsChildOf returns true if the node is a child of the parent. If target is nil, it returns false.

Parameters:

  • target: The target parent to check for.

Returns:

  • bool: True if the node is a child of the parent, false otherwise.

func (*HelperNode[T]) IsLeaf added in v0.1.19 

func (tn *HelperNode[T]) IsLeaf() bool

IsLeaf implements the treenode.Noder interface.

func (*HelperNode[T]) IsRoot added in v0.1.19 

func (tn *HelperNode[T]) IsRoot() bool

IsRoot returns true if the node does not have a parent.

Returns:

  • bool: True if the node is the root, false otherwise.

func (*HelperNode[T]) IsSingleton added in v0.1.19 

func (tn *HelperNode[T]) IsSingleton() bool

IsSingleton implements the treenode.Noder interface.

func (*HelperNode[T]) Iterator added in v0.1.19 

func (tn *HelperNode[T]) Iterator() common.Iterater[treenode.Noder]

Iterator implements the treenode.Noder interface.

This function iterates over the children of the node, it is a pull-based iterator, and never returns nil.

func (*HelperNode[T]) LinkChildren added in v0.1.19 

func (tn *HelperNode[T]) LinkChildren(children []treenode.Noder)

LinkWithParent implements the treenode.Noder interface.

Children that are not of type *HelperNode[T] or nil are ignored.

func (*HelperNode[T]) Match added in v0.1.19 

func (h *HelperNode[T]) Match(top *gr.Token[T], stack *ud.History[lls.Stacker[*gr.Token[T]]]) error

Match matches the top of the stack with the helper.

Parameters:

  • top: The top of the stack.
  • stack: The stack.

Returns:

  • error: An error if the match failed.

Behaviors:

  • The stack is refused.

func (*HelperNode[T]) RemoveNode added in v0.1.19 

func (tn *HelperNode[T]) RemoveNode() []treenode.Noder

RemoveNode removes the node from the tree while shifting the children up one level to maintain the tree structure.

Also, the returned children can be used to create a forest of trees if the root node is removed.

Returns:

  • []treenode.Noder: A slice of pointers to the children of the node iff the node is the root. Nil otherwise.

Example: 

// Given the tree:
1
├── 2
└── 3
	├── 4
	└── 5
└── 6

// The tree after removing node 3:

1
├── 2
└── 4
└── 5
└── 6

func (*HelperNode[T]) ReplaceRhsAt added in v0.1.19 

func (h *HelperNode[T]) ReplaceRhsAt(index int, rhs T) *HelperNode[T]

ReplaceRhsAt replaces the right-hand side of the item at the specified index with the right-hand side of the other item.

Parameters:

  • index: The index of the right-hand side to replace.
  • otherH: The other helper.

Returns:

  • *Helper: The new helper with the replaced right-hand side.
  • error: An error if the operation failed.

Errors:

  • *ers.ErrInvalidParameter: The index is out of bounds, otherH is nil, otherH.Item is nil, or otherH.Item.Rule is nil.
  • *gr.ErrLhsRhsMismatch: The left-hand side of the item does not match the right-hand side of the other item.

func (*HelperNode[T]) SetAction added in v0.1.19 

func (h *HelperNode[T]) SetAction(action HelperElem[T])

SetAction sets the action of the helper.

Parameters:

  • action: The action to set.

Behaviors:

  • If the action is nil, then the action is not set.

func (*HelperNode[T]) SetParent added in v0.1.19 

func (tn *HelperNode[T]) SetParent(parent treenode.Noder) bool

SetParent implements the treenode.Noder interface.

func (*HelperNode[T]) Size added in v0.1.19 

func (tn *HelperNode[T]) Size() int

Size implements the treenode.Noder interface.

This is expensive as it has to traverse the whole tree to find the size of the tree. Thus, it is recommended to call this function once and then store the size somewhere if needed.

Despite the above, this function does not use recursion and is safe to use.

Finally, the traversal is done in a depth-first manner.

func (*HelperNode[T]) String added in v0.1.19 

func (tn *HelperNode[T]) String() string

String implements the treenode.Noder interface.

func (*HelperNode[T]) SubstituteRhsAt added in v0.1.19 

func (h *HelperNode[T]) SubstituteRhsAt(index int, other_helper *HelperNode[T]) *HelperNode[T]

ReplaceRhsAt replaces the right-hand side of the item at the specified index with the right-hand side of the other item.

Parameters:

  • index: The index of the right-hand side to replace.
  • otherH: The other helper.

Returns:

  • *Helper: The new helper with the replaced right-hand side.
  • error: An error if the operation failed.

Errors:

  • *ers.ErrInvalidParameter: The index is out of bounds, otherH is nil, otherH.Item is nil, or otherH.Item.Rule is nil.
  • *gr.ErrLhsRhsMismatch: The left-hand side of the item does not match the right-hand side of the other item.

type HelperNodeIterator added in v0.1.19 

type HelperNodeIterator[T gr.TokenTyper] struct {
	// contains filtered or unexported fields
}

HelperNodeIterator is a pull-based iterator that iterates over the children of a HelperNode.

func (*HelperNodeIterator[T]) Consume added in v0.1.19 

func (iter *HelperNodeIterator[T]) Consume() (treenode.Noder, error)

Consume implements the common.Iterater interface.

*common.ErrExhaustedIter is the only error returned by this function and the returned node is never nil.

func (*HelperNodeIterator[T]) Restart added in v0.1.19 

func (iter *HelperNodeIterator[T]) Restart()

Restart implements the common.Iterater interface.

type InfoStruct 

type InfoStruct[T gr.TokenTyper] struct {
	// contains filtered or unexported fields
}

InfoStruct is the information about the expansion tree.

func NewInfoStruct 

func NewInfoStruct[T gr.TokenTyper](root *HelperNode[T]) *InfoStruct[T]

NewInfoStruct creates a new InfoStruct.

Parameters:

  • root: The root of the expansion tree.

Returns:

  • *InfoStruct: The new InfoStruct.

Behaviors:

  • The root is set to seen.
  • If the root is nil, then nil is returned.

func (*InfoStruct[T]) Copy 

func (is *InfoStruct[T]) Copy() uc.Copier

Copy implements the Copier interface.

func (*InfoStruct[T]) IsNotSeen added in v0.1.10 

func (is *InfoStruct[T]) IsNotSeen(h *HelperNode[T]) bool

IsSNoteen checks if the helper is seen.

Parameters:

  • h: The helper to check.

Returns:

  • bool: True if the helper is seen, false otherwise.

func (*InfoStruct[T]) SetSeen added in v0.1.10 

func (is *InfoStruct[T]) SetSeen(h *HelperNode[T])

SetSeen sets the helper as seen.

Parameters:

  • h: The helper to set as seen.

type Item 

type Item[T gr.TokenTyper] struct {
	// Rule is the production rule that the item represents.
	Rule *gr.Production[T]

	// Pos is the position of the item in the production rule.
	Pos int
	// contains filtered or unexported fields
}

Item represents an item in a decision table.

func NewItem 

func NewItem[T gr.TokenTyper](rule *gr.Production[T], pos int, rule_index int) (*Item[T], error)

NewItem is a constructor of Item.

Parameters:

  • rule: The production rule that the item represents.
  • pos: The position of the item in the production rule.
  • ruleIndex: The index of the rule in the decision table.

Returns:

  • *Item: The pointer to the new Item.
  • error: An error of type *uc.ErrInvalidParameter if the rule is nil or the pos is out of bounds.

func (*Item[T]) Copy 

func (i *Item[T]) Copy() uc.Copier

Copy implements the Copier interface.

func (*Item[T]) GetPos 

func (item *Item[T]) GetPos() int

GetPos returns the position of the item in the production rule.

Returns:

  • int: The position of the item.

func (*Item[T]) GetRhs 

func (item *Item[T]) GetRhs() T

GetRhs returns the right-hand side of the production rule at the current position.

Returns:

  • T: The right-hand side of the production rule.

func (*Item[T]) GetRhsAt 

func (item *Item[T]) GetRhsAt(index int) (T, error)

GetRhsAt returns the right-hand side of the production rule at the specified index.

Parameters:

  • index: The index of the right-hand side to get.

Returns:

  • T: The right-hand side of the production rule.
  • error: An error if it is unable to get the right-hand side.

Errors:

  • *uc.ErrInvalidParameter: If the index is out of bounds or the item's rule is nil.

func (*Item[T]) GetRule 

func (item *Item[T]) GetRule() *gr.Production[T]

GetRule returns the production rule that the item represents.

Returns:

  • *gr.Production: The production rule that the item represents.

func (*Item[T]) GetSymbolsUpToPos 

func (item *Item[T]) GetSymbolsUpToPos() []T

GetSymbolsUpToPos returns the symbols of the production rule up to the current position.

Returns:

  • []T: The symbols of the production rule up to the current position.

Behaviors:

  • The symbols are reversed. Thus, the symbol at index 0 is the current symbol of the item.

func (*Item[T]) IndicesOfRhs 

func (item *Item[T]) IndicesOfRhs(rhs T) []int

IndicesOfRhs returns the indices of the right-hand side of the item that match the specified right-hand side.

Parameters:

  • rhs: The right-hand side to search for.

Returns:

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

func (*Item[T]) IsLhsRhs 

func (item *Item[T]) IsLhsRhs(rhs T) bool

IsLhsRhs returns true if the left-hand side of the production rule matches the right-hand side.

Parameters:

  • rhs: The right-hand side to compare with the left-hand side.

Returns:

  • bool: True if the left-hand side matches the right-hand side. Otherwise, false.

func (*Item[T]) IsReduce 

func (item *Item[T]) IsReduce() bool

IsReduce returns true if the item is a reduce item.

Returns:

  • bool: True if the item is a reduce item. Otherwise, false.

Behaviors:

  • If the item's rule is nil, it returns false.

func (*Item[T]) ReplaceRhsAt 

func (item *Item[T]) ReplaceRhsAt(index int, rhs T) *Item[T]

ReplaceRhsAt replaces the right-hand side of the production rule at the given index with the right-hand side of the other item.

Parameters:

  • index: The index of the right-hand side to replace.
  • otherI: The other item to replace the right-hand side with.

Returns:

  • *Item: The new item with the replaced right-hand side.
  • error: An error if it is unable to replace the right-hand side.

Errors:

  • *uc.ErrInvalidParameter: If the other item is nil, otherI.Rule is nil, or the index is out of bounds.
  • *gr.ErrLhsRhsMismatch: If the left-hand side of the production rule does not match the right-hand side.

func (*Item[T]) String 

func (i *Item[T]) String() string

String implements the fmt.Stringer interface.

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

func (item *Item[T]) SubstituteRhsAt(index int, other_item *Item[T]) *Item[T]

ReplaceRhsAt replaces the right-hand side of the production rule at the given index with the right-hand side of the other item.

Parameters:

  • index: The index of the right-hand side to replace.
  • otherI: The other item to replace the right-hand side with.

Returns:

  • *Item: The new item with the replaced right-hand side.
  • error: An error if it is unable to replace the right-hand side.

Errors:

  • *uc.ErrInvalidParameter: If the other item is nil, otherI.Rule is nil, or the index is out of bounds.
  • *gr.ErrLhsRhsMismatch: If the left-hand side of the production rule does not match the right-hand side.

type RuleTable added in v0.1.10 

type RuleTable[T gr.TokenTyper] struct {
	// contains filtered or unexported fields
}

RuleTable represents a table of items.

func NewRuleTable added in v0.1.10 

func NewRuleTable[T gr.TokenTyper](symbols []T, rules []*gr.Production[T]) *RuleTable[T]

NewRuleTable is a constructor of RuleTable.

Parameters:

  • symbols: The symbols to use.
  • rules: The rules to use.

Returns:

  • *RuleTable: The new rule table.

func (*RuleTable[T]) GetBucketsCopy added in v0.1.10 

func (rt *RuleTable[T]) GetBucketsCopy() map[T][]*HelperNode[T]

GetBucketsCopy gets a copy of the buckets of the rule table.

Returns:

  • map[T]*uts.Bucket[*Helper]: The copy of the buckets.

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.