编译原理复习整理
编译原理复习整理
绪论
重点掌握
翻译、解释、编译的区别和联系
编译过程分为哪些步骤
程序设计语言和编译程序
计算机所能执行的每一种操作称为一条指令，计算机能够执行的全部指令集合就是该计算机的指令系统
指令格式：操作码 + 操作地址码
低级语言
机器语言：二进制形式的指令序列，是计算机唯一能直接识别并执行的语言
汇编语言：助记符代替机器语言
高级语言
高级语言程序也必须翻译(编译)成最终能够直接执行的机器语言程序
程序设计语言的转换
翻译
是指将某种语言的源程序，在不改变语义(逻辑上等价)的条件下，转换成另一种语言程序——目标语言程序
编译
专指由高级语言程序一次性转换成低级语言程序，类似于全文翻译
解释
接受某高级语言的一个语句输入，进行解释并控制计算机执行，得到这个语句的执行结果后，等待下一个语句的解释执行，执行过程中并不产生目标程序。类似于口译
编译型高级语言程序的阶段
两个阶段
高级语言程序的执行通常分为两个阶段：编译阶段和运行阶段
编译程序就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序（如C语言下的exe）
三个阶段
高级语言程序的执行分为三个阶段的情况：编译阶段、汇编阶段和运行阶段
编译过程和编译程序结构
高级语言的编译过程
输入：源程序
输出：目标程序
编译五个阶段
词法分析
语法分析
语义分析和中间代码生成
中间代码优化
目标代码生成
词法分析
任务：将源程序的字符串变成单词符号流
词法分析所遵循的是语言的构词规则
语法分析
任务：根据语法规则，从单词符号串中识别出各种语法单位（如表达式、说明、程序段等），并检查语法结构的正确性
语法分析遵循语言的语法规则，通常使用上下文无关文法
语义分析和中间代码生成
任务：
1.对每种语法单位（范畴）进行静态语义审查(验证语法结构合法的程序是否真正有意义)
2.在语义检查正确的情况下进行中间代码的翻译
中间代码是介于高级语言语句和低级语言的指令之间的一种独立于具体硬件的记号系统，既有一定抽象，又与低级语言指令十分接近，因此转换成目标代码比较容易
中间代码的常用表示形式：四元式、三元式、间接三元式和逆波兰记号等
把语法单位翻译成中间代码，遵循语言的语义规则
中间代码优化
任务：是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效(节省时间和空间)的目标代码
优化遵循等价变换规则
手段：删除冗余运算、删除无用赋值、合并已知量、循环优化等
目标代码生成
任务：是把中间代码(或经优化处理之后)变换成特定机器上的机器语言代码或汇编语言代码，实现最终的翻译工作
该阶段的工作依赖硬件及其指令系统
总结
词法分析所遵循的是语言的构词规则
语法分析遵循语言的语法规则，通常使用上下文无关文法
把语法单位翻译成中间代码，遵循语言的语义规则
中间代码优化遵循等价变换规则
编译程序结构
注意：一个编译过程可分为一遍、两遍或多遍完成，每一遍完成所规定的任务
但是多遍会导致编译效率的降低
表格管理和出错处理
编译程序的各个阶段需要构造、查找、更新变量和函数的信息，表格管理耗费了编译过程的绝大部分时间
编译程序的开发
编译程序开发技术
自编译：已有编译程序，用某种高级语言编写更强的编译程序
交叉编译：A机有编译程序，针对B机器，在A机上编写一个编译程序，使得B机器上的源代码可以被编译成目标程序（针对不同机子）
自展
移植
本章小结
掌握编译程序与高级程序设计语言的关系
编译程序就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑上等价的低级语言形式的目标程序
掌握编译分为哪几个阶段
词法分析，语法分析，语义分析和中间代码生成，中间代码优化，目标代码生成
了解各个阶段完成的主要功能
词法分析：将源程序的字符串变成单词符号流
语法分析：根据语法规则，从单词符号串中识别出各种语法单位（如表达式、说明、程序段等），并检查语法结构的正确性
语义分析和中间代码生成：对每种语法单位（范畴）进行静态语义审查(验证语法结构合法的程序是否真正有意义)；在语义检查正确的情况下进行中间代码的翻译
中间代码优化：是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效(节省时间和空间)的目标代码
目标代码生成：是把中间代码(或经优化处理之后)变换成特定机器上的机器语言代码或汇编语言代码，实现最终的翻译工作
词法分析
定位：是编译过程的第一个阶段
任务：从左至右逐个字符地对源程序进行扫描，产生一个个单词（Token）符号；输入源程序，输出单词符号（流）；需要不断访问、更新符号表
重点掌握
状态转换图的概念
正规表达式的概念和运算
有限自动机理论
有限自动机的构造、确定化和化简
词法分析器的设计方法
词法分析器的处理结构（2种）
第一种：词法分析器和语法分析器完全分开
词法分析器的输出（单词符号流）作为语法分析器的输入
第二种：词法分析器作为语法分析器调用的子程序
每当语法分析器需要一个单词时便调用词法分析器
单词符号的分类与输出形式
单词符号分类
分类：单词符号是程序语言的基本语法单位，具有确定的语法意义
基本分为五种：保留字，标识符，常数，运算符，界符
保留字
如C语言中的if、else、while和do等
几乎所有的程序语言都禁止用户使用保留字作为标识符
标识符
用户自己定义的常量名、变量名、方法名等
常数
布尔常数（true/false）和其它常数
运算符
“+”、“- ”、“ * ”、“/ ”、“>”、“<”等
界符
在语言中是作为语法上的分界符号使用的，如“,”、“;”、“(”、“)”、“=”等
单词符号输出形式
单词符号通常表示成如下的二元式：（单词种别，单词自身的值/内码值）
单词种别
单词种别：即单词的种类。为了处理方便，通常让每种单词对应一个整数码，可以最大限度地将每个单词区别开来
保留字：可以统一视为一种，也可一字一种（后一种较常用）
标识符：统一归为一种
常数：可统一归为一种或按照整型、实型、布尔型等分为几种
运算符和界符：可统一归为一种或采用一符一种
单词自身的值
如果一个种别只含一个单词符号，对于这个单词符号，种别编码就完全代表它自身的值——如保留字、运算符、界符
如果一个种别含有多个单词符号，除了给出种别编码之外，还应给出单词符号自身的值，以便区分同一种类的单词——标识符自身的值就是标识符自身的字符串，常数自身的值是常数本身的二进制数值或数值
分类举例
状态转换图
状态转换图概念
在词法分析中，可以用状态转换图来识别单词
状态转换图是状态有限的有向图，结点代表状态，用圆圈表示；结点之间可由有向边连接，代表状态转换关系，有向边上可标记字符，表示前一状态接受某一个字符之后的状态转移
状态转换图表示
状态转换图的要求
状态（即结点）个数有限
至少一个初始状态，若干终止状态
每条边上标有字符（也可以是空字符）
状态转换图表示习惯
特别说明：*表示回退，但是终态也可以不加*，只需要用两个圈即可表示
有时候起始状态的箭头会省略
状态转换图编程实现
一个简单的词法分析器
引入助记符：使用种别编码不利于记忆，故使用助记符和种别编码对应
首先对输入程序串预处理：即剔除多余的空白符(在实际的词法分析中，预处理还包括剔除注释和制表换行符等编辑性字符的工作)，使词法分析工作既简单又清晰
将保留字作为一类特殊的标识符来处理：即对保留字不专设对应的状态转换图，当转换图识别出一个标识符时就去查对表2.1的前五项，确定它是否为一个保留字。当然，也可以专设一个保留字表来进行处理
注意终止状态时星号*的有无：如果有*就回退（*表示读入了一个不需要的字符），无*表示读到就终止，通常是一个确定的符号
状态转换图的实现：让每个状态对应一小段程序
正规表达式与有限自动机
正规表达式与正规集
定义和运算
状态转换图可以构造词法分析程序，但属于非形式化描述
正规表达式（简称正规式）是词法分析的形式化表示方法
所谓形式化的方法，是指用一整套带有严格规定的符号体系来描述问题的方法，优点：更加清晰和准确
*代表0次或多次，+代表1次或多次，?表示0次或1次
正规集：正规式能表示出来的所有单词的集合
相关基础概念
字母表：语言元素的非空有穷集合，通常用"\(\Sigma\)"表示
符号：字母表中的每一个元素，也叫字符（空字\(\varepsilon\)不是字符）
符号串：由符号组成的有穷序列（可以是0个），也叫字
空字：长度为0的字，用“\(\varepsilon\)”表示
字的全体：所有字组成的集合，用“\(\Sigma^*\)”表示（即空字和字母表中任意元素排列组合的全集）
空语言：不含任何字的语言{ }，用"\(\Phi\)"表示
区分\(\varepsilon\)(空字)、{ }（空语言，\(\Phi\)，不包括任何字，长度为0的字也不包括）、{\(\varepsilon\)}(只有一个空字的集合):
\(\varepsilon是\)\(\Sigma^*\)的元素
递归定义
对于给定的字母表\(\Sigma\)，正规式和正规集定义为:
一个正规式，他对应的正规集就直接加一对花括号 { }
这两条规则称为基础规则，第二条：从普通的符号产生对应的正规式和正规集
第三条规则称为归纳规则，根据已有的正规式和正规集生成其它正规式和正规集
第四条规则称为界限规则或者终止规则，根据已有的正规式和正规集生成其它正规式和正规集
注意：在后面的正规式中，约定：不做特殊说明情况下，大写字母（如R、S等）对应字的集合（正规集）
正规式的运算
连接运算
闭包运算
正规式运算性质
例题
有限自动机（FA）
有限自动机：可以自动识别单词的机器
有限自动机（Finite Automation）：
FA是一个状态转换图，“有限”指的是状态有限。当前状态读入一个字符后，和后继状态的转换有以下三种情形：
(1)后继状态为自身
(2)后继状态只有一个
(3)后继状态有多个
如果每次转换的后继状态是唯一的，则称它为确定有限自动机（Deterministic FA）
如果每次转换的后继状态不是唯一的，则称它为非确定有限自动机（Nondeterministic FA）
确定有限自动机（DFA）
五元组\(M_d=(S,\Sigma,f,s_0,Z)\)
S：有限状态集合，每个元素为一个状态
\(\Sigma\)：有穷字母表，每个元素为一个输入字符
f：状态转移函数
\(s_0\)：\(s_0\in S\)是唯一初态
Z：终态集
状态转换图和状态转换矩阵
非确定有限自动机（NFA）
五元组\(M_d=(S,\Sigma,f,Q,Z)\)
S：有限状态集合，每个元素为一个状态
\(\Sigma\)：有穷字母表，每个元素为一个输入字符
f：状态转移函数（多值映射）
\(Q\)：\(Q\subset S\)，是非空初态集（可以有若干初态）
\(Z\)：\(Z\subset S\)，终态集
NFA相比于DFA
NFA允许接收字（字的长度为0时为\(\varepsilon\)）
状态转换图和状态转换矩阵
只是针对这个例子来说，接收的只有长度为1的字，但是NFA也可以接收其他长度的字
NFA后继状态不唯一，所以需要加{}表示为一个集合
状态转换到\(\Phi\)时不用画
FA识别的语言
把箭头上的字符连接起来构成字符串a，即为所识别的字
所识别的字集为FA识别的语言
FA等价
等价就看识别的语言L(M)是否相等
对于任意一个NFA：M，一定存在一个DFA：M’与其等价
例DFA与NFA
正规表达式构造有限自动机
正规式到DFA过程：正规式构造NFA，NFA构造等价DFA，DFA化简
正规式构造等价NFA
注意闭包的画法：接收空字\(\varepsilon\)到中间状态\(s_k\)，再接受闭包的字符，再接受空字\(\varepsilon\)到\(s_j\)
例题
先把正闭包+变成本身和闭包的连接，再画NFA
NFA确定化（构造等价DFA）
NFA的确定化：构造一个和NFA等价的DFA
相关概念
引入概念：状态集合\(I\)的\(\varepsilon\)闭包，\(I_a\)的\(\varepsilon\)闭包
\(I\)本身的元素属于\(I\)的\(\varepsilon\)闭包，\(I\)中元素经过任意条\(\varepsilon\)通路后到达的状态也属于\(I\)的\(\varepsilon\)闭包
\(I_a\)定义为\(J\)的\(\varepsilon\)闭包，\(J\)为从\(I\)出发经过一条有向边a所能到达的状态集合
例题
若I为{1}，找\(\varepsilon\)闭包：
I的元素属于\(\varepsilon\)闭包，则1属于\(\varepsilon\)闭包
1状态经过1条\(\varepsilon\)通路到达2，则2属于\(\varepsilon\)闭包，没有更多的\(\varepsilon\)通路
故若I为{1}，\(\varepsilon\)闭包为{1,2}
若I为{5}，找\(\varepsilon\)闭包：
I的元素属于\(\varepsilon\)闭包，则5属于\(\varepsilon\)闭包
5状态经过1条\(\varepsilon\)通路到达状态6，则6属于\(\varepsilon\)闭包；5经过2条\(\varepsilon\)通路到达2，则2属于\(\varepsilon\)闭包
故若I为{5}，\(\varepsilon\)闭包为{5,6,2}
求\(I_a\)先求\(J\)，再求\(J\)的\(\varepsilon\)闭包
子集法
每次算的新\(I_a\)，要是没出现过就拉到下面，直到没有重复出现为止
例题
DFA化简
化简概念
状态等价：
DFA化简：
化简方法
划分原则
例题
先把集合分成两个集合：一个终态集，一个非终态集
看接收同一字符后状态转移到哪个集合
3,4,5,6四个状态，接收a以后都在2集合中，接收b以后也都在2集合中，所以3,4,5,6合成一个状态，即不划分
0，1，2三个状态都不等价，需要划分
最后结果如图
总结
求正规式对应的DFA
先写出NFA
再求NFA等价的DFA
最后化简DFA
本章小结
词法分析器设计与实现
正规表达式与有限自动机
正规表达式到有限自动机
语法分析
重点掌握
文法的表示
短语、直接短语、素短语、句柄的概念
二义性的消除
消除左递归
消除回溯
构建递归下降子程序
LL(1)分析器工作原理
LL(1)分析表的构造
FIRST集合，FOLLOW集合
算符优先关系表的构造
FirstVT集合
LastVT集合
LR分析表的构造
语法分析
定位
语法分析是编译过程的第二个阶段，也是核心部分
任务
根据语言的语法规则对单词序列进行语法分析，识别合法的语法单位（如表达式、语句、程序段等），若不存在语法错误则给出正确的语法结构（语法树）
理论依据：上下文无关文法
方法
自顶向下分析（推导：开始符号 → 句子）
自底向上分析（规约：句子 → 开始符号）
文法和语言
文法和语言的基本概念
文法(Grammar)是程序语言的生成系统，用文法可以精确定义一个语言，并依据该文法构造出识别这个语言的自动机
给一门文法就可以确定一个语言
语言
字的集合都叫语言
举例
L就是\(\Sigma^*\)的子集
L里的元素是句子
文法
文法（Grammar）定义
四元组\(G[S]=(V_T,V_N,S,\xi)\)
\(V_T\)：terminate，终结符集
\(V_N\)：非终结符集
\(V_T,V_N\)都是非空集
文法中的基本概念
终结符（字母表上的字符）：是指语言不可再分的基本符号，通常是一个语言的字母表；终结符代表了语法的最小元素，是一种个体记号
非终结符（代表一个类）：也称语法变量，它代表语法实体或语法范畴；非终结符代表一个特定的语法概念，因此，一个非终结符是一个类、一个集合
文法开始符号S：是一个特殊的非终结符，它代表文法所定义的语言中我们最终感兴趣的语法实体，即语言的目标，而其它语法实体只是构造语言目标的中间变量
产生式（也称产生规则或规则）：是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个
\(\xi\)：产生式的非空有限集
例子
关于文法的约定
大写字母表示非终结符
小写字母表示终结符
例题
（1）
（2）
文法产生的语言
推导
单横线箭头出现在规则里面（题干里）
双横线箭头出现在推导过程中（答题中）
广义推导：0步或若干步
直接推导：一步
举例
每次只能替换一个非终结符
句型与句子
S经过0步或若干步推导出来的字符串，叫做文法的句型
仅含有终结符的句型是句子（就是字）
文法产生的语言
给定一门文法，可以唯一确定一个语言
给定一个语言，文法可以有若干个
比如加法和乘法的表达式，\(a+b*c\)，可以由几种文法推导出来
概念总结
语言：对字母表\(\Sigma\)来说，\(\Sigma^*\)的任意子集就是\(\Sigma\)上的语言
文法：四元组\(G[S]=(V_T,V_N,S,\xi)\)
终结符（字母表上的字符）：是指语言不可再分的基本符号，通常是一个语言的字母表；终结符代表了语法的最小元素，是一种个体记号
非终结符（代表一个类）：也称语法变量，它代表语法实体或语法范畴；非终结符代表一个特定的语法概念，因此，一个非终结符是一个类、一个集合
文法开始符号S：是一个特殊的非终结符，它代表文法所定义的语言中我们最终感兴趣的语法实体，即语言的目标，而其它语法实体只是构造语言目标的中间变量
产生式(也称产生规则或规则)：是定义语法实体的一种书写规则。一个语法实体的相关规则可能不止一个
\(\xi\)：产生式的非空有限集
推导：广义推导和直接推导
句型：S经过0步或若干步推导（广义推导）出来的字符串，叫做文法的句型
句子：仅含有终结符的句型是句子（就是字）
文法产生的语言：给定文法产生的所有句子的集合
形式语言分类（4类）
0型文法与0型语言(对应图灵机)
只有非终结符才能产生其他字符
1型文法与1型语言(对应线性界限自动机，自然语言)
产生式左端长度≤产生式右端长度
上下文有关语言，处理自然语言
2型文法与2型语言(对应下推自动机，程序设计语言)
2型文法是单非产生式（产生式左端仅有一个非终结符）
2型文法不一定是1型文法，因为a可能为空，1型文法的要求是产生式左端长度≤右端
上下文无关语言
3型文法与3型语言(对应有限自动机)
3型文法一定是2型文法：单非产生式
3型文法不一定是1型文法：a可能为空
四类文法总结
不管是1,2,3文法，都是0型文法（产生式左端至少有一个非终结符）
2型文法不一定是1型文法，因为a可能为空
3型文法一定是2型文法：单非产生式
3型文法不一定是1型文法：a可能为空
从0型文法到3型文法的限制逐渐增
1型文法不允许\(A\rightarrow \varepsilon\)的产生式存在
1型文法：上下文有关
2型文法：上下文无关
3型文法：处理线性
正规表达式与上下文无关文法
正规表达式所描述的语言结构均可用上下文无关文法描述，反之则不一定
例题
推导与语法树
推导与短语
规范推导
最右推导（规范推导）：每次都对最右边的非终结符替换
最左推导：每次都对最左边的非终结符替换
推导过程不能跳步，每次只能用给定产生式推导
规范推导的逆过程叫规范规约
短语
在推导过程中，用谁替换了一个非终结符，谁就是对应句型的一个短语
脱离了句型谈短语没意义，短语必须是某个句型的短语，且短语是这个句型的一部分
如示例，\(\beta\)是句型\(\alpha \beta \delta\)的一个短语，则\(\beta\)是\(\alpha \beta \delta\)的一部分
句柄
句柄就是最左直接短语
素短语
从最短的短语开始找素短语
例题
尽管没有A→ba这样的一步，但是A经过若干步一定能推出ba，所以ba也是短语，但不是直接短语
直接短语：Sb, a
句柄：最左直接短语，a在Sb左边，为句柄
语法树与二义性
语法树
语法树生长的任意时刻，叶子节点从左到右排列就是一个句型
子树与短语
找短语：以非终结符为根的子树，所有叶子节点连起来就是短语
如：S为根，baSb就是短语，替换了S；A为根，ba就是短语，替换了A；B为根，Sb就是短语；B为根，a就是短语
baSb，ba，Sb，a都是针对句型baSb的短语（即以根节点为根的短语baSb的短语）
找直接短语：看简单子树，即只有一层分枝
找句柄就是找最左直接短语
找素短语从语法树不好看，就按之前找的方法：从最短的短语开始找，只要有终结符就是素短语
例题
文法的二义性
对如图所示文法：
句子i+i*i存在两种最左推导，对应两棵不同语法树
因为加法和乘法的优先级没定义，所以会出现这种情况
可以人为定义优先级
二义性：
二义性的消除
自顶向下语法分析
自顶向下分析
不确定的自顶向下分析
确定的自顶向下分析（递归下降、LL(1））
递归下降分析法
不确定的自顶向下
这种自顶向下的分析是一个不断试探的过程；即，在分析过程中，如果出现多个产生式(即候选式)可供选择，则逐一试探每一候选式进行匹配，每当一次试探失败，就选取下一候选式再进行试探
此时，必须回溯到这一次试探的初始现场，包括注销已生长的子树及将匹配指针调回到失败前的状态
这种带回溯的自顶向下分析方法实际上是一种穷举的试探方法，其分析效率极低，在实用的编译程序中很少使用
确定的自顶向下
满足条件
文法不含左递归
无回溯
回溯：候选式里有公共左因子
无回溯：有多个候选式时，首部两两不相交
把不确定的变成确定的：消除左递归，消除回溯
消除左递归
正常消除左递归
当候选式中有多个左递归
消除间接左递归
带入即可得到直接左递归，再改为右递归
例题
消除回溯
递归下降分析器
递归下降分析法：是确定的自上而下分析法。它的基本思想是，对文法中的每个非终结符编写一个函数（或子程序），每个函数的功能是识别由该非终结符所表示的语法成分
也称递归子程序法或递归下降分析法
递归下降分析程序即为递归下降分析器，对文法的要求：不含左递归，不含回溯
递归下降分析器思想：对文法中的每个非终结符编写一个函数（或子程序），每个函数的功能是识别由该非终结符所表示的语法成分
先人为加一个#在栈里
字符串是从左向右扫描的，因此左边的一定在栈上面
所以是从右向左的顺序入栈
如图，E→TE'时，应该先扫描到T，再扫描到E'
E先出栈，再将表达式右边从右向左的顺序依次入栈
所以栈里T在E'上面，即E'先入栈，T后入栈
LL(1)分析法
LL(1)分析法又称预测分析法，是一种不带回溯的非递归自顶向下分析法
LL(1)的含义是：第一个L表明自顶向下分析是从左至右扫描输入串的；第二个L表明分析过程中将用最左推导；“1”表明只需向右查看一个符号就可决定如何推导(即可知用哪个产生式进行推导)
表驱动的LL(1)分析器
基本思想
一个LL(1)分析器由一张LL(1)分析表（也称预测分析表）、一个先进后出的分析栈和一个控制程序（表驱动程序）组成
(1)输入串是待分析的符号串，它以界符“#”作为结束标志
(注：\(\#\in V_T\)但不是文法符号，是由分析程序自动添加的。)
(2)分析栈中存放分析过程中的文法符号。分析开始时栈底先放入一个“#”，然后再压入文法的开始符号；当分析栈中仅剩“#”，输入串指针也指向串尾的“#”时，分析成功
(3)分析表用一个矩阵(或二维数组)M表示，它概括了相应文法的全部信息
(4)控制程序逻辑：
控制程序描述：
LL(1)分析表构造
除了分析表因文法的不同而异之外，分析栈、控制程序都是相同的
因此，构造一个文法的表驱动LL(1)分析器的关键就是构造该文法的分析表
为了构造分析表M，需要预先定义和构造两族与文法有关的集合FIRST和FOLLOW
FIRST集
FIRST(α)是可从α推导得到的所有字的首字符集合(包括\(\varepsilon\)，仅当α能推出空才加入)
比如："abc"的FIRST集是{a}，"a"的FIRST集是{a}（终结符和句子的FIRST集就是第一个位置的终结符）
FIRST集构造方法
注意：X→Y时，Y的FIRST集的非空元素加入X的FIRST集
比如X→Yb，Y推出空，则b才是X推导出的第一个终结符
例题
用T'产生空的条件：看T'后面紧跟的终结符是谁
FOLLOW集
用T'产生空的条件：看T'后面紧跟的终结符是谁
FOLLOW集：在面对哪些字符时，用产生空进行推导不会出错，即FOLLOW集用于放产生空的式子
紧紧跟在A后面的终结符集
FOLLOW集构造方法
对文法开始符号，将#加入FOLLOW集
FOLLOW集中无空
先把#加入文法开始符号的FOLLOW集
两种情况：
Bβ在产生式右边，就将β的FIRST集加入B的FOLLOW集
A→Bβ且β能产生空\(\varepsilon\)，则将A的FOLLOW集加入B的FOLLOW集（\(Aa\Rightarrow B\beta a \Rightarrow Ba\)）
例题
FIRST集和FOLLOW集理解
构造分析表M
产生空的式子只放在FOLLOW集
如果没有产生空的式子，FOLLOW集就没用
表中空白地方为出错
注意
LL(1)文法是无左递归无回溯的
例题
（1）
（2）
自底向上语法分析
自底向上分析原理
所谓自底向上分析，就是自左至右扫描输入串，自底向上进行分析
通过反复查找当前句型的句柄(最左直接短语)，并使用产生式规则将找到的句柄归约为相应的非终结符
这样逐步进行“归约”，直到规约至文法的开始符号
或者说，从语法树的末端开始，步步向上“归约”，直到根结点
若能规约为文法的开始符号，则表示分析成功，说明输入符号串是文法的合法句子，否则有语法错误
移进-规约
移进：读入一个单词，压入分析栈，读头右移
规约：检查栈顶能否构成句柄，一旦形成某个句型的句柄，用产生式左部的非终结符替换句柄
关键问题：如何选择合适的句柄（可规约串）进行规约
规范句型：规范推导（最右推导）得来的句型
对于规范句型（规范推导所得）来说，句柄的后面不会出现非终结符（也即句柄的后面只能出现终结符）
算符优先分析方法
算符优先分析法是一种简单直观的自底向上分析方法，特别适合于分析程序语言中的各类表达式
算符优先分析并不是规范规约。在规约过程中起决定作用的是相继两个终结符的优先关系
算符优先文法规约的是最左素短语
算符优先文法
算符文法：不存在两个相邻的非终结符
算符优先文法：首先得是一个算符文法，其次不能含有空产生式，对于文法中两个相邻的终结符，他们之间的关系至多只有三种中的一种
三种关系指的是规约的先后
注：\(a\gtrdot b\)不能推出\(b \lessdot a\)
a和b有个出现的先后顺序，先出现的在左边
结合语法树
出现顺序：c,a,b,d
规约顺序:\(c \lessdot a , a \dot{=} b, b\gtrdot d\)
例题
相邻两个终结符直接最多只能有一种关系，所以不是算符优先
算符优先关系表的构造
相关概念
FIRSTVT(P)
P推导出来的第一个终结符
FIRSTVT比FIRST集大
构造FIRSTVT(P)：
FIRSTVT和FIRST集：
FIRST集用于LL(1)
FIRSTVT用于算符优先文法
LASTVT(P)
P推导出来的最后一个终结符
构造LASTVT：
如Q→ad，则P→...Q→...ad，则d属于P的LASTVT
LASTVT和FOLLOW集：啥关系都没有
算符优先关系表构造方法
注意相等的情况
只要同一级就是等，两个井号也是等
例
算符优先分析法
算符优先分析不是规范规约分析
算符优先不用“句柄”刻画可规约串，用“最左素短语”刻画可规约串
可以用算符优先分析素短语
尖括号括起来的终结符所形成的字符串就是素短语
可以依此找到最左素短语
算符优先只关心相邻的两个终结符，只要知道终结符之间的关系，就可以开始规约
算符优先分析是规约“最左素短语”
算符优先分析总结
每次规约当前句型的最左素短语(语法树）
规约的不都是真句柄（仅i规约为F是句柄，但它不是最左短语）
没有完全按规则进行规约
也就是说可以把不是该文法产生的句型规约成功
终结符数目太多，算符优先关系表会占用大量空间
课后习题
短语：(SdSdS)，SdSdS，SdS，S
直接短语：S
句柄：S
素短语：SdS
最左素短语：SdS
(adb)的语法树：
从这里就能看出，把不是该文法产生的句型规约成功，即SdS规约成A，但并没有A→SdS这样的产生式
规范规约的自底向上语法分析
LR分析的原理
多了个状态栈
总控程序
查表，得知应该移进还是规约
表用例
S后数字代表状态，R后数字代表产生式的序号
举例前两行：
S代表移进，如S5代表当前指针指向的字符移进符号栈，状态栈移进5
R代表规约，如R6代表用6号产生式进行规约，i出栈，F入栈，然后查goto表，当前状态栈栈顶0，当前符号栈栈顶F，则3号状态入状态栈
LR文法
每个入口都是唯一确定的，是无二义性的文法
但可以用于左递归和回溯的文法
基本上所有编程语言都可以用LR文法分析
优缺点：
对文法限制少，适用范围广
表的构建麻烦
手动完成工作量大
LR(0)
引入概念
字的前缀：一个字的任意首部
规范句型的活前缀：规范推导所得到的句型，不含有句柄之后的任意首部符号串
蓝色标记的就是句柄
项目：产生式右部任意位置打点
移进项目，待约项目，规约项目
点的位置可以理解为指针位置
B不能直接移进，非终结符必须通过规约得来
把项目看做一个状态
项目集：多个项目的集合
项目集I的CLOSURE(I)：
点后面跟非终结符为待约项目，对应的非终结符产生点XX也属于闭包
LR(0)分析表构造
（1）拓广文法
把有多项候选式的分开写
再写一个S'→S
就完成了
（2）写出G'[S']所有产生式的项目
初态项目和接受项目（DFA）
（3）根据闭包画DFA
只需要构建出\(I_0\)，剩下的直接写
（4）根据DFA构造分析表
S后数字代表状态，R后数字代表产生式的序号
对移进项目：
如图DFA，\(I_0\)接收a变成\(I_3\)，就在0行，a列，写上S3
即接收终结符的状态转移，在对应状态行，终结符列，写上S转移状态
对规约项目：
如\(I_5\)里含有规约项目，就在第5行，所有终结符列，写上R1（对应规约式为1）
待约项目中特殊的：接受项目，即终止状态，如\(I_1\)，就在1行#列写上acc
对待约项目：
如\(I_0\)接收S变成\(I_1\)，就在第0行第S列写上1
剩下空白为报错
LR(0)的问题
会造成多重入口
原因就是规约方式有问题，所有终结符列都写了R
移进-规约冲突
规约-规约冲突
SLR(1)
Simple LR(1)
与LR(0)不同的就在规约
规约成某个非终结符，这个非终结符的FOLLOW集里才写规约
所以需要计算每一个非终结符的FOLLOW集
例子
能解决多余动作和一部分规约-规约冲突和移进-规约冲突
如果在SLR(1)所有项目集中不存在冲突，则该文法是SLR(1)文法
即SLR(1)仍可能出现冲突
LR(1)
只在FOLLOW集里规约还是有些大
例如：
A的FOLLOW集是{d,c}
规约aed和aec就有差别
即只有当指针指向a时，才能用A→α规约
a：项前搜索符，仅对规约项目才有意义
LR(K)：将项目扩充，每一个都有项前搜索符
LR(1)分析表构造
跟LR(0)步骤差不多，但要多求项前搜索符
状态转移时，项前搜索符不变，直接继承
初态项目的项前搜索符是#
项前搜索符只有在算闭包时才进行更新
更新原则：如果有待约项目，如\(A\rightarrow\alpha \cdot B\beta（\beta为紧跟B的字符串）,a\)，则\(B\rightarrow\cdot XXX,b\)也在闭包中，b是（\(\beta a\)）的FIRST集
移进项目与LR(0)一致
规约项目：指针指向项前搜索符时才进行规约，即第项前搜索符列写规约
待约项目与LR(0)一致
例题
构造LR(1)
注：相同产生式可能有不同项前搜索符，这就算两种状态，如\(I_3,I_6\)，这两个叫同心项目
再注意\(I_2\)的项前搜索符，\(B\cdot B,\#\)里B后面紧跟的是空，所以是空#的FIRST集，即为#，注意打点的非终结符后面紧跟的是什么，建议拿笔画一下
LALR(1)
同心项目：除去项前搜索符，其他完全一样
LALR(1)：在LR(1)基础上合并同心项目
可能会产生规约规约冲突，不会产生移进规约冲突
对比
LR(0)：在所有终结符列都写规约
SLR(1)：只在FOLLOW集列写规约（需要算FOLLOW集）
LR(1)：只在项前搜索符列写规约（需要算FIRST集）
LALR(1)：在LR(1)基础上合并了同心项目
分析能力：
LR(0)<SLR(1)<LALR(1)<LR(1)
总结
LR是一种自底向上的规范规约分析法
对文法的限制比其它分析方法要少的多：
递归下降法、LL(1)分析法：要求无左递归，无回溯
算符优先分析法：要求是算符文法
LR分析器的结构：
分析栈（状态栈+符号栈）、LR分析表
四种LR分析表的构造方法
LR(0)：规约\(A\rightarrow α\) 时，不考虑面临的终结符
SLR(1)：规约\(A\rightarrow α\) 时，面临的终结符\(a\in Follow(A)\)，即在FOLLOW集列写规约
LR(1)：面临终结符a满足: \(\delta Aa\)是规范句型活前缀(\(\delta\):栈中符号)，即在项前搜索符列写规约
LALR：考察LR(1)表中有无同心项目集
课堂练习
语义分析和中间代码生成
重点掌握
语法制导翻译思想
逆波兰表示法
三地址代码（四元式、三元式）
算数表达式语义子程序
布尔表达式真假出口
翻译图得到布尔表达式四元式
代码结构图翻译if，while语句
语义分析概述
语义分析的内容
语义分析分为两部分：
静态语义审查，生成目标代码或中间代码
如何实现语义分析
语义分析的描述工具：属性文法（语法分析的基础上加些属性）
语义分析的实现方式：语法制导翻译（语法分析的同时，进行语义分析）
属性文法是语法制导翻译的基础
语法制导翻译方法
语法制导翻译的方法就是为每个产生式配上一个翻译子程序(称语义动作或语义子程序)，并在语法分析的同时执行这些子程序
语义子程序的作用：描述一个产生式所对应的翻译工作
扩充LR分析栈：多了一个语义值栈，跟状态栈和符号栈同步变化
属性文法
文法的属性
属性是指与文法符号的类型和值等有关的一些信息，在编译中用属性描述处理对象的特征
对于一棵等待翻译的语法树，它的各个结点都是文法中的一个符号：X，该X可以是终结符或非终结符
文法符号的属性有三种：类型，存储位置，值
文法符号的属性按照语法分析方向（推导还是规约）分为两种：继承属性和综合属性
继承属性：自顶向下
综合属性：自底向上
属性文法
属性有助于更详细地指定文法中的代码生成动作
几种常见的中间语言
抽象语法树
把操作对象当做叶子结点，操作符当做内部节点
表达式的逆波兰式表示法
程序语句的逆波兰式
宏定义
BL: break line，只针对go to语句
BT: break true
BF: break false
BR: break
顺序号：第几个单词，不是行号
条件语句例题
if判假，如果判真，那就没机会执行else了
BL只针对go to语句，用行号
BT, BF用于条件判断，用顺序号（单词号）
其他都是BR，用单词号
三地址代码
四元式
常用三地址与四元式
第二个参数没有就不写
等号左边的在result位，即最后一个位置
四元式约定俗成：
三元式
计算结果存在编号里
间接三元式
给执行顺序表
表达式及赋值语句的翻译
简单算数表达式
简单变量：普通变量和常数，不包括数组、结构体成员等复合型数据结构
简单算术表达式：仅含简单变量的算术表达式
简单算术表达式与四元式
简单算术表达式的计值顺序与四元式出现的顺序相同，因此很容易将其翻译成四元式形式
布尔表达式的翻译
真出口
真出口：表达式为真时，代码往哪走
假出口
假出口：表达式为假时，代码往哪走
例题
注意四元式的写法
真：(jnz,a,_,T)
假：(j,_,_,F)
重点内容
单独的一个变量
真：(jnz,a,_,T)
假：(j,_,_,F)
有运算符的
真：(jrop,x,y,T)
假：(j,_,_,F)
例题
注意：
逻辑运算符优先级：非>与>或
运算符优先级：算术>关系>布尔>=
先画翻译图
再把每个布尔分量对的表达式写出来
（1）
（2）
控制语句的翻译
条件语句if-else
else处强制跳转，为了跳过S2
多重else，不能直接跳到最后，需要一步一步跳
仅有else多产生跳转，但一个if不多产生
例题
循环语句while
在while代码块的最后有一个强制跳转
例题
for语句
例题
符号表管理
符号表
对符号表的操作占据了编译过程的大部分时间
代码优化
局部优化：合并常量和已知量，删除无用赋值，删除冗余运算
循环优化：不变代码外提，强度削弱，删除归纳变量
参考资料
课程PPT
上课录播（陈欢是这学期唯一真神）