编译原理总复习(2)市公开课获奖课件省名师优质课赛课一等奖课件

1题型及分值一、判断题（1′×5=5′）二、填空题（1′×10=10′）三、选择题（2′×5=10′）四、简答题（本题共35分）:其中包含两个名词解释。五、计算题（10′+15′+15′=40′）

编译原理1/342教材各章知识点概览编译程序概论

1文法和语言

2词法分析与有限自动机

3自上而下语法分析方法

4自下而上语法分析方法

5语法制导翻译和语义分析

6符号表

7代码优化

8编译原理2/341、编译程序概论（1）基本概念

翻译程序，编译程序（2）编译过程五个阶段，各阶段任务及其依循规则、描述工具分别是什么？除了这个5个阶段之外，还应该有哪两个主要内容？ 五个逻辑阶段：词法分析、语法分析、语义分析和中间代码产生、代码优化和目标代码生成。除了这五个阶段之外，编译程序每个阶段都包括到表格管理和错误处理这两个主要内容。编译原理3/341、编译程序概论（3）编译错误种类 从编译程序角度来看，源程序中错误主要分为：语法错误和语义错误两类错误。（4）高级程序设计语言翻译两种方式以及它们区分 高级程序设计语言翻译主要有两种方式：编译方式和解释方式。 区分：是否生成目标代码。编译原理4/342、文法和语言（1）基本概念

文法、推导、最左推导、最右推导、句型、句子、语言、文法二义性（2）对文法G，能够给出给定句型或句子最左推导及最右推导序列，并画出其对应语法分析树。（3）能够计算某文法语言。（4）了解文法二义性，能够说明一个文法是二义。

编译原理5/342、文法和语言（5）形式语言分类(chomsky,1956)0型普通（短语）文法1型上下文相关文法2型上下文无关文法3型线性（正规、正则）文法 3型 2型 1型 0型

编译原理6/343、词法分析与有限自动机（1）基本概念

状态等价、DFA化简（2）词法分析器任务及其输出形式

任务：自左至右逐一字符地对源程序进行扫描，按语言构词规则识别出一个个单词，把作为字符串源程序改造为单词符号串中间程序。

输出形式：二元式（单词种别，单词符号属性值）（3）单词符号种类

关键字、标识符、常数、运算符、界符

编译原理7/343、词法分析与有限自动机（4）正规文法、正规式、有限自动机之间相互等价性定理（5）正规式→NFA→DFA→最小化DFA （注意：状态函数定义不完整之情形）（6）状态转换图结构(标识符、整数)

编译原理8/344、自上而下语法分析方法（1）语法分析方法 依据语法分析树建立方向不一样，将语法分析分成两类：自上而下语法分析方法和自下而上语法分析方法。（2）自上而下分析基本思想 穷举试探法（3）自上而下分析面临两个最主要问题

左递归、回溯（4）自上而下分析基本方法

LL（1）分析法、递归下降分析器

编译原理9/344、自上而下语法分析方法（5）左递归（直接、间接）和回溯消除直接左递归消除间接左递归消除排序代入及消除左递归化简编译原理10/344、自上而下语法分析方法（5）左递归（直接、间接）和回溯消除回溯消除：提左公因子编译原理11/344、自上而下语法分析方法（6）LL(1)含义 LL(1)中第一个L表示从左至右扫描输入串，第二个L表示最左推导，1表示分析时每一步只需向前查看一个符号。（7）LL(1)分析器组成部分

输入缓冲区、分析栈、分析表、总控程序（8）LL(1)分析四种动作

成功、匹配、推导、报错编译原理12/344、自上而下语法分析方法（9）LL(1)文法判定条件 ①文法不含左递归。 ②文法中每一个非终止符A各个产生式候选首符集两两不相交。即，若则

③对文法中每个非终止符A，若它存在某个候选首符集包含ε，则假如一个文法G满足以上条件，则称该文法G为LL(1)文法。编译原理13/344、自上而下语法分析方法

（10）LL(1)分析方法 假设要用非终止符A进行匹配，面临输入符号为a，关于A全部产生式为则LL(1)分析算法以下：①若，则指派去执行匹配任务。②若a不属于任何一个候选首符集，则若ε属于某个且，则让A与ε自动匹配；不然，a出现是一个语法错误。依据LL(1)文法条件，每一步这么工作都是确信无疑。编译原理14/344、自上而下语法分析方法

（11）FIRST集和FOLLOW集结构 （12）预测分析表结构

编译原理15/345、自下而上语法分析方法（1）基本概念

短语、直接短语、句柄、素短语、最左素短语、算符文法、算符优先文法、LR（0）项目、活前缀、可归前缀（2）自下而上分析基本思想及其关键

基本思想：移进-归约

关键问题：可归约串界定（3）自下而上分析基本方法算符优先分析法：以最左素短语作为可归约串，非规范归约LR分析法：以句柄作为可归约串，规范归约编译原理16/345、自下而上语法分析方法（4）给定一个文法句型，找出其短语、直接短语、句柄、素短语和最左素短语 方法：首先画出句型语法分析树，然后依据语法树寻找。每棵子树叶子结点自左至右排列组成一个相对于子树根短语。每棵简单子树（只有父子两代）叶子结点自左至右排列组成一个直接短语。最左简单子树叶子结点自左至右排列组成一个句柄。将全部短语中最少含一个终止符短语，按长度从小到大排列，长度最短认定为素短语，然后考查其余长度较大，若不包含更小素短语，则也为素短语。位于句型中最左边素短语即为最左素短语。17/345、自下而上语法分析方法（5）算符文法与算符优先文法

算符文法：任意产生式右部不含两个连续非终止符，（...QR...）

算符优先文法：算符文法中任意两个终止符之间至多只含“>”、“<”、“=”三种关系之一。

算符优先文法一定是算符文法。 算符优先关系是有序，但不满足对称性和传递性，即对于文法G终止符a、b和c：假如a<b，并不意味着b>a；假如存在a=b和b=c，不一定有b=a或a=c；假如存在a<b和b<c，也不能得出a<c。18/345、自下而上语法分析方法（6）FIRSTVT集与LASTVT集计算①FIRSTVT规则一：若有产生式P→a…或P→Qa…，则a∈FIRSTVT(P)；规则二：若a∈FIRSTVT(Q)且有产生式P→Q…，则a∈FIRSTVT(P)；规则三：重复使用以上两条规则，直到FIRSTVT(P)不再增大为止。②LASTVT规则一：若有产生式P→…a或P→…aQ，则a∈LASTVT(P)；规则二：若a∈LASTVT(Q)且有产生式P→…Q，则a∈LASTVT(P)；规则三：重复使用以上两条规则，直到LASTVT(P)不再增大为止。

19/345、自下而上语法分析方法（7）算符优先关系表结构

规则一：对形如P→…ab…或P→…aQb…产生式，有a=b；

规则二：对形如P→…aR…产生式，若有b∈FIRSTVT(R)，则a<b；

规则三：对形如P→…Rb…产生式，若有a∈LASTVT(R)，则a>b；

规则四：对于语句括号#，有#=#，且若a∈FIRSTVT(S)和b∈LASTVT(S)，则有#<a且b>#。

20/345、自下而上语法分析方法（8）优先表与优先函数之间关系 对应一个优先关系表优先函数f和g不唯一，只要存在一对，就存在无穷多对。也有许多优先关系表不存在对应优先函数。（9）算符优先分析算法 ①最左素短语寻找依据：21/345、自下而上语法分析方法（9）算符优先分析算法 ②算符优先分析特点：算符优先分析普通并不等价于规范归约无法使用单非产生式(如：TF)进行归约。算符优先分析比规范归约过程要快，跳过了全部单非产生式。可能将原来不是句子输入串误认为是句子。（10）LR分析器基本思想及其组成部分基本思想：记住历史、展望未来、定夺现在组成部分：输入缓冲区、分析栈（状态、符号）、分析表（动作、转换）、总控程序22/345、自下而上语法分析方法（11）四类LR分析表 LR分析表是LR分析器关键，主要有以下几个分析表：LR(0)表、SLR(1)表（即简单LR表）、LR(1)表（即规范LR表）、LALR表（即向前LR表）。其中，L代表自左至右扫描输入串，R代表构建最右推导逆过程，1代表分析时每一步至多向前查看一个符号，S代表简单。（12）LR分析器四种动作

移进、归约、接收、报错（13）LR分析器两种冲突

移进——归约冲突和归约——归约冲突23/345、自下而上语法分析方法（14）四类不一样项目

项目类型形式说明归约项目A→α•这类项目表示句柄α恰好包含在栈顶中，即当前栈中符号恰好为可归前缀，应按A→α进行归约。接收项目S΄→α•S΄是文法唯一开始符号。这类项目实际是特殊归约项目，即按S΄→α进行归约，可直接归约到文法开始符号，表示分析成功。移进项目A→α•aβa∈VT，这类项目表示当前栈中符号串为不完全包含句柄活前缀，为组成可归前缀，需将a移进分析栈。待约项目A→α•BβB∈VN，这类项目表示当前栈中符号串为不完全包含句柄活前缀，为组成可归前缀，应先把当前输入字符串中对应内容先归约到B。24/345、自下而上语法分析方法（15）四类LR分析表结构 ①拓广文法 ②结构LR(0)（LR(0)和SLR分析表）或LR(1)（LR(1)和LALR分析表）项目集规范簇 ③结构对应分析表（16）LR文法特点LR文法必定是无二义，一个二义文法决不会是LR文法。LR分析法比预测分析法愈加普通化。LR(0)文法一定是SLR文法，SLR文法和LALR文法一定是LR(1)文法。25/346、语法制导翻译和语义分析（1）基本概念

S—属性文法、L—属性文法（2）属性分类

综合属性：用于“自下而上”地传递信息。

继承属性：用于“自上而下”地传递信息。 ①终止符号只有综合属性，由词法分析器提供。 ②非终止符既可有综合属性也可有继承属性，文法开始符号全部继承属性作为属性计算前初始值。（3）语义规则表示

26/346、语法制导翻译和语义分析（4）常见中间代码几个形式 ①后缀式（逆波兰表示式） ②图表示法抽象语法树DAG图 ③三地址代码四元式三元式间接三元式27/346、语法制导翻译和语义分析（5）后缀式（逆波兰式）表示 把运算量（操作数）写在前面，把运算符写在后面（后缀）一个表示式表示方法。其归纳定义以下：假如E是一个变量或常数，则E后缀式是E本身。假如E是E1opE2形式表示式，op是二元操作符，则E后缀式为E1´E2´op，其中E1´，E2´分别是E1和E2后缀式。若E是（E1）形式表示式，则E后缀式就是E1后缀式。28/346、语法制导翻译和语义分析（6）将以下语句翻译为四元式序列表示式（算术及布尔）赋值语句数组IF语句WHILE语句（7）参数传递几个方式

传地址、传值、传名、得结果29/347、符号表（1）符号表主要性 合理地组织符号表并选择好查表、填表方法是提升编译程序工作效率有效方法。（2）符号表基本组成、基本操作

组成：一张符号表每一项入口包含：名字栏和信息栏

操作：查表、填表、访表、更新、删除（3）符号表组织方式 按照处理对象特点，符号表组织方式普通可分为直接方式和间接方式。也按标识符种属分别建立不一样符号表。 30/347、符号表（4）符号表结构和处理方法 符号表主要有三种结构和处理方式：线性表、二叉树、杂凑（哈希）。（5）内情向量基本表项 在编译过程中，碰到数组说明时，通常将数组相关信息统计在一个内情向量表中，