Class: RLTK::Parser::ParseStack

Inherits:
Object
  • Object
show all
Defined in:
lib/rltk/parser.rb

Overview

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

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(id, ostack = [], sstack = [0], nstack = [], connections = [], labels = [], positions = []) ⇒ ParseStack

Instantiate a new ParserStack object.

Parameters:

  • ID for this parse stack. Used by GLR algorithm.

  • (defaults to: [])

    Output stack. Holds results of Reduce and Shift actions.

  • (defaults to: [0])

    State stack. Holds states that have been shifted due to Shift actions.

  • (defaults to: [])

    Node stack. Holds dot language IDs for nodes in the parse tree.

  • (defaults to: [])

    Integer pairs representing edges in the parse tree.

  • (defaults to: [])

    Labels for nodes in the parse tree.

  • (defaults to: [])

    Position data for symbols that have been shifted.



1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
 
# 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

Instance Attribute Details

#id ⇒ Integer (readonly)

Returns ID of this parse stack.

Returns:

  • ID of this parse stack.



1327
1328
1329
 
# File 'lib/rltk/parser.rb', line 1327

def id
  @id
end

#output_stack ⇒ Array<Object> (readonly)

Returns Array of objects produced by Reduce actions.

Returns:

  • Array of objects produced by Reduce actions.



1330
1331
1332
 
# File 'lib/rltk/parser.rb', line 1330

def output_stack
  @output_stack
end

#state_stack ⇒ Array<Integer> (readonly)

Returns Array of states used when performing Reduce actions.

Returns:

  • Array of states used when performing Reduce actions.



1333
1334
1335
 
# File 'lib/rltk/parser.rb', line 1333

def state_stack
  @state_stack
end

Instance Method Details

#branch(new_id) ⇒ ParseStack

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

Parameters:

  • ID for the new ParseStack.

Returns:



1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
 
# 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

#pop(n = 1) ⇒ Array(Object, StreamPosition)

Pop some number of objects off of the inside stacks.

Parameters:

  • (defaults to: 1)

    Number of object to pop off the stack.

Returns:

  • Values popped from the output and positions stacks.



1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
 
# 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 ⇒ StreamPosition

Returns Position data for the last symbol on the stack.

Returns:

  • Position data for the last symbol on the stack.



1384
1385
1386
1387
1388
1389
1390
 
# 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) ⇒ void

This method returns an undefined value.

Push new state and other information onto the stack.

Parameters:

  • ID of the shifted state.

  • Value of Token that caused the shift.

  • Label for node in parse tree.

  • Position token that got shifted.



1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
 
# 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 ⇒ Object

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

Returns:

  • The end result of this parse stack.



1434
1435
1436
1437
1438
1439
1440
 
# 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 ⇒ Integer

Returns Current state of this ParseStack.

Returns:

  • Current state of this ParseStack.



1443
1444
1445
 
# File 'lib/rltk/parser.rb', line 1443

def state
  @state_stack.last
end

#tree ⇒ String

Returns Representation of the parse tree in the DOT langauge.

Returns:

  • Representation of the parse tree in the DOT langauge.



1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
 
# 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