编译原理 陈火旺
第一章 引论
P1
1.翻译程序
翻译程序指的是这样一个程序，它能够把某一种语言程序(源语言程序)改造成另一种语言程序(目标语言程序)，
而(源语言程序)(目标语言程序)两者在逻辑上是等价的
2.编译程序
将高级程序设计语言 翻译成 逻辑上等价的低级语言 (汇编语言,机器语言) 的翻译程序。
从高级语言转换为低级语言，然后运行计算。
先编译 后执行
3.解释程序
边解释边执行
接受高级语言的语句输入，进行解释并控制计算机执行，得到结果。
P2
1.五个阶段 词法分析 语法分析 语义分析 优化 目标代码生成
1词法分析
2. 语法分析
3.语义分析
4优化
5目标代码生成
P6
1.符号表
（1）表格与表格管理
编译程序在工作过程中需要保持系列的表格，用以登记源程序的各类信息和编译各阶段的进展状况。
（2）合理的设计和使用表格式编译程序构造的一个重要问题。
（3）与编译的头三个阶段有关的表格有：
符号表、常数表、标号表、分程序入口表、中间代码表、过程引用表、循环特征表、等价名表、公用链表、格式表
（4）它用来登记 源程序中出现的每一个名字 以及 名字的各种属性
2.遍
从外部介质读取源件经过加工获得某种结果并将其送回外部介质的过程，称为一遍。
3.编译前端与后端
编译前端：由与源语言有关但与目标机无关的那些部分组成。包括词法分析、语法分析、语义分析与中间代码生成。
编译后端：包括编译程序中与目标机有关的那些部分，有代码优化和目标代码生成。
P12
程序语言主要由语法和语义两方面定义。
1.语法：所谓一个语言的语法是指这样的一组规则，用它可以形成和产生一个合适的程序
这些规则一部分称为词法规则，另一部分则称为语法规则（或产生规则）。
2.语义
对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。这就是语义问题。
语义是指这样的一组规则，使用它可以定义一个程序的意义。
我们采用的方法为：基于属性文法的语法制导翻译方法。
3.一个程序语言的基本功能是描述数据和对数据的运算。
所谓程序，从本质上来说是描述一定数据的处理过程。
在现今的程序语言中，一个程序大体可以视为下面所示的层次结构。
4.程序语言的每个组成成分都有（抽象的）逻辑 和 计算机实现两方面的意义。
当从数学上考虑每一个组成成分时，我们注重它的逻辑意义，
当从计算机这个角度来看时，我们注重他在机内的表示和实现的可能性与效率。
5.语句
从功能上说语句大体可分执行性语句 和 说明性语句两大类，
说明性语句旨在定义不同数据类型的变量或运算。执行性语句旨在描述程序的动作。
执行性语句又可分赋值语句、控制语句和输入/输出语句.
从形式上说，语句还可分为简单句、复合句和分程序等。
6.一个上下文无关文法G包括四个组成部分：一组终结符号，一组非终结符，一个开始符号，以及一组产生式。
7.产生式（也称为产生规则或简称规则）是定义语法范畴的一种书写规则。
一个产生式的形式是 A→ α ,
其中箭头左边的A是一个非终结符，称为产生式的左部符号；
箭头右边的α是终结符号或与非终结符号组成的一符号串，称为产生式的右部。
8.上下文无关文法Ｇ（ＶＴ，ＶＮ，Ｓ，￡）
形式上定义一个上下文无关文法Ｇ是一个四元式（ＶＴ，ＶＮ，Ｓ，￡）其中
ＶＴ 是一个非空有限集，它的每一个元素 称为终结符号；
ＶＮ 是一个非空有限集，它的每一个元素称为非终结符号，ＶＴ∩ＶＮ＝；
Ｓ 是一个非终结符号，称为开始符号；
￡ 是一个产生式（有限）集合，每个产生式形式是Ｐ→，
其中，Ｐ∈ＶＮ， ∈（ ＶＴ∪ＶＮ）＊开始符号S至少必须在某一产生式的左部出现一次。
9.假定G是一个文法，S是它的开始符号。
如果S*(表示从S出发，经0步或若干步可推出），则称是一个句型。
仅含终结符号的句型是一个句子。
文法G所产生的句子的全体是一个语言，将它记为L(G).
L(G)={|S + & ∈VT }
一个语言的 文法 不是唯一的
10.
为了对句子结构进行确定性分析，我们往往只考虑最左推导或最右推导。
所谓最左推导是指：任何一步
都是对中的最左非终结符进行替换的。
同样，可定义最右推导。
最左推导：任何一步
都是对α中的最左非终结符进行替换。
最右推导：任何一步
都是对α中的最右非终结符进行替换。
11.语法分析树与二义性
可以用一张图表示一个句型的推导，这种表示称为语法分析树，或简称语法树。
语法树的根结由开始符号所标记。
随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生了下一代新结。
每个新结和其父亲结间都有一条连线。
在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左至右排列起来就是一个句型
12.
如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。
也就是说，若一个文法存在某个句子，它有两个不同的最左（最右)推导，
则这个文法是法是二义的
同一个句子（仅含终结符号的句型） 对应 两棵不同的语法树
定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。
语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。
13.文法分成四种类型：0，1，2，3型
它们都由四部分组成，但对产生式的限制有所不同
0型(短语文法，图灵机)： 产生式形如：
其中：α(VT VN)*且至少含有一个非终结符；
β (VT VN)*
1型(上下文有关文法，线性界限自动机, 非确定的 下推自动机)：
产生式形如：
其中： 仅 S-->ԑ 例外。
2型(上下文无关文法， 非确定下推自动机)：
产生式形如： A
其中：A VN； (VT VN)*。
3型(正规文法，正规式，有限自动机)：
a.右限性正规文法
产生式形如： A B 或 A
其中： VT*；A，BVN
b.左线性正规文法
产生式形如： A B 或 A
其中： VT*；A， BVN
P37
1.编译程序首先是在单词级别上来分析和翻译源程序的。
词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，
把作为字符串的源程序 改造成为 单词符号串的中间程序。
因此，词法分析是编译的基础。
执行词法分析的程序称为词法分析器。
2. 输入源程序，输出单词符号。
程序语言的单词符号一般分为五种：
关键字
标识符
常数
运算符
界符
3. 词法分析器输出的单词符号常常表示为二元式： （单词种别，单词符号的属性值）
4.NFA转换成对应的DFA
一、NFA的确定化——子集法基本思想：
将DFA状态间转换关系映射成NFA中状态子集间的转换。
子集法：
(1)状态子集I的 闭包 _CLOSURE(I)：
(a)若q I,则q _CLOSURE(I)
(b)若q I,那么多q出发经过任意条弧而能到达的任何状态q’都属于 _CLOSURE(I)
I的 闭包的作用：主要是消除弧所带来的不确定性。
(2)Ia子集:
(a)由I中的状态出发，经过一条a弧（跳过a弧前的任意条弧）可到达的状态集合称J，则
Ia= _CLOSURE(J)。
通过Ia求出状态子集间的转换关系。
Ia子集的作用：
求出状态子集间的转换关系。
即： Ia 是指从I出发经过一条a弧（前后可以有任意多条弧）而到达的状态的集合。
(3)利用子集构造确定的有穷自动机DFA
即找到DFA的五个部分（如前面的NFA）
NFA=(S’, Σ’,δ’,S0’, F’)
DFA=(S, Σ,δ,s0, F)
字符集：Σ= Σ’
开始状态：
在NFA中：S0’={s}
_CLOSURE(S0)={S，A，B}
将NFA中的开始子集看作是DFA中的开始状态。即
s0= _CLOSURE(S0)
映射关系：
在NFA中： _CLOSURE(S0)输入a得到子集I0a（记为I1）,将I1映射成DFA中的S1
以此类推I1输入a得到子集I1a记为I2映射成DFA中的S2……直到不再产生新的状态为止。这样就可以将DFA中的映射关系求出。S1，S2……即为DFA中所有状态的集合。
终止状态集：
由至少包含一个NFA终止状态的DFA状态组成。
二、DFA的最小化
5.确定有限自动机(DFA)是一个五元式
M= (S, ,δ,s0, F) 其中:
(1)S是一个有限集，它的每个元素称为一个状态。
（2）Σ是一个有穷字母集，它的每个元素称为一个输入字符。
（3） δ是一个从S x 至S的单值部分映射。δ(s,a）=S’。
意味着：当现行状态为s、输入字符为a时，将转换到下一个状态S’。
我们称S’为s的后继状态。
（4）s0S，是唯一的初态。
（5）FS，是一个终态集（可空）
6.一个非确定有限自动机（NFA)是一个五元式
M= (S, Σ,δ,S0, F) 其中:
(1) S 同3.3.2的1
（2）Σ同3.3.2的2
（3）δ是一个从S x Σ*到S的子集的映照，即 δ：S x Σ*→2s
(4) S0S,是一个非空的初态集；
（5）F S，是一个终态集（可空）
7.
1、DFA与NFA的定义:
DFA=(S, Σ,δ,s0, F)
NFA=(S, Σ,δ,S0, F)
两者的区别在于:开始状态与映射关系的不同。
2、有穷自动机DFA的表示方法
状态转换矩阵 状态转换图
3、作用：
识别字符串
P66 第4章 语法分———自上而下分析
1.语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。
一类是自上而下分析法 (自顶向下） a. 递归下降 b.预测分析
另一类为自下而上分析法 （自底向上） a. 算符优先文法 b.规范归约
2.
自上而下分析所遇到的主要困难是
语法的左递归性使分析陷入无限循环；
回溯的不确定性，要求我们将已经完成工作推倒从来，为解决这些问题我们要消除左递归和消除回溯。
3.FOLLOW(B)的构造分为四条:
(1)如果B是文法的开始符号, 则 #属于FOLLOW(B)
(2)对形如: A … Ba…, 则把则 a属于FOLLOW(B)
(3)对形如:A ... BP…的规则(其中P为非终结符),则FIRST(P)中的非元素属于FOLLOW(B);
(4)对形如:A …B,或者A … B且 则FOLLOW(A)中的所有元素也属于FOLLOW(B);
判断某给定文法是否为LL(1)文法其条件为：
（1）文法不含左递归。
（2）对于文法中每个非终结符A的各个产生式的候选首符集两两不相交。
即，若
A 1 | 2 |…| n
则： FIRST(i) FIRST(j) = （i j )
(3) 对文法中每一个非终结符A，若它存在某个候选首符集包含，则
FIRST(A) FLLOW(A)=
一个文法若满足以上条件，则称该文法G为LL(1)文
P83 第5章 语法分析 ———自下而上分析
1. 所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根结。
2. 自下而上分析的关键问题是寻找可归约串。
对“可归约串”概念的不同定义，就形成了不同的自下而上的分析方法。
在算符优先分析法中我们用“最左素短语” 来刻画“可归约串”，
在“规范归约”中， 则用“句柄” 来刻画“可归约串”
3. 令G是一个文法，S是文法的开始符，假定是文法G的一个句型，
如果有：
S*A 且 A +
则称是句型相对于非终结符A的短语。
特别是，如果有
A
则称是句型相对于规则A 的直接短语，
一个句型的最左直接短语成为该句型的句柄。注意：短语的两个条件是：
S*A 且 A +
4.规范归约是关于α的一个最右推导的逆过程。因此规范归约也成最左归约。
在形式语言中， 最右推导常被称为规范推导。
由规范推导所得的句型称为规范举行。
如果文法G是无二义的，那么规范推导（最右推导） 的逆过程必是 规范归约（最左推导）
5.一个文法，如果它的任何产生式的右部都不含量个相继（并列）的非终结符，即不含如下形式的产生式右部：
…QR… 则我们称该文法为算符文法。
在后面的定义中，a、b代表任意终结符；
P、Q、R代表任意非终结符；
‘…’代表有终结符和非终结符组成的任意序列，包括空字。
6. 假定G是一个不含--产生式的算符文法。对于任何一对终结符a、b，我们说：
ab 当且仅当文法G中含有形如P …ab…或P …aQb…的产生式;
a<b 当且仅当G中含有形如P …aR…的产生式， 而R+b… 或R +Qb…;
a>b 当且仅当G中含有形如P …Rb…的产生式， R而R+…a或R +…aQ;
如果一个文法G中的任何终结符对（a, b ）至多只满足下述三关系之一：
a=·b, a<·b, a·>b
则称G是一个算符优先文法。
7.
为了刻画什么是“可归约串”我们将定义算符优先文法的句型的“最左素短语”这个概念。
素短语这样的一个短语，它至少含有一个终结符，并且除它自身外，不再含有更小的素短语
所谓最左素短语，是指处于句型最左边的那个素短语。
8.LR分析是应用最广泛的一类分析方法，它是实用的编译器***能最强的分析器，其特点是：
① 采用最一般的无回溯移进—归约方法；
② 可分析的文法是LL文法的真超集；
③ 能够及时发现错误，快到从左到右扫描输入序列的最大可能；
④ 分析表较复杂，难以手工构造。
9. LR分析与LR文法
LR分析器的核心是 LR分析表和驱动器。
与LL分析表不同的是， LR分析表可以被明显地分为两个部分：
一部分称为 动作表(action)，
另一部分称为 转移表(goto)。
两者都是二维数组，且行下标由称之为状态的整型数统一表示。
动作表以 终结符 作为列下标，
转移表 以非终结符 作为列下标。
若以s表示当前状态，a表示终结符，A表示非终结符，
则action[s, a]指示当前栈顶状态为s 和 输入 终结符为a时 应进行的下一动作；
而goto[s, A]指示在当前栈顶为s 和 非终结符A时的下一状态转移。
goto[s, A] 定义了一个以 文法符号A为 字母表的 DFA
由于确定goto[s, A]的是当前状态与非终结符，
所以转移表与输入序列无关，它只实现对非终结符的状态转移。
与输入终结符有关的仅有动作表。
10.根据当前状态与当前的剩余输入，动作表中有四种动作
（1）移进
（2）规约
（3）接受
（4）报错
11. LR的特点：
首先文法中允许左递归，这是LL分析无法做到的；
其次文法中减号
既可以用于二元运算，又可以用于一元运算，这是算符优先分析不容易做到的。
P136
第六章 属性文法和语法制导翻译
1.属性文法
属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为属性）。
这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列、符号表内容等等。
属性和变量一样，可以进行计算和传递。
2.属性一般分为两类：综合属性和继承属性
综合属性用于“自下而上”传递信息，
继承属性用于“自上而下”传递信息。
属性加工加工的过程 即是 语义处理的过程，
对于文法的每一个产生式都配备了一组属性的计算规则，则称为语义规则。
3.综合属性：
在语法树中，一个结点的综合属性的值由其子结点的属性值确定。
因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。
仅仅使用综合属性的属性文法称S—属性文法。
继承属性：
在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。 用继承属性来表示程序语言结构中的上下文依赖关系很方便。
4.基于属性文法的 语法制导翻译法
从概念上讲，基于属性文法的处理过程通常是这样的：
对单词符号串进行语法分析，构造语法分析树，
然后根据需要遍历语法树，并在语法树的各结点处按语义规则进行计算。
输入串--〉 语法树 --〉依赖图 --〉语义规则计算次序
这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法。
语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其它动作。对输入串的翻译也就是根据语义规则进行计算得出结果。
5.如果一属性文法不存在属性之间的循环依赖关系，那么该文法为良定义的。
为了设计编译程序，我们只处理良定义的属性文法。
P166
第七章 语义分析和中间代码的产生
1.紧接在词法分析和语法分析之后，编译程序要做的工作是进行静态语义检查和翻译。
静态语义检查通常包括：
（1）类型检查。
（2）控制流检查。
（3）一致性检查。
（4）相关名字检查。
2.翻译为中间语言的好处：
1）便于进行与机器无关的代码优化；
2）使编译程序改变目标机更容易；
3）使编译程序的结构 在逻辑上更为简单明确，
以中间语言为界面，编译前端和后端的接口更清晰。
3.中间语言的基本结构：
逆波兰表示（后缀式）
图表示法（DAG 和抽象语法树），
三地址代码（四元式、三元式、间接三元式）
P221
第八章 符 号 表
1.编译过程中编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有关信息。
这些信息通常记录在一张或几张符号表中。
符号表的每一项包括两部分：一部分是名字（标识符）；另一部分是此名字的有关信息。
每个名字的有关信息是指种属（如简单变量、数组、过程等）、类型（如整、实、布尔等）。
这些信息将用于语义检查、产生中间代码以及最终生成目标代码等不同阶段。
编译过程中，每当扫描器识别出一个单词后，编译程序就查阅符号表，看它是否已在其中。如果它是一个新名就将它填进表里。它的有关信息将在词法分析和语法-语义分析过程中陆续填入。
几乎在编译程序工作的全过程中，都需要对符号表进行频繁访问，可以认为查表或填表等操作，在编译程序的编译过程中是很大的一笔开销。
因此，合理地组织符号表，并相应地选择好查表和填表的方法，是提高编译序工作效率的重要一环。
2.一张符号表的每一项（或称入口）包含两大栏（或称区段，字域），即名字栏和信息栏。
P1
1.翻译程序
翻译程序指的是这样一个程序，它能够把某一种语言程序(源语言程序)改造成另一种语言程序(目标语言程序)，
而(源语言程序)(目标语言程序)两者在逻辑上是等价的
2.编译程序
将高级程序设计语言 翻译成 逻辑上等价的低级语言 (汇编语言,机器语言) 的翻译程序。
从高级语言转换为低级语言，然后运行计算。
先编译 后执行
3.解释程序
边解释边执行
接受高级语言的语句输入，进行解释并控制计算机执行，得到结果。
P2
1.五个阶段 词法分析 语法分析 语义分析 优化 目标代码生成
1词法分析
2. 语法分析
3.语义分析
4优化
5目标代码生成
P6
1.符号表
（1）表格与表格管理
编译程序在工作过程中需要保持系列的表格，用以登记源程序的各类信息和编译各阶段的进展状况。
（2）合理的设计和使用表格式编译程序构造的一个重要问题。
（3）与编译的头三个阶段有关的表格有：
符号表、常数表、标号表、分程序入口表、中间代码表、过程引用表、循环特征表、等价名表、公用链表、格式表
（4）它用来登记 源程序中出现的每一个名字 以及 名字的各种属性
2.遍
从外部介质读取源件经过加工获得某种结果并将其送回外部介质的过程，称为一遍。
3.编译前端与后端
编译前端：由与源语言有关但与目标机无关的那些部分组成。包括词法分析、语法分析、语义分析与中间代码生成。
编译后端：包括编译程序中与目标机有关的那些部分，有代码优化和目标代码生成。
P12
程序语言主要由语法和语义两方面定义。
1.语法：所谓一个语言的语法是指这样的一组规则，用它可以形成和产生一个合适的程序
这些规则一部分称为词法规则，另一部分则称为语法规则（或产生规则）。
2.语义
对于一个语言来说，不仅要给出它的词法、语法规则，而且要定义它的单词符号和语法单位的意义。这就是语义问题。
语义是指这样的一组规则，使用它可以定义一个程序的意义。
我们采用的方法为：基于属性文法的语法制导翻译方法。
3.一个程序语言的基本功能是描述数据和对数据的运算。
所谓程序，从本质上来说是描述一定数据的处理过程。
在现今的程序语言中，一个程序大体可以视为下面所示的层次结构。
4.程序语言的每个组成成分都有（抽象的）逻辑 和 计算机实现两方面的意义。
当从数学上考虑每一个组成成分时，我们注重它的逻辑意义，
当从计算机这个角度来看时，我们注重他在机内的表示和实现的可能性与效率。
5.语句
从功能上说语句大体可分执行性语句 和 说明性语句两大类，
说明性语句旨在定义不同数据类型的变量或运算。执行性语句旨在描述程序的动作。
执行性语句又可分赋值语句、控制语句和输入/输出语句.
从形式上说，语句还可分为简单句、复合句和分程序等。
6.一个上下文无关文法G包括四个组成部分：一组终结符号，一组非终结符，一个开始符号，以及一组产生式。
7.产生式（也称为产生规则或简称规则）是定义语法范畴的一种书写规则。
一个产生式的形式是 A→ α ,
其中箭头左边的A是一个非终结符，称为产生式的左部符号；
箭头右边的α是终结符号或与非终结符号组成的一符号串，称为产生式的右部。
8.上下文无关文法Ｇ（ＶＴ，ＶＮ，Ｓ，￡）
形式上定义一个上下文无关文法Ｇ是一个四元式（ＶＴ，ＶＮ，Ｓ，￡）其中
ＶＴ 是一个非空有限集，它的每一个元素 称为终结符号；
ＶＮ 是一个非空有限集，它的每一个元素称为非终结符号，ＶＴ∩ＶＮ＝；
Ｓ 是一个非终结符号，称为开始符号；
￡ 是一个产生式（有限）集合，每个产生式形式是Ｐ→，
其中，Ｐ∈ＶＮ， ∈（ ＶＴ∪ＶＮ）＊开始符号S至少必须在某一产生式的左部出现一次。
9.假定G是一个文法，S是它的开始符号。
如果S*(表示从S出发，经0步或若干步可推出），则称是一个句型。
仅含终结符号的句型是一个句子。
文法G所产生的句子的全体是一个语言，将它记为L(G).
L(G)={|S + & ∈VT }
一个语言的 文法 不是唯一的
10.
为了对句子结构进行确定性分析，我们往往只考虑最左推导或最右推导。
所谓最左推导是指：任何一步
都是对中的最左非终结符进行替换的。
同样，可定义最右推导。
最左推导：任何一步
都是对α中的最左非终结符进行替换。
最右推导：任何一步
都是对α中的最右非终结符进行替换。
11.语法分析树与二义性
可以用一张图表示一个句型的推导，这种表示称为语法分析树，或简称语法树。
语法树的根结由开始符号所标记。
随着推导的展开，当某个非终结符被它的某个候选式所替换时，这个非终结符的相应结就产生了下一代新结。
每个新结和其父亲结间都有一条连线。
在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结自左至右排列起来就是一个句型
12.
如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。
也就是说，若一个文法存在某个句子，它有两个不同的最左（最右)推导，
则这个文法是法是二义的
同一个句子（仅含终结符号的句型） 对应 两棵不同的语法树
定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。
语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。
13.文法分成四种类型：0，1，2，3型
它们都由四部分组成，但对产生式的限制有所不同
0型(短语文法，图灵机)： 产生式形如：
其中：α(VT VN)*且至少含有一个非终结符；
β (VT VN)*
1型(上下文有关文法，线性界限自动机, 非确定的 下推自动机)：
产生式形如：
其中： 仅 S-->ԑ 例外。
2型(上下文无关文法， 非确定下推自动机)：
产生式形如： A
其中：A VN； (VT VN)*。
3型(正规文法，正规式，有限自动机)：
a.右限性正规文法
产生式形如： A B 或 A
其中： VT*；A，BVN
b.左线性正规文法
产生式形如： A B 或 A
其中： VT*；A， BVN
P37
1.编译程序首先是在单词级别上来分析和翻译源程序的。
词法分析的任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，
把作为字符串的源程序 改造成为 单词符号串的中间程序。
因此，词法分析是编译的基础。
执行词法分析的程序称为词法分析器。
2. 输入源程序，输出单词符号。
程序语言的单词符号一般分为五种：
关键字
标识符
常数
运算符
界符
3. 词法分析器输出的单词符号常常表示为二元式： （单词种别，单词符号的属性值）
4.NFA转换成对应的DFA
一、NFA的确定化——子集法基本思想：
将DFA状态间转换关系映射成NFA中状态子集间的转换。
子集法：
(1)状态子集I的 闭包 _CLOSURE(I)：
(a)若q I,则q _CLOSURE(I)
(b)若q I,那么多q出发经过任意条弧而能到达的任何状态q’都属于 _CLOSURE(I)
I的 闭包的作用：主要是消除弧所带来的不确定性。
(2)Ia子集:
(a)由I中的状态出发，经过一条a弧（跳过a弧前的任意条弧）可到达的状态集合称J，则
Ia= _CLOSURE(J)。
通过Ia求出状态子集间的转换关系。
Ia子集的作用：
求出状态子集间的转换关系。
即： Ia 是指从I出发经过一条a弧（前后可以有任意多条弧）而到达的状态的集合。
(3)利用子集构造确定的有穷自动机DFA
即找到DFA的五个部分（如前面的NFA）
NFA=(S’, Σ’,δ’,S0’, F’)
DFA=(S, Σ,δ,s0, F)
字符集：Σ= Σ’
开始状态：
在NFA中：S0’={s}
_CLOSURE(S0)={S，A，B}
将NFA中的开始子集看作是DFA中的开始状态。即
s0= _CLOSURE(S0)
映射关系：
在NFA中： _CLOSURE(S0)输入a得到子集I0a（记为I1）,将I1映射成DFA中的S1
以此类推I1输入a得到子集I1a记为I2映射成DFA中的S2……直到不再产生新的状态为止。这样就可以将DFA中的映射关系求出。S1，S2……即为DFA中所有状态的集合。
终止状态集：
由至少包含一个NFA终止状态的DFA状态组成。
二、DFA的最小化
5.确定有限自动机(DFA)是一个五元式
M= (S, ,δ,s0, F) 其中:
(1)S是一个有限集，它的每个元素称为一个状态。
（2）Σ是一个有穷字母集，它的每个元素称为一个输入字符。
（3） δ是一个从S x 至S的单值部分映射。δ(s,a）=S’。
意味着：当现行状态为s、输入字符为a时，将转换到下一个状态S’。
我们称S’为s的后继状态。
（4）s0S，是唯一的初态。
（5）FS，是一个终态集（可空）
6.一个非确定有限自动机（NFA)是一个五元式
M= (S, Σ,δ,S0, F) 其中:
(1) S 同3.3.2的1
（2）Σ同3.3.2的2
（3）δ是一个从S x Σ*到S的子集的映照，即 δ：S x Σ*→2s
(4) S0S,是一个非空的初态集；
（5）F S，是一个终态集（可空）
7.
1、DFA与NFA的定义:
DFA=(S, Σ,δ,s0, F)
NFA=(S, Σ,δ,S0, F)
两者的区别在于:开始状态与映射关系的不同。
2、有穷自动机DFA的表示方法
状态转换矩阵 状态转换图
3、作用：
识别字符串
P66 第4章 语法分———自上而下分析
1.语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。
一类是自上而下分析法 (自顶向下） a. 递归下降 b.预测分析
另一类为自下而上分析法 （自底向上） a. 算符优先文法 b.规范归约
2.
自上而下分析所遇到的主要困难是
语法的左递归性使分析陷入无限循环；
回溯的不确定性，要求我们将已经完成工作推倒从来，为解决这些问题我们要消除左递归和消除回溯。
3.FOLLOW(B)的构造分为四条:
(1)如果B是文法的开始符号, 则 #属于FOLLOW(B)
(2)对形如: A … Ba…, 则把则 a属于FOLLOW(B)
(3)对形如:A ... BP…的规则(其中P为非终结符),则FIRST(P)中的非元素属于FOLLOW(B);
(4)对形如:A …B,或者A … B且 则FOLLOW(A)中的所有元素也属于FOLLOW(B);
判断某给定文法是否为LL(1)文法其条件为：
（1）文法不含左递归。
（2）对于文法中每个非终结符A的各个产生式的候选首符集两两不相交。
即，若
A 1 | 2 |…| n
则： FIRST(i) FIRST(j) = （i j )
(3) 对文法中每一个非终结符A，若它存在某个候选首符集包含，则
FIRST(A) FLLOW(A)=
一个文法若满足以上条件，则称该文法G为LL(1)文
P83 第5章 语法分析 ———自下而上分析
1. 所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根结。
2. 自下而上分析的关键问题是寻找可归约串。
对“可归约串”概念的不同定义，就形成了不同的自下而上的分析方法。
在算符优先分析法中我们用“最左素短语” 来刻画“可归约串”，
在“规范归约”中， 则用“句柄” 来刻画“可归约串”
3. 令G是一个文法，S是文法的开始符，假定是文法G的一个句型，
如果有：
S*A 且 A +
则称是句型相对于非终结符A的短语。
特别是，如果有
A
则称是句型相对于规则A 的直接短语，
一个句型的最左直接短语成为该句型的句柄。注意：短语的两个条件是：
S*A 且 A +
4.规范归约是关于α的一个最右推导的逆过程。因此规范归约也成最左归约。
在形式语言中， 最右推导常被称为规范推导。
由规范推导所得的句型称为规范举行。
如果文法G是无二义的，那么规范推导（最右推导） 的逆过程必是 规范归约（最左推导）
5.一个文法，如果它的任何产生式的右部都不含量个相继（并列）的非终结符，即不含如下形式的产生式右部：
…QR… 则我们称该文法为算符文法。
在后面的定义中，a、b代表任意终结符；
P、Q、R代表任意非终结符；
‘…’代表有终结符和非终结符组成的任意序列，包括空字。
6. 假定G是一个不含--产生式的算符文法。对于任何一对终结符a、b，我们说：
ab 当且仅当文法G中含有形如P …ab…或P …aQb…的产生式;
a<b 当且仅当G中含有形如P …aR…的产生式， 而R+b… 或R +Qb…;
a>b 当且仅当G中含有形如P …Rb…的产生式， R而R+…a或R +…aQ;
如果一个文法G中的任何终结符对（a, b ）至多只满足下述三关系之一：
a=·b, a<·b, a·>b
则称G是一个算符优先文法。
7.
为了刻画什么是“可归约串”我们将定义算符优先文法的句型的“最左素短语”这个概念。
素短语这样的一个短语，它至少含有一个终结符，并且除它自身外，不再含有更小的素短语
所谓最左素短语，是指处于句型最左边的那个素短语。
8.LR分析是应用最广泛的一类分析方法，它是实用的编译器***能最强的分析器，其特点是：
① 采用最一般的无回溯移进—归约方法；
② 可分析的文法是LL文法的真超集；
③ 能够及时发现错误，快到从左到右扫描输入序列的最大可能；
④ 分析表较复杂，难以手工构造。
9. LR分析与LR文法
LR分析器的核心是 LR分析表和驱动器。
与LL分析表不同的是， LR分析表可以被明显地分为两个部分：
一部分称为 动作表(action)，
另一部分称为 转移表(goto)。
两者都是二维数组，且行下标由称之为状态的整型数统一表示。
动作表以 终结符 作为列下标，
转移表 以非终结符 作为列下标。
若以s表示当前状态，a表示终结符，A表示非终结符，
则action[s, a]指示当前栈顶状态为s 和 输入 终结符为a时 应进行的下一动作；
而goto[s, A]指示在当前栈顶为s 和 非终结符A时的下一状态转移。
goto[s, A] 定义了一个以 文法符号A为 字母表的 DFA
由于确定goto[s, A]的是当前状态与非终结符，
所以转移表与输入序列无关，它只实现对非终结符的状态转移。
与输入终结符有关的仅有动作表。
10.根据当前状态与当前的剩余输入，动作表中有四种动作
（1）移进
（2）规约
（3）接受
（4）报错
11. LR的特点：
首先文法中允许左递归，这是LL分析无法做到的；
其次文法中减号
既可以用于二元运算，又可以用于一元运算，这是算符优先分析不容易做到的。
P136
第六章 属性文法和语法制导翻译
1.属性文法
属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为属性）。
这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列、符号表内容等等。
属性和变量一样，可以进行计算和传递。
2.属性一般分为两类：综合属性和继承属性
综合属性用于“自下而上”传递信息，
继承属性用于“自上而下”传递信息。
属性加工加工的过程 即是 语义处理的过程，
对于文法的每一个产生式都配备了一组属性的计算规则，则称为语义规则。
3.综合属性：
在语法树中，一个结点的综合属性的值由其子结点的属性值确定。
因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。
仅仅使用综合属性的属性文法称S—属性文法。
继承属性：
在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。 用继承属性来表示程序语言结构中的上下文依赖关系很方便。
4.基于属性文法的 语法制导翻译法
从概念上讲，基于属性文法的处理过程通常是这样的：
对单词符号串进行语法分析，构造语法分析树，
然后根据需要遍历语法树，并在语法树的各结点处按语义规则进行计算。
输入串--〉 语法树 --〉依赖图 --〉语义规则计算次序
这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法。
语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其它动作。对输入串的翻译也就是根据语义规则进行计算得出结果。
5.如果一属性文法不存在属性之间的循环依赖关系，那么该文法为良定义的。
为了设计编译程序，我们只处理良定义的属性文法。
P166
第七章 语义分析和中间代码的产生
1.紧接在词法分析和语法分析之后，编译程序要做的工作是进行静态语义检查和翻译。
静态语义检查通常包括：
（1）类型检查。
（2）控制流检查。
（3）一致性检查。
（4）相关名字检查。
2.翻译为中间语言的好处：
1）便于进行与机器无关的代码优化；
2）使编译程序改变目标机更容易；
3）使编译程序的结构 在逻辑上更为简单明确，
以中间语言为界面，编译前端和后端的接口更清晰。
3.中间语言的基本结构：
逆波兰表示（后缀式）
图表示法（DAG 和抽象语法树），
三地址代码（四元式、三元式、间接三元式）
P221
第八章 符 号 表
1.编译过程中编译程序需要不断汇集和反复查证出现在源程序中各种名字的属性和特征等有关信息。
这些信息通常记录在一张或几张符号表中。
符号表的每一项包括两部分：一部分是名字（标识符）；另一部分是此名字的有关信息。
每个名字的有关信息是指种属（如简单变量、数组、过程等）、类型（如整、实、布尔等）。
这些信息将用于语义检查、产生中间代码以及最终生成目标代码等不同阶段。
编译过程中，每当扫描器识别出一个单词后，编译程序就查阅符号表，看它是否已在其中。如果它是一个新名就将它填进表里。它的有关信息将在词法分析和语法-语义分析过程中陆续填入。
几乎在编译程序工作的全过程中，都需要对符号表进行频繁访问，可以认为查表或填表等操作，在编译程序的编译过程中是很大的一笔开销。
因此，合理地组织符号表，并相应地选择好查表和填表的方法，是提高编译序工作效率的重要一环。
2.一张符号表的每一项（或称入口）包含两大栏（或称区段，字域），即名字栏和信息栏。
编译原理 Compiler Principles 文章被收录于专栏
2015 朱素英 编译原理 陈火旺 软件设计师
查看20道真题和解析
投递美团等公司10个岗位
飞鱼科技公司福利 124人发布