编译原理计算方法技巧

Author Avatar
zccz14 4月 30, 2017
  • 在其它设备中阅读本文章

编译原理,学了一半以后,深深感受到了它其实是个数学课呀。

而且那繁琐而机械的计算方法(算法)让我一不小心就会算错,我觉得很困扰。

于是花了很多时间研究老师没有讲的一些方法。

目前先简单地列出一个目录吧。

Tricks Contents

非确定性状态机的化简

NFA Simplification

  • 通过消除 NFA 中的 epsilon (空串)边,从而使得在之后的NFA确定化NFA模拟过程中不需要求 eps 闭包,可以大幅减少重复的计算量,并提高计算准确度。
  • 通过消除 NFA 中的不可达状态并且对不可能接受的状态进行剪枝来减少 NFA 的状态数也可以有效控制计算量。

强烈推荐在 NFA 确定化之前进行 NFA 的化简,这样求出的 DFA 也是相对较简的(但不能保证已经是最简,存在可以进一步化简的例子)。当然这个过程是可选的,不影响正确性。

具体描述:

TBD

例子:

TBD

基于转移表的 DFA 化简

DFA Simplification based on transition table

对于状态转移表(一步转移表),如果有两行(两个DFA的状态)的内容(对应的转移规则)是完全相同的,那么这两行是很有可能可以合并的。

再进一步检查一下,它们是否同为终结态或非终结态,如果是,确定可以合并状态以化简 DFA。

重复检查这个规则可以找到所有的 DFA 化简位置,它的完备性可以用拓扑排序来简单证明。

这个方法比按照 DFA 图“玄学”检查比对更加有效率并且准确。

具体描述:

TBD

例子:

TBD

集合计算

Set Calculation

e.g. FIRST, FOLLOW, FIRSTVT, LASTVT, etc…

集合的定义通常都基于集合间的包含关系定义。所以你经常可以看到诸如“对于A中的任意元素 a,a属于B”这样的表述,按照集合论的观点就是“A 含于 B” 或 “B 包含 A”,这就是集合间的包含关系

这种集合计算的计算量还是不小的,但真正的问题是准确性,一旦关系变得复杂,很容易算错。

解决方案的核心思想是先维护集合间的关系,最后再规约出集合中具体的元素

这与数据模型设计的不一致性是类似的,所以解决方法也是类似的,那就是遵循范式,减少冗余,使得一致性容易维护。

这个技巧的适用范围很广,一切涉及集合计算的计算都可以用。

具体描述:

TBD

例子:

TBD

基于优先关系表的优先函数计算

Priority Function Generation based on Priority Relation Table

组合等价类划分拓扑排序算法可以直接基于优先关系表计算出优先函数。

等价类划分的实现往往采用一种称为并查集的数据结构。

相比教材上的画图方法,这个方法显得更为简洁。

我首次在第三次作业中描述并使用了这个算法,描述与例子都参见 Homework #3 Releases (v3.x)