How To Build a Yacc?(13)

实际上，有了上面的准备后，计算DFA的算法很清楚：

class DFA
  SHIFT = 1
  REDUCE = 2
  ERROR = 3
  ACCEPT = 4
 
  def initialize()
    @state_set = Array.new
    
    @current_state = 0    
    @max_state = 0
    @action_table = Hash.new
    
    @first_set = Hash.new
    @follow_set = Hash.new
    @first_set.extend(HashDup)
    @follow_set.extend(HashDup)
  end
 
  def token_type(token, parser)
    parser.vocabs.identify(token)   
  end
 
  def action(state, token)
    key = "#{state},#{token}"
    return @action_table[key]
  end
 
  ########################################################
  # 生成DFA
  # 首先计算first, follow集合, 产生第一个状态,然后依次产生每一个后继
  ########################################################
  def generate(parser)
    calc_first_set(parser)
    calc_follow_set(parser)
    #@state_set.push(generate_first_state(parser))
    #dump_first_follow
    @state_set[@current_state] = generate_first_state(parser)
    #p "fisrt state: #{@state_set[@current_state].to_s}"
    while @current_state <= @max_state
      successors(@current_state, parser)
      @current_state = @current_state + 1
    end    
    @action_table.store("0,nil", [ACCEPT, 0])
    @action_table.store("0,$", [ACCEPT, 0])
  end
 
  ########################################################
  # 求DFA的第一个状态
  # 我们把nil = #S的item闭包作为第一个状态，其中S是开始符号
  ########################################################
  def generate_first_state(parser)  
    itemset = Array.new
    parser.rules.each do |rule|
      #p "DFA::#{rule}"
      if token_type(rule.lt, parser) == Vocab::NULL
        #p "DFA::match nil rule #{rule}"
        itemset.push(Item.new(rule, 0))
      end
    end
    first_state = closure(itemset, parser)
  end  
 
  ########################################################
  # 求一个状态的闭包
  # 对于状态集合中的任意一个item: S = av#BC, 如果B是nonterminal
  # 那么把所有rule中rule.lt = B的rule加入到这个闭包中
  ########################################################
  def closure(itemset, parser)    
    oldset = nil
    begin      
      itemset.each do |item|    
        oldset = itemset.dup    
        nt = item.next_token
        if !item.is_end? && token_type(nt, parser) == Vocab::NONTERMINAL
          additem = Array.new
          parser.rules.each do |rule|
            if rule.lt == nt
              expand = Item.new(rule, 0)
              additem.push(expand) if (!itemset.include?(expand))
            end            
          end            
          itemset.concat(additem)
        end
      end
    end while !oldset.eql?(itemset) # end begin...end while
    return itemset
  end
 
  ########################################################
  # 由item: S = a#vBC前进到 S = av#BC
  ########################################################
  def advance(itemset)
    newitemset = Array.new
    itemset.each do |item|     
      newitemset.push(item.step)
    end    
    return newitemset
  end
 
  ########################################################
  # 求每一个状态的所有后继
  # 对于状态s中任意一个item:
  # 1. 如果存在item: S = a#vBC, 那么当下一个 token是v时，意味着
  # 将v进行shift操作，并将状态转移到下一个状态closure(S = av#BC);
  # 2. 如果存在item: S = avBC#, 那么当下一个token在follow(S)中
  # 意味着需要救星reduce操作，将stack里的avBC序列替换为S, 并移动到
  # 下一个状态 goto(stack.last, S)
  ########################################################
  def successors(state, parser)
    itemset = @state_set[state]    
    parser.vocabs.each_token do |token|
      key = "#{state},#{token}"
      # 找到所有 s = a.vc中v=token的item
      next_items = itemset.find_all { |item| item.next_token == token }
      if !next_items.empty?
        next_items_c = closure(advance(next_items), parser)       
        # 检查next_items_s是否已经在状态表中        
        next_state_no = @state_set.index(next_items_c)
        if !next_state_no
          next_state_no = @max_state + 1
          @max_state = next_state_no
          @state_set[next_state_no] = next_items_c
        end        
        
        @action_table.store(key, [SHIFT, next_state_no])
      end
      
      # 找到所有 s= av. 的rule, 并将@follow_set(rule.rt.last)
      end_items = itemset.find_all { |item| item.is_end? == true }
      if !end_items.empty?
        end_items.each do |item|
          if @follow_set[item.rule.lt].include?(token)
            @action_table.store(key, [REDUCE, end_items])
          end
        end
      end
      
      # 如果没有任何可用的项目
      #@action_table.store(key, [ERROR, nil]) until @action_table[key]       
    end
  end  
    
  ########################################################
  # 计算token的first集合
  # 对于terminal, first(terminal) = [terminal]
  # 对于nonterminal S, 如果有S = aBC, first(S) = first(aBC)
  # if a -> nil , first(aBC) = first(BC), 依次类推
  # if a not-> nil, first(aBC) = first(a).
  ########################################################
  def calc_first_set(parser)
    parser.vocabs.each_terminal do |terminal|
      @first_set.store(terminal, terminal)
    end
    
    begin   
      old_first_set = @first_set.dup
      parser.vocabs.each_nonterminal do |nonterminal|
        parser.rules.each do |rule|
          if rule.lt == nonterminal
            if !rule.rt.empty? && @first_set[rule.rt[0]]
              @first_set.store(nonterminal, @first_set[rule.rt[0]])
            end
          end
        end
      end   
    end while @first_set.eql?(old_first_set)
    return @first_set
  end
 
  ########################################################
  # 计算token的follow集合
  # 对每个rule(产生式进行遍历)
  # S = aBC, 每个rule右边的产生序列(rule.rt=aBC)的每一个非结尾符号
  # 比如a,B; follow集合对于紧邻符号的first集合;follow(a) = fisrt(B).
  # 而每一个结尾符号，其follow集合等于左边非终结符的follow集合
  # follow(C) = follow(S)
  ########################################################
  def calc_follow_set(parser)
    begin
      old_follow_set = @follow_set.dup
      parser.rules.each do |rule|
        if token_type(rule.lt, parser) == Vocab::NULL
          @follow_set.store(rule.lt, Vocab.eofs)
        end
        for i in 0...rule.rt.length
          if i < rule.rt.length-1
            @follow_set.store(rule.rt[i], @first_set[rule.rt[i+1]])
          else
            @follow_set.store(rule.rt[i], @follow_set[rule.lt])
          end
        end #end for
      end #end parser.rules.each
    end while !@follow_set.eql?(old_follow_set)
    return @follow_set
  end
 
  #### debug util function################
  def dump_state_set
    index = 0
    @state_set.each do |state|
      p "state:#{index}, item:#{state.to_s}"
      index = index + 1
    end
  end
 
  def dump_action_table
    p "[action table]:"
    @action_table.each_pair do |key, value|
      cond = key.gsub(/,(.*)/, '(/1)')      
      p "#{cond} -->  [#{DFA.action_name(value[0])}], #{value[1]}"
    end
  end
 
  def dump_first_follow
    p "first: #{@first_set.inspect}"
    p "follow: #{@follow_set.inspect}"
  end
 
  def DFA.action_name(action)
    DFA.constants.each do |x|
      return x if eval(x) == action      
    end
    return "unknown action"
  end
 
  #attr_reader :state_set, :action_table, :goto_table
end



而Yacc这时的实现也仅仅是转调一下DFA的方法而已:
class Yacc
  def initialize(file_name)
    @parser = RuleParser.new(file_name)
    @dfa = DFA.new
  end
 
  def rule_parser
    @parser
  end 
 
  def dfa
    @dfa
  end
 
  def generate
    @dfa.generate(@parser)
  end 
end


回头运行一下我们的test_yacc，看看有什么结果?