HNU 软件编译原理实验 2（Go 实现）

本文最后更新于 47 天前，其中的信息可能已经有所发展或是发生改变。

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

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

GitHub

cyp0633/compiler-lab

数据结构

产生式

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

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

// epsilon 不属于非终结符，也不属于终结符！！！
// 看起来要用好多次，就先定义好了
var epsilonSymbol = GrammarSymbol{
	Name: "epsilon",
	Type: Null,
}

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

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

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 查表的操作未免太不优雅了。

var LL1AnalysisTable = map[struct {
	*NonTerminalSymbol
	string
}]*Production{}

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

LR(0)

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

type ItemSet struct {
	// 状态序号
	ID int
	// LR(0) 项目表（其实是个集合）
	ItemTable map[LR0Item]struct{}
}

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

// LR Action 表
// 由状态 ID 和终结符名称，到动作类型和编号的映射
var ActionTable map[struct {
	// 当前栈顶状态序号
	StateID int
	// 待读入的终结符名称
	TerminalSymbolName string
}]struct {
	// 动作类型
	Type ActionCategory
	// 动作编号，如归约的产生式编号和移进的下个状态
	ActionID int
}

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

// 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函数时：

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

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

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

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

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

	// 寻找 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，应该不会存在重复计算过多的问题。

					// 先看成 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中，就代表有左递归。这样能同时检测直接和间接的左递归。

// 对所有非终结符检测左递归
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多行）。基本思想：

循环提取，直到检测不到左因子
先检测开头的因子是否有重复，确定首公因子之后再尝试延长公因子。如对于1123、114和514，先确定提取开头的1，然后延长到11
倾向于提取更多产生式的左因子（而不是提取更长的左因子），包括每次选择包含产生式最多的公因子进行提取（如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状态对应的项目集，对每个非归约项目直接把点后移之后加入新项目集就行了，遍历完成后，核心项就都有了。

	// 遍历项目集中的每个项目
	// 此处并不需要驱动符一层项目再一层，省点时间
	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这样的判断就写不出来，着实不太方便。

		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...
			}
		}

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

数据结构

产生式

LL(1)

LR(0)

方法

产生式

LL(1)

LR(0)

发送评论 编辑评论

推荐文章

发送评论编辑评论