首页
社区
课程
招聘
[原创]【编译原理】FIRST集、FOLLOW集算法原理和实现
2018-12-19 14:21 8473

[原创]【编译原理】FIRST集、FOLLOW集算法原理和实现

2018-12-19 14:21
8473

书中一些话,不知是翻译的原因。还是我个人理解的原因感觉不是非常好理解。个人重新整理了一下。

不过相对于消除左递归和提取左公因,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
}


[培训]《安卓高级研修班(网课)》月薪三万计划

最后于 2018-12-20 09:36 被菜鸟级X编辑 ,原因:
收藏
点赞4
打赏
分享
最新回复 (5)
雪    币: 22975
活跃值: (3312)
能力值: (RANK:648 )
在线值:
发帖
回帖
粉丝
KevinsBobo 8 2018-12-19 18:57
2
0
图片有问题,麻烦楼主重新上传一下
雪    币: 2391
活跃值: (294)
能力值: ( LV7,RANK:100 )
在线值:
发帖
回帖
粉丝
菜鸟级X 2 2018-12-20 09:36
3
0
KevinsBobo 图片有问题,麻烦楼主重新上传一下
已重新上传
雪    币: 22975
活跃值: (3312)
能力值: (RANK:648 )
在线值:
发帖
回帖
粉丝
KevinsBobo 8 2018-12-20 10:17
4
0
感谢分享
雪    币: 16428
活跃值: (59359)
能力值: (RANK:125 )
在线值:
发帖
回帖
粉丝
Editor 2018-12-24 10:13
5
0
感谢分享!666
雪    币: 1535
活跃值: (695)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
开花的水管 2018-12-24 14:36
6
0
学习一下
游客
登录 | 注册 方可回帖
返回