Class: Mapper::Validator

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

Overview

Utilities for Mapper::Grammar validation.

Class Method Summary (collapse)

Class Method Details

+ (Object) analyze_all(grammar)

Perform all analyses needed 



12
13
14
15
16
17
18
 
# File '../lib/validator.rb', line 12

def Validator.analyze_all grammar 
  Validator.analyze_recursivity grammar 
  Validator.analyze_sn_altering grammar 
  Validator.analyze_arity  grammar 
  Validator.analyze_min_depth grammar 
  grammar
end

+ (Object) analyze_arity(grammar)

Fill the :arity attribute of each RuleAlt in the grammar. It is used later by the Mapping::Base process for the Mapper#complexity calculation. Note the grammar argument is altered (no grammar.clone is done). 



145
146
147
148
149
150
151
152
153
 
# File '../lib/validator.rb', line 145

def Validator.analyze_arity grammar
  grammar.each_value do |rule|
    rule.each do |alt|
      alt.arity = ( alt.find_all { |token| token.type == :symbol } ).size
    end
  end

  grammar
end

+ (Object) analyze_min_depth(grammar)

Fill the :min_depth attribute for each Rule and RuleAlt in the grammar. It is used later by the Mapping::Base process for selecting RuleAlts with the proper minimal depth. Note the grammar argument is altered (no grammar.clone is done). 



159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
 
# File '../lib/validator.rb', line 159

def Validator.analyze_min_depth grammar
  raise 'Validator: cannot analyze_min_depth of undefined symbols' unless Validator.check_undefined( grammar ).empty?    
  
  grammar.each_value do |rule|
    rule.min_depth = nil
    rule.each { |alt| alt.min_depth = nil }
  end

  changed = true
  while changed
    changed = false

    grammar.each_value do |rule|

      symbol_depth = nil         
      rule.each do |alt| 
        next unless alt.min_depth.nil?
        
        alt_depth = nil
        alt.each do |token|
          depth = (token.type == :symbol) ? grammar[token.data].min_depth : 1
          if depth.nil?
            alt_depth = nil
            break
          end
          alt_depth = depth if alt_depth.nil? or alt_depth < depth
        end # token

        next if alt_depth.nil?
        changed = true if alt.min_depth != alt_depth
        alt.min_depth = alt_depth
        symbol_depth = alt_depth if symbol_depth.nil? or symbol_depth > alt_depth

      end # alt

      next if symbol_depth.nil?         
      next unless rule.min_depth.nil? # do not recompute rule.min_depth
      rule.min_depth = symbol_depth + 1
      changed = true 

    end # rule
  end # changed

  grammar     
end

+ (Object) analyze_recursivity(gram)

Compute Rule#recursivity and RuleAlt#recursivity attributes for the Mapper::Grammar syntax tree.

The symbol S may have one of three possible recursivity values: 


  grammar[S].recursivity == :terminating ... all possible expansions of S lead to terminal symbols (literals) ( S -> "T1" | "T2" )
  grammar[S].recursivity == :infinite  ... all possible expansions of S lead to infinite syntax loops ( S -> R, R -> S )
  grammar[S].recursivity == :cyclic ... expansions of S sometimes terminates, but some of them are recursive ( S -> R, R -> S | "T" )

This method is utilised in the sensitive initialisation (Mapper::Generator) and for general classification of Grammars: 


  grammar.start_symbol.recursivity == :terminating ... trivial grammars, producing only phenotypes of intrinsically limited sizes 
  grammar.start_symbol.recursivity == :infinite ... a grammar unusable for mapping 
                                                   (Mapper::Base#phenotype would not terminate in a finite time).
  grammar.start_symbol.recursivity == :cyclic ... a typical grammar producing nontrivial phenotypes 
                                                 (intrinsically unlimited in size)

Note: The termination of mapping with :cyclic grammars is guaranteed by external means (Mapper::Base#wraps_to_fail, Mapper::Base#wraps_to_fading) 



77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
# File '../lib/validator.rb', line 77

def Validator.analyze_recursivity gram                      
  raise 'Validator: cannot analyze_recursivity of undefined symbols' unless Validator.check_undefined( gram ).empty?     

  gram.each_value do |rule|
    rule.recursivity = :infinite
    rule.each { |alt| alt.recursivity = :infinite }
  end

  changed = true
  while changed
    changed = false
    gram.each_value do |rule|

      rule.each do |alt| 

        references = alt.find_all { |token| token.type == :symbol } 
        res = recursivity_over( references.map {|token| gram[token.data] } )
        now = if res.include? :infinite
                :infinite
              elsif res.include? :cyclic
                :cyclic
              else
                :terminating
              end

        changed = true if alt.recursivity != now  
        alt.recursivity = now

      end

      res = recursivity_over rule
      now = (res.size == 1) ? res.first : :cyclic 

      changed = true if rule.recursivity != now  
      rule.recursivity = now

    end
  end

  gram
end

+ (Object) analyze_sn_altering(grammar)

For all grammar’s symbols fill :sn_altering attributes. These attributes (see Grammar#sn_altering) are used by MutationStructural and MutationNodal classes (see). Note the grammar argument is altered (no grammar.clone is done). 



123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# File '../lib/validator.rb', line 123

def Validator.analyze_sn_altering grammar  
  
  grammar.each_value do |rule|

    rule.sn_altering = :nodal
    subsyms = nil
    rule.each do |alts|
      sub = alts.find_all {|token| token.type == :symbol }
      subsyms = sub if subsyms.nil?
      next if subsyms == sub
      rule.sn_altering = :structural
      break
    end
  end

  grammar
end

+ (Object) check_undefined(grammar)

Check the right hand sides of all rules for the presence of undefined symbols. (The symbol is defined if there is exactly one rule where the symbol is used on the left hand side.) Returns the array of all undefined symbols. 



46
47
48
49
50
51
52
53
54
55
56
57
58
59
 
# File '../lib/validator.rb', line 46

def Validator.check_undefined grammar
  undefs = []
  defs = grammar.symbols
  grammar.each_value do |rule|
    rule.each do |alt|
      alt.each do |token| 
        next unless token.type == :symbol
        next if defs.include? token.data 
        undefs.push token.data 
      end
    end
  end
  undefs
end

+ (Object) check_unused(grammar)

Check the left hand sides of all rules for the presence of unused symbols. (The symbol is used (referenced) if there is at least one rule using it on it’s right hand side.) Returns the array of all unused symbols. Note it is often expected that grammar.start_symbol is returned. 



26
27
28
29
30
31
32
33
34
35
36
37
38
39
 
# File '../lib/validator.rb', line 26

def Validator.check_unused grammar
  defs = grammar.symbols
  #defs.delete grammar.start_symbol
  grammar.each_value do |rule|
    rule.each do |alt|
      alt.each do |token| 
        next unless token.type == :symbol
        next unless defs.include? token.data 
        defs.delete token.data 
      end
    end
  end
  defs
end