diff options
Diffstat (limited to 'lib/racc/statetransitiontable.rb')
-rw-r--r-- | lib/racc/statetransitiontable.rb | 311 |
1 files changed, 0 insertions, 311 deletions
diff --git a/lib/racc/statetransitiontable.rb b/lib/racc/statetransitiontable.rb deleted file mode 100644 index 4d54287258..0000000000 --- a/lib/racc/statetransitiontable.rb +++ /dev/null @@ -1,311 +0,0 @@ -#-- -# -# -# -# Copyright (c) 1999-2006 Minero Aoki -# -# This program is free software. -# You can distribute/modify this program under the same terms of ruby. -# see the file "COPYING". -# -#++ - -require 'racc/parser' - -module Racc - - StateTransitionTable = Struct.new(:action_table, - :action_check, - :action_default, - :action_pointer, - :goto_table, - :goto_check, - :goto_default, - :goto_pointer, - :token_table, - :reduce_table, - :reduce_n, - :shift_n, - :nt_base, - :token_to_s_table, - :use_result_var, - :debug_parser) - class StateTransitionTable # reopen - def StateTransitionTable.generate(states) - StateTransitionTableGenerator.new(states).generate - end - - def initialize(states) - super() - @states = states - @grammar = states.grammar - self.use_result_var = true - self.debug_parser = true - end - - attr_reader :states - attr_reader :grammar - - def parser_class - ParserClassGenerator.new(@states).generate - end - - def token_value_table - h = {} - token_table().each do |sym, i| - h[sym.value] = i - end - h - end - end - - - class StateTransitionTableGenerator - - def initialize(states) - @states = states - @grammar = states.grammar - end - - def generate - t = StateTransitionTable.new(@states) - gen_action_tables t, @states - gen_goto_tables t, @grammar - t.token_table = token_table(@grammar) - t.reduce_table = reduce_table(@grammar) - t.reduce_n = @states.reduce_n - t.shift_n = @states.shift_n - t.nt_base = @grammar.nonterminal_base - t.token_to_s_table = @grammar.symbols.map {|sym| sym.to_s } - t - end - - def reduce_table(grammar) - t = [0, 0, :racc_error] - grammar.each_with_index do |rule, idx| - next if idx == 0 - t.push rule.size - t.push rule.target.ident - t.push(if rule.action.empty? # and @params.omit_action_call? - then :_reduce_none - else "_reduce_#{idx}".intern - end) - end - t - end - - def token_table(grammar) - h = {} - grammar.symboltable.terminals.each do |t| - h[t] = t.ident - end - h - end - - def gen_action_tables(t, states) - t.action_table = yytable = [] - t.action_check = yycheck = [] - t.action_default = yydefact = [] - t.action_pointer = yypact = [] - e1 = [] - e2 = [] - states.each do |state| - yydefact.push act2actid(state.defact) - if state.action.empty? - yypact.push nil - next - end - vector = [] - state.action.each do |tok, act| - vector[tok.ident] = act2actid(act) - end - addent e1, vector, state.ident, yypact - end - set_table e1, e2, yytable, yycheck, yypact - end - - def gen_goto_tables(t, grammar) - t.goto_table = yytable2 = [] - t.goto_check = yycheck2 = [] - t.goto_pointer = yypgoto = [] - t.goto_default = yydefgoto = [] - e1 = [] - e2 = [] - grammar.each_nonterminal do |tok| - tmp = [] - - # decide default - freq = Array.new(@states.size, 0) - @states.each do |state| - st = state.goto_table[tok] - if st - st = st.ident - freq[st] += 1 - end - tmp[state.ident] = st - end - max = freq.max - if max > 1 - default = freq.index(max) - tmp.map! {|i| default == i ? nil : i } - else - default = nil - end - yydefgoto.push default - - # delete default value - tmp.pop until tmp.last or tmp.empty? - if tmp.compact.empty? - # only default - yypgoto.push nil - next - end - - addent e1, tmp, (tok.ident - grammar.nonterminal_base), yypgoto - end - set_table e1, e2, yytable2, yycheck2, yypgoto - end - - def addent(all, arr, chkval, ptr) - max = arr.size - min = nil - arr.each_with_index do |item, idx| - if item - min ||= idx - end - end - ptr.push(-7777) # mark - arr = arr[min...max] - all.push [arr, chkval, mkmapexp(arr), min, ptr.size - 1] - end - - n = 2 ** 16 - begin - Regexp.compile("a{#{n}}") - RE_DUP_MAX = n - rescue RegexpError - n /= 2 - retry - end - - def mkmapexp(arr) - i = ii = 0 - as = arr.size - map = String.new - maxdup = RE_DUP_MAX - curr = nil - while i < as - ii = i + 1 - if arr[i] - ii += 1 while ii < as and arr[ii] - curr = '-' - else - ii += 1 while ii < as and not arr[ii] - curr = '.' - end - - offset = ii - i - if offset == 1 - map << curr - else - while offset > maxdup - map << "#{curr}{#{maxdup}}" - offset -= maxdup - end - map << "#{curr}{#{offset}}" if offset > 1 - end - i = ii - end - Regexp.compile(map, 'n') - end - - def set_table(entries, dummy, tbl, chk, ptr) - upper = 0 - map = '-' * 10240 - - # sort long to short - entries.sort_by!.with_index {|a,i| [-a[0].size, i] } - - entries.each do |arr, chkval, expr, min, ptri| - if upper + arr.size > map.size - map << '-' * (arr.size + 1024) - end - idx = map.index(expr) - ptr[ptri] = idx - min - arr.each_with_index do |item, i| - if item - i += idx - tbl[i] = item - chk[i] = chkval - map[i] = ?o - end - end - upper = idx + arr.size - end - end - - def act2actid(act) - case act - when Shift then act.goto_id - when Reduce then -act.ruleid - when Accept then @states.shift_n - when Error then @states.reduce_n * -1 - else - raise "racc: fatal: wrong act type #{act.class} in action table" - end - end - - end - - - class ParserClassGenerator - - def initialize(states) - @states = states - @grammar = states.grammar - end - - def generate - table = @states.state_transition_table - c = Class.new(::Racc::Parser) - c.const_set :Racc_arg, [table.action_table, - table.action_check, - table.action_default, - table.action_pointer, - table.goto_table, - table.goto_check, - table.goto_default, - table.goto_pointer, - table.nt_base, - table.reduce_table, - table.token_value_table, - table.shift_n, - table.reduce_n, - false] - c.const_set :Racc_token_to_s_table, table.token_to_s_table - c.const_set :Racc_debug_parser, true - define_actions c - c - end - - private - - def define_actions(c) - c.module_eval "def _reduce_none(vals, vstack) vals[0] end" - @grammar.each do |rule| - if rule.action.empty? - c.alias_method("_reduce_#{rule.ident}", :_reduce_none) - else - c.define_method("_racc_action_#{rule.ident}", &rule.action.proc) - c.module_eval(<<-End, __FILE__, __LINE__ + 1) - def _reduce_#{rule.ident}(vals, vstack) - _racc_action_#{rule.ident}(*vals) - end - End - end - end - end - - end - -end # module Racc |