《[理学]《编译原理》复习》由会员分享，可在线阅读，更多相关《[理学]《编译原理》复习（47页珍藏版）》请在金锄头文库上搜索。
1、编译原理复习,延安大学计算机学院 郝继升,2,课程内容,要求（希望） 牢固掌握基本概念 灵活使用基本方法 归纳总结所学内容（锻炼提高抽象能力）,一、引言 二、词法分析 三、语法分析 四、语义分析语法制导翻译生成中间代码,学习不能走捷径，付出多少劳动就有多少收获。 掌握正确的学习方法，学会联想与归纳总结。,3,第一章 引言, 语言的翻译,不同的翻译形式：汇编、编译、转换（预编译）、逆向翻译 翻译方法：,4, 编译器的基本组成,5, 编译器的分析综合模式, 编译器的扫描遍数与编译器的编写,6,第二章 词法分析,构词规则与词法分析： 首先规定单词形成的规则，称为构词规则；然后根据构词规则识别输入序列
2、，称为词法分析。,主要内容： 记号、模式与单词 记号的说明模式的形式化描述（正规式与正规集） 记号的识别有限自动机 从正规式到词法分析器,词法分析器的作用： 滤掉源程序中的无用成分； 处理与具体操作系统或机器有关的输入； 识别记号并交给语法分析器； 调用符号表管理器和出错处理器进行相关处理。,7, 记号、模式与单词,模式（pattern）：规定单词识别的规则 记号（token）：按照某模式识别出的一类单词（记号种类） 单词（lexeme）：被识别出的字符串本身 词法分析器的输出：记号=记号种类+记号属性, 记号的说明模式的形式化描述,正规式与正规集： 正规式与正规集的定义(基本正规式、三个运算
3、) 正规式的等价(描述相同的集合) 利用正规式的等价对正规式进行化简(正规式的代数性质) 用正规式形式化描述模式： 如何用正规式描述程序设计语言中常见的记号，如标识符、数字、运算符和分隔符等 正规式的简化形式以及辅助定义与规则,8, 记号的识别有限自动机（FA）,NFA与DFA的定义：FA = (S, , move, s0, F)； NFA与DFA的表示：定义表示、状态转换图、状态转换矩阵； NFA与DFA的关键区别：NFA的不确定性（当前状态下，对同一字符可能有多于一个的下一状态转移）； 用NFA识别输入序列的弱点：尝试所有路径才能确定一个输入不被接收、回溯带来的问题； 模拟DFA的算法：用
4、DFA识别记号。, 从正规式到词法分析器,构造NFA的Thompson算法(与NFA定义的对应关系)； 模拟NFA的“并行”算法； 从NFA构造DFA子集法： smove(S, a)与-闭包(T)的计算； DFA的最小化可区分的概念：所有不可区分的状态看作是一个状态； 灵活运用各种方法构造DFA(正规式化简、状态转换图等)，特别是手工构造和算法构造的区别。,10,第三章 语法分析,语法分析是编译器中的重要阶段之一，可以认为是语法制导翻译模式编译器的核心。语法分析也有双重含义：根据一定的规则构成语言的各种结构，即语法规则；根据语法规则识别输入序列（记号流）中的语言结构，即语法分析。,语法分析的分
5、析对象是组成语言的句子，句子具有层次结构的特征，表征该结构的最好方法是树，从而使得对语法的分析就有了从根到叶子和从叶子到根两种分析方法。,主要内容 程序设计语言与文法 有关推导的基本概念 自上而下分析 自下而上分析,11, 程序设计语言与文法,正规式与正规文法：正规式与正规文法用于描述线性结构，如构成句子的记号(终结符)；识别正规语言的自动机是有限自动机，它们的特征是没有记忆能力； 上下文无关文法(CFG=(N, T, S, P)：CFG用于描述层次结构，如构成程序的句子；识别CFL的自动机是下推自动机，它是在有限自动机的基础上增加了一个下推栈，从而有了简单的记忆能力；,文法的分类：0型、1型
6、、2型和3型文法 词法分析器与语法分析器：FA与PDA,12, 有关推导的基本概念,CFG产生语言的基本方法推导：从文法的开始符号开始，反复地用产生式的右部替换句型中的非终结符。 推导的基本概念：句子、直接推导、最左推导、左句型（最右推导、右句型）； 分析树与语法树：分析树和语法树都反映了语言结构；分析树还记录了分析的过程（含有非终结符）； 文法的二义性：二义性的本质是在文法中缺少对文法符号优先级和结合性的限制，从而使得一个句子可以推导出多于一棵分析树。 二义性的消除： 改写二义文法为非二义文法； 对文法符号施加优先级与结合性的限制，使得分析的每一步有唯一选择。,13, 自上而下分析,分析方法
7、：推导，从上到下构造分析树，是一种预测的、试探的方法； 对文法的要求：没有公共左因子和左递归； 递归下降子程序方法：匹配终结符，展开非终结符（子程序调用） 预测分析表方法: 工作方式与过程：PDA（DPDA）、格局与改变格局的动作； 预测分析表的构造：FIRST集合与FOLLOW集合， FIRST与FOLLOW的计算； LL(1)文法及其判别：预测分析表中没有多重定义条目（推论3.2）。,14, 自下而上分析,分析方法：归约(推导的逆过程)，从叶子到根构造分析树； 基本概念：短语、直接短语、句柄、归约、规范归约； 采用的方法: 用移进-归约方法实现剪句柄（格局中的两个关键动作），关键问题是如何
8、确定栈顶已经形成句柄，当句柄形成时，如何判定采用哪个产生式进行规约； 识别活前缀的DFA：活前缀与LR(0)项目(NFA状态)，拓广文法与子集法构造DFA；,一个产生式是一个识别活前缀的NFA 一个LR(0)项目是NFA的一个状态,15, 自下而上分析（续）,DFA分析输入序列：有效项目、可移进项目、可规约项目、移进/归约冲突、归约/归约冲突；解决冲突的方法SLR(1)：简单向前看一个终结符（计算归约项非终结符的FOLLOW，与可移进终结符比较）；,移进-归约分析表：动作表转移表； LR文法与LR分析：LR(0)、SLR(1)、LALR(1)、LR(1)。,习题与试题（略过语法制导翻译）,16
9、,第四章 语法制导翻译生成中间代码,本章讨论程序设计语言的静态语义分析，并且在语法分析的基础上生成中间代码，采用的基本方法是语法制导翻译。 与前两章词法分析和语法分析不同的是，词法分析和语法分析的讨论侧重于理论，而本章则侧重于结合程序设计语言的实际例子讨论语言结构的具体翻译方法和一些实用的技术。,主要内容 语法制导翻译与中间代码 符号表的组织 声明语句的翻译 可执行语句的翻译,17, 语法制导翻译与中间代码,语法与语义：语法和语义描述语言的不同方面、二者之间没有严格界线、语义形式化描述的困难性； 属性：用属性表示语义特征（语义值），属性的计算和属性之间的依赖关系； 语法制导翻译：为产生式配上“
10、语义规则”并在适当的时刻执行；语义规则的两种形式； 分析方法与翻译方案：以语法分析为基础，分析树的作用； 中间代码：为什么生成中间代码，中间代码的特征，各种形式的中间代码及它们之间的关系，最常用中间代码形式。,18, 声明语句的翻译 定义与声明：类型定义与变量声明，过程定义与过程声明 变量声明：符号表信息的填写 过程声明： 左值与右值 参数传递：参数传递的不同形式 名字的作用域：静态作用域与最近嵌套原则 声明中作用域信息的保存,符号表的条目与信息的存储（关键字内容） 作用域信息的保存（栈结构） 线性表与散列表, 符号表的组织,19, 可执行语句的翻译,简单算术表达式和赋值句的翻译：语法制导翻译
11、的设计，类型转换； 数组元素的引用：数组元素地址计算的递推公式，地址的可变部分与不变部分，可变部分计算的语法制导翻译； 布尔表达式短路计算的翻译：为什么需要短路计算，短路计算的控制流，真出口与假出口，真值链与假值链； 控制语句的翻译：控制语句的分类，无条件转移与条件转移，拉链/回填技术；,习题与试题,认真复习，重点是掌握基本概念。基本概念掌握了，相当一部分试题的解就有了。 习题与试题的目的区别：习题的目的是通过反复的练习理解、掌握所学知识，会有不少繁、难、大量步骤的题；试题的目的是考察对本课程综合掌握的情况，特点是短时间内覆盖大量内容。太繁琐步骤或太难等需要耗费大量时间的题是不可能出的，大部分
12、应该是基本概念题，但也会有一些综合性的题目。 自己要会辨别什么是主要的什么是次要的，抓什么丢什么。“基本概念要严谨（清楚），基本方法要灵活”。 总之一句话，学习方法的掌握是个人努力的结果，单纯靠别人教是学不会的。,21,关于考试,题目类型：简答题(25分)、填空题(25分)、计算题(50分) 考试范围：14章讲过的内容 侧重考察：基本概念与基本方法的掌握,易犯的错误 不认真审题（对题目的要求理解错误：意思理解错、难题想容易、容易题想难。关键问题是基本概念不清楚） 所答非所问(例如：没有要求LL分析却将文法改为LL的) 画蛇添足(例如：仅问有无冲突却将分析表先构造出来) 偷工减料(例如：有若干问
13、，仅回答部分或问题仅答一半),警示 千万不要作弊！命运掌握在自己的手中！,实际试题举例 一、简答题,1（2分）有哪些方法可以去除文法的二义性。 2（2分）写出 -(a+b)*c)+d 的后缀式。 3（4分）试证明正规式(ab)*a与a(ba)*是等价的。,1 （1）改写文法 （2）规定文法符号的优先级和结合性 2 ab+c*d+（或ab+c*-d+） 3 证明： 考虑L(ab)*a)中的任意一个串ababab.aba， 由串连接的结合性可得：a(ba)(ba)(b.a)(ba)，它恰好是L(a(ba)*)，即L(ab)*a)= L(a(ba)*)。 也可以用归纳法证明（提示：以ab重复0次、1
14、次作为归纳基础，假设ab重复n次成立，证明ab重复n+1次也成立）。,二、填空题（30分）,1（6分）编译程序的基本组成有：词法分析、 、 、中间代码生成、 、 、 和 。 2（1分）正规式r和s等价说明 相同。 3（2分）不含子串baa的所有a、b符号串的正规式是 。 4（4分） 已知文法G定义如下： SeT|RT TDR| RdR| Da|bd 则FIRST(S)= ，FIRST(D)= ，FIRST(T)= ，FIRST(R)= 。,1 语法分析、语义分析、代码优化、目标代码生成、符号表管理和出错处理 2 r和s表示的正规集 3 a*(b|ba)* 4 FIRST(S)= e，d，a，b
15、 ，FIRST(D)= a，b ，FIRST(T)= ，a，b ，FIRST(R)= d， 。,三、计算题（1）,1（13分）已知一个NFA如图。 (a)(4分) 用自然语言简要叙述该自动机所识别的语言 的特点，列举两个它可识别的串。 (b)（3分）写出与该自动机等价的正规式r。 (c)（6分）用子集法构造识别r的最小DFA。,解：,含有至少两个连续b的a、b串，例如bb、bbb等。 r=(a|b)*bb(a|b)*。 直接用状态转换矩阵构造： 初态：0 子集法得：（2是终态）,令： 0=A，0,1=B，0,1,2=C，0,2=D 得：,最小化DFA得：（C和D不可区分）,三、计算题（2）,2
16、（15分）有文法G和G的语法制导翻译如下： EE1*T E.place=newtemp; emit(*,E1.place,T.place,E.place; | T E.place=T.place; TT1+F T.place=newtemp; emit(+,T1.place,F.place,T.place; | F T.place=F.place; F(E) F.place=E.place; | id F.place=id.name; (a)（4分）求句型(T+F)*id 的短语、直接短语以及句柄； (b)（4分）根据语法制导翻译写出句子a*b+c*d的中间代码； (c)（3分）若a=3，b=5，c=7，d=8，请给出中间代码计算结果； (d)（4分）将文法G简化为：EE*T|T，TT+F|F，Fid。给出它的识别活前缀的DFA。,解：,(a) 短语：(T+F)*i
