Class: Resyma::Core::Engine

Inherits:
Object
  • Object
show all
Defined in:
lib/resyma/core/algorithm/engine.rb

Overview

The engine of the matching algorithm

Constant Summary collapse

CACHE_INDEX_TO_NODE = 
"ALGO_IDX_NODE_MAP".freeze

Instance Method Summary collapse

Constructor Details

#initialize(automata) ⇒ Engine

Create an instance of the algorithmic engine

Parameters:

Raises:

  • (TypeError) 


17
18
19
20
21
22
 
# File 'lib/resyma/core/algorithm/engine.rb', line 17

def initialize(automata)
  automata = [automata] if automata.is_a?(Automaton)
  raise TypeError, "Need a list of automata" unless automata.is_a?(Array)

  @automata = automata
end

Instance Method Details

#accepted_tuples(parsetree) ⇒ Set<Resyma::Core::Tuple4>

Compute accepted 4-tuples in the processed tree

Parameters:

Returns:



141
142
143
144
145
146
147
148
149
 
# File 'lib/resyma/core/algorithm/engine.rb', line 141

def accepted_tuples(parsetree)
  Utils.big_union(RMP(parsetree).map do |node|
    Utils.big_union(node.field.trans.values.map do |set_of_tuple4|
      set_of_tuple4.select do |tuple4|
        @automata[tuple4.belongs_to].accept?(tuple4.q_)
      end.to_set
    end)
  end)
end

#assign_start!(node) ⇒ nil

Step 2 of the algorithm

Parameters:

Returns:

  • (nil) —

    Nothing



61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/resyma/core/algorithm/engine.rb', line 61

def assign_start!(node)
  @automata.each_with_index do |automaton, idx|
    node.field.start[idx] =
      case node_type(node)
      when :a
        Set[Tuple2.new(-1, automaton.start, belongs_to: idx)]
      when :b
        node.parent.field.start[idx]
      when :c
        # @type [Resyma::Core::ParseTree]
        brother = node.parent.children[node.index - 1]
        Utils.big_union(RMP(brother).map do |node_|
          node_.field.trans[idx].map do |tuple4|
            Tuple2.new(tuple4.p_, tuple4.q_, belongs_to: idx)
          end
        end)
      end
  end
end

#assign_trans!(node) ⇒ nil

Step 3 of the algorithm

Parameters:

Returns:

  • (nil) —

    Nothing



88
89
90
91
92
93
94
95
96
 
# File 'lib/resyma/core/algorithm/engine.rb', line 88

def assign_trans!(node)
  @automata.each_with_index do |automaton, idx|
    node.field.trans[idx] = node.field.start[idx].map do |tuple2|
      next_q = automaton.destination(tuple2.q, node)
      next_q and Tuple4.new(tuple2.p, tuple2.q, node.field.id, next_q,
                            belongs_to: idx)
    end.compact.to_set
  end
end

#backtrack(parsetree, terminal_tuples = accepted_tuples(parsetree)) ⇒ Array<Array<Resyma::Core::Tuple4>] Derivational node sequences

Backtrack the derivational node sequence(s) of a parse tree processed by

the algorithm

Parameters:

  • parsetree (Resyma::Core::ParseTree) —

    A parse tree processed by ‘#traverse!`

  • terminal_tuples (Set<Resyma::Core::Tuple4>) (defaults to: accepted_tuples(parsetree)) —

    Accepted sets derived from ‘#accepted_tuples`

Returns:

  • (Array<Array<Resyma::Core::Tuple4>] Derivational node sequences) —

    Array<Array<Resyma::Core::Tuple4>] Derivational node sequences



184
185
186
 
# File 'lib/resyma/core/algorithm/engine.rb', line 184

def backtrack(parsetree, terminal_tuples = accepted_tuples(parsetree))
  terminal_tuples.map { |tuple4| backtrack_for(parsetree, tuple4) }
end

#backtrack_for(parsetree, tuple4) ⇒ Array<Resyma::Core::Tuple4>

Backtrack the derivational node sequence terminating at the 4-tuple

Parameters:

Returns:



160
161
162
163
164
165
166
167
168
169
170
171
 
# File 'lib/resyma/core/algorithm/engine.rb', line 160

def backtrack_for(parsetree, tuple4)
  if tuple4.p == -1
    [tuple4]
  else
    # @type [Resyma::Core::ParseTree]
    prev = parsetree.cache[Engine::CACHE_INDEX_TO_NODE][tuple4.p]
    prev_tuple4 = prev.field.trans[tuple4.belongs_to].find do |candidate|
      candidate.p_ == tuple4.p && candidate.q_ == tuple4.q
    end
    backtrack_for(parsetree, prev_tuple4) + [tuple4]
  end
end

#node_of(parsetree, id) ⇒ Resyma::Core::ParseTree?

Find the parse tree through its ID

Parameters:

  • parsetree (Resyma::Core::ParseTree) —

    A parse tree processed by ‘#traverse!`

  • id (Integer) —

    Depth-first ordered ID, based on 0

Returns:



110
111
112
 
# File 'lib/resyma/core/algorithm/engine.rb', line 110

def node_of(parsetree, id)
  parsetree.cache[Engine::CACHE_INDEX_TO_NODE][id]
end

#node_type(parsetree) ⇒ :a, ...

Determine the type of the node corresponding step 2 of the algorithm

Parameters:

Returns:

  • (:a, :b, :c) —

    Type of the node



31
32
33
34
35
36
37
 
# File 'lib/resyma/core/algorithm/engine.rb', line 31

def node_type(parsetree)
  if parsetree.root?          then :a
  elsif parsetree.index.zero? then :b
  else
    :c
  end
end

#RMP(parsetree) ⇒ Set<Resyma::Core::ParseTree>

Right-most path of the tree

Parameters:

Returns:



46
47
48
49
50
51
52
 
# File 'lib/resyma/core/algorithm/engine.rb', line 46

def RMP(parsetree)
  if parsetree.leaf?
    Set[parsetree]
  else
    Set[parsetree] | RMP(parsetree.children.last)
  end
end

#traverse!(parsetree) ⇒ nil

Traverse the parse tree once and modify fields for every nodes

Parameters:

Returns:

  • (nil) —

    Nothing



121
122
123
124
125
126
127
128
129
130
131
 
# File 'lib/resyma/core/algorithm/engine.rb', line 121

def traverse!(parsetree)
  id = 0
  parsetree.cache[Engine::CACHE_INDEX_TO_NODE] = {}
  parsetree.depth_first_each do |tree|
    tree.field.id = id
    assign_start! tree
    assign_trans! tree
    parsetree.cache[Engine::CACHE_INDEX_TO_NODE][id] = tree
    id += 1
  end
end