From 9a26bd3f57fac024f0b6d6ad11882ced875a5007 Mon Sep 17 00:00:00 2001 From: akr Date: Thu, 16 Aug 2007 10:21:16 +0000 Subject: * test/ruby/sentence.rb: Sentence class implemented based on sentgen.rb * test/ruby/sentgen.rb: removed. * test/ruby/test_assignment.rb: use sentence.rb. * test/ruby/test_yield.rb: block parameter passing emulator implemented. git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@13064 b2dd03c8-39d4-4d8f-98ff-823fe69b080e --- test/ruby/sentence.rb | 338 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 338 insertions(+) create mode 100644 test/ruby/sentence.rb (limited to 'test/ruby/sentence.rb') diff --git a/test/ruby/sentence.rb b/test/ruby/sentence.rb new file mode 100644 index 0000000000..3697fbea10 --- /dev/null +++ b/test/ruby/sentence.rb @@ -0,0 +1,338 @@ +# sentence + +class Sentence + def initialize(ary) + @sent = ary + end + + def to_s + @sent.join('') + end + + def to_a + @sent + end + + def [](i) + Sentence.new(@sent[i]) + end + + def inspect + "#<#{self.class}: #{@sent.inspect}>" + end + + def subst(target, &b) + Sentence.new(subst_rec(@sent, target, &b)) + end + + def subst_rec(obj, target, &b) + if obj.respond_to? :to_ary + a = [] + obj.each {|e| a << subst_rec(e, target, &b) } + a + elsif target === obj + yield obj + else + obj + end + end + + def find_subtree(&b) + if r = find_subtree_rec(@sent, &b) + Sentence.new(r) + else + nil + end + end + + def find_subtree_rec(obj, &b) + if obj.respond_to? :to_ary + if b.call obj + return obj + else + obj.each {|e| + r = find_subtree_rec(e, &b) + return r if r + } + end + end + nil + end + + def expand(&b) + Sentence.new(expand_rec(@sent, &b)) + end + + def expand_rec(obj, r=[], &b) + #puts "#{obj.inspect}\t\t#{r.inspect}" + if obj.respond_to? :to_ary + if b.call obj + obj.each {|o| + expand_rec(o, r, &b) + } + else + a = [] + obj.each {|o| + expand_rec(o, a, &b) + } + r << a + end + else + r << obj + end + r + end + + def Sentence.each(syntax, sym, limit) + Gen.new(syntax).each_tree(sym, limit) {|tree| + yield Sentence.new(tree) + } + end + + class Gen + def Gen.each_tree(syntax, sym, limit, &b) + Gen.new(syntax).each_tree(sym, limit, &b) + end + + def Gen.each_string(syntax, sym, limit, &b) + Gen.new(syntax).each_string(sym, limit, &b) + end + + def initialize(syntax) + @syntax = syntax + end + + def self.expand_syntax(syntax) + syntax = remove_underivable_rules(syntax) + syntax = expand_justempty_rules(syntax) + syntax = remove_emptyable_rules(syntax) + syntax = expand_channel_rules(syntax) + + syntax = expand_noalt_rules(syntax) + syntax = reorder_rules(syntax) + end + + def self.remove_underivable_rules(syntax) + deribable_syms = {} + changed = true + while changed + changed = false + syntax.each {|sym, rules| + next if deribable_syms[sym] + rules.each {|rhs| + if rhs.all? {|e| String === e || deribable_syms[e] } + deribable_syms[sym] = true + changed = true + break + end + } + } + end + result = {} + syntax.each {|sym, rules| + next if !deribable_syms[sym] + rules2 = [] + rules.each {|rhs| + rules2 << rhs if rhs.all? {|e| String === e || deribable_syms[e] } + } + result[sym] = rules2.uniq + } + result + end + + def self.expand_justempty_rules(syntax) + justempty_syms = {} + changed = true + while changed + changed = false + syntax.each {|sym, rules| + next if justempty_syms[sym] + if rules.all? {|rhs| rhs.all? {|e| justempty_syms[e] } } + justempty_syms[sym] = true + changed = true + end + } + end + result = {} + syntax.each {|sym, rules| + result[sym] = rules.map {|rhs| rhs.reject {|e| justempty_syms[e] } }.uniq + } + result + end + + def self.expand_emptyable_syms(rhs, emptyable_syms) + if rhs.empty? + elsif rhs.length == 1 + if emptyable_syms[rhs[0]] + yield rhs + yield [] + else + yield rhs + end + else + butfirst = rhs[1..-1] + if emptyable_syms[rhs[0]] + expand_emptyable_syms(butfirst, emptyable_syms) {|rhs2| + yield [rhs[0]] + rhs2 + yield rhs2 + } + else + expand_emptyable_syms(butfirst, emptyable_syms) {|rhs2| + yield [rhs[0]] + rhs2 + } + end + end + end + + def self.remove_emptyable_rules(syntax) + emptyable_syms = {} + changed = true + while changed + changed = false + syntax.each {|sym, rules| + next if emptyable_syms[sym] + rules.each {|rhs| + if rhs.all? {|e| emptyable_syms[e] } + emptyable_syms[sym] = true + changed = true + break + end + } + } + end + result = {} + syntax.each {|sym, rules| + rules2 = [] + rules.each {|rhs| + expand_emptyable_syms(rhs, emptyable_syms) {|rhs2| + rules2 << rhs2 + } + } + result[sym] = rules2.uniq + } + result + end + + def self.expand_channel_rules(syntax) + channel_rules = {} + syntax.each {|sym, rules| + channel_rules[sym] = {sym=>true} + rules.each {|rhs| + if rhs.length == 1 && Symbol === rhs[0] + channel_rules[sym][rhs[0]] = true + end + } + } + changed = true + while changed + changed = false + channel_rules.each {|sym, set| + n1 = set.size + set.keys.each {|s| + set.update(channel_rules[s]) + } + n2 = set.size + changed = true if n1 < n2 + } + end + result = {} + syntax.each {|sym, rules| + rules2 = [] + channel_rules[sym].each_key {|s| + syntax[s].each {|rhs| + unless rhs.length == 1 && Symbol === rhs[0] + rules2 << rhs + end + } + } + result[sym] = rules2.uniq + } + result + end + + def self.expand_noalt_rules(syntax) + noalt_syms = {} + syntax.each {|sym, rules| + if rules.length == 1 + noalt_syms[sym] = true + end + } + result = {} + syntax.each {|sym, rules| + rules2 = [] + rules.each {|rhs| + rhs2 = [] + rhs.each {|e| + if noalt_syms[e] + rhs2.concat syntax[e][0] + else + rhs2 << e + end + } + rules2 << rhs2 + } + result[sym] = rules2.uniq + } + result + end + + def self.reorder_rules(syntax) + result = {} + syntax.each {|sym, rules| + result[sym] = rules.sort_by {|rhs| + [rhs.find_all {|e| Symbol === e }.length, rhs.length] + } + } + result + end + + def each_tree(sym, limit) + generate_from_sym(sym, limit) {|_, tree| + yield tree + } + nil + end + + def each_string(sym, limit) + generate_from_sym(sym, limit) {|_, tree| + yield [tree].join('') + } + nil + end + + def generate_from_sym(sym, limit, &b) + return if limit < 0 + if String === sym + yield limit, sym + else + rules = @syntax[sym] + raise "undefined rule: #{sym}" if !rules + rules.each {|rhs| + if rhs.length == 1 || rules.length == 1 + limit1 = limit + else + limit1 = limit-1 + end + generate_from_rhs(rhs, limit1, &b) + } + end + nil + end + + def generate_from_rhs(rhs, limit) + return if limit < 0 + if rhs.empty? + yield limit, [] + else + generate_from_sym(rhs[0], limit) {|limit1, child| + generate_from_rhs(rhs[1..-1], limit1) {|limit2, arr| + yield limit2, [child, *arr] + } + } + end + nil + end + end + +end + -- cgit v1.2.3