Class: Rley::SPPF::ParseForest

Inherits:
Object
  • Object
show all
Defined in:
lib/rley/sppf/parse_forest.rb

Overview

In an ambiguous grammar there are valid inputs that can result in multiple parse trees. A set of parse trees is commonly referred to as a parse forest. More specifically a parse forest is a graph data structure designed to represent a set of equally syntactically correct parse trees. Parse forests generated by Rley are so-called Shared Packed Parse Forests (SPPF). SPPFs allow very compact representation of parse trees by sharing common sub-tree amongst the parse trees.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(theRootNode) ⇒ ParseForest

Returns a new instance of ParseForest.

Parameters:

  • theRootNode (ParseForestNode) —

    The root node of the parse tree.



26
27
28
29
30
 
# File 'lib/rley/sppf/parse_forest.rb', line 26

def initialize(theRootNode)
  @root = theRootNode
  @key2node = {}
  @is_ambiguous = false
end

Instance Attribute Details

#is_ambiguous=(value) ⇒ Object (writeonly)

A setter that tells that the parse is ambiguous.



22
23
24
 
# File 'lib/rley/sppf/parse_forest.rb', line 22

def is_ambiguous=(value)
  @is_ambiguous = value
end

#key2node ⇒ Object (readonly)

A Hash with pairs of the kind node key => node



19
20
21
 
# File 'lib/rley/sppf/parse_forest.rb', line 19

def key2node
  @key2node
end

#root ⇒ Object (readonly)

The root node of the forest



16
17
18
 
# File 'lib/rley/sppf/parse_forest.rb', line 16

def root
  @root
end

Instance Method Details

#accept(aVisitor) ⇒ Object

Part of the 'visitee' role in the Visitor design pattern. A visitee is expected to accept the visit from a visitor object

Parameters:



50
51
52
53
54
55
56
57
 
# File 'lib/rley/sppf/parse_forest.rb', line 50

def accept(aVisitor)
  aVisitor.start_visit_pforest(self)

  # Let's proceed with the visit of nodes
  root.accept(aVisitor) if root

  aVisitor.end_visit_pforest(self)
end

#ambiguous? ⇒ Boolean

Returns true if the parse encountered a structural ambiguity (i.e. more than one parse tree for the given input)

Returns:

  • (Boolean) 


43
44
45
 
# File 'lib/rley/sppf/parse_forest.rb', line 43

def ambiguous?()
  return @is_ambiguous
end

#done! ⇒ Object

Notification that the SPPF construction is over



33
34
 
# File 'lib/rley/sppf/parse_forest.rb', line 33

def done!()
end

#include?(aNode) ⇒ Boolean

Returns true if the given node is present in the forest.

Returns:

  • (Boolean) 


37
38
39
 
# File 'lib/rley/sppf/parse_forest.rb', line 37

def include?(aNode)
  return key2node.include?(aNode)
end