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 (Integer) —

    ID for this parse stack. Used by GLR algorithm.

  • ostack (Array<Object>) (defaults to: []) —

    Output stack. Holds results of Reduce and Shift actions.

  • sstack (Array<Integer>) (defaults to: [0]) —

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

  • nstack (Array<Integer>) (defaults to: []) —

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

  • connections (Array<Array<Integer>>) (defaults to: []) —

    Integer pairs representing edges in the parse tree.

  • labels (Array<Symbol>) (defaults to: []) —

    Labels for nodes in the parse tree.

  • positions (Array<StreamPosition>) (defaults to: []) —

    Position data for symbols that have been shifted.



1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
 
# File 'lib/rltk/parser.rb', line 1301

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:

  • (Integer) —

    ID of this parse stack.



1284
1285
1286
 
# File 'lib/rltk/parser.rb', line 1284

def id
  @id
end

#output_stack ⇒ Array<Object> (readonly)

Returns Array of objects produced by Reduce actions.

Returns:

  • (Array<Object>) —

    Array of objects produced by Reduce actions.



1287
1288
1289
 
# File 'lib/rltk/parser.rb', line 1287

def output_stack
  @output_stack
end

#state_stack ⇒ Array<Integer> (readonly)

Returns Array of states used when performing Reduce actions.

Returns:

  • (Array<Integer>) —

    Array of states used when performing Reduce actions.



1290
1291
1292
 
# File 'lib/rltk/parser.rb', line 1290

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:

  • new_id (Integer) —

    ID for the new ParseStack.

Returns:



1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
 
# File 'lib/rltk/parser.rb', line 1319

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:

  • n (Integer) (defaults to: 1) —

    Number of object to pop off the stack.

Returns:

  • (Array(Object, StreamPosition)) —

    Values popped from the output and positions stacks.



1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
 
# File 'lib/rltk/parser.rb', line 1376

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:

  • (StreamPosition) —

    Position data for the last symbol on the stack.



1341
1342
1343
1344
1345
1346
1347
 
# File 'lib/rltk/parser.rb', line 1341

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:

  • state (Integer) —

    ID of the shifted state.

  • o (Object) —

    Value of Token that caused the shift.

  • node0 (Symbol) —

    Label for node in parse tree.

  • position (StreamPosition) —

    Position token that got shifted.



1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
 
# File 'lib/rltk/parser.rb', line 1357

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:

  • (Object) —

    The end result of this parse stack.



1391
1392
1393
1394
1395
1396
1397
 
# File 'lib/rltk/parser.rb', line 1391

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:

  • (Integer) —

    Current state of this ParseStack.



1400
1401
1402
 
# File 'lib/rltk/parser.rb', line 1400

def state
	@state_stack.last
end

#tree ⇒ String

Returns Representation of the parse tree in the DOT langauge.

Returns:

  • (String) —

    Representation of the parse tree in the DOT langauge.



1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
 
# File 'lib/rltk/parser.rb', line 1405

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