编译原理考点梳理

期末考试对一些重点内容的梳理总结，希望能帮助到需要的小伙伴。
keep me far away everything i love
keep me far away everyone i know
i’m nothing campared to who uesd to be
words of song Homesick ,belong Flower Face

参考

B站视频链接 老师讲课通俗易懂。

参考博客链接
编译原理第三版《陈意云》

习题：

• 机试题

符号和名词⚽⚽⚽

代表	意义	备注
∑	基本字母表	字母表中无 ε
∪	并集 相当于
L*	L的闭包	0个或多个L连接的并集, r** = r*
L+	L的正闭包	一个或多个L的连接的并集
LM	L连接M，有顺序 。rs	(rs)t = r(st)
ε	空串，长度为0的特殊串。_e_是连接的恒等元素	er = r; re =r ， r* = (r
词法记号	二元组合集 <记号名,属性值>	即词法分析器所输出的
模式	if for esle
词法单元	age ,100,
名字和符号	为区分二者，使用黑体表示名字
[abc], [A-z]	[abc]代表 a	b
一元运算符 ？	零个或一个实例 ,r?是r	ε的缩写
一元运算符 +	一个或多个实例
保留字	是语言预先确定了含义的词法单元
标准标识符	也是预先确定了含义的标识符，但程序可以重新声明它的含义
正规集	正规式表示的语言叫做正规集或正规语言。

重点内容????????????

第一章 绪论

什么是编译型和解释型语言？

编译型：先编译后执行

• 把高级语言程序翻译成机器语言程序运行所得机器语言程序求得计算结果
• 翻译程序，编译程序口

解释型：解释执行

• 边解释边执行
• 解释程序

编译型：运行前先应泽器将高级语言代码编泽为对应机器的cpu汇辑指令集，曲汇绸器汇编为目标机器码，生成可执行文件，然最后运行生成的可执行文件。最典型的代表语言为C/C++，一般生成的可执行文件及.exe文件
解释型：在运行时由翻器将高级语言代码翻译成于款行的中间代码，并由解释器（例如浏器、虚拟机）速一将该中间代码解释成机器码并执行（可看做是将编解、运行合二为一了），最典型的代表话言为 Javascript、 Python、Ruby和Perl等

翻译器，编译器，解释器？

能够完成从一种语言到另一种语言的保语义变换的软件称为翻译器
编译器是一种翻译器，它的特点是目标语言比源语言低级
解释器是不同于编译器的另一类语言处理器。 解释器不像编译器那样通过翻译来生成目标程序，而是直接执行源程序所指定的运算。解释器也需要对源程序进行词法分析、语法分析和语义分析等，这样它才有可能知道源程序制定了一些什么运算。

解释执行效率低的原因？

• 对于编译方式来说，对源程序的词法分析、语法分析和语义分析只要进行一次。
• 对于解释执行来说，每次执行到源程序的某个语句，都要对它进行一次词法分析、语法分析和语义分析，确定了这个语句的含义以后，才能执行它指定的运算。

编译器的各个阶段?

• 词法分析：将源程序代码的字符流转成记号流 。记号流就是个二元组（表示符号的时候是单个的）。** 字符流—记号流**
• 语法分析（syntax analysis）**检查记号流是否符合编程语言的规则，然后根据编程语言规则用记号的第一元建立一种树形中间表示。典型的中间表示是语法树。**记号流—树形中间表示（语法树）
• **语义分析 使用语法树和符号表，根据语言的定义检查源程序之间的语法一致性。确保各部分都能组合。另外还进行类型检查。**语法树—更低级的中间代码表示。
• 独立于机器的代码优化 优化代码。速度快或者功耗低。
• 代码生成是指源程序的一种中间表示作为输入并把它映射到一种目标语言。

如果目标语言是机器代码，则需要为源程序所用的变量选择寄存器或内存单元，然后把中间指令序列翻译为完成同样任务的机器指令序列

第二章

（1）词法分析器的相关概念

• 构造词法分析器可以用状态转换图来描述词法记号的结构，然后手动把这些状态图翻译成为识别词法记号的程序。
• 任务：把源程序的字符流翻译成词法记号流。

•词法分析器的任务是把构成源程序的字符流翻译成词法记号流。
•构造词法分析器的一种简单办法是用状态转换图来描述元词法记号的结构，然后手工把这种状态转换图翻译成为识别词法记号的程序。

词法记号 ：二元组合集
模式： if for esle
词法单元: age ,100,
// 都是为了能够识别出具有特定意义的整体。而非一个一个的被分割。
>>
关键字、保留字和标准标识符的区别
•保留字是语言预先确定了含义的词法单元
•标准标识符也是预先确定了含义的标识符，但程序可以重新声明它的含义
>>
大多数词法错误是多、漏或错一个字符、或相邻的两个字符错位。（无法发现。可以发现123.x这种）
>>

1. 字符串集合由称为模式的规则来描述。
2. 正规式是表示这些规则的一种重要方法

一些名词：
字母表：符号的有限集合 {0,1}
串：字母表符号的又穷序列。 banana 串长是6
xy就是把y串连到x后
语言：字母表上的一个串集



串和语言的运算

（2）正规式与正规集

正规式是按照一组定义规则，由简单的正规式构成。
正规式r表示一个语言L®。
下面是定义字母表_Σ_上正规式的规则，和每条规则相联系的是被定义的正规式所表示的语言描述。
（1）ε_是正规式，它表示{ε}。
（2）如果_a_是_Σ_上的符号，那么_a_可以作为正规式，它表示语言{a}。
（3）假设_r_和_s_都是正规式，它们分别表示语言语言_L(r)和语言_L_(s)，那么(_r _)|( _s _)、(_r _)( _s _)、(_r _)*和(r )都是正规式，分别表示语言_L(r) L(s) 、L(r) L(s)、(L(r))*和_L(r) 。
和下面的表示的一样。

• * > () > |

正规定义

例题2.4 C语言标识符的定义。
例题2.5 无符号数的定义。
简化表示：

总结：

并：就是二者合集元素中选一个。语言中用 ∪ ，正规式为 | 表示。
所以 | 是可以交换的。
连接：两个集合中元素随机拼接，但有顺序的 因此连接可以有结合律，例如 r(s|t) = rs|rt但不能交换。用()() 表示 L®L(s).
闭包：零到n个的连接。就是集合的0-n次倍
正闭包：。。

（3）状态转换图

状态转换图描绘词法分析器被语法分析器调用时，词法分析器为下一个记号所做的动作。
转换图：

符号	意义	备注
圆圈	表示状态	状态由有向边连接
两个圆圈	表示它们是接受状态，控制进入这样的状态表明识别了一个记号。另外接受状态可以有动作，，控制到达接受状态时执行它的状态。
other	如果离开状态s的某个边上有标记other，则表示它离开s的其他边所指示的字符以外的任意字符
*	表示输入指针必须回退的状态。
installId()	获取要返回的记号名和属性	会先检查关键字表。再检查标识符表。
delim	blank	tab
圆圈上有有向边指回	和L*一样，0个或多个
ε-closure(s)	从NFA的状态s出发，只用ε转换能到达的NFA的状态集合。
ε-closure(T)	NFA的状态集合UtÎT ε-closure(t)
move(T,a)	NFA的状态集合UtÎT move(t,a)（move被拓展成多态函数）

转换例题：important

（4）有限自动机

NFA、DFA、NFA与DFA的转换、DFA的化简
转换表

• NFA同一状态的多条边代表 a | b关系

例题 识别语言(a|b)ab 的NFA
*


**
NFA含义：对于某点来说，下一步将符号输入到那个状态，就填那个状态的符合集合



分叉的可以加上ε


NFA转成DFA
转换思想：新构造的DFA的每个状态对应到NFA的一个状态集上，

**
解答：

1. **先计算 **ε-closure(0) 得到 **A = {0,1,2,4,7} // **ε-closure(0) 从0开始能够通过 ε*到达的状态点。包括0状态。相当于ε组成的通路。
2. 输入字母表为{a,b}，先标记A，然后计算：ε-closure (move(A,a))

move(A,a) = {3,8} // 即A中的状态可以通过a到达点的集合。

3. 计算 ε-closure({3,8}) = {1,2,3,4,6,7,8} 记做Dtran[A,a] = B// 同理 3,8分别能到达的并集。
4. 同理计算 move(A,b) ε-closure (move(A,b)) 即ε-closure (move(A,b))= ε-closure (5) = {1,2,4,5,6,7}。记做Dtran[A,b] =C
5. 剩余接受状态。通过ABC进行推理。

DFA化简:
目的：化简到DFA状态最少
重复细分，直到没有任何一个子集再需细分为止。
满足条件：

• 没有多余状态
• 没有两个状态是等价的。

求解步骤
① 将DFA M的状态集Q分划成两个子集：终态集和非终态集；
② 对每个子集G，如果面对某个输入符号得到的后继状态不属于同一个子集，则将G进一步划分；
③ 重复②直到不再产生新划分；
④ 在每个子集中选一个状态作代表，消去其他状态，得到最少状态的等价DFA M’。
例题：

（5）从正规式到有限自动机

步骤
构造NFA，转变成DFA（子集构造，输入符号），然后再化简。

第三章

（1）上下文无关文法、推导与归约、语法分析树、二义性

较复杂的语言不能用正规式表达，如正规式不能描述配对或嵌套的结果.因此引出。比正规式更强的上下文无关文法。
正规式可以描述的语言都能用上下文无关文法来描述

类似于词法分析，我们为了描述一类单词，使用了正则表达式，在这里，我们为了描述一类语法，我们使用了上下文无关文法。由此可以知道，文法是用来定义句子结构的（单词与单词之间的关系），上下文无关文法是指，该文法所定义的所有的句子结构之间是没有关系的。例如ID ＝ ID ＋ ID，我们不关心ID在怎么来的，经历了那些东西，我们只关心一个字符是不是ID，以及ID的等价形式有那些。

上下文无关文法G是一个四元组(V V S P)文法
VT : 终结符集合（非空有限） 词法分析器返回的记号的集合
VN : 非终结符集合（非空有限），并且V∩V=Φ 。
S: 开始符号，非终结符中的一个
P: 产生式集合， 产生式形式 : A® a ，其中AϵVN，a ϵ (VN∪VT )*。开始符号至少出现在某个产生式的左部。

开始符号至少出现在某个产生式的左部。产生式指明了终结符和非终结符组成串的方式。 产生式的形式是A－>B这种形式，其中左面一定是非终结符，右面是终结符和非终结符的混合。所以，凡事能够放到左面的符号都成为非终结符，是由语法的设计者定义的。终结符就是不能产生产生式的符号，比如语言中的＋，－，），>等。起始符号是非终结符集合中的一个，表示语法分析从这个符号开始。例如：A->B+C, B->A,C->-C，使用B和C代替第一产生式中的相应部分，就可以得到一个能不限数字个数的加减法运算表达式 非终结符： - 大写字母 - 代表开始符号S - 小写字母组成的名字 如_expr和 stmt_

**

因为最左的非终结符和最右的非终结符是唯一的，所以最左推导和最右推导具有唯一性。
最左推导：需要考虑每一步都是代换句型中最左边非终结符的推导。 - 在最左推导中，总是选择每个句型的最左非终结符进行替换 - 在自顶向下的分析中，总是采用最左推导的方式

最右推导（用的多） - 在最右推导中，总是选择每个句型的最右非终结符进行替换 - 在自底向上的分析中，总是采用最左归约的方式，因此把最左归约称为规范归约，而最右推导相应地称为规范推导

| |

（2）语法分析器的相关概念（文法）

**文法的优点 **
•文法给出了精确的，易于理解的语法说明。
•对于某些文法类，可以为其中的文法自动产生高效的分析器。
•可以给语言定义出层次结构（如嵌套和配对）。
•以文法为基础的语言的实现便于语言的修改。
文法的问题
•文法只能描述编程语言的大部分语法，不能描述语言中上下文有关（如形参实参）的语法特征。

3.2.2 分离词法器的理由
为什么要用正规式定义词法？	- 词法规则非常简单，不必用上下文无关文法 - 对于词法记号，正规式描述简洁且易于理解 - 从正规式构造出的词法分析器效率高
从软件工程角度看，词法分析和语法分析的分离有如下好处	- 简化词法分析器的设计 - 编译器的效率会改进 - 编译器的可移植性加强 - 便于编译器前端的模块划分
能否把词法分析并入到语法分析中，直接从字符流进行语法分析？	不能 - 若把词法分析和语法分析合在一起，则必须将语言的注解和空白的规则反映在文法中，文法将大大复杂。 - 注解和空白由自己来处理的分析器，比注解和空白已由词法分析器删除的分析器要复杂得多。
总结： •正规式是描述诸如标识符、常数和关键字等词法结构的最有力武器。 •上下文无关文法是描述括号配对、begin和end配对、语句嵌套、表达式嵌套等结构的最有力武器，这些结构不可能用正规式来描述。

（3）二义性

如果一个文法对一个句子进行分析可以产生多个语法分析树，我们就称这个文法是二义文法，二义文法计算机不能处理，这时候需要转化为非二义文法。
文法二义性不代表语言一定是二义的，只要当一个语言所有的文法都是二义时，这个语言才称为二义的。
二义性产生的原因：没有清楚的定义文法的加减乘除的优先级，
解决办法：改造文法，引入新的文法变量。
消除二义性：

（4）语法分析的方法：

自下而上	自上而下
- 定义：从输入串开始，逐步进行归约，直到文法的开始符号 - 归约：根据文法的产生式规则，把串中出现的产生式的右部替换成左部符号 - 特点：从树叶节点开始，构造语法树	- 方法：算符优先分析法、LR分析法 - 定义：从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导 - 推导：根据文法的产生式规则，把串中出现的产生式的左部符号替换成右部 - 特点：从树的根开始，构造语法树 - 方法：递归下降分析法、预测分析程序

（）的数字代表往后看几步。

（5）自上而下分析面临的问题

• 二义性问题
• 文法左递归问题。E→E+T 产生式的右部刚好是左部
  

即一个文法含有下列形式的产生式之一时：
1)A→Aβ，A∈VN，β∈V*
2)A→Bβ，B→Aα，A、B∈VN，α、β∈V*
则称该文法是左递归的。
一个文法是左递归时，不能采取自顶向下分析法。

• 回溯问题（类比DFS）

虽然语法树是唯一的，但是当进入分叉口的时候，然后就没办法判断，是否能走通。
分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。
产生原因：一个推导有多种可能。

（6）左递归的消除，

参考链接


直接左递归经过一次推导就可以看出文法存在左递归，如P→Pa｜b。
间接左递归侧需多次推导才可以看出文法存在左递归，如文法：S→Qc｜c，Q→Rb｜b，R→Sa｜a有S =>Qc =>Rbc =>Sabc
直接左递归消除（转成右递归）
记住公式，对αβ整体代换

| 设有文法产生式：A→Aβ|γ。其中β非空，γ不以A打头。
可写为：A→γA’
A’→βA’|ε
一般情况下，假定关于A的产生式是：
A→Aα1| Aα2 |… |Aαm|β1|β2 |…|βn
其中，αi(1≤i≤m)均不为空，βj(1≤j≤n)均不以A打头。
则消除直接左递归后改写为：
A→ β1A’| β2 A’ |…| βnA’
A’→ α1A’ | α2A’ |…| αmA’ |ε

根据上面例子找到谁是α，β。
例：有文法G(E)：
**E→E +T |T **
T→T*F | F
F→ (E)|i
消除该文法的直接左递归。
解：按转换规则,可得:
E→TE’
E’→+TE’|ε
T→FT '
T’→*FT’|ε
F→(E)|i
|
| — |

间接左递归消除
用编号小的替换编号大的变量。

（7）公共左因子的提取

和提取公因子一样。(消除了选择困难)

#### （8）first集 follow集（难点） > 算预测分析表的工具

对于终结符而言，FIRST集中的元素只有它本身
对于非终结符而言，如果开始符是终结符或者空符号串ε，则加入其FIRST集中；若开始符是非终结符，则要加入它的不含ε的FIRST集，并考虑其为ε时的情况。

推出的第一个为b的所有集合。
P55例题3.12

便于选择。
对于非终结符而言，如果开始符是终结符或者空符号串ε，则加入其FIRST集中；若开始符是非终结符，则要加入它的不含ε的FIRST集，并考虑其为ε时的情况。
(先找首部，然后再替换移到左边。要过几遍最终返回)


根据生成式的首部（STMT,EXPR,TERM） 和右表从上到下标记。（未考虑推出空的情况）
遇到非终结符就把右表的一列都标记上，



如果A可以推出空集（包括多步推导），就把空集放到对应集合里（先考虑上面的，最后再考虑空集）
特殊：如果上一个可能是空串的时候，第二个就是首部（此时需要把第二个的集合放到对应集合上面），他也会为空集。注意。

参考视频链接

（9） LL(1)文法的条件

产生式A—>α|β 满足下列条件：
（1）如果α、β均不能推导出ε，则 FIRST(α) ∩ FIRST(β) = ∅。
（2）α 和 β 至多有一个能推导出 ε。
（3）如果 β *═> ε，则 FIRST(α) ∩ FOLLOW(A) = ∅。
将满足上述条件的文法称为LL(1)文法。
LL(1)核心思想:利用前瞻字符确定产生式的选择。BFS 适用任何文法（效率极低），DFS 无法处理左递归

• 优点：
  • 复杂度为线性。
• 缺点：
  • 处理文法范围变小

（10）LL(1)分析表的构造及预测分析过程

行数是非终结符格式，列数是输入符号（终结符）
推出的首个终结符a是唯一的。（firrst集合）



如果是非终结符需要进行扩展。

总结步骤：
如果是非终结符，需要先计算FIRST(A).
如果有空集记得考虑空集。
构造分析表。
然后用栈的方式消除。

待完成

（2）优先集、结合性；名字、标识符；左值和右值；
（3）符号串和符号串集合的相关概念以及相关运算


（4）形式语言鸟瞰（了解），即四种类型的文法
第四章
（1）概念的掌握，如短语、直接短语、句柄
（2）算符优先分析
（3）LR分析步骤
（4）掌握LR（0）分析表、SLR分析表、规范LR分析表、LALR分析表的画法
第五章
（1）综合属性、继承属性
（2）S-属性文法 和 L-属性文法
（3）语法制导定义
（4）翻译模式
第6章
（1）中间语言的表示形式
（2）布尔表达式和控制语句的翻译
第7章
（1）符号表的组织与作用


。