实际上，有了上面的准备后，计算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，看看有什么结果?
