sppf

Documentation

Overview

Package sppf implements a "Shared Packed Parse Forest".

A packed parse forest re-uses existing parse tree nodes between different parse trees. For a conventional non-ambiguous parse, a parse forest degrades to a single tree. Ambiguous grammars, on the other hand, may result in parse runs where more than one parse tree is created. To save space these parse trees will share common nodes.

BSD License

Copyright (c) 2019–20, Norbert Pillmayer

All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.

2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

3. Neither the name of this software nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Index

• Variables
• func T() tracing.Trace
• func ToGraphViz(forest *Forest, w io.Writer)
• type Breakmode
• type Cursor
  • func (c *Cursor) BottomUp(Listener, Direction, Breakmode) interface{}
  • func (c *Cursor) Down(dir Direction) (*RuleNode, bool)
  • func (c *Cursor) RHS(sym *SymbolNode) (int, []*RuleNode)
  • func (c *Cursor) Sibling() (*RuleNode, bool)
  • func (c *Cursor) TopDown(listener Listener, dir Direction, breakmode Breakmode) interface{}
  • func (c *Cursor) Up() (*RuleNode, bool)
• type Direction
• type Forest
  • func NewForest() *Forest
  • func (f *Forest) AddEpsilonReduction(sym *lr.Symbol, rule int, pos uint64) *SymbolNode
  • func (f *Forest) AddReduction(sym *lr.Symbol, rule int, rhs []*SymbolNode) *SymbolNode
  • func (f *Forest) AddTerminal(t *lr.Symbol, pos uint64) *SymbolNode
  • func (f *Forest) Root() *RuleNode
  • func (f *Forest) SetCursor(rnode *RuleNode, pruner Pruner) *Cursor
  • func (f *Forest) SetRoot(symnode *SymbolNode)
• type Listener
• type Pruner
• type RuleCtxt
• type RuleNode
  • func (rnode *RuleNode) HasConflict() bool
  • func (rnode *RuleNode) Span() lr.Span
  • func (rnode *RuleNode) Symbol() *lr.Symbol
• type SymbolNode
  • func (sn *SymbolNode) String() string

Variables

var DontCarePruner dcp = dcp{}

DontCarePruner never prunes an ambiguity alternative, thus resulting in always selecting the first alternative considered. It is the default Pruner if none is given by the caller of a Cursor.

Functions

func T

func T() tracing.Trace

T traces to the global SyntaxTracer

func ToGraphViz

func ToGraphViz(forest *Forest, w io.Writer)

ToGraphViz exports an SPPF to an io.Writer in GrahpViz DOT format.

Types

type Breakmode

type Breakmode int

Breakmode is a client hint wether to stop traversing on break-signals or not.

const (
	Continue Breakmode = iota
	Break
)

Setting Continue will always traverse a complete (sub-)tree. Break will skip traversing sub-tree as soon as an Enter-function signals a break.

type Cursor

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

A Cursor is a movable mark within a parse forest, intended for navigating over rule nodes. It abstracts away the notion of the and-or-tree. Clients therefore are able to view the parse forest as a tree of SymbolNodes.

func (*Cursor) BottomUp

func (c *Cursor) BottomUp(Listener, Direction, Breakmode) interface{}

BottomUp TODO

func (*Cursor) Down

func (c *Cursor) Down(dir Direction) (*RuleNode, bool)

Down moves the cursor down to the first child of the curent node, if any. dir lets clients start at either the leftmost child (default) or the rightmost child.

func (*Cursor) RHS

func (c *Cursor) RHS(sym *SymbolNode) (int, []*RuleNode)

RHS collects the children symbols of a node as a slice. It uses a pruner to decide between ambiguous RHS variants.

func (*Cursor) Sibling

func (c *Cursor) Sibling() (*RuleNode, bool)

Sibling moves the cursor to the next sibling of the current node, if any.

func (*Cursor) TopDown

func (c *Cursor) TopDown(listener Listener, dir Direction, breakmode Breakmode) interface{}

TopDown traverses a sub-tree top-down, applying Listener-methods for all nodes encountered. It returns a user-defined value, calculated by the listener.

func (*Cursor) Up

func (c *Cursor) Up() (*RuleNode, bool)

Up moves the cursor up to the parent node of the current node, if any.

type Direction

type Direction int

Direction lets clients decide wether children nodes should be traversed left-to-right (default) or right-to-left.

const (
	LtoR Direction = 1
	RtoL Direction = -1
)

Children nodes may be traversed left-to-right (default) or right-to-left.

type Forest

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

Forest is a data structure for a "shared packed parse forest" (SPPF). A packed parse forest re-uses existing parse tree nodes between different parse trees. For a conventional non-ambiguous parse, a parse forest consists of a single tree. Ambiguous grammars, on the other hand, may result in parse runs where more than one parse tree is created. To save space these parse trees will share common nodes.

func NewForest

func NewForest() *Forest

NewForest returns an empty forest.

func (*Forest) AddEpsilonReduction

func (f *Forest) AddEpsilonReduction(sym *lr.Symbol, rule int, pos uint64) *SymbolNode

AddEpsilonReduction adds a node for a reduced ε-production.

func (*Forest) AddReduction

func (f *Forest) AddReduction(sym *lr.Symbol, rule int, rhs []*SymbolNode) *SymbolNode

AddReduction adds a node for a reduced grammar rule into the forest. The extent of the reduction is derived from the RHS-nodes.

If the RHS is void, nil is returned. For this case, clients should use AddEpsilonReduction instead.

func (*Forest) AddTerminal

func (f *Forest) AddTerminal(t *lr.Symbol, pos uint64) *SymbolNode

AddTerminal adds a node for a recognized terminal into the forest.

func (*Forest) Root

func (f *Forest) Root() *RuleNode

Root returns the root node of a parse forest.

func (*Forest) SetCursor

func (f *Forest) SetCursor(rnode *RuleNode, pruner Pruner) *Cursor

SetCursor sets up a cursor at a given rule node in a given forest. If rnode is nil, the cursor will be set up at the root node of the forest.

A pruner may be given for solving disambiguities. If it is nil, parse tree variants will be selected at random.

func (*Forest) SetRoot

func (f *Forest) SetRoot(symnode *SymbolNode)

SetRoot tells the parse forest which of the nodes will be the root node. This is intended for cases where no top-level artificial symbol S' has been wrapped around the grammar (usually done by the grammar analyzer).

type Listener

type Listener interface {
	EnterRule(*lr.Symbol, []*RuleNode, RuleCtxt) bool
	ExitRule(*lr.Symbol, []*RuleNode, RuleCtxt) interface{}
	Terminal(int, interface{}, RuleCtxt) interface{}
	Conflict(*lr.Symbol, RuleCtxt) (int, error)
	MakeAttrs(*lr.Symbol) interface{}
}

Listener is a type for walking a parse tree/forest.

Arguments are:

• *lr.Symbol: the grammar symbol at the current node
• []*RuleNode: the right-hand side of the grammar production at this node
• RuleCtxt: contextual information for the node

enterRule returns a boolean value indicating if the traversal should continue to the children of this node. ExitRule and Terminal may return user-defined values to be propagated upwards of the tree.

Conflict is called whenever the traversal encounters an ambiguous node, i.e. one where the parse symbol has more than one right-hand side, resulting from different applications of grammar productions. The return value indicates the positional number of the RHS-variant to be selected. If it returns an error, traversal will be aborted. (If in doubt what to do, simply return (0, nil).)

type Pruner

type Pruner interface {
	// contains filtered or unexported methods
}

Pruner is an interface type for an entity to help prune ambiguous children edges.

type RuleCtxt

type RuleCtxt struct {
	Span      lr.Span     // span of input symbols covered by this rule
	Level     int         // nesting level
	RuleIndex int         // -1 for terminals
	Attrs     interface{} // client-defined attributes local to node
}

RuleCtxt is a context structure for Listeners.

type RuleNode

type RuleNode struct {
	Value interface{} // user-defined value of a node
	// contains filtered or unexported fields
}

RuleNode represents a node occuring during a parse tree/forest walk.

func (*RuleNode) HasConflict

func (rnode *RuleNode) HasConflict() bool

HasConflict returns true if this node is ambiguous.

func (*RuleNode) Span

func (rnode *RuleNode) Span() lr.Span

Span returns the span of input symbols this rule covers.

func (*RuleNode) Symbol

func (rnode *RuleNode) Symbol() *lr.Symbol

Symbol returns the grammar symbol a RuleNode refers to. It is either a terminal or the LHS of a reduced rule.

type SymbolNode

type SymbolNode struct {
	Symbol *lr.Symbol // A
	Extent lr.Span    // (x…y), i.e., positions in the input covered by this symbol
}

SymbolNode represents a node in the parse forest, referencing a grammar symbol which has been reduced (Earley: completed).

func (*SymbolNode) String

func (sn *SymbolNode) String() string