class RLTK::Parser::ParseStack

The ParseStack class is used by a Parser to keep track of state during parsing.

Attributes

id[R]

@return [Integer] ID of this parse stack.

output_stack[R]

@return [Array<Object>] Array of objects produced by {Reduce} actions.

state_stack[R]

@return [Array<Integer>] Array of states used when performing {Reduce} actions.

Public Class Methods

new(id, ostack = [], sstack = [0], nstack = [], connections = [], labels = [], positions = []) click to toggle source

Instantiate a new ParserStack object.

@param [Integer] id ID for this parse stack. Used by GLR algorithm. @param [Array<Object>] ostack Output stack. Holds results of {Reduce} and {Shift} actions. @param [Array<Integer>] sstack State stack. Holds states that have been shifted due to {Shift} actions. @param [Array<Integer>] nstack Node stack. Holds dot language IDs for nodes in the parse tree. @param [Array<Array<Integer>>] connections Integer pairs representing edges in the parse tree. @param [Array<Symbol>] labels Labels for nodes in the parse tree. @param [Array<StreamPosition>] positions Position data for symbols that have been shifted.

# File lib/rltk/parser.rb, line 1344
def initialize(id, ostack = [], sstack = [0], nstack = [], connections = [], labels = [], positions = [])
        @id = id

        @node_stack   = nstack
        @output_stack = ostack
        @state_stack  = sstack

        @connections  = connections
        @labels       = labels
        @positions    = positions
end

Public Instance Methods

branch(new_id) click to toggle source

Branch this stack, effectively creating a new copy of its internal state.

@param [Integer] new_id ID for the new ParseStack.

@return [ParseStack]

# File lib/rltk/parser.rb, line 1362
        def branch(new_id)
                # We have to do a deeper copy of the output stack to avoid
                # interactions between the Proc objects for the different
                # parsing paths.
                #
                # The being/rescue block is needed because some classes
                # respond to `clone` but always raise an error.
                new_output_stack = @output_stack.map do |o|
                        # Check to see if we can obtain a deep copy.
                        if 0.respond_to?(:copy)
                                o.copy

                        else
                                begin o.clone rescue o end
                        end
                end

                ParseStack.new(new_id, new_output_stack, @state_stack.clone,
                        @node_stack.clone, @connections.clone, @labels.clone, @positions.clone)
        end

        # @return [StreamPosition] Position data for the last symbol on the stack.
        def position
                if @positions.empty?
                        StreamPosition.new
                else
                        @positions.last.clone
                end
        end

        # Push new state and other information onto the stack.
        #
        # @param [Integer]                   state   ID of the shifted state.
        # @param [Object]                    o                Value of Token that caused the shift.
        # @param [Symbol]                    node0    Label for node in parse tree.
        # @param [StreamPosition]    position   Position token that got shifted.
        #
        # @return [void]
        def push(state, o, node0, position)
                @state_stack        << state
                @output_stack       << o
                @node_stack << @labels.length
                @labels             << if CFG::is_terminal?(node0) and o then node0.to_s + "(#{o})" else node0 end
                @positions  << position

                if CFG::is_nonterminal?(node0)
                        @cbuffer.each do |node1|
                                @connections << [@labels.length - 1, node1]
                        end
                end
        end

        # Pop some number of objects off of the inside stacks.
        #
        # @param [Integer] n Number of object to pop off the stack.
        #
        # @return [Array(Object, StreamPosition)] Values popped from the output and positions stacks.
        def pop(n = 1)
                @state_stack.pop(n)

                # Pop the node stack so that the proper edges can be added
                # when the production's left-hand side non-terminal is
                # pushed onto the stack.
                @cbuffer = @node_stack.pop(n)

                [@output_stack.pop(n), @positions.pop(n)]
        end

        # Fetch the result stored in this ParseStack.  If there is more
        # than one object left on the output stack there is an error.
        #
        # @return [Object] The end result of this parse stack.
        def result
                if @output_stack.length == 1
                        return @output_stack.last
                else
                        raise InternalParserException, "The parsing stack should have 1 element on the output stack, not #{@output_stack.length}."
                end
        end

        # @return [Integer] Current state of this ParseStack.
        def state
                @state_stack.last
        end

        # @return [String] Representation of the parse tree in the DOT langauge.
        def tree
                tree  = "digraph tree#{@id} {\n"

                @labels.each_with_index do |label, i|
                        tree += "\tnode#{i} [label=\"#{label}\""

                        if CFG::is_terminal?(label)
                                tree += " shape=box"
                        end

                        tree += "];\n"
                end

                tree += "\n"

                @connections.each do |from, to|
                        tree += "\tnode#{from} -> node#{to};\n"
                end

                tree += "}"
        end
end
pop(n = 1) click to toggle source

Pop some number of objects off of the inside stacks.

@param [Integer] n Number of object to pop off the stack.

@return [Array(Object, StreamPosition)] Values popped from the output and positions stacks.

# File lib/rltk/parser.rb, line 1419
def pop(n = 1)
        @state_stack.pop(n)

        # Pop the node stack so that the proper edges can be added
        # when the production's left-hand side non-terminal is
        # pushed onto the stack.
        @cbuffer = @node_stack.pop(n)

        [@output_stack.pop(n), @positions.pop(n)]
end
position() click to toggle source

@return [StreamPosition] Position data for the last symbol on the stack.

# File lib/rltk/parser.rb, line 1384
def position
        if @positions.empty?
                StreamPosition.new
        else
                @positions.last.clone
        end
end
push(state, o, node0, position) click to toggle source

Push new state and other information onto the stack.

@param [Integer] state ID of the shifted state. @param [Object] o Value of Token that caused the shift. @param [Symbol] node0 Label for node in parse tree. @param [StreamPosition] position Position token that got shifted.

@return [void]

# File lib/rltk/parser.rb, line 1400
def push(state, o, node0, position)
        @state_stack        << state
        @output_stack       << o
        @node_stack << @labels.length
        @labels             << if CFG::is_terminal?(node0) and o then node0.to_s + "(#{o})" else node0 end
        @positions  << position

        if CFG::is_nonterminal?(node0)
                @cbuffer.each do |node1|
                        @connections << [@labels.length - 1, node1]
                end
        end
end
result() click to toggle source

Fetch the result stored in this ParseStack. If there is more than one object left on the output stack there is an error.

@return [Object] The end result of this parse stack.

# File lib/rltk/parser.rb, line 1434
def result
        if @output_stack.length == 1
                return @output_stack.last
        else
                raise InternalParserException, "The parsing stack should have 1 element on the output stack, not #{@output_stack.length}."
        end
end
state() click to toggle source

@return [Integer] Current state of this ParseStack.

# File lib/rltk/parser.rb, line 1443
def state
        @state_stack.last
end
tree() click to toggle source

@return [String] Representation of the parse tree in the DOT langauge.

# File lib/rltk/parser.rb, line 1448
def tree
        tree  = "digraph tree#{@id} {\n"

        @labels.each_with_index do |label, i|
                tree += "\tnode#{i} [label=\"#{label}\""

                if CFG::is_terminal?(label)
                        tree += " shape=box"
                end

                tree += "];\n"
        end

        tree += "\n"

        @connections.each do |from, to|
                tree += "\tnode#{from} -> node#{to};\n"
        end

        tree += "}"
end