HNU 软件编译原理实验 2(Go 实现)

做这次实验有点难受,我不知道该怪罪 Go 的类型系统还是杨某人的面向对象结构。

代码已上传至 GitHub,为防止篇幅过长,没有内置所有代码,仅对个人认为值得讲述的地方进行说明,可以对比阅读。

cyp0633/compiler-lab

数据结构

产生式

Production 结构体与其说是产生式,不如说是产生式的右部,而直到 LR(0) 项目中才记录了左部信息。

有两个特殊的文法符,$\epsilon$ 和 $#$,为了让它们在每一处都有相同的地址以方便比较,直接将定义写死在了代码里。

go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// epsilon 不属于非终结符,也不属于终结符!!!
// 看起来要用好多次,就先定义好了
var epsilonSymbol = GrammarSymbol{
    Name: "epsilon",
    Type: Null,
}

var endSymbol = TerminalSymbol{
    GrammarSymbol: GrammarSymbol{
        Name: "#",
        Type: Terminal,
    },
}

由于 Go 没有继承没有多态,只有嵌入以让一个结构体拥有另一个结构体的完整成员,那也无法使用一个 GrammarSymbol 指针指向终结符或非终结符。因此,在希望存储更多类型时,只能用一个 interface{} 解决。果然是著名的万物皆是 interface。比如:

go
1
2
3
4
5
6
7
8
type NonTerminalSymbol struct {
    GrammarSymbol
    ProductionTable      []*Production               // 非终结符的产生式表
    NumOfProduction      int                         // 产生式数量
    FirstSet             map[interface{}]bool        // 该非终结符的 First 函数值
    FollowSet            map[interface{}]bool        // 该非终结符的 Follow 函数值
    DependentSetInFollow map[*NonTerminalSymbol]bool // 该非终结符的 Follow 函数中依赖的非终结符
}

而这里就带来了一个问题:interface{} 完全没有类型检查,可以放指针,也可以放结构体本身。这就要求类型检查覆盖到不正常的情况,算了,大道至简嘛——

go 的教徒还住着毛坯房,毕竟大道至简

V2EX 网友

不过可以规定,此处的 interface{} 里存的全都是指针,并且代码实现保证同一个语法符仅存一份(即不会存在对象相同但指针不同)。

follow 依赖的非终结符完全没用过,倒不是说没用,而是觉得没必要。后面直接算的是所有非终结符的 follow

LL(1)

LL(1) 分析表并没有使用预定义的 cell,毕竟通过遍历一个 slice 查表的操作未免太不优雅了。

go
1
2
3
4
var LL1AnalysisTable = map[struct {
    *NonTerminalSymbol
    string
}]*Production{}

这里嵌入了一个匿名结构体,key 的两个 scope 分别为非终结符和向前看的下一个语法符,value 为对应的产生式。

LR(0)

和上面同理,既然项目集的本质是一个集合,就没必要使用数组这么傻的东西。

go
1
2
3
4
5
6
type ItemSet struct {
    // 状态序号
    ID int
    // LR(0) 项目表(其实是个集合)
    ItemTable map[LR0Item]struct{}
}

同时也直接砍掉了那几个 cell,对 LR(0) 分析表可以直接使用 map 映射。如下是 $\text{ACTION}$ 表的定义,用了两个匿名结构体。$\text{GOTO}$ 表定义同理。

go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
// LR Action 表
// 由状态 ID 和终结符名称,到动作类型和编号的映射
var ActionTable map[struct {
    // 当前栈顶状态序号
    StateID int
    // 待读入的终结符名称
    TerminalSymbolName string
}]struct {
    // 动作类型
    Type ActionCategory
    // 动作编号,如归约的产生式编号和移进的下个状态
    ActionID int
}

同样能使用 map 优化的还有自动机的边表。一般的查询都是根据起始状态和驱动符查找到达状态的,使用 map 会快很多。

go
1
2
3
4
5
6
7
8
// LR(0) 自动机
var DFA struct {
    // 开始项集
    StartItemSet *ItemSet
    // map 优化的变迁边表
    // 通常查询更快,极端情况下也不会更慢
    EdgeSet map[TransitionKey]*ItemSet
}

方法

产生式

定义了终结符、非终结符和产生式的 First 函数。对于终结符,可以直接返回包含自己的集合。而对于非终结符,

不要忘了如果 First 已经计算完成,就不要再算一次了,毕竟值都存储到了对应的数据结构中。

而在 Follow 函数中,关于是否有新的加入,个人使用的是比较插入前后 map 长度变化,不过先检查 key 是否存在似乎更快点。

在这里引入了一个库:github.com/google/go-cmp/cmp,它能够提供比 reflect.DeepEqual 更好的比较。如果是两个指针,前者会比较指向的内容,而后者只比较地址。如计算产生式的 First 函数时:

go
1
2
3
4
    // 只有 epsilon,就直接返回
    if p.BodySize == 1 && cmp.Equal(p.BodySymbol[0], &epsilonSymbol) {
        return map[interface{}]bool{&epsilonSymbol: true}
    }

由于每次添加 $\epsilon$ 时都是引用了同一个实例,所以这么比较没什么问题。只是听说 Go 的反射挺慢的,这个怕不是会更慢……

说到反射那当然还是要用的,因为又回到了没有多态的问题。不像其他语言,基类指针可以访问基类的内容,Go 仅凭一个 interface{} 根本无法获取它的真正类型。于是,如 Follow 初始化时添加非终结符的操作:

go
1
2
3
4
5
6
7
8
    // 初始化 FOLLOW 集合
    for _, A := range GrammarSymbolTable {
        // 如果不是非终结符,跳过
        if reflect.TypeOf(A) != reflect.TypeOf(RootSymbol) {
            continue
        }
        A.(*NonTerminalSymbol).FollowSet = make(map[interface{}]bool)
    }

使用反射就可以轻松判断真实类型了,当然也可以像是在非终结符 First 函数中,寻找 $\epsilon$ 产生式的代码这样:

go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
    // 寻找 epsilon 的产生式(仅含 epsilon)
    for _, p := range nt.ProductionTable {
        if p.BodySize == 1 {
            symbol, ok := p.BodySymbol[0].(*GrammarSymbol)
            if ok && symbol.Type == Null { // 为什么不能放到一个 if 里啊!!!
                // 如果存在将 epsilon 加入该非终结符的 First 函数值
                nt.FirstSet[&epsilonSymbol] = true
            }
        }
    }

(现在我们知道,当然是可以放在一个 if 里的,用反射就优雅多了)

在求产生式的非终结符时,需要求某产生式右部某一部分的 First 函数。此处选择构造一个产生式求 First,然后一切交给 GC,应该不会存在重复计算过多的问题。

go
1
2
3
4
5
6
7
                    // 先看成 A \Rightarrow \alpha B \beta,求 FIRST(\beta)
                    // 将 \beta 部分组合成一个产生式
                    tempProduction := Production{
                        BodySymbol: production.BodySymbol[index+1:],
                        BodySize:   len(production.BodySymbol[index+1:]),
                    }
                    betaFirst := tempProduction.First()

LL(1)

检测左递归使用的是 DFS 方法,每一层对某个特定非终结符的所有产生式进行搜索,在搜索路径上维护一个 map,记录非终结符的出现与否(毕竟只有非终结符才有左递归这回事),思想比较像递归子程序法。如果当前非终结符已经处于那个 map 中,就代表有左递归。这样能同时检测直接和间接的左递归。

go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 对所有非终结符检测左递归
func CheckLeftRecursion() (ret bool) {
    return checkLeftRecursion(make(map[string]bool), RootSymbol)
}

// 使用 DFS 检测左递归,rec 用于记录已经检测过的非终结符
func checkLeftRecursion(rec map[string]bool, curr *NonTerminalSymbol) bool {
    // 如果已经检测过,返回
    if rec[curr.Name] {
        return true
    }
    // 否则加入 map
    rec[curr.Name] = true

    for _, production := range curr.ProductionTable {
        // 长度为 0,返回
        if len(production.BodySymbol) == 0 {
            continue
        }
        // 是非终结符
        if symbol, ok := production.BodySymbol[0].(*NonTerminalSymbol); ok {
            if checkLeftRecursion(rec, symbol) {
                return true
            }
        }
    }
    return false
}

消除左递归其实就是套课本上的算法了,没有什么好说的。

检测左因子就是对某个非终结符的所有产生式首语法符进行查重,重点在 “有没有”,而提取左因子面临着一个取舍,在同一次提取中,无法既对尽量多的产生式进行提取,又提取出尽量长的公因子。在这篇博客 中介绍了一种通过树实现的算法,不需要考虑取舍也不需要进行多次提取。

多好的算法啊,可惜有点复杂,我还是老老实实多次提取吧(然而还是 100 多行)。基本思想:

  1. 循环提取,直到检测不到左因子

  2. 先检测开头的因子是否有重复,确定首公因子之后再尝试延长公因子。如对于 1123、114 和 514,先确定提取开头的 1,然后延长到 11

  3. 倾向于提取更多产生式的左因子(而不是提取更长的左因子),包括每次选择包含产生式最多的公因子进行提取(如 123、145、245、255、244 中提取 2,因为有 2 的多于有 1 的),以及延长时遇到无法延长的产生式时直接放弃(如 1123、1134、11156、11145 只会延长到 11,而不会放弃前两个来提取 111)

另外还要注意新产生式为空时 epsilon 的问题。新非终结符的产生式和被移除的产生式序号一一对应,也可以重复利用。实在看不懂就看 代码 吧……

LL(1) 分析表的构造也是课本上就有的算法了,实现起来难度也不高。

LR(0)

LR(0) 写起来真的让我血压高,穷举变迁时已经得到了从哪个状态来、借由某个驱动符、到哪个状态去的信息,但却要再写一个求解 DFA,再求一次变迁…… 真的不优雅,想了好久如何把它变得快一点,然后失败了。

求解变迁时常用的是直接调 Goto 函数,而这里由于是对某个项目集所有的项目求对应的变迁,所以不需要两层循环,直接一层循环即可。这里提前新建一个 map newItemSets,对每个驱动符映射到其 GOTO 状态对应的项目集,对每个非归约项目直接把点后移之后加入新项目集就行了,遍历完成后,核心项就都有了。

go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    // 遍历项目集中的每个项目
    // 此处并不需要驱动符一层项目再一层,省点时间
    for item := range itemSet.ItemTable {
        // 如果已经是归约 / 接受项目(A \to \cdot \alpha),则不需要变迁
        if item.DotPosition == len(item.Production.BodySymbol) {
            continue
        }
        // 取出该驱动符对应的项目集
        itemSet := newItemSets[item.Production.BodySymbol[item.DotPosition]].ItemTable
        // 将项目 item 的点后移一位
        // 新的项目!
        item1 := LR0Item{
            NonTerminalSymbol: item.NonTerminalSymbol,
            Production:        item.Production,
            DotPosition:       item.DotPosition + 1,
            Type:              CoreItem, // 一定是核心项啦
        }
        // 将新项目加入项目集
        itemSet[item1] = struct{}{}
    }

至于求解 DFA 嘛,其实也就大差不差了,我甚至复制了一大段代码。

在 SLR(1) 的检查之中,可以使用一个 map(set)存放归约项集的各个左部(即 $A \to \alpha \cdot$ 的 $A$),一个 map 存放移进项集对应的驱动终结符集(即 $A \to \alpha \cdot a \beta$ 的 $a$),更方便计算交集。

接下来是构造 LR 分析表,我也不知道杨某人这句话是什么意思,那就先填个 LR(0) 吧。

四个 if-else 让人血压挺高的,你问我为什么不用 switch?因为 case 里面不能声明局部变量,所以 case symbol, ok := item.Production.BodySymbol[item.DotPosition].(*TerminalSymbol); ok 这样的判断就写不出来,着实不太方便。

go
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
        for item := range itemSet.ItemTable {
            // 判断项目类型
            // 为什么不用一个 switch?因为特么的 go 不支持 switch 里做声明
            if item.NonTerminalSymbol == RootSymbol && item.DotPosition == len(item.Production.BodySymbol) {
                // 接受项目 S' \to S \cdot
                // ACTION[i,#] = accept
                // code...
            } else if item.DotPosition == len(item.Production.BodySymbol) {
                // 归约项目 A \to \alpha \cdot
                // 对所有非终结符 a 或 #,ACTION[i,a] = reduce j
                // code...
            } else if symbol, ok := item.Production.BodySymbol[item.DotPosition].(*TerminalSymbol); ok {
                // 移进项目 A \to \alpha \cdot a \beta
                // action[i,a] = shift j
                // code...
            } else if symbol, ok := item.Production.BodySymbol[item.DotPosition].(*NonTerminalSymbol); ok {
                // 待约项目 A \to \alpha \cdot B
                // goto[i,B] = j
                // code...
            }
        }

CC BY-SA

This content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International license.