【编译原理】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
", 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
", 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
}