Documentation
¶
Overview ¶
Package dss implements variants of a DAG-structured stack (DSS). It is used for GLR-parsing and for substring parsing. A DSS is suitable for parsing with ambiguous grammars, so the parser can execute a breadth-first (quasi-)parallel shift and/or reduce operation in inadequate (ambiguous) parse states.
Each parser (logical or real) sees it's own linear stack, but all stacks together form a DAG. Stacks share common fragments, making a DSS more space-efficient than a separeted forest of stacks. All stacks are anchored at the root of the DSS.
root := NewRoot("G", -1) // represents the DSS
stack1 := NewStack(root) // a linear stack within the DSS
stack2 := NewStack(root)
Please note that a DSS (this one, at least) is not well suited for general purpose stack operations. The non-deterministic concept of GLR-parsing will always lurk in the detail of this implementation.
API ¶
The main API of this DSS consists of
root = NewRoot("...", impossible)
stack = NewStack(root)
state, symbol = stack.Peek() // peek at top state and symbol of stack
newstack = stack.Fork() // duplicate stack
stacks = stack.Reduce(handle) // reduce with RHS of a production
stack = stack.Push(state, symbol) // transition to new parse state, i.e. a shift
stack.Die() // end of life for this stack
Additionally, there are some low-level methods, which may help debugging or implementing your own add-on functionality.
nodes = stack.FindHandlePath(handle, 0) // find a string of symbols down the stack DSS2Dot(root, path, writer) // output to Graphviz DOT format WalkDAG(root, worker, arg) // execute a function on each DSS node
Other methods of the API are rarely used in parsing and exist more or less to complete a conventional stack API. Note that a method for determining the size of a stack is missing.
stacks = stack.Pop()
GLR Parsing ¶
A GLR parser forks a stack whenever an ambiguous state on top of the parse stack is processed. In a GLR-parser, shift/reduce- and reduce/reduce-conflicts are not uncommon, as potentially ambiguous grammars are used.
Assume that a shift/reduce-conflict is signalled by the TOS. Then the parser will duplicate the stack (stack.Fork()) and carry out both operations: for one stack a symbol will be shifted, the other will be used for the reduce-operations.
Further Information ¶
For further information see for example
https://people.eecs.berkeley.edu/~necula/Papers/elkhound_cc04.pdf
Status ¶
This is experimental software, currently not intended for production use.
BSD License ¶
Copyright (c) 2017-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 ¶
- func DSS2Dot(root *Root, path []*Node, w io.Writer)
- func PrintDSS(root *Root)
- func T() tracing.Trace
- func WalkDAG(root *Root, worker func(*Node, interface{}), arg interface{})
- type Node
- type NodePath
- type Root
- type Stack
- func (stack *Stack) Die()
- func (stack *Stack) FindHandlePath(handle []*lr.Symbol, skip int) NodePath
- func (stack *Stack) Fork() *Stack
- func (stack *Stack) IsAlone() bool
- func (stack *Stack) Peek() (int, *lr.Symbol)
- func (stack *Stack) Pop() (ret []*Stack)
- func (stack *Stack) Push(state int, sym *lr.Symbol) *Stack
- func (stack *Stack) Reduce(handle []*lr.Symbol) (ret []*Stack)
- func (stack *Stack) String() string
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
Types ¶
type Node ¶
type Node struct {
State int // identifier of a parse state
Sym *lr.Symbol // symbol on the stack (between states)
// contains filtered or unexported fields
}
Node is a type for a node in a DSS stack.
type NodePath ¶
type NodePath []*Node
NodePath is a run within a stack. We often will have to deal with fragments of a stack
type Root ¶
type Root struct {
Name string // identifier for the DSS
// contains filtered or unexported fields
}
Root is the root of a DSS-stack. All stacks of a DSS stack structure share a common root. Clients have to create a root before stacks can be created.
func NewRoot ¶
NewRoot creates a named root for a DSS-stack, given a name. The second parameter is an implementation detail: clients have to supply a state the root will use as a stopper. It should be an "impossible" state for normal execution, to avoid confusion.
func (*Root) ActiveStacks ¶
ActiveStacks gets the stack-heads currently active in the DSS. No order is guaranteed.
func (*Root) IsAlone ¶
IsAlone checks if a stack may safely delete nodes for a reduce operation. There are exactly two cases when deletion is not permitted: (1) One or more other stacks are sitting on the same node as this one (2) There are nodes present further up the stack (presumably operated on by other stacks).
type Stack ¶
type Stack struct {
// contains filtered or unexported fields
}
Stack is a data structure for a linear stack within a DSS (DAG structured stack = DSS). All stacks together form a DSS, i.e. they may share portions of stacks. Each client carries its own stack, without noticing the other stacks. The data structure hides the fact that stack- fragments may be shared.
func (*Stack) Die ¶
func (stack *Stack) Die()
Die signals end of life for this stack. The stack will be detached from the DSS root and will let go of its TOS.
func (*Stack) FindHandlePath ¶
FindHandlePath finds a run within a stack corresponding to a handle, i.e., a list of parse symbols.
For reduce operations on a stack it is necessary to identify the nodes which correspond to the symbols of the RHS of the production to reduce. The nodes (some or all) may overlap with other stacks of the DSS.
For a RHS there may be more than one path downwards the stack marked with the symbols of RHS. It is not deterministic which one this method will find and return. Clients may call this method multiple times. If a clients wants to find all simultaneously existing paths, it should increment the parameter skip every time. This determines the number of branches have been found previously and should be skipped now.
Will return nil if no (more) path is found.
func (*Stack) Fork ¶
Fork duplicates the head of a stack, resulting in a new stack. The new stack is implicitely registered with the (common) root.
func (*Stack) IsAlone ¶
IsAlone checks if a stack may safely delete nodes for a reduce operation. There are exactly two cases when deletion is not permitted: (1) One or more other stacks are sitting on the same node as this one (2) There are nodes present further up the stack (presumably operated on by other stacks).
func (*Stack) Pop ¶
Pop the TOS of a stack. This is straigtforward for (non-empty) linear stacks without shared nodes. For stacks with common suffixes, i.e. with inverse joins, it is more tricky. The popping may result in multiple new stacks, one for each predecessor.
For parsers Pop may not be very useful. It is included here for conformance with the general contract of a stack. With parsing, popping of states happens during reductions, and the API offers more convenient functions for this.
func (*Stack) Push ¶
Push a state and a symbol on the stack. Interpretation is as follows: a transition has been found consuming symbol sym, leading to state state.
The method looks for a TOS in the DSS representing the combination of (state, sym) and -- if present -- uses (reverse joins) the TOSs. Otherwise it creates a new DAG node.
func (*Stack) Reduce ¶
Reduce performs a reduce operation, given a handle, i.e. a right hand side of a grammar rule. Strictly speaking, it performs not a complete reduce operation, but just the first part: popping the RHS symbols off the stack. Clients will have to push the LHS symbol separately.
With a DSS, reduce may result in a multitude of new stack configurations. Whenever there is a reduce/reduce conflict or a shift/reduce-conflict, a GLR parser will perform both reduce-operations. To this end each possible operation (i.e, parser) will (conceptually) use its own stack. Thus multiple return values of a reduce operation correspond to (temporary or real) ambiguity of a grammar.
Example: X ::= A + A (grammar rule)
Stack 1: ... a A + A
Stack 2: ... A + A + A
as a DSS: -[a]------
[A] [+]-[A] // now reduce this: A + A to X
-[A]-[+]--
This will result in 2 new stack heads:
as a DSS: -[a] // return stack #1 of Reduce() -[A]-[+] // return stack #2 of Reduce()
After pushing X onto the stack, the 2 stacks may be merged (on 'X'), thus resulting in a single stack head again.
as a DSS: -[a]----- [X] -[A]-[+]-
The stack triggering the reduce will be the first stack within the returning array of stacks, i.e. the Reduce() return the stack itself plus possibly other stacks created during the reduce operation.
Source Files