写在编译原理考试前

明天还要考最后一门编译原理,正好有一个周末可以准备。今天看了两遍「龙书」,昨天打了一天的《茶杯头》,这个周末恐怕是和龙过不去了:

Chomsky 文法分类体系

https://en.wikipedia.org/wiki/Chomsky_hierarchy

短语、直接短语和句柄

  • 从抽象语法树的角度来看:

    • 短语(Phrase)是某个子树的叶子节点序列。

    • 直接短语(Simple Phrase)是不包含其它子树的子树的叶子节点序列。

    • 句柄(Handle, i.e. Left-Most Simple Phrase)是最左直接短语。

  • 句柄 直接短语 短语。

FIRST

  • 串首终结符:串首第一个符号,并且是终结符。

  • 给定一个文法符号串 串首终结符集 被定义为可以从 推导出的所有串首终结符构成的集合。如果 ,那么 也在 中。

    • 的串首终结符集为空集,即

    • 如果 ,那么

    • 如果 ,那么

FOLLOW

  • 非终结符 后续符号集 :可能在某个句型中紧跟在 后边的终结符 的集合。如果 是某个句型的最右符号,则将结束符「$」添加到 中。

SELECT

  • 产生式 可选集是指可以选用该产生式进行推导时对应的输入符号的集合,记为

    • 条件 满足。

    • 条件 满足。

  • 文法中,产生式 的可选集:

    • 如果 ,那么
    • 如果 ,那么

LL(1) 文法

一个文法 的,当且仅当 的任意两个不同的产生式 满足下面的条件:

  • 如果 均不能推导出 ,则 ,这样可以保证
  • 至多有一个能推导出 ,否则 ,导致 相交。
  • 如果 (此时 ),则 ;如果 (此时 ),则

预测分析法

递归的预测分析法:在递归下降分析中,编写每一个非终结符对应的过程,根据预测分析表进行产生式的选择。

非递归的预测分析法:不需要为每个非终结符编写递归下降过程,而是根据预测分析表构造一个自动机,也叫表驱动的预测分析。

预测分析法实现步骤

  1. 构造文法。

  2. 改造文法:消除二义性、消除左递归、消除回溯。

  3. 求每个变量的 集和 集,从而求得每个候选式的 集。

  4. 检查是不是 文法,若是,则构造预测分析表。

  5. 对于递归的预测分析,根据预测分析表为每一个非终结符编写一个过程;对于非递归的预测分析,实现表驱动的预测分析算法。

LR(0) 项目

  • 例子:

    • 移进项目
    • 待约项目
    • 待约项目
    • 归约项目
  • 待约项目可能具有等价项目,等价项目可形成项集的闭包。

LR(0) 分析表构造算法

  • 构造 的规范 项集族

  • 对应状态 。状态 的语法分析动作按照下面的方法决定:

    • 如果 ,则
    • 如果 ,则
    • 如果 ,则对于所有 ,有 是产生式 的编号)。
    • 如果 ,则
  • 没有定义的所有条目都设置为

SLR(1) 分析表构造算法

  • 构造 的规范 项集族

  • 对应状态 。状态 的语法分析动作按照下面的方法决定:

    • 如果 ,则
    • 如果 ,则
    • ☑️ 如果 ,则对于所有 ,有 是产生式 的编号)。
    • 如果 ,则
  • 没有定义的所有条目都设置为

LR(1) 分析表构造算法

  • 构造 的规范 项集族

  • 对应状态 。状态 的语法分析动作按照下面的方法决定:

    • 如果 ,则
    • 如果 ,则
    • ☑️ 如果 ,则有 是产生式 的编号)。
    • 如果 [,则
  • 没有定义的所有条目都设置为

LALR(1) 的特点

  • 在形式上与 相同。

  • 在大小上与 相当。

  • 的分析能力介于 之间,也就是 < <

  • 中,合并后的展望集仍为 集的子集。

Updated: