写在编译原理考试前
明天还要考最后一门编译原理,正好有一个周末可以准备。今天看了两遍「龙书」,昨天打了一天的《茶杯头》,这个周末恐怕是和龙过不去了:
Chomsky 文法分类体系
https://en.wikipedia.org/wiki/Chomsky_hierarchy
短语、直接短语和句柄
-
从抽象语法树的角度来看:
-
短语(Phrase)是某个子树的叶子节点序列。
-
直接短语(Simple Phrase)是不包含其它子树的子树的叶子节点序列。
-
句柄(Handle, i.e. Left-Most Simple Phrase)是最左直接短语。
-
-
句柄 直接短语 短语。
FIRST
-
串首终结符:串首第一个符号,并且是终结符。
-
给定一个文法符号串 , 的串首终结符集 被定义为可以从 推导出的所有串首终结符构成的集合。如果 ,那么 也在 中。
-
的串首终结符集为空集,即 。
-
如果 ,那么 。
-
如果 ,那么 。
-
FOLLOW
- 非终结符 的后续符号集 :可能在某个句型中紧跟在 后边的终结符 的集合。如果 是某个句型的最右符号,则将结束符「$」添加到 中。
SELECT
-
产生式 的可选集是指可以选用该产生式进行推导时对应的输入符号的集合,记为 。
-
条件 满足。
-
条件 满足。
-
-
在 文法中,产生式 的可选集:
- 如果 ,那么 。
- 如果 ,那么 。
LL(1) 文法
一个文法 是 的,当且仅当 的任意两个不同的产生式 满足下面的条件:
- 如果 和 均不能推导出 ,则 ,这样可以保证 。
- 和 至多有一个能推导出 ,否则 ,导致 和 相交。
- 如果 (此时 ),则 ;如果 (此时 ),则 。
预测分析法
递归的预测分析法:在递归下降分析中,编写每一个非终结符对应的过程,根据预测分析表进行产生式的选择。
非递归的预测分析法:不需要为每个非终结符编写递归下降过程,而是根据预测分析表构造一个自动机,也叫表驱动的预测分析。
预测分析法实现步骤
-
构造文法。
-
改造文法:消除二义性、消除左递归、消除回溯。
-
求每个变量的 集和 集,从而求得每个候选式的 集。
-
检查是不是 文法,若是,则构造预测分析表。
-
对于递归的预测分析,根据预测分析表为每一个非终结符编写一个过程;对于非递归的预测分析,实现表驱动的预测分析算法。
LR(0) 项目
-
例子:
- 为移进项目。
- 为待约项目。
- 为待约项目。
- 为归约项目。
-
待约项目可能具有等价项目,等价项目可形成项集的闭包。
LR(0) 分析表构造算法
-
构造 的规范 项集族 。
-
令 对应状态 。状态 的语法分析动作按照下面的方法决定:
- 如果 且 ,则 。
- 如果 且 ,则 。
- 如果 且 ,则对于所有 ,有 ( 是产生式 的编号)。
- 如果 ,则 。
-
没有定义的所有条目都设置为 。
SLR(1) 分析表构造算法
-
构造 的规范 项集族 。
-
令 对应状态 。状态 的语法分析动作按照下面的方法决定:
- 如果 且 ,则 。
- 如果 且 ,则 。
- ☑️ 如果 且 ,则对于所有 ,有 ( 是产生式 的编号)。
- 如果 ,则 。
-
没有定义的所有条目都设置为 。
LR(1) 分析表构造算法
-
构造 的规范 项集族 。
-
令 对应状态 。状态 的语法分析动作按照下面的方法决定:
- 如果 且 ,则 。
- 如果 且 ,则 。
- ☑️ 如果 且 ,则有 ( 是产生式 的编号)。
- 如果 [,则 。
-
没有定义的所有条目都设置为 。
LALR(1) 的特点
-
在形式上与 相同。
-
在大小上与 和 相当。
-
的分析能力介于 和 之间,也就是 < < 。
-
在 中,合并后的展望集仍为 集的子集。