生成DFA的第1步，计算first集合和follow集合。
first_set和follow_set都是一个hast set结构，这个hash的key是一个 vocab,而value是一个集合，用一个array表示，这与普通的hash不同，因此写了一个HashDup的module,其中重写了hash的store方法，用来满足上述要求：
###### hashdup.rb ###########
module HashDup
def store(key, value)
return if !value
if self.has_key?(key)
self[key].push(value)
else
self[key] = [value]
end
self[key].flatten!
self[key].uniq!
end
def eql?(other)
self.each_pair do |key, value|
if !other[key].eql?(value)
return false
end
end
return true
end
end
其中eql?方法十分有用，在计算first和follow集合时，每遍循环都要检查集合是否有变化以决定集合是否计算终止。
class DFA
def initialize()
@first_set = Hash.new
@follow_set = Hash.new
@first_set.extend(HashDup)
@follow_set.extend(HashDup)
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
end
