ConflictSolver

package
v0.1.18 Latest Latest
Warning

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

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

Documentation

Index

Constants

This section is empty.

Variables

View Source 
var (
	// 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.
	FilterTerminalLeaf us.PredicateFilter[*tr.TreeNode[*Helper]]

	// 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.
	FilterNonTerminalLeaf us.PredicateFilter[*tr.TreeNode[*Helper]]
)
View Source 
var GlobalDebugMode bool = true

Functions

func MatchAction added in v0.1.10 

func MatchAction(a Actioner, top gr.Token, stack *ud.History[lls.Stacker[gr.Token]]) 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 ActReduce 

type ActReduce struct {
	*Action
	// contains filtered or unexported fields
}

ActReduce represents a reduce action.

func NewActReduce 

func NewActReduce(rule *gr.Production, shouldAccept bool) *ActReduce

NewActReduce creates a new reduce action.

Parameters:

  • rule: The rule to reduce by.
  • shouldAccept: True if the reduce action should accept.

Returns:

  • *ActReduce: A pointer to the new reduce action.

Behaviors:

  • If the rule is nil, nil is returned.

func (*ActReduce) Copy 

func (a *ActReduce) Copy() uc.Copier

Copy implements the common.Copier interface.

func (*ActReduce) GetOriginal added in v0.1.10 

func (a *ActReduce) GetOriginal() *gr.Production

GetOriginal returns the original rule to reduce by.

Returns:

  • *gr.Production: The original rule to reduce by.

func (*ActReduce) GetRule 

func (a *ActReduce) GetRule() *gr.Production

GetRule returns the rule to reduce by.

Returns:

  • *gr.Production: The rule to reduce by.

func (*ActReduce) ShouldAccept added in v0.1.10 

func (a *ActReduce) ShouldAccept() bool

ShouldAccept returns true if the reduce action should accept.

Returns:

  • bool: True if the reduce action should accept.

func (*ActReduce) String 

func (a *ActReduce) String() string

String implements the Actioner interface.

type ActShift 

type ActShift struct {
	*Action
}

ActShift represents a shift action.

func NewActShift 

func NewActShift() *ActShift

NewActShift creates a new shift action.

Returns:

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

func (*ActShift) Copy 

func (a *ActShift) Copy() uc.Copier

Copy implements the common.Copier interface.

func (*ActShift) String 

func (a *ActShift) String() string

String implements the Actioner interface.

type Action added in v0.1.10 

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

Action represents an action in a decision table.

func (*Action) AppendRhs added in v0.1.10 

func (a *Action) AppendRhs(rhs string)

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

Parameters:

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

func (*Action) GetLookahead added in v0.1.10 

func (a *Action) GetLookahead() *string

GetLookahead returns the lookahead token ID for the action.

Returns:

  • *string: The lookahead token ID.

func (*Action) Iterator added in v0.1.10 

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

Iterator implements the Iterators.Iterater interface.

func (*Action) SetLookahead added in v0.1.10 

func (a *Action) SetLookahead(lookahead *string)

SetLookahead sets the lookahead token ID for the action.

Parameters:

  • lookahead: The lookahead token ID to set.

func (*Action) Size added in v0.1.10 

func (a *Action) Size() int

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

Returns:

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

func (*Action) String added in v0.1.10 

func (a *Action) String() string

String implements the Actioner interface.

type Actioner 

type Actioner interface {
	// GetLookahead returns the lookahead token ID for the action.
	//
	// Returns:
	//   - *string: The lookahead token ID.
	GetLookahead() *string

	// Iterator returns an iterator of the right-hand side tokens.
	//
	// Returns:
	//   - uc.Iterater[string]: An iterator of the right-hand side tokens.
	Iterator() uc.Iterater[string]

	fmt.Stringer
}

Actioner represents an action that the parser will take.

type CMPerSymbol 

type CMPerSymbol map[string]uc.Pair[[]*Helper, int]

CMPerSymbol is a type that represents conflicts per symbol.

type ConflictSolver 

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

ConflictSolver solves conflicts in a decision table.

func NewConflictSolver 

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

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(symbols []string, rules []*gr.Production) (*ConflictSolver, 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) FString 

func (cs *ConflictSolver) 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) FindConflicts 

func (cs *ConflictSolver) FindConflicts() CMPerSymbol

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

func (cs *ConflictSolver) GetElemsWithLhs(rhs string) []*Helper

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

func (cs *ConflictSolver) MakeExpansionForests(index int, nextRhs map[*Helper]string) (map[*Helper][]string, 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) Match 

func (cs *ConflictSolver) Match(stack *ud.History[lls.Stacker[gr.Token]]) ([]HelperElem, 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) Solve 

func (cs *ConflictSolver) Solve() error

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

Returns:

  • error: An error if the operation failed.

func (*ConflictSolver) SolveAmbiguous 

func (cs *ConflictSolver) SolveAmbiguous(index int, conflicts []*Helper) (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) SolveAmbiguousShifts 

func (cs *ConflictSolver) 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 struct {
	// Elem is the helper that caused the error.
	Elem *Helper

	// 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(elem *Helper, reason error) *ErrHelper

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

func (e *ErrHelper) 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 struct {
	// contains filtered or unexported fields
}

ExpansionTree is a tree of expansion helpers.

func NewExpansionTreeRootedAt 

func NewExpansionTreeRootedAt(cs *ConflictSolver, h *Helper) (*ExpansionTree, 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) Collapse 

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

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

Returns:

  • []string: The collapsed expansion tree.

func (*ExpansionTree) PruneNonTerminalLeaves 

func (et *ExpansionTree) PruneNonTerminalLeaves()

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

func (*ExpansionTree) Size 

func (et *ExpansionTree) Size() int

Size returns the size of the expansion tree.

Returns:

  • int: The size of the expansion tree.

type Helper 

type Helper struct {
	// Item is the item of the helper.
	*Item

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

Helper represents a helper in a decision table.

func NewHelper 

func NewHelper(item *Item, action HelperElem) *Helper

NewHelper is a constructor of Helper.

Parameters:

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

Returns:

  • *Helper: The pointer to the new Helper.

Behaviors:

  • If the item or action are nil, then nil is returned.

func (*Helper) AppendRhs 

func (h *Helper) AppendRhs(symbol string) error

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

Parameters:

  • symbol: The symbol to append.

Returns:

  • error: An error of type *ErrNoActionProvided if the action is nil.

func (*Helper) Copy 

func (h *Helper) Copy() uc.Copier

Copy implements the common.Copier interface.

func (*Helper) EvaluateLookahead 

func (h *Helper) EvaluateLookahead() error

EvaluateLookahead evaluates the lookahead of the action.

Returns:

  • error: An error if the evaluation failed.

func (*Helper) ForceLookahead added in v0.1.10 

func (h *Helper) ForceLookahead(lookahead string)

ForceLookahead forces the lookahead of the action.

Parameters:

  • lookahead: The lookahead to force.

func (*Helper) GetAction added in v0.1.9 

func (h *Helper) GetAction() HelperElem

GetAction returns the action of the helper.

Returns:

  • Actioner: The action of the helper.

func (*Helper) GetLookahead 

func (h *Helper) GetLookahead() *string

GetLookahead returns the lookahead of the action.

Returns:

  • *string: The lookahead token ID.

func (*Helper) Match added in v0.1.9 

func (h *Helper) Match(top gr.Token, stack *ud.History[lls.Stacker[gr.Token]]) 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 (*Helper) ReplaceRhsAt 

func (h *Helper) ReplaceRhsAt(index int, rhs string) *Helper

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 (*Helper) SetAction 

func (h *Helper) SetAction(action HelperElem)

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 (*Helper) Size added in v0.1.9 

func (h *Helper) Size() int

Size returns the size of the helper.

Returns:

  • int: The size of the helper.

Behaviors:

  • If the action is invalid, -1 is returned.

func (*Helper) String 

func (h *Helper) String() string

String implements the fmt.Stringer interface.

func (*Helper) SubstituteRhsAt added in v0.1.10 

func (h *Helper) SubstituteRhsAt(index int, otherH *Helper) *Helper

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 HelperElem added in v0.1.10 

type HelperElem interface {
	// SetLookahead sets the lookahead of the action.
	//
	// Parameters:
	//   - lookahead: The lookahead to set.
	SetLookahead(lookahead *string)

	fmt.Stringer
	uc.Copier
}

type InfoStruct 

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

InfoStruct is the information about the expansion tree.

func NewInfoStruct 

func NewInfoStruct(root *Helper) *InfoStruct

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

func (is *InfoStruct) Copy() uc.Copier

Copy implements the Copier interface.

func (*InfoStruct) IsNotSeen added in v0.1.10 

func (is *InfoStruct) IsNotSeen(h *Helper) 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) SetSeen added in v0.1.10 

func (is *InfoStruct) SetSeen(h *Helper)

SetSeen sets the helper as seen.

Parameters:

  • h: The helper to set as seen.

type Item 

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

	// 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(rule *gr.Production, pos int, ruleIndex int) (*Item, 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) Copy 

func (i *Item) Copy() uc.Copier

Copy implements the Copier interface.

func (*Item) GetPos 

func (item *Item) GetPos() int

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

Returns:

  • int: The position of the item.

func (*Item) GetRhs 

func (item *Item) GetRhs() string

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

Returns:

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

func (*Item) GetRhsAt 

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

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

func (item *Item) GetRule() *gr.Production

GetRule returns the production rule that the item represents.

Returns:

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

func (*Item) GetSymbolsUpToPos 

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

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

Returns:

  • []string: 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) IndicesOfRhs 

func (item *Item) IndicesOfRhs(rhs string) []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) IsLhsRhs 

func (item *Item) IsLhsRhs(rhs string) 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) IsReduce 

func (item *Item) 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) ReplaceRhsAt 

func (item *Item) ReplaceRhsAt(index int, rhs string) *Item

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

func (i *Item) String() string

String implements the fmt.Stringer interface.

func (*Item) SubstituteRhsAt added in v0.1.10 

func (item *Item) SubstituteRhsAt(index int, otherI *Item) *Item

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 struct {
	// contains filtered or unexported fields
}

RuleTable represents a table of items.

func NewRuleTable added in v0.1.10 

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

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) GetBucketsCopy added in v0.1.10 

func (rt *RuleTable) GetBucketsCopy() map[string][]*Helper

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

Returns:

  • map[string]*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.