编译原理

编译阶段

编译的过程分为词法分析、语法分析、语义分析、中间代码生成、机器无关代码优化、目标代码生成、机器相关代码优化等几个步骤。词法分析、语法分析、语义分析、中间代码生成统一称为分析部分（前端），目标代码生成、机器相关代码优化被统一称为综合部分（后端）。 当语法分析、语义分析、中间代码生成三个部分合在一起时称为语法制导翻译。

词法分析

词法分析的主要任务是从左向右扫描源程序的字符，识别出各个单词，确定单词的类型，并将识别出的单词转换为统一的机内表示——词法单元（ token）形式。

自顶向下分析

从文法的开始符号开始进行分析的过程被称为自顶向下分析.

最左推导: 从文法开始符号的产生式中最左的符号开始替换的推导方式被称为最左推导。 最左推导对应的规约方式被称为最右规约。

最右推导: 从文法开始符号的产生式中最右的符号开始替换的推导方式被称为最右推导。 最右推导对应的规约方式被称为最左规约。

递归下降分析: 递归下降解析器由一组相互递归的程序（或等价的非递归程序）构建而成，其中每个程序都实现了文法中的一个非终结符。

左递归: 若 , , 则称该产生式是左递归的. 含有左递归产生式的文法被称为左递归文法. 左递归文法会使递归下降解析器陷入无限循环.

左递归的消除:

通过引入非终结符和空产生式将直接左递归转化为右递归;

如下算法消除间接左递归:

1. sort all non-terminal ;

2. :

   • :

     • rewrite into , where ;

   • eliminate directly left-recursion.

几类重要集合

First 集是指文法 中文法符号串 所能推导出的所有串的第一个终结符构成的集合, 记为 .

如果 , 则 .

对于串 , 计算 的算法为:

0. if , return ;

1. , ;

2. forall :

   • ;

   • ? , break;

3. ? ;

4. return .

Follow 集是指文法 中非终结符 能紧跟的终结符构成的集合, 记为 .

如果 是某个句型的最右符号, 则结束符号 .

计算非终结符 的算法为:

0. ;

1. forall :

   • if is like , ;

   • elif is like , ;

   • elif is like , ;

   • else continue;

2. return .

计算文法 的全部 Follow 集的算法为:

1. forall , supose is like :
   • ;
   • forall :
     • ;
2. repeate #1 until no changes.

可选集是指选用产生式 推导时对应的输入符号的集合，记为 .

从而对于产生式 , 有

LL(1) 文法

即从左(left)向右扫描的最左(left)推导文法, 且有一个(1) 前看符号.

称文法 是 LL(1) 文法, 当且仅当 的任意两个具有相同左部的产生式 满足：

1. 若 , 则 ;

2. 和 至多有一个推导出 ;

3. , 若 则 .

表驱动的预测分析法

使用 PDA 进行分析预测的方式即为表驱动的预测分析法，也称为非递归的预测分析法.

首先根据文法 的产生式构造分析表一个 的表 :

然后设置驱动程序为:

• 输入: 符号串 和文法 的分析表 ;

• 输出: 若 , 则输出 的最左推导，否则给出错误指示;

• 设 为驱动程序采用的 PDA, 则算法为:

  0. be current stack series, ;

  1. while :

     • if :

       • ;

       • ;

     • elif :

       • raise error;

     • elif :

       • raise error;

     • elif :

       • output ;

       • .

即可进行表驱动的预测分析.

注意 的切分方向为 . 且产生式入栈时需要逆序压栈, 即 的尾部为栈顶，头部为栈底. 其中 .

表驱动预测分析法的步骤：

1. 消除二义性, 消除左递归;

2. 提取左公因子，消除回溯;

3. 求 集合;

4. 若 有交集，则非 LL(1) 文法，无法进行自顶向下分析; 否则

5. 根据 集合求出预测分析表;

6. 使用驱动程序进行预测分析.

自底向上分析

从输入串 规约为文法开始符号 的过程被称为自底向上分析.

移入-规约分析时自底向上分析普遍采用的分析形式.

移入-规约分析的下推自动机:

• be a PDA:

  • ;

  • ;

  • for :

    • ;

    • , if no reduction;

    • , if ;

    • , if , where is a state has been analyzed;

    • , if .

    • otherwise .

  • , otherwise .

项是指文法 的某个产生式 加上右部某位置上的一点形成的表达式 , 该点代表栈顶指向的当前位置, 说明分析器已经识别到该产生式的前缀.

增广文法(Augmented Grammar)是指在 中加入一个新的开始符号 和新的产生式 得到的文法 .

项目闭包是指项目集合 通过 即可到达的所有可能的状态, 记为 .

项目闭包的计算算法为:

0. ;

1. , :

   • if :

     • ;

2. repeat #1 until no new item added to .

Goto 集合是指状态集合 对栈顶符号 的集合 , 即在状态 将 压栈之后能进入的状态集合.

显然，我们要求每一个状态 , 都必须只能有 .

LR(0) 文法

即从左(left)向右扫描的最右(right)推导的文法, 且向前零个(0)符号.

LR(0) 分析器就是上述移入-规约分析的下推自动机, 当 不为空时:

• 若 , ;

• 若 , .

而对于 LR(0) 的规约，则为 , if .

因而 LR(0) 只能处理前缀不同的规约规则.

SLR(1) 文法

即从左(left)向右扫描的最右(right)推导的文法, 且向前看一个(1)符号, 采用极简(S)的前看方式.

SLR(1) 的自动机的栈被修改为, 其中的元素表示为 , 即当前栈为 , 前看符号为 .

SLR(1) 的 动作较 没有变化, 前看符号并不会影响 动作, 但是其规约规则被改进为:

, if .

SLR(1) 能处理有相同前缀的情况，但是却不能处理一个规则有不同后继的情况.

LR(1) 文法

即从左(left)向右扫描的最右(right)推导的文法, 且向前看一个(1)符号.

LR(1) 根据产生式的 集为每一个项目都派遣前看符号，即 iif. .

同时，项目集闭包的算法也有所不同:

0. ;

1. , :

   • :

     • if :

       • ;

2. repeat #1 until no new item added to .

同样，, 其中 .

LR(1) 分析器也不会改变对 的动作, 当 不为空时:

• 若 , ;

• 若 , .

而对于 LR(1) 的规约，则为 , if .

即后继状态 依赖于前看符号 .

由于后继状态依赖于前看符号，因此 LR(1) 能处理不同后缀的文法，但是也正因此，LR(1) 的状态数量急剧膨胀.

LALR(1) 文法

为解决 LR(1) 的状态膨胀的问题，LALR(1) 引入合并同心项目集合的操作.

若 ，则称 和 具有相同核心.

将具有相同核心的状态合并为同一个状态的操作，则称为合并同心项目集.

将 LR(1) 分析表进行合并同心项目集即可得到 LALR(1).

但是合并同心项目集合有可能导致归约-归约冲突, 这是因为在合并时忽略了前看符号.

仅合并具有相同项目 的状态不会导致归约-归约冲突.