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.



28
29
30
31
32
 
# File 'lib/rley/sppf/parse_forest.rb', line 28

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.



24
25
26
 
# File 'lib/rley/sppf/parse_forest.rb', line 24

def is_ambiguous=(value)
  @is_ambiguous = value
end

#key2node ⇒ Object (readonly)

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



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

def key2node
  @key2node
end

#root ⇒ Object (readonly)

The root node of the forest



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

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:



65
66
67
68
69
70
71
72
 
# File 'lib/rley/sppf/parse_forest.rb', line 65

def accept(aVisitor)
  aVisitor.start_visit_pforest(self)

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

  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) 


46
47
48
 
# File 'lib/rley/sppf/parse_forest.rb', line 46

def ambiguous?
  @is_ambiguous
end

#done! ⇒ Object

Notification that the SPPF construction is over



35
36
37
 
# File 'lib/rley/sppf/parse_forest.rb', line 35

def done!
  # Do nothing
end

#include?(aNode) ⇒ Boolean

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

Returns:

  • (Boolean) 


40
41
42
 
# File 'lib/rley/sppf/parse_forest.rb', line 40

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

#to_ptree_enum ⇒ Enumerator

Create an Enumerator that helps to iterate over the possible parse trees. That enumerator will generate a parse tree when called with next method.

Returns:

  • (Enumerator) 


54
55
56
57
58
59
60
 
# File 'lib/rley/sppf/parse_forest.rb', line 54

def to_ptree_enum
  # How to implement?
  # One visits the forest => beware of dependency
  # At each visited item create a corresponding  tree node.
  # At end of visit & stack not empty
  # Re-generate another ptree
end