第1章绪论

1.1 什么是编译

编译： 将高级语言（源语言）翻译成汇编语言或机器语言（机器语言）的过程。

编译在语言处理系统中的位置

预处理器：
- 把存储在不同文件中的源程序聚合在一起
- 把称为宏的缩写语句转换为原始语句
可重定位（Relocatable）：

在内存中存放的起始地址 L 是不固定的。
链接器：
- 将多个可重定位的机器代码文件（包括库文件）连接到一起
- 解决外部内存地址问题
加载器：

修改可重定位地址：将修改后的指令和数据放到内存中的适当位置。

1.2 编译系统的结构

编译系统的结构与执行顺序如下图所示：

将字符流输入 词法分析器 获得词法单元流，然后经过 语法分析器 生成语法分析树。利用 语义分析器 来分析语法分析树所具有的语义。获得语义后，利用 中间代码生成器 将语法分析树转换成中间代码。中间代码为了具有更好的普适性，经过了一步 机器无关代码优化 。

优化后的中间表示形式经 目标代码生成器 转化为目标机器语言，再经过一步优化转化为与 目标机器相关 的目标机器语言，此时的代码将更好的在目标机器上执行。

1.2.1 词法分析/扫描（Scanning）

词法分析的主要任务：

从左向右逐行扫描源程序的字符，识别出各个单词，确定单词的类型。将识别出的单词转换成统一的机内表示——**词法单元(token)**形式。

token：< 种别码，属性值 >

	单词类型	种别	种别码
1	关键字	program、if、else、then、…	一词一码
2	标识符	变量名、数组名、记录名、过程名、…	多词一码
3	常量	整型、浮点型、字符型、布尔型、…	一型一码
4	运算符	算术（ + - * / ++ – ）关系（ > < == != >= <= ）逻辑（ & \| ~ ）	一词一码或一型一码
5	界限符	; ( ) = { } …	一词一码

1.2.2 语法分析（parsing）

**语法分析器(parser)**从词法分析器输出的 token 序列中识别出各类短语，并构造语法分析树（parse tree）。

1.2.3 语义分析

语义分析的主要任务：

一、收集标识符的属性信息

种属 (Kind)

简单变量、复合变量（数组、记录、…）、过程、…
类型 (Type)

整型、实型、字符型、布尔型、指针型、…
存储位置、长度
值
作用域
参数和返回值信息
参数个数、参数类型、参数传递方式、返回值类型、…

思考： 符号表中为什么要设计字符串表这样一种数据结构？

答：由于不同的标识符的NAME字段的长度不同：

如果设计为定长存储，则造成内存浪费

如果设计为变长存储，则查询效率会大大降低

这样的字符串表设计，通过指针指向首地址，并标明NAME字段的长度，可以节省空间，同时具有极好查询性能。

二、语义检查

了解即可，没啥好记的。

变量（包括数组、指针、结构体）或过程未经声明就使用
变量（包括数组、指针、结构体）或过程名重复声明
运算分量类型不匹配
操作符与操作数之间的类型不匹配

赋值号左边出现一个只有右值的表达式
数组下标不是整数
对非数组变量使用数组访问操作符
对非结构体类型变量使用“.”操作符
对非过程名使用过程调用操作符
过程调用的参数类型或数目不匹配
函数返回类型有误

1.2.4 中间代码生成器

常用的中间表示形式：

一、三地址码

三地址码由类似于汇编语言的指令序列组成，每个指令最多有三个操作数(operand)。

三地址指令序列唯一确定了运算完成的顺序。

常用的三元地址指令如下：

三地址指令的表示：

四元式 (Quadruples)
(op, arg1, arg2, result)
三元式 (Triples)
(op, arg1, agr2)
间接三元式 (Indirect triples)

二、语法结构树/语法树（Syntax Trees）

一个程序片段，既可以表示为三地址码的形式（如右边蓝色的框中），也可以表示为语法结构树的形式（如下左图）。

怎么由这棵语法树转换为三地址指令呢？后面会学到。

1.2.5 目标代码生成器

目标代码生成以源程序的中间表示形式作为输入，并把它映射到目标语言。

目标代码生成的一个重要任务是为程序中使用的变量合理分配寄存器。

1.2.6 代码优化

为改进代码所进行的等价程序变换，使其运行得更快一些、占用空间更少一些，或者二者兼顾。

1.3 编译程序的生成

编译器的 T 形图

1.3.1 自展

在同一机器上实现不同语言的编译器。

为了好理解，下图中 $P_i'$ 视为我们期望的最终编译器效果（例如，用L1实现对L2的编译）。 $P_i$ 是最终在已有编译器的基础上实现的效果（例如，利用P1编译器实现了L2程序通过层层转换最终编译为A程序）。

构造P1： 只需要将 L1程序通过 A语言转换为 A程序即可；

构造P2： 为了方便，使用高级语言L1实现编译器。将 L2程序通过 L1语言转换为 A程序，中间经历了 L2→L1→A 的过程。

构造P3： 使用高级语言L2实现编译器。将 L3程序通过 L2语言转换为 A程序，中间经历了 L3→L2→L1→A 的过程。

如果继续这个过程，自展情况如下：

1.3.2 移植（交叉编译）

将一台机器上运行的编译器进行处理，构造出在另一个台机器上可以运行的编译器。

使同一程序运行在不同机器上。

如上图，首先在 A机器上构造 L程序的编译器。这样就可以使用 L语言构造其他编译器了。

我们的目标是构造一个 P2 使其能够运行在 B 机器上。首先，通过 P1 可以构造出一个 $P_2''$ ，该编译器在功能上与 P2 相同，但是是由 A语言实现的，并不能运行在 B机器上。不过此时我们有了可以从 L程序经过 A语言编译为 B代码的编译器 $P_2''$ 。

利用 $P_2''$ ，可以通过 L→A→B 的编译语言的转化过程，从而实现利用 B语言将 L程序编译为 B代码的编译器 P2。

1.4 为什么要学习编译原理

更深刻地理解高级语言程序的内部运行机制
教给我们如何严谨地去思考、编写程序
编译原理涉及了计算机科学求解问题的基本思路和方法，即问题的“形式化描述→自动化处理”
所涉及的理论和方法在很多领域都会被用到

自然语言处理、模式识别、人工智能、……
很多应用软件都会用到编译技术

1.5 编译技术的应用

结构化编辑器（Structure editors）

引导用户在语言的语法约束下编制程序
- 能自动地提供关键字和与其匹配的关键字
智能打印机（Pretty printers）

对程序进行分析，打印出结构清晰的程序
- 注释以一种特殊的字体打印
- 根据各个语句在程序的层次结构中的嵌套深度进行缩进
静态检测器（Static checkers）

静态定位程序中的错误
- 释放空指针或已释放过的指针
- 检测出程序中永远不能被执行的语句
文本格式器（Text formatters）

文本格式器处理的字符流中除了需要排版输出的字符以外，还包含一些用来说明字符流中的段落、图表或者上标和下标等数学结构的命令
数据库查询解释器（ Database Query Interpreters ）

数据库查询语句由包含了关系和布尔运算的谓词组成。查询解释器把这些谓词翻译成数据库命令，在数据库中查询满足条件的记录。
高级语言的翻译工具

第2章语言及其文法

2.1 基本概念

串（String）： 是一个有穷符号（symbol）序列。

字母表（Alphabet）： 是一个有穷符号集合。

2.2 文法的定义

2.3 语言的定义

2.3.1 文法

2.3.2 推导（Derivations）和归约（Reductions）

2.3.3 句型（sentential form）和句子（sentence）

句型：既可以包含终结符，也可以包含非终结符，也可以是空串。
句子：不包含非终结符。

2.3.4 语言的形式化定义

2.3.5 语言上的运算

2.4 文法的分类

2.4.1 0型文法（Type-0 Grammer）

2.4.2 1型文法（Type-1 Grammer）

2.4.3 2型文法（Type-2 Grammer）

2.4.4 3型文法（Type-3 Grammer）

2.4.5 四种文法之间的关系

2.5 CFG的语法分析树

2.5.1 树的产出（yield）或边缘（frontier）

注意：产出（边缘）是指所有叶节点从左到右排列得到的符号串。

2.5.2 短语（phrase）和直接短语（immediate phrase）

2.5.3 二义性文法（Ambiguous Grammer）

二义性文法的判定

对于任意一个上下文无关文法，不存在一个算法，判定它是否为二义性的；

但能给出一组充分条件，满足这组充分条件的文法是无二义性的

满足，肯定无二义性
不满足，也未必就是有二义性的

第3章词法

3.1 单词的描述

3.1.1 正则表达式（Regular Expression, RE）

3.1.2 正则定义（Regular Definition）

3.2 单词的识别

3.2.1 有穷自动机（Finite Automata）

FA模型

FA的表示

FA定义（接收）的语言

满足最长子串匹配原则（Longest String Matching Principle）

3.2.2 有穷自动机的分类

①确定的FA（Deterministic finite automata, DFA）

②非确定的FA（Nondeterministic finite automata, NFA）

③DFA与NFA的等价性

④RE->NFA->DFA(转化)

下面的内容均以上图为例题：

参考博客1

参考博客2

因为 NFA 的状态转移不确定，不适合直接做词法分析器的识别，在写算法时往往需要使用回溯。所以我们一般使用子集构造算法，将 NFA 转换成 DFA，得到确定的状态转移，再转化成一个词法分析器的代码。

1.NFA→DFA

子集构造法：

下面从开始状态出发，构造可到达的子集，发现新的子集（ (～￣▽￣)～）则利用新子集继续构造子集，直到没有子集可以构造为止。

$q_1=\{0\}$

$q_1 \stackrel{a}{\rightarrow} \{0,1\}$ 即 $q_2 = \{0,1\}$ (～￣▽￣)～

$q_1 \stackrel{b}{\rightarrow} \{0\}$

$q_2 \stackrel{a}{\rightarrow} \{0,1\}$

$q_2 \stackrel{b}{\rightarrow} \{0,2\}$ 即 $q_3 = \{0,2\}$ (～￣▽￣)～

$q_3 \stackrel{a}{\rightarrow} \{0,1\}$

$q_3 \stackrel{b}{\rightarrow} \{0,3\}$ 即 $q_4 = \{0,3\}$ (～￣▽￣)～

$q_4 \stackrel{a}{\rightarrow} \{0,1\}$

$q_4 \stackrel{b}{\rightarrow} \{0\}$

到这里就没有新的子集可以构造了，那么构造的 DFA 如下图所示：

利用状态转换表实现：

状态重命名	将来要列的状态	a	b	新产生的状态集合
S0	{0}	{0,1}	{0}	{0,1}
S1	{0,1}	{0,1}	{0,2}	{0,2}
S2	{0,2}	{0,1}	{0,3*}	{0,3*}
S3	{0,3*}	{0,1}	{0}

2.RE→NFA

⑤带有“ $\varepsilon -$ 边”的NFA

⑥带有和不带有“ $\varepsilon-$ 边”的NFA的等价性

3.2.3 从正则表达式到有穷自动机

子集构造法（subset construction）伪代码

3.2.4 识别单词的DFA

识别标识符的DFA

识别无符号数的DFA

识别各进制的无符号整数的DFA

识别注释的DFA

识别Token的DFA

3.3 词法分析阶段的错误处理

3.3.1 错误检测类型

词法错误的类型

单词拼写错误

例：int i = 0x3G; float j =1.05e;
非法字符例：~ @

词法错误检测

如果当前状态与当前输入符号在 转换表对应项中的信息为空 ，而 当前状态又不是终止状态 ，则调用错误处理程序

3.3.2 错误处理

查找已扫描字符串中最后一个对应于某终态的字符

如果找到了，将该字符与其前面的字符识别成一个单词。然后将输入指针退回到该字符，扫描器重新回到初始状态，继续识别下一个单词
如果没找到，则确定出错，采用错误恢复策略

3.3.3 错误恢复策略

最简单的错误恢复策略：“恐慌模式 (panic mode)”恢复

从剩余的输入中不断删除字符，直到词法分析器能够在剩余输入的开头发现一个正确的字符为止

3.4 词法分析器生成工具 Lex

Lex的使用

Lex

第4章语法分析

语法分析的主要任务：

根据给定的文法，识别输入句子的各个成分，从而构造出句子的分析树。
大部分程序设计语言的语法构造可以用 CFG 来描述，CFG 以 token 作为终结符。
大部分语法分析器都期望文法是无二义性的，否则，就不能为一个句子构造唯一的语法分析树。

语法分析的种类：

自顶向下分析（Top-Down Parsing）

从分析树的根节点向叶节点构造分析树

从文法开始符号 $S$ 推导出串 $w$
自底向上分析（Bottom-up Parsing）

从分析树的叶节点向根节点构造分析树

将一个串 $w$ 归约为文法开始符号 $S$

最高效的自顶向下和自底向上方法 只能处理某些文法子类 ，但是其中的某些子类，特别是 LL 和 LR 文法，其表达能力 足以描述现代程序设计语言的大部分语法构造。

4.1 自顶向下分析

从分析树的顶部（根节点）向底部（叶节点）⽅向构造分析树。
可以看成是从⽂法开始符号 S 推导出词串 w 的过程。

4.1.1 最左推导（Left-most Derivation）

4.1.2 最右推导（Right-most Derivation）

最右句型也称规范句型。

最左推导和最右推导具有唯一性。

4.1.3 自定向下语法分析的通用形式

递归下降分析（Recursive-Descent Parsing）

由一组过程组成，每个过程对应文法的一个 非终结符
从文法 开始符号S 对应的过程开始，其中 递归调用 文法中其他 非终结符 对应的过程。如果 S 对应过程体恰好扫描了 整个输入串 ，则成功完成语法分析。

4.1.4 自顶向下分析存在的问题

同一非终结符的多个候选式存在 共同前缀 ，将导致回溯现象

因为有相同前缀时机器不知道如何选择，只能逐个尝试，试错了就要回溯。

解决方法：提取左公因子
左递归文法会使递归下降分析器陷入无限循环

左递归是在最左推导过程中，左边表达式的非终结符推出的右边表达式中最左侧还是自己。

$A \Rightarrow ^+Aa$ 左递归文法

$A \rightarrow Aa$ 直接左递归

经过两步或者两步以上推导产生的左递归称为是 间接左递归

解决方法：消除左递归

①消除直接左递归

消除直接左递归的一般形式：

②消除间接左递归

消除间接左递归的方法就是 间接左递归->直接左递归->消除直接左递归

4.2 预测分析法（Predictive Parsing）

预测分析 是 递归下降分析 技术的一个特例，同过在输入中向前看 固定个数 （通常是一个）符号来选择正确的 A-产生式。

可对某些文法构造出向前看 k 个输入符号的预测分析器，该类文法有时也称为 LL(k) 文法类。

预测分析 不需要回溯 ，是一种 确定的 自顶向下分析方法。

4.2.1 LL(1) 文法

我们先把 FIRST、FOLLOW、SELECT 集学完，最后看 LL(1) 文法。

这部分 B站有个 up 讲的很好，我是跟着他学的：https://www.bilibili.com/video/BV1Yr4y1m7PX/?spm_id_from=333.337.search-card.all.click&vd_source=e7300d5accad8932a257efb8871bb9ee

S_ 文法

抓住 确定性 就很好理解了。

FIRST 集

FIRST 集的计算

计算方法的关键：要推导的非终结符可以推导出的第一个终结符是什么？

做几个例题：

$A \rightarrow aB|\varepsilon | c$ 结果是 A 可推导出的第一个终结符

答案是 $\{a, \varepsilon, c\}$

$A \rightarrow ba$

答案是 $\{b\}$

$A \rightarrow bc | c$

答案是 $\{b, c\}$

$A \rightarrow bc | b | c | \varepsilon$

答案是 $\{b,c,\varepsilon\}$

FOLLOW(A) 集

FOLLOW(A) 的求法

计算过程遵照如下三条规则：

先看开始符号，则将结束符 $ 添加到 Follow(A) 中（有的教材将$写做#）
右边 A 后面有东西（该东西不能==> $\varepsilon$ ）, First(东西) 加入 Follow(A) ，把 $\varepsilon$ 扣除（因为有ε说明按照推出ε的路径下去，推到 $ 了，而终结符可以通过产生式左端或者左边的Follow集得到，不用单独考虑）
右边 A 后面没有东西（或者右边的非终结符推出ε了），Follow(产生式左边) 加入 Follow(A)

求Follow集不需要超前的往后推导，自己右边没有东西或者推出ε了没关系，从产生式左端或者左边的Follow集找答案就好，一次找不到，不停的循环迭代答案，每次都更完整一些，最后一定可以得到正确的、完整的Follow集。

先看一个例题：

首先求 First 集，按照前面的方法求：

A	推导式	First(A)
`E`	`E->TE->FT'E->PF'T'E` `P->(E)\|a\|b\|^`	`{(,a,b,^}`
`E'`	`E'->+E\|` $\varepsilon$	`{+,` $\varepsilon$ `}`
`T`	`T->FT'->PF'T'` `P->(E)\|a\|b\|^`	`{(,a,b,^}`
`T'`	`T'->T\|` $\varepsilon$	`First(T)` $\bigcup$ { $\varepsilon$ } = `{(,a,b,^,` $\varepsilon$ `}`
`F`	`F->PF'`	`First(P)` = `{(,a,b,^}`
`F'`	`F'->*F'\|` $\varepsilon$	`{*,` $\varepsilon$ `}`
`P`	`P->(E)\|a\|b\|^`	`{(,a,b,^}`

求出 First 集后，再求 Follow 集：

A	First(A)	中间过程（在右边找A）	使用的规则	Follow(A)
`E`	`{(,a,b,^}`	`E'->+E\|` $\varepsilon$ `P->(E)\|a\|b\|^`	1:`#加入` 3:`Follow(E')加入Follow(E)` 2:`{ ) }加入Follow(E)`	`{ #, Follow(E'), ) }` = `{ #, ) }`
`E'`	`{+,` $\varepsilon$ `}`	`E->TE'`	3: `Follow(E)加入Follow(E')`	`{ Follow(E) }` = `{ #, ) }`
`T`	`{(,a,b,^}`	`E->TE'` `T'->T\|` $\varepsilon$	2(`E'->+E`):`First(E')去掉` $\varepsilon$ `加入Follow(E)` 3:`Follow(T')加入Follow(T)` 3:`E'->` $\varepsilon$ 时 `Follow(E)加入Follow(T)`	`{ +, Follow(T'), Follow(E) }` = `{ +, #, ) }`
`T'`	`{(,a,b,^,` $\varepsilon$ `}`	`T->FT'`	3:`Follow(T)加入Follow(T')`	`{ Follow(T) }` = `{ +, #, ) }`
`F`	`{(,a,b,^}`	`T->FT'`	2`(T'->T)`:`First(T')去掉` $\varepsilon$ `加入Follow(F)` 3:`T'->` $\varepsilon$ 时 `Follow(T)加入Follow(F)`	`{ (, a, b, ^, +, #, ) }`
`F'`	`{*,` $\varepsilon$ `}`	`F->PF'` `F'->*F'\|` $\varepsilon$	3:`Follow(F)加入Follow(F')` 3:`Follow(F')加入Follow(F')`	`{ (, a, b, ^, +, #, ) }`
`P`	`{(,a,b,^}`	`F->PF'`	2: `First(F')去掉` $\varepsilon$ `加入Follow(P)` 3:`F'->` $\varepsilon$ 时 `Follow(F')加入Follow(P)`	`{ *, (, a, b, ^, +, #, ) }`

最终结果如下：

再看一个例题：同上

SELECT 集

Select 集计算：

先计算 First 集和 FOLLOW 集，然后将对每个表达式文法各产生式求 SELECT 集，规则如下：

注意：SELECT集不包含 ε 。

q_ 文法

q_ 文法在 s_ 文法的基础上，要求放宽了一点，右部可以出现 ε 了。

预测分析表

得到可以通过 SELECT 集得到预测分析表

预测分析表用于预测对某个输入符号，可能的产生式。

有了预测分析表，机器就可以根据输入符号，通过查表得方式判断用哪个产生式来解释。

LL(1)文法

简单的说 LL(1) 文法是能够通过输入的这一个字符 唯一确定 下一步选择哪个产生式的文法。

根据 LL(1) 文法的定义来判断一个文法是不是 LL(1) 文法，分三步走：

起始上面这三条约束都是为了让机器在做选择的时候有确定的答案。

光看文字有点麻，看一道例题理解一下：

判断下述文法是否是 LL(1) 文法：

$S \rightarrow aAS | b$

$A \rightarrow bA | \varepsilon$

解：按照 LL(1) 文法的定义来判断：

$First(aAS) = \{a\}$ $First(b) = \{b\}$

$First(bA) = \{b\}$ $First(\varepsilon) = \{ \varepsilon \}$

可以看到相同左部推不出相同终结符开头的串，满足条件（1）
对于相同左部的表达式，至多只有一个右部能推出 ε，满足条件（2）
因为 $\varepsilon \in First(A \rightarrow \varepsilon)$ 下面判断 A 是否满足条件 (3)

$Follow(A) = First(S) = \{a, b\}$

$Follow(A) \cap First(bA) \neq \phi$

不满足条件(3)，则不是 LL(1) 文法。

4.2.2 递归的预测分析法

实现预测分析的方法：

递归的方式：基于 预测分析表 对 递归下降分析法 进行扩展
非递归的方式： 显式地 维护一个栈结构来模拟 最左推导 过程

举个例子：

当表达式右部推导出 $\varepsilon$ 时，判断 TOKEN 是否等于其该表达式的 SELECT 集。

根据预测分析表为每一个非终结符编写一个过程。

4.2.3 非递归的预测分析法

非递归的预测分析显式地维护一个栈结构，而不是通过递归调用地方式隐式地维护栈。这样地语法分析器可以模拟 最左推导 过程。

这里维护栈实现了一个下推自动机（以匹配 a 串后面的 b 串的数量为例，即遇到 a 压栈，遇到 b 弹栈）。

表驱动的预测分析法

下面看一个例子：

后面同理，利用这种方式模拟，根据输入去预测表中选择产生式，当栈顶为终结符时，与剩余输入的第一个字符匹配，如果相等，则读出字符并将栈顶弹出。

递归预测 vs. 非递归预测

预测分析法实现步骤

构造文法
改造文法：消除二义性、消除左递归、消除回溯
求每个变量的 FIRST 集和 FOLLOW 集，从而求得每个候选式的 SELECT 集。
检查是不是 LL(1) 文法(确定性)。若是，构造预测分析表。
对于 递归预测分析 ，根据预测分析表为每一个非终结符编写一个过程；对于 非递归预测分析 ，实现表驱动的预测分析算法。

4.2.4 预测分析中的错误恢复

1. 错误检测

下面两种情况可以检测到错误：

栈顶的 终结符 和当前 输入符号 不匹配
栈顶的 非终结符 与当前 输入符号 再预测分析表对应项中的信息为空

2. 错误恢复

恐慌模式（Panic Mode）：

忽略输入中的一些符号，如果对应预测分析表中的“空”，则忽略该输入符号；
直到输入中出现由设计者选定的 同步词法单元（synchronizing token）集合 中的某个词法单元，弹出栈顶非终结符

同步词法单元集合，即对应非终结符的FOLLOW集。预测表中查到synch，则栈中弹出该非终结符。

因为该非终结符之后就应该出现其FOLLOW集中的内容，但是预测表中没有，就说明这一步可能是该非终结符整错了，弹掉它。

下面看一个例子：

4.3 自底向上的分析

从分析树的底部(叶节点)向顶部(根节点)方向构造分析树， 可以看成是将输入串w归约为文法开始符号S的过程 。

自顶向下的语法分析采用最左推导方式（构造句子的最左推导）
自底向上的语法分析采用最左归约方式（反向构造句子的最右推导）

自底向上语法分析的通用框架： 移入-归约分析(Shift-Reduce Parsing)

4.3.0 句型、短语、简单短语、句柄

看下面这张图更好理解关于子树的划分：

4.3.1 移入-归约分析

每次归约的符号串称为“句柄”。

语法分析器不断地重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空（当进入这样的格局时，语法分析器停止运行，并宣称成功完成了语法分析）为止.

4.3.2 移入-归约分析中存在的问题

1. 归约-归约冲突

2. 移入归约冲突

4.4 LR 分析法

LR文法 (Knuth, 1963) 是最大的、可以构造出相应 移入-归约语法分析器 的文法类

L: 对输入进行从左到右的扫描
R: 反向构造出一个最右推导序列

LR(k)分析： （决定是否归约时）需要向前查看k个输入符号的LR分析

k = 0 和 k = 1 这两种情况具有实践意义
当省略(k)时，表示k =1

4.4.1 LR 分析法的基本原理

自底向上分析的关键问题是什么？
如何正确地识别句柄
句柄是逐步形成的，用“状态”表示句柄识别的进展程度：

4.4.2 LR 分析器（自动机）的总体结构

4.4.3 LR 分析器工作过程

动图演示如下：

令a为w$的第一个符号；
while(1) { /* 永远重复*/ 
    令s是栈顶的状态；
    if ( ACTION [s，a] = st ) {
        将t压入栈中；
        令a为下一个输入符号；
    } else  if (ACTION [s，a] =归约A → β ) {
        从栈中弹出│ β │个符号；
        将GOTO [t，A]压入栈中；
        输出产生式 A → β ；
    } else  if (ACTION [s，a] =接受) break； /* 语法分析完成*/
    else调用错误恢复例程； 
}

4.4.4 构造给定文法的 LR 分析表

1. LR(0)分析

增广文法（Augmented Grammar）

文法中的项目

上面15个项目中，有些项目是等价的。可以把等价的项目组成一个项目集（I），称为项目集闭包（Closure of Item Sets），每个项目集闭包对应着自动机的一个状态。

LR(0)分析过程中的冲突

从上图可以看出，标红的状态既可以移入也可以归约。那么此时遇到*是移进呢？还是归约呢？

2. SLR分析

LR(0)考虑了A的上文（规范句型的前缀），但未考虑A的下文，因此消解冲突能力有限。

用 SLR 来分析上面这个例子，分析的方法如下图所示：

SLR 分析表构造算法

可惜，SLR分析也有冲突。

3. LR(1)分析

关于LR(1)的后继符号/前向搜索符，这个阿婆主讲的真的非常棒！

SLR 分析存在的问题：
SLR 只是简单地考察下一个输入符号 b 是否属于与归约项目 $A→α$ 相关联的 $FOLLOW(A)$ ，但 $b∈FOLLOW(A)$ 只是归约 $α$ 的一个必要条件，而非充分条件。

同一状态下，合并项目集中可合并的部分

各种LR分析表构造方法的不同之处在于归约项目的处理上

4. LALR（lookahead-LR）分析

为什么说合并同心项目时不会产生 移进-归约 冲突？

因为合并同心项目集其实是合并相同项目的后继符号，这样移进项目的移进字符一定是相同的，所以只可能有 归约-归约 冲突，而不会发生 移进-归约 冲突。

合并同心项的时候如果看不出来，可以按照下面的方法，先合并项目相同的各集合，利用LR(1)的预测分析表生成LALR的预测分析表，即通过LR(1)模拟过程，向状态合并后的新表中添加状态。

为什么说合并同心项会延迟错误发现呢？

可以看出当输入 d$ 时，如果没有合并 $I_4,I_9$ 的同心项，经过 I0->I4 就能发现错误。

但是合并同心项后，需要经过 I0->I4->I0->I2 才能发现错误，这延迟了两步。

5. 二义性文法

再看一个例子：

二义性文法的使用

应该保守地使用二义性文法，并且必须在严格控制之下使用，因为稍有不慎就会导致语法分析器所识别的语言出现偏差。

6. LR分析中的错误处理

4.5 算符优先分析法

略。

4.6 语法分析器自动生成工具

第5章语法制导翻译

语法制导翻译的基本思想

如何表示语义信息

为 CFG 中的文法符号设置语义属性，用来表示语法成分对应的语义信息。

如何计算语义属性

文法符号的语义属性值是用与文法符号所在产生式（语法规则）相关联得语义规则来计算的。

对于给定的输入串 $x$ ，构建 $x$ 的语法分析树，并利用与产生式（语法规则）相关联的语义规则来计算分析树中各结点对应的语义属性值。

将语义规则同语法规则（产生式）联系起来要涉及两个概念

语法制导定义（Syntax-Directed Definitions, SDD）
- SDD 是对 CFG 的推广
- 将每个 文法符号 和一个 语义属性 集合相关联
- 将每个 产生式 和一组 语义规则 相关联，这些规则用于计算该产生式中各文法符号的属性值。
例：
语法制导翻译（Syntax-Directed Translation Scheme, SDT）
- SDT 是在产生式右部嵌入了程序片段的 CFG ，这些 程序片段 称为 语义动作 。按照惯例，语义动作放在花括号内。
- 一个语义动作在产生式中的位置决定了这个动作的执行时间。
例：

SDD

是关于语言翻译的高层次规格说明
隐藏了许多具体实现细节，使用户不必显式地说明翻译发生地顺序

SDT

可以看作对 SDD 的一种补充，是 SDD 的具体实施方案
显式地指明了语义规则地计算顺序，以便说明某些实现细节

5.1 语法制导定义 SDD

语法制导定义 SDD 是对 CFG 的推广
- 将每个 文法符号 和一个 语义属性 集合相关联
  
  语义属性就是结构体成员。
- 将每个 产生式 和一组 语义规则 相关联，用来计算该产生式中各文法符号的属性值
  
  语义规则就是待执行的函数语句。
文法符号的属性
- 综合属性（synthesized attribute）
  - 在分析树节点 N 上的非终结符 A 的 综合属性 只能通过N的子节点或N本身的属性值来定义
  - 终结符可以具有综合属性。不过其值是由词法分析器提供的词法值，因此在 SDD 中没有计算终结符属性值的语义规则。
- 继承属性（inherited attribute）
  - 在分析树节点 N 上的非终结符 A 的继承属性只能通过N 的父节点、N 的兄弟节点或N 本身的属性值来定义。
  - 终结符没有继承属性。
看三个例子 ：
- 一个没有副作用的 SDD 有时也称为属性文法
  - 属性文法的规则：仅仅通过其他属性值和常量来定义一个属性值
  例：
SDD 求值顺序
- SDD 为 CFG 中的文法符号设置语义属性。对于给定的输入串 $x$ ，应用语义规则计算分析树中各个节点对应的属性值
- 语义规则建立了属性之间的依赖关系，在对语法分析树节点的一个属性求值之前，必须首先求出这个属性值所依赖的所有属性值
依赖图（Dependency Graph）
- 依赖图描述了分析树中节点属性间依赖关系的有向图。如果属性 $X.a$ 的值依赖于属性 $Y.b$ 的值，则依赖图中有一条从 $Y.b$ 的节点指向 $X.a$ 的节点的有向边。
例：
- 属性值计算的顺序可以使用拓扑排序（topological sort）来表示。
- 对于只具有综合属性的 SDD ，可以按照任何自底向上的顺序计算它们的值。
- 对于同时具有继承属性和综合属性的 SDD，不能保证存在一个顺序来对各个节点上的属性进行求值：

从计算的角度看，给定一个 SDD ，很难确定是否存在某棵语法分析树，使得 SDD 的属性之间存在循环依赖关系。

不过，一定存在一个 SDD 的有用子类，它们能够保证对每棵语法分析树都存在一个求值顺序，因为它们不允许产生带有环的依赖图。

5.2 S-属性定义与L-属性定义

这两类 SDD 可以和自顶向下及自底向上的语法分析过程一起高效地实现：

S-属性定义（S-Attributed Definitions, S-SDD）

仅仅使用综合属性的 SDD 称为 S 属性的 SDD（S-属性定义/S-SDD）。
- 如果一个 SDD 是 S 属性的，可以按照语法分析树节点的任何自底向上顺序来计算她的各个属性值。
- S-属性定义可以在自底向上的语法分析过程中实现。
L-属性定义（L-Attributed Definitions, L-SDD）

一个 SDD 是 L-属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：假设存在一个产生式 $A \rightarrow X_1X_2...X_n$ ，其右边部符号 $X_i(1 \leq i \leq n)$ 的继承属性仅依赖于下列属性：
1. A 的继承属性（不能是 A 的综合属性，因为如下图，A 的综合属性可以来自子节点的综合属性和继承属性，如果子节点继承父节点的综合属性就会在依赖图中形成回路)
2. 产生式中 $X_i$ 左边的符号的属性
3. $X_i$ 本身的属性，但 $X_i$ 的全部属性不能在依赖图中形成环路。
每个S-属性定义都是L-属性定义。

换句话说：在一个产生式所关联的各个属性之间，依赖图的边可以从左到右，但不能从右到左（因此称为L属性的，L是Left的首字母）。

称为L属性的 SDD （L-属性定义/L-SDD）

L-SDD 实例

5.3 语法制导翻译方案 SDT

语法制导翻译方案（SDT）是在产生式右部中嵌入了程序片段（称为语义动作）的CFG

SDT 可以看作是 SDD 的具体实施方案：

SDD 定义了各属性的计算方法（计算规则）怎么算？
SDT 进一步明确了各属性的计算时机（计算顺序）怎么算？+ 何时算？

两类重要SDD的SDT实现，SDT可在语法分析过程中实现：

基本文法可以使用 LR 分析技术，且 SDD 是 S 属性的

将 S-SDD 转换为 SDT 的方法：将每个语义动作都放在产生式的最后。

例：
基本文法可以使用 LL 分析技术，且 SDD 是 L 属性的

将 L-SDD 转换为 SDT 的规则
- 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端
- 将计算某个非终结符 A 的继承属性的动作插入到产生式右部中紧靠在 A 的本次出现之前的位置上
如果一个 L-SDD 的基本文法可以使用 LL 分析技术，那么它的 SDT 可以在 LL 或 LR 语法分析过程中实现。例子如下：