[原创]【编译原理】FIRST集、FOLLOW集算法原理和实现
书中一些话，不知是翻译的原因。还是我个人理解的原因感觉不是非常好理解。个人重新整理了一下。
不过相对于消除左递归和提取左公因,FIRST集和FOLLOW集的算法相对来说比较简单。
书中的重点给出:
FIRST:
一个文法符号的FIRST集就是这个符号能推导出的第一个终结符号的集合, 包括空串。例: A -> abc | def | ε 那么FIRST(A) 等于 { a, d, ε }。
FOLLOW：
蓝线画的部分很重要。
特别是这句话：请注意，在这个推导的某个阶段，A和a之间可能存在一些文法符号。单如果这样，这些符号会推导得到 ε并消失。
这句话的意思就是好比说：
S->ABa
B->c | ε
这个文法 FOLLOW(A)的值应该是FIRST(B)所有的终结符的集合（不包含ε），但是FIRST(B)是包含ε的，说明B是可空的，既然B是可空的 S->ABa 也可以看成 S->Aa。那么a就可以跟在A的后面.所以在这种情况下，FOLLOW(A)的值是包含a的。
换句话说就是。一个文法符号A的FOLLOW集合就是它的下一个文法符号B的FIRST集合。如果下一个文法符号B的FIRST集合包含ε，那么我们就要获取下一个文法符号B的FOLLOW集添加到FOLLOW(A)中
代码中的注释已经很详细
GIT: https://github.com/hixiaosan/dragon_algorithm.git
// 提取First集合
func First(cfg []*Production, sym *Symbolic) map[string] *Symbolic {
result := make(map[string] *Symbolic)
// 规则一 如果符号是一个终结符号，那么他的FIRST集合就是它自身
if sym.SymType() == SYM_TYPE_TERMINAL || sym.SymType() == SYM_TYPE_NIL {
result[sym.Sym()] = sym
return result
}
// 规则二 如果一个符号是一个非终结符号
// (1) A -> XYZ 如果 X 可以推导出nil 那么就去查看Y是否可以推导出nil
// 如果 Y 推导不出nil，那么把Y的First集合加入到A的First集合
// 如果 Y 不能推导出nil，那么继续推导 Z 是否可以推导出nil,依次类推
// (2) A -> XYZ 如果XYZ 都可以推导出 nil, 那么说明A这个产生式有可能就是nil， 这个时候我们就把nil加入到FIRST(A)中
for _, production := range cfg {
if production.header == sym.Sym() {
nilCount := 0
for _, rightSymbolic := range production.body { // 对于一个产生式
ret := First(cfg, rightSymbolic) // 获取这个产生式体的First集合
hasNil := false
for k, v := range ret {
if v.SymType() == SYM_TYPE_NIL { // 如果推导出nil, 标识当前产生式体的符号可以推导出nil
hasNil = true
} else {
result[k] = v
}
}
if false == hasNil { // 当前符号不能推导出nil, 那么这个产生式的FIRST就计算结束了，开始计算下一个产生式
break
}
// 当前符号可以推导出nil，那么开始推导下一个符号
nilCount++
if nilCount == len(production.body) { // 如果产生式体都可以推导出nil，那么这个产生式就可以推导出nil
result["@"] = &Symbolic{sym: "@", sym_type: SYM_TYPE_NIL}
}
}
}
}
return result
}
// 提取FOLLOW集合
func Follow(cfg []*Production, sym string) [] *Symbolic {
fmt.Printf("Follow ------> %s\n", sym)
result := make([] *Symbolic, 0)
// 一个文法符号的FOLLOW集就是 可能出现在这个文法符号后面的终结符
// 比如 S->ABaD, 那么FOLLOW(B)的值就是a。
// FOLLOW(A)的值包含了FIRST(B)中除了ε以外的所有终结符,如果First(B)包含空的话。说明跟在B后面的终结符号就可以跟在A后面，这时我们要把FOLLOW(B)的值也添加到FOLLOW(A)中
// 因为D是文法符号S的最右符号，那么所有跟在S后面的符号必定跟在D后面。所以FOLLOW(S)所有的值都在FOLLOW(D)中
// 以下是书中的总结
// 不断应用下面这两个规则，直到没有新的FOLLOW集 被加入
// 规则一: FOLLOW(S)中加入$, S是文法开始符号
// 规则二: A->CBY FOLLOW(B) 就是FIRST(Y)
// 规则三: A->CB 或者 A->CBZ(Z可以推导出ε) 所有FOLLOW(A)的符号都在FOLLOW(B),
//
if sym == "S" { // 如果是文法的开始符号
result = append(result, &Symbolic{sym: "$", sym_type: SYM_TYPE_TERMINAL})
}
for _, pro := range cfg {
for idx, p_r_sym := range pro.body {
if p_r_sym.Sym() == sym { // 寻找到这个符号
if idx + 1 == len(pro.body) { // 是文法最右部的符号
if pro.header == p_r_sym.Sym() {
continue
}
ret := Follow(cfg, pro.header) // 获取产生式头的FOLLOW集合
result = append(result, ret...)
continue
}
firstSet := First(cfg, pro.body[idx + 1]) // 获取下一个First集合
hasNil := false
for _, first := range firstSet {
fmt.Printf("first -> %s\n", first.Sym())
if first.SymType() == SYM_TYPE_NIL {
hasNil = true
continue
}
result = append(result, first) // 添加Follow集合
}
if hasNil { // 如果下一个符号包含空串 那么要在获取下一个的符号的Follow集合
nextFollow := Follow(cfg, pro.body[idx + 1].Sym())
result = append(result, nextFollow...)
continue
}
}
}
}
unique := make(map[string]*Symbolic)
for _, sym := range result {
if _, ok := unique[sym.Sym()]; !ok {
unique[sym.Sym()] = sym
}
}
result = make([]*Symbolic, 0)
for _, sym := range unique {
result = append(result, sym)
}
return result
}
注意：上传附件及图片大小不得大于30M。
⚠️ 版权声明：
本博客所有内容（含教程、源码、工具）仅供个人技术学习与研究交流使用，严禁商用、倒卖、二次分发及非法用途。
未经作者书面授权，任何组织或个人不得转载、复制或用于其他平台，违者将追究相关责任。
参与讨论
登录后可查看全部回复并参与讨论。
