西安电子科技大学编译原理复习.ppt

编译原理复习,西安电子科技大学 软件工程研究所 刘 坚,2,课程内容,要求（希望） 牢固掌握基本概念 灵活使用基本方法 归纳总结所学内容,一、引言 二、词法分析 三、语法分析 四、语义分析语法制导翻译生成中间代码,学习不能走捷径，付出多少劳动就有多少收获 掌握正确的学习方法，提高自学能力,3,第一章 引言, 语言的翻译,不同的翻译形式：汇编、编译、转换（预编译）、逆向翻译 翻译方法：,4, 编译器的基本组成,5, 编译器的分析综合模式, 编译器的扫描遍数与编译器的编写,6,第二章 词法分析,构词规则与词法分析： 首先规定单词形成的规则，称为构词规则；然后根据构词规则识别输入序列，称为词法分析。,主要内容： 记号、模式与单词 记号的说明模式的形式化描述（正规式与正规集） 记号的识别有限自动机 从正规式到词法分析器,词法分析器的作用： 滤掉源程序中的无用成分； 处理与具体操作系统或机器有关的输入； 识别记号并交给语法分析器； 调用符号表管理器和出错处理器进行相关处理。,7, 记号、模式与单词,模式（pattern）：规定单词识别的规则 记号（token）：按照某模式识别出的一类单词（记号种类） 单词（lexeme）：被识别出的字符串本身 词法分析器的输出：记号=记号种类+记号属性, 记号的说明模式的形式化描述,正规式与正规集 正规式与正规集的定义(基本正规式、三个运算) 正规式的等价(描述相同的集合) 利用正规式的等价对正规式进行化简(正规式的代数性质) 用正规式形式化描述模式 如何用正规式描述程序设计语言中常见的记号，如标识符、数字、运算符和分隔符等 正规式的简化形式以及辅助定义与规则,8, 记号的识别有限自动机（FA）,NFA与DFA的定义：FA = (S, , move, s0, F)； NFA与DFA的表示：定义表示、状态转换图、状态转换矩阵； NFA与DFA的关键区别：NFA的不确定性： 有状态转移； 当前状态下，对同一字符有多于一个的下一状态转移； 用NFA识别输入序列的弱点：尝试所有路径才能确定一个输入不被接收、回溯带来的问题； 模拟DFA的算法（算法2.1 ）：用DFA识别记号。, 从正规式到词法分析器,构造NFA的Thompson算法(算法2.2)：与正规式的对应关系； 模拟NFA的“并行”算法（算法2.3）； 从NFA构造DFA子集法（算法2.5）： smove(S, a)与-闭包(T)的计算； DFA的最小化可区分的概念：所有不可区分的状态看作是一个状态（算法2.6）； 灵活运用各种方法构造DFA(正规式化简、状态转换图等)，特别是手工构造和算法构造的区别（考虑(a|b)*abb的NFA）。,10,第三章 语法分析,语法分析是编译器中的重要阶段之一，可以认为是语法制导翻译模式编译器的核心。语法分析也有双重含义：根据一定的规则构成语言的各种结构，即语法规则；根据语法规则识别输入序列（记号流）中的语言结构，即语法分析。,语法分析的分析对象是组成语言的句子，句子具有层次结构的特征，表征该结构的最好方法是树，从而使得对语法的分析就有了从根到叶子和从叶子到根两种分析方法。,主要内容 程序设计语言与文法 有关推导的基本概念 自上而下分析 自下而上分析,11, 程序设计语言与文法,正规式与正规文法：正规式与正规文法用于描述线性结构，如构成句子的记号(终结符)；识别正规语言的自动机是有限自动机，它们的特征是没有记忆能力； 上下文无关文法(CFG=(N, T, S, P)：CFG用于描述层次结构，如构成程序的句子；识别CFL的自动机是下推自动机，它是在有限自动机的基础上增加了一个下推栈，从而有了简单的记忆能力；,文法的分类：0型、1型、2型和3型文法 词法分析器与语法分析器：FA与PDA,12, 有关推导的基本概念,CFG产生语言的基本方法推导：从文法的开始符号开始，反复地用产生式的右部替换句型中的非终结符。 推导的基本概念：句子、直接推导、最左推导、左句型（最右推导、右句型）；（定义3.2、3.3、3.4） 分析树与语法树：分析树和语法树都反映了语言结构；分析树还记录了分析的过程(含有非终结符)；(定义3.5、3.6) 文法的二义性：二义性的本质是在文法中缺少对文法符号优先级和结合性的限制，从而使得一个句子可以推导出多于一棵分析树。(定义3.7) 二义性的消除： 改写二义文法为非二义文法；（两个关键步骤） 对文法符号施加优先级与结合性的限制，使得分析的每一步有唯一选择。,13, 自上而下分析,分析方法：推导，从上到下构造分析树，是一种预测的、试探的方法； 对文法的要求：没有公共左因子和左递归 左递归与直接左递归（定义3.9） 消除直接左递归与左递归（算法3.1、3.2） 提取公共左因子（类似于提取公因式） 递归下降子程序方法：匹配终结符，展开非终结符（子程序调用）, 自上而下分析（续）,预测分析表方法: 工作方式与过程：PDA（DPDA） 格局：（栈内容，当前剩余输入，改变格局的动作） 改变格局的动作：匹配终结符、展开非终结符、接受、报错 驱动器（算法3.4） 预测分析表和分析表的构造： 分析表的构成与意思：MA, a FIRST集合与FOLLOW集合（定义3.10、3.11） FIRST与FOLLOW的计算（算法3.5、3.6） 分析表的构造（算法3.7） LL(1)文法及其判别：预测分析表中没有多重定义条目（定义3.12、推论3.2）。,15, 自下而上分析,分析方法：归约(推导的逆过程)，从叶子到根构造分析树； 基本概念： 短语、直接短语、句柄（定义3.13） 最左归约（定义3.14）、归约、规范归约 采用的方法: 剪句柄 实现方法：移进-归约（格局中的两个关键动作） 关键问题：是如何确定栈顶已经形成句柄，当句柄形成时，如何判定采用哪个产生式进行规约； 移进-归约分析器的工作模式（与预测分析表方法对着看） 移进（匹配终结符） 归约（展开非终结符） 驱动器（算法3.8）, 自下而上分析（续1）,移进-归约分析表：动作表（action）和转移表（goto） LR(k)文法（定义3.15） 核心：识别活前缀的DFA：活前缀与LR(0)项目(NFA状态)（定义3.16、3.17 ）,一个产生式是一个识别活前缀的NFA 一个LR(0)项目是NFA的一个状态,拓广文法与子集法构造DFA closure(I)、goto(I，X)(定义3.18、3.19 ) 核心项目与非核心项目（定义3.20） 构造算法（算法3.9）核心是：closure(goto(I，x),17, 自下而上分析（续2）,DFA如何分析输入序列 有效项目（定义3.21）、可移进项目、可规约项目 移进/归约冲突、归约/归约冲突； 解决冲突的方法SLR(1)：简单向前看一个终结符（计算归约项非终结符的FOLLOW，与可移进终结符比较）；,移进-归约分析表的构造：（算法3.10）； LR文法与LR分析：LR(0)、SLR(1)、LALR(1)、LR(1)。,18,第四章 语法制导翻译生成中间代码,讨论程序设计语言的静态语义分析，并且在语法分析的基础上生成中间代码，采用的基本方法是语法制导翻译。 与前两章词法分析和语法分析不同的是，词法分析和语法分析的讨论侧重于理论，而本章则侧重于结合程序设计语言的实际例子讨论语言结构的具体翻译方法和一些实用的技术。,主要内容 语法制导翻译：概念与基本方法 中间代码 符号表的组织 声明语句的翻译 可执行语句的翻译, 语法制导翻译的基本概念,语法与语义 语法：语言的结构；语义：附在结构上的实际意思 属性与属性的计算 属性：附在文法符号上的意思，如：val、place等 语义规则：实现属性的计算 语义规则的两种表现形式 语法制导定义：抽象的属性和计算表示的语义规则 翻译方案：具体的属性和计算表示的语义规则, 基本设计方法,与语法分析的关系：自下而上语法分析（LR分析的两点扩充），自上而下语法分析（递归下降子程序方法） 语义规则的设计：设计属性、基本操作（函数或过程）、语义规则； 声明性语句：需要保存什么信息，这些信息有哪些特征，设计什么样的数据结构存放这些信息，以便于对它们的处理； 可执行语句：语句的结构应生成什么样的中间代码序列，根据中间代码序列设计语法制导定义，根据序列的特点设计翻译方案。, 中间代码,为什么生成中间代码：中间代码是编译器分析综合模式前端与后端的分水岭； 中间代码的特征：形式接近目标机器代码，但又与具体机器无关，便于编译器的开发移植和代码的优化； 常用的中间代码形式：后缀式、树（图）、三地址码； 三地址码的实现：三元式、四元式 中间代码之间的关系： 树与后缀式的关系 树与三元式和四元式的关系, 符号表的组织,符号表的作用：连接声明与引用的桥梁 符号表的条目与信息的存储：直接存储与间接存储 作用域信息的保存 静态作用域+最近嵌套原则 线性表：栈结构，表上的操作 散列表：每个子表是栈结构，提高表上操作的效率, 声明语句的翻译,定义与声明：类型定义与变量声明，过程定义与过程声明 变量声明：符号表信息的填写（简单变量和数组变量）； 过程声明： 左值与右值； 参数传递：参数传递的不同形式，各种参数传递形式的处理方式； 名字的作用域：满足静态作用域与最近嵌套原则； 声明中作用域信息的保存。, 可执行语句的翻译,简单算术表达式和赋值句的翻译：语法制导翻译的设计，类型转换； 数组元素的引用： 多维数组到一维存储空间的映射； 数组元素地址计算的递推公式； 数组元素地址计算的语法制导翻译； 布尔表达式短路计算的翻译： 为什么需要短路计算和短路计算的控制流； 真出口与假出口； 拉链/回填技术：真值链与假值链 控制语句的翻译：控制语句的分类，转移与条件转移。,结 束（2010年5月25日）,试题与习题,认真复习，重点是掌握基本概念。基本概念掌握了，相当一部分试题的解就有了。 习题与试题的目的区别：习题的目的是通过反复的练习理解、掌握所学知识，会有不少繁、难、大量步骤的题；试题的目的是考察对本课程综合掌握的情况，特点是短时间内覆盖大量内容。太繁琐步骤或太难等需要耗费大量时间的题是不可能出的，大部分应该是基本概念题，但也会有一些综合性的题目。 自己要会辨别什么是主要的什么是次要的，抓什么丢什么。“基本概念要严谨（清楚），基本方法要灵活”。 总之一句话，学习方法的掌握是个人努力的结果，单纯靠别人教是学不会的。,27,关于考试,题目类型：填空题(30分)、简答题(20分)、计算题(50分) 考试范围：14章讲过的内容 侧重考察：基本概念与基本方法的掌握,易犯的错误 不认真审题（对题目的要求理解错误：意思理解错、难题想容易、容易题想难。关键问题是基本概念不清楚） 所答非所问(例如：没有要求LL分析却将文法改为LL的) 画蛇添足(例如：仅问有无冲突却将分析表先构造出来) 偷工减料(例如：有若干问，仅回答部分或问题仅答一半),警示 千万不要作弊！命运掌握在自己的手中！,实际试题举例一、简答题,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次作为归纳基础，假设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 ，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（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)*id、(T+F)、T+F、id 直接短语：T+F、id 句柄：T+F (b) a*b+c*d的中间代码：(1) (+, b, c, t1) (2) (*, a, t1, t2) (3) (*, t2, d, t3) (c) 计算结果：t3=288 (d) 识别活前缀的DFA：,34,部分习题解答,习题2.4,写出下述语言的正规式描述 （1）由偶数个0和奇数个1构成的所有01串 （2）所有不含子串011的01串 （3）每个a后面至少紧随两个b的ab串 （4）C的形如/*/ 的注释。其中代表不含*/的字符串,思路：分析题意，从最简单的例子考虑，然后找出统一规律 （1）的解题步骤： 1. 最简单的符合要求的串：1、010（还有100、001、111等） 2. 所有01均为偶数的串： A=(00|11)|(01|10)(00|11)*(10|01)* 3. 符合要求的所有串：A1A、A0A1A0A（为什么没有后三个？） 结果：A1A | A0A1A0A 思考：识别它的DFA又应该如何构造？,（4）C的形如/*/ 的注释。其中代表不含*/的字符串,思路：注释中若遇到*：若后边是/则结束注释否则仍然是注释 步骤： 1. 注释串是空； 2. 考虑没有*的注释； 3. 考虑含*的注释 结果：(4) /* (*|*/)* */,（2）所有不含子串011的01串：1*(01|0)* （3）每个a后面至少紧随两个b的ab串：(b|abb)*,习题2.9,用自然语言给出下述正规式所描述的语言，并构造他们的最小DFA：10*1(0|1)*011(0|1)*,说明：所谓用自然语言描述就是解释字符串的性质，一般情况下是已经有了形式化描述。 解：10*1：首尾是1中间有零或若干个0的01串。 (0|1)*011(0|1)* ：至少含一个011的01串。 注意： *是0或若干次的重复；+是至少一次的重复 绝对不允许用正规式表示，因为正规式是已知条件 DFA（略）(0|1)*011(0|1)* 的DFA构造与考试题中计算题相似,习题2.10,有一NFA的状态转换矩阵下表，其中S为初态，D为终态,求出它的最小DFA 用正规式描述DFA所接受的语言,问题：根据DFA写出对应的正规式，通常的考虑和步骤是什么？,再重复一遍： 正规式、DFA是从两个不同的侧面表示一个集合(即正规集)。所以，根本的方法是把正规集作为桥梁，先分析清楚DFA识别出的是一个什么集合，然后再设计此集合的正规式。反之亦然。,习题2.10（2）的解,该DFA从初态到终态有三条路径：b|c|a(a|c)*b，而且是这三条路径的至少一次重复，故正规式为：(b|c|a(a|c)*b)+,习题3.7,设计一文法G，使得L(G)=|是不以0开始的正奇数 思路：首先根据集合的描述设计几个句子，然后从句子中找出规律（或共性），把它们的性质用产生式表示出来。 解：正规式： 个位：13579 个位以上：0-9* 最高位：1-9 三段连起来：1-90-9*13579 两种情况： 1-90-9*13579 | 13579 产生式： SACB|B A1|2|3|4|5|6|7|8|9 B1|3|5|7|9 C|0C|AC,习题3.14,下述四个文法，无需构造预测分析表，指出哪一个是LL(1)文法，并指出其他文法为什么不是LL(1)文法。,解： (1) 不是LL(1)文法，因为它是左递归的：S=Ra=Sba。 (2) 是LL(1)文法。 (3) 不是LL(1)文法，因为对于S的两个候选项Aa和Aa，FIRST(aA)FIRST(Aa)=a不满足推论3.2的条件。 (4) 不是LL(1)文法，因为S的前两个候选项中含有左公因子iCtS，不满足推论3.2的条件。,习题3.11+3.18,文法G如下: SaABeAb|Abc Bd (1) 改写G为等价的LL(1)文法； (2) 求每个非终结符的FIRST集合和FOLLOW集合； (1) 构造识别活前缀的DFA； (2) 指出DFA中的冲突(如果有的话)；,解：(3.11) (1) 改写后的文法： SaABe AbA AbcA| Bd (2) FIRST(S) = a, FOLLOW(S)=# FIRST(A) = b, FOLLOW(A)=d FIRST(A) = b, FOLLOW(A)=d FIRST(B) = d, FOLLOW(B)=e,习题3.11+3.18（续）,解：(3.18) (1) SaABeAb|Abc Bd 的DFA如下。 (2) 无冲突。,44,To know how to do something well is to enjoy it.战略上藐视敌人，战术上重视敌人。 The trees that are slow to grow bear the best fruit.,认真复习、迎接考试 （结 束 2010年5月27日）,习题 3.17,对于文法G3.4和它所产生的句子-id+id*id 和 -(id+id)*id E E+T|T T T*F|F (G3.4) F (E) |-F|id （1）构造基于LR(0)项目集的识别活前缀的DFA （2）指出DFA中所有含有冲突的项目集，并说明这些冲突可以用SLR(1)方法解决； （3）构造文法G3.4的SLR(1)分析表 （4）用分析表对句子-id+id*id 和 -(id+id)*id进行分析（以格局变化的方式） （5）根据（4）的分析给出-id+id*id的分析树和剪句柄的过程 解：,习题 3.17（解）,（1）构造基于LR(0)项目集的识别活前缀的DFA （2）指出DFA中所有含有冲突的项目集，并说明这些冲突可以用SLR(1)方法解决；,冲突的项目集:I2，I11 计算FOLLOW(E)，看*是否在其中（略）,构造SLR（1）分析表的方法：,1可移进项直接从DFA上看： actionI,a:=sjgotoI,A:=k 2可归约项分两步走：若在I状态中有A.， 首先计算：FOLLOW(A), 然后填写：actionI,b:=Ri 其中：bFOLLOW(A)且A是第i个产生式。,习题3.6,设字母表=0,1,设计下述语言的文法。对于正规语言， 可用正规式表示。 （1）每个0后面至少跟随一个1的字符串 （2）0和1个数相等的字符串 （3）0和1个数不相等的字符串 （4）不以011作为子串的字符串,解：（1）(01|1)* （2）S0S1S|1S0S| （3）SA0A|B1B A0A1A|1A0A|0A|（0不少于1） B0B1B|1B0B|1B|（1不少于0） （4）1*(0|01)*,习题3.22,构造SLR(1)分析表的算法3.9基于的假设是LR(0)项目集中可能有 冲突。如果基于的假设是LR(0)项目集中没有冲突，则构造方法 可以简化（无需计算FOLLOW集合），得到的是LR(0)分析表。试 修改算法3.9成为构造LR(0)分析表的算法。,1.if DFA中有不能解决的移进/归约和归约/归约冲突 then error; else for 每个状态转移Dtrani,x=j loop if xT then actioni,x:=Sj; else gotoi,x:=j; end if; end loop; for 状态i的每个可归约项A. loop if S S. then actioni, #:=acc; else for 每个aFOLLOW(A) loop actioni,a:=Rk; end loop; end if; end loop; end if;,每个终结符a,A.,状态i：,B.,x,习题 4.4,假定下述程序分别采用值调用，引用调用，复写-恢复和换名调用，请给出它们的打印结果。 program main(input output); procedure p(x,y,z); begin y:=y+1; z:=z+x end; begin a:=2; b:=3; p(a+b, a, a); print a end; 两种解题的思路： 1. 把自己当作计算机，按照参数传递的实现方式“运行”一遍程序，得出结果； 2. 找台机子把程序敲进去试试（辅助手段） 困惑的是：表达式a+b如何作为引用调用和复写-恢复的实参？ 解决方案：忽略返回值问题。其实这一思想可以推广到任何不支持某种方式的情况（放心，考试中不会有这种很困惑的问题） 具体结果（略）,习题4.9,设整型数组声明的形式为int Ad1,d2,d3，并且假设每个整型 数占据4个字节。 （1）试导出以列为主存储时计算c和v的递推公式； （2）*设计数组声明的语法制导翻译（包括语法和语义），以使得 在对数组声明从左到右分析的同时，正确填写符号表和内情向量的 所有信息。,解： （1）n=1时，addr(Ai1)=a+(i1-1)*4 n=2时，addr(Ai1,i2)=a+(i2-1)*d1*4+(i1-1)*4 addr(Ai1,i2,in)=?,n维数组元素的地址计算,addr(Ai1，i2，.，in) =a+(in-1)*dn-1*dn-2*.*d1+(in-1-1)*dn-2*dn-3*.*d1+.+ (i1-1)*w =a-(dn-1*dn-2*.*d1+dn-2*dn-3*.*d1+.+d1+1)*w +(in*dn-1*dn-2*.*d1+in-1*dn-2*dn-3*.*d1+.+i2*d1+i1)*w =ac*w+v*w 其中：,c=dn-1*dn-2*dn-3*d1+dn-2*dn-3*dn-4*d1+*dn-3*dn-4*dn-5*d1+d1+1 =(dn-1+1)*dn-2*.*d1+dn-3*dn-4.*d1+.+d1+1 =(dn-1+1)*dn-2+1)*dn-3*dn-4.*d1+.+d1+1 . =(.(dn-1+1)*dn-2+1)*dn-3.+1)*d1+1,同理： v = (.(in*dn-1+in-1)*dn-2+in-2)*dn-3.+i2)*d1+i1,n维数组元素的地址计算（续1）,c=(.(dn-1+1)*dn-2+1)*dn-3.+1)*d1+1 v=(.(in*dn-1+in-1)*dn-2+in-2)*dn-3.+i2)*d1+i1,令： v0 = in 则： v1 = in*dn-1+in-1 = v0*dn-1+in-1 v2 = (v0*dn-1+in-1)*dn-2+in-2 = v1*dn-2+in-2 . 于是有： v0 = in vj = vj-1*dn-j+in-j (j=1，2，., n-1) 同理可得： c0 = 1 cj = cj-1*dn-j+1 (j=1，2，., n-1),（2）要适合LR分析，应该将文法改成右递归的。,修改文法以适应递推公式的同步计算： A V := E(1) V id(2) | N EL(3) N id(4) EL E (5) | E , EL(6) E E + E(7) | ( E )(8) | V(9),习题4.10,教材中的语法制导翻译将表达式Eid1id2翻译成一对三地址码 if id1id2 goto goto 现将上述三地址码对用三地址码“if id1id2 goto ”代替，当 E为真时执行后继代码。请修改教材中的语法制导翻译，使之产生 这样性质的三地址码序列。,解： 与原来翻译方案的根本区别在于：表达式为真时并不生成三地址码，因此表达式的真出口默认为下一条三地址码。 如果真出口不是下一条三地址码，则仍需要生成两条goto语句。,