西安电子科技大学编译原理复习学习教案

1、会计学1西安电子科技大学编译西安电子科技大学编译(biny)原理复习原理复习第一页，共54页。2不同的翻译形式(xngsh)：汇编、编译、转换（预编译）、逆向翻译翻译方法： 第2页/共54页第二页，共54页。3第3页/共54页第三页，共54页。4 编译器的扫描(somio)遍数与编译器的编写 第4页/共54页第四页，共54页。5构词规则与词法分析： 首先规定单词形成的规则，称为构词规则；然后根据构词规则识别(shbi)输入序列，称为词法分析。 主要内容： 记号、模式与单词 记号的说明模式的形式化描述（正规式与正规集） 记号的识别(shbi)有限自动机 从正规式到词法分析器 词法分析器的作用：滤

2、掉源程序中的无用成分；处理与具体操作系统或机器有关的输入；识别记号并交给语法分析器；调用符号表管理器和出错处理器进行相关处理。 第5页/共54页第五页，共54页。6模式（pattern）：规定单词识别(shbi)的规则记号（token）：按照某模式识别(shbi)出的一类单词（记号种类）单词（lexeme）：被识别(shbi)出的字符串本身词法分析器的输出：记号=记号种类+记号属性 记号(j ho)的说明模式的形式化描述 1.正规式与正规集正规式与正规集的定义(基本正规式、三个运算)正规式的等价(描述相同的集合)利用正规式的等价对正规式进行化简(正规式的代数性质)2.用正规式形式化描述模式如何

3、用正规式描述程序设计语言中常见的记号，如标识符、数字、运算符和分隔符等正规式的简化形式以及辅助定义与规则第6页/共54页第六页，共54页。7NFA与DFA的定义：FA = (S, , move, s0, F)；NFA与DFA的表示：定义表示、状态转换图、状态转换矩阵；NFA与DFA的关键区别：NFA的不确定性：有状态转移；当前状态下，对同一字符有多于一个的下一状态转移；用NFA识别输入序列的弱点：尝试所有路径才能确定一个输入不被接收(jishu)、回溯带来的问题；模拟DFA的算法（算法2.1 ）：用DFA识别记号。 第7页/共54页第七页，共54页。构造NFA的Thompson算法(算法2.2

4、)：与正规式的对应关系； 模拟NFA的“并行”算法（算法2.3）； 从NFA构造DFA子集法（算法2.5）：smove(S, a)与-闭包(T)的计算； DFA的最小化可区分(qfn)的概念：所有不可区分(qfn)的状态看作是一个状态（算法2.6）； 灵活运用各种方法构造DFA(正规式化简、状态转换图等)，特别是手工构造和算法构造的区别（考虑(a|b)*abb的NFA）。第8页/共54页第八页，共54页。9 语法分析是编译器中的重要阶段之一，可以认为是语法制导翻译模式编译器的核心。语法分析也有双重含义：根据一定的规则构成语言的各种结构(jigu)，即语法规则；根据语法规则识别输入序列（记号流）

5、中的语言结构(jigu)，即语法分析。 语法分析的分析对象是组成语言的句子，句子具有(jyu)层次结构的特征，表征该结构的最好方法是树，从而使得对语法的分析就有了从根到叶子和从叶子到根两种分析方法。 主要内容 程序设计语言与文法 有关推导的基本概念 自上而下分析(fnx) 自下而上分析(fnx) 第9页/共54页第九页，共54页。10正规式与正规文法：正规式与正规文法用于描述线性结构，如构成句子的记号(j ho)(终结符)；识别正规语言的自动机是有限自动机，它们的特征是没有记忆能力； 上下文无关文法(CFG=(N, T, S, P)：CFG用于描述层次结构，如构成程序的句子；识别CFL的自动机

6、是下推自动机，它是在有限自动机的基础上增加了一个下推栈，从而有了简单的记忆能力； 文法的分类(fn li)：0型、1型、2型和3型文法 词法分析器与语法分析器：FA与PDA第10页/共54页第十页，共54页。111.CFG产生语言的基本方法推导：从文法的开始符号开始，反复地用产生式的右部替换句型中的非终结符。 2.推导的基本概念：句子、直接推导、最左推导、左句型（最右推导、右句型）；（定义3.2、3.3、3.4） 3.分析树与语法树：分析树和语法树都反映了语言结构；分析树还记录了分析的过程(含有非终结符)；(定义3.5、3.6) 4.文法的二义性：二义性的本质是在文法中缺少对文法符号优先级和结

7、合性的限制，从而使得一个句子可以推导出多于一棵分析树。(定义3.7) 5.二义性的消除：6.改写二义文法为非二义文法；（两个关键步骤） 7.对文法符号施加优先级与结合性的限制，使得分析的每一步(y b)有唯一选择。 第11页/共54页第十一页，共54页。121.分析方法：推导，从上到下构造分析树，是一种预测的、试探的方法； 2.对文法的要求：没有公共左因子和左递归3.左递归与直接左递归（定义3.9）4.消除直接左递归与左递归（算法3.1、3.2）5.提取公共左因子（类似于提取公因式）6.递归下降子程序方法：匹配(ppi)终结符，展开非终结符（子程序调用） 第12页/共54页第十二页，共54页。

8、4.预测分析表方法: 5.工作方式与过程：PDA（DPDA）6.格局：（栈内容，当前剩余输入，改变格局的动作(dngzu)）7.改变格局的动作(dngzu)：匹配终结符、展开非终结符、接受、报错8.驱动器（算法3.4）9.预测分析表和分析表的构造：10.分析表的构成与意思：MA, a11.FIRST集合与FOLLOW集合（定义3.10、3.11）12.FIRST与FOLLOW的计算（算法3.5、3.6） 13.分析表的构造（算法3.7） 14.LL(1)文法及其判别：预测分析表中没有多重定义条目（定义3.12、推论3.2）。第13页/共54页第十三页，共54页。141.分析方法：归约(推导的逆

9、过程)，从叶子到根构造分析树；2.基本概念：3.短语、直接短语、句柄（定义3.13）4.最左归约（定义3.14）、归约、规范归约5.采用(ciyng)的方法: 6.剪句柄7.实现方法：移进-归约（格局中的两个关键动作）8.关键问题：是如何确定栈顶已经形成句柄，当句柄形成时，如何判定采用(ciyng)哪个产生式进行规约；9.移进-归约分析器的工作模式（与预测分析表方法对着看）10.移进（匹配终结符）11.归约（展开非终结符）12.驱动器（算法3.8）第14页/共54页第十四页，共54页。6.移进-归约分析表：动作表（action）和转移表（goto）7.LR(k)文法(wnf)（定义3.15）8

10、.核心：识别活前缀的DFA：活前缀与LR(0)项目(NFA状态)（定义3.16、3.17 ）一个产生(chnshng)式是一个识别活前缀的NFA一个LR(0)项目是NFA的一个状态9.拓广文法与子集法构造DFAclosure(I)、goto(I，X)(定义3.18、3.19 )核心项目与非核心项目（定义3.20）构造算法（算法3.9）核心是：closure(goto(I，x)第15页/共54页第十五页，共54页。1610.DFA如何分析输入序列11.有效项目（定义3.21）、可移进项目、可规约项目12.移进/归约冲突、归约/归约冲突；13.解决冲突的方法SLR(1)：简单向前看一个终结符（计算

11、(j sun)归约项非终结符的FOLLOW，与可移进终结符比较）； 11.移进-归约分析表的构造(guzo)：（算法3.10）； 12.LR文法与LR分析：LR(0)、SLR(1)、LALR(1)、LR(1)。第16页/共54页第十六页，共54页。17 讨论程序设计语言的静态语义分析，并且在语法分析的基础上生成中间代码，采用的基本方法是语法制导翻译。 与前两章词法分析和语法分析不同的是，词法分析和语法分析的讨论侧重于理论，而本章则侧重于结合程序设计语言的实际(shj)例子讨论语言结构的具体翻译方法和一些实用的技术。主要内容 语法(yf)制导翻译：概念与基本方法 中间代码 符号表的组织 声明语句

12、的翻译 可执行语句的翻译 第17页/共54页第十七页，共54页。1.语法与语义2.语法：语言的结构；语义：附在结构上的实际意思3.属性与属性的计算4.属性：附在文法符号上的意思，如：val、place等5.语义规则：实现属性的计算6.语义规则的两种表现形式7.语法制导(zhdo)定义：抽象的属性和计算表示的语义规则8.翻译方案：具体的属性和计算表示的语义规则第18页/共54页第十八页，共54页。1.与语法分析的关系：自下而上语法分析（LR分析的两点扩充），自上而下语法分析（递归下降子程序方法）2.语义规则的设计：设计属性、基本操作（函数或过程）、语义规则；3.声明性语句：需要保存什么信息，这些

13、信息有哪些特征，设计什么样的数据结构存放这些信息，以便于对它们的处理(chl)；4.可执行语句：语句的结构应生成什么样的中间代码序列，根据中间代码序列设计语法制导定义，根据序列的特点设计翻译方案。 第19页/共54页第十九页，共54页。1.为什么生成中间代码：中间代码是编译器分析综合模式前端与后端的分水岭；2.中间代码的特征：形式接近目标机器代码，但又与具体机器无关，便于编译器的开发移植和代码的优化；3.常用的中间代码形式：后缀式、树（图）、三地址码；4.三地址码的实现(shxin)：三元式、四元式5.中间代码之间的关系：6.树与后缀式的关系7.树与三元式和四元式的关系 第20页/共54页第二

14、十页，共54页。1.符号表的作用：连接声明与引用的桥梁2.符号表的条目与信息的存储：直接存储与间接存储3.作用域信息的保存4.静态作用域+最近嵌套原则5.线性表：栈结构，表上的操作(cozu)6.散列表：每个子表是栈结构，提高表上操作(cozu)的效率 第21页/共54页第二十一页，共54页。1.定义与声明：类型定义与变量声明，过程定义与过程声明2.变量声明：符号表信息的填写（简单变量和数组变量）；3.过程声明：4.左值与右值；5.参数传递：参数传递的不同形式，各种参数传递形式的处理方式；6.名字的作用域：满足静态作用域与最近嵌套原则(yunz)；7.声明中作用域信息的保存。 第22页/共54

15、页第二十二页，共54页。1.简单算术表达式和赋值句的翻译：语法制导(zhdo)翻译的设计，类型转换；2.数组元素的引用：3.多维数组到一维存储空间的映射；4.数组元素地址计算的递推公式；5.数组元素地址计算的语法制导(zhdo)翻译；6.布尔表达式短路计算的翻译：7.为什么需要短路计算和短路计算的控制流；8.真出口与假出口；9.拉链/回填技术：真值链与假值链10.控制语句的翻译：控制语句的分类，转移与条件转移。 第23页/共54页第二十三页，共54页。第24页/共54页第二十四页，共54页。认真复习，重点是掌握基本概念。基本概念掌握了，相当一部分试题的解就有了。习题与试题的目的区别：习题的目的

16、是通过反复的练习理解、掌握所学知识，会有不少繁、难、大量步骤的题；试题的目的是考察对本课程综合掌握的情况，特点是短时间内覆盖大量内容。太繁琐步骤或太难等需要耗费大量时间的题是不可能出的，大部分应该是基本概念题，但也会有一些综合性的题目。自己要会辨别什么是主要的什么是次要的，抓什么丢什么。“基本概念要严谨（清楚），基本方法要灵活(ln hu)”。总之一句话，学习方法的掌握是个人努力的结果，单纯靠别人教是学不会的。第25页/共54页第二十五页，共54页。26题目类型：填空题(30分)、简答题(20分)、计算题(50分)考试范围(fnwi)：14章讲过的内容侧重考察：基本概念与基本方法的掌握易犯的错

17、误不认真审题（对题目的要求(yoqi)理解错误：意思理解错、难题想容易、容易题想难。关键问题是基本概念不清楚）所答非所问(例如：没有要求(yoqi)LL分析却将文法改为LL的)画蛇添足(例如：仅问有无冲突却将分析表先构造出来)偷工减料(例如：有若干问，仅回答部分或问题仅答一半)警示千万不要作弊！命运掌握在自己的手中！第26页/共54页第二十六页，共54页。1（2分）有哪些方法可以去除文法的二义性。分）有哪些方法可以去除文法的二义性。2（2分）写出分）写出 -(a+b)*c)+d 的后缀式。的后缀式。3（4分）试证明分）试证明(zhngmng)正规式正规式(ab)*a与与a(ba)*是等价的。是

18、等价的。1 （1）改写文法）改写文法 （2）规定文法符号的优先级和结合性）规定文法符号的优先级和结合性2 ab+c*d+（或（或ab+c*-d+）3 证明：证明： 考虑考虑L(ab)*a)中的任意中的任意(rny)一个串一个串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次也成

19、立）。次也成立）。第27页/共54页第二十七页，共54页。1（6分）编译程序的基本(jbn)组成有：词法分析、 、 、中间代码生成、 、 、 和 。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 语法分析(fnx)、语义分析(fnx)、代码优化、目标代码生成、符号表管理和出错处理 2 r和s表示的正规集 3 a*(b|ba)* 4 FIRST(S)= e，d，a，b ，FIRS

20、T(D)= a，b ，FIRST(T)= ，a，b ，FIRST(R)= d， 。第28页/共54页第二十八页，共54页。1（13分）已知一个NFA如图。 (a)(4分) 用自然语言简要叙述(xsh)该自动机所识别的语言 的特点，列举两个它可识别的串。 (b)（3分）写出与该自动机等价的正规式r。 (c)（6分）用子集法构造识别r的最小DFA。012bba,ba,b第29页/共54页第二十九页，共54页。1.含有至少两个(lin )连续b的a、b串，例如bb、bbb等。2.r=(a|b)*bb(a|b)*。3.直接用状态转换矩阵构造：4.初态：05.子集法得：（2是终态）ab000,10,10

21、0,1,20,1,2 0,20,1,20,20,20,1,2令： 0=A，0,1=B，0,1,2=C，0,2=D得：abAABBACCDCDDC最小化DFA得：（C和D不可(bk)区分）abAABBACCCC第30页/共54页第三十页，共54页。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

22、(E) F.place=E.place; | id F.place=; (a)（4分）求句型(T+F)*id 的短语、直接(zhji)短语以及句柄；(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。 第31页/共54页第三十一页，共54页。(a) 短语：(T+F)*id、(T+F)、T+F、id 直接(zhji)短语：T+F、id 句柄：T+F(b) a*b+c*d的中间代码：(1) (+, b, c,

23、 t1)(2) (*, a, t1, t2)(3) (*, t2, d, t3)(c) 计算结果：t3=288 (d) 识别活前缀的DFA： E.EE.E*TE.TT.T+FT.FF.idEE.EE.*TET.TT.+FTF.Fid.EE*.TT.T+FT.FF.idTT+.FF.idEE*T.TT.+FFETFid*+TididI0I1I2I3I4I5I6I7TT+F.I8F第32页/共54页第三十二页，共54页。33第33页/共54页第三十三页，共54页。写出下述语言的正规式描述(mio sh)（1）由偶数个0和奇数个1构成的所有01串（2）所有不含子串011的01串（3）每个a后面至少紧

24、随两个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思考：识别(shbi)它的DFA又应该如何构造？第34页/共54页第三十四页，共54页。思路(sl)：注释中若遇到*：若后边是/则结束注释否则仍然是注释步骤：1. 注释串是空；2. 考虑没有*的

25、注释；3. 考虑含*的注释结果：(4) /* (*|*/)* */（2）所有(suyu)不含子串011的01串：1*(01|0)*（3）每个a后面至少紧随两个b的ab串：(b|abb)*第35页/共54页第三十五页，共54页。 用自然语言给出下述正规(zhnggu)式所描述的语言，并构造他们的最小DFA：10*1(0|1)*011(0|1)*说明：所谓用自然语言描述就是(jish)解释字符串的性质，一般情况下是已经有了形式化描述。解：10*1：首尾是1中间有零或若干个0的01串。(0|1)*011(0|1)* ：至少含一个011的01串。注意： *是0或若干次的重复；+是至少一次的重复 绝对不

26、允许用正规式表示，因为正规式是已知条件DFA（略）(0|1)*011(0|1)* 的DFA构造与考试题中计算题相似第36页/共54页第三十六页，共54页。有一NFA的状态(zhungti)转换矩阵下表，其中S为初态，D为终态abcSA,BC,DDA,B,CAACBBADCCBAADCBS1.求出它的最小DFA2.用正规式描述(mio sh)DFA所接受的语言问题：根据DFA写出对应的正规式，通常的考虑和步骤是什么？ 再重复一遍： 正规式、DFA是从两个不同的侧面表示一个集合(即正规集)。所以，根本的方法是把正规集作为桥梁，先分析清楚DFA识别出的是一个什么集合，然后再设计此集合的正规式。反之亦

27、然。第37页/共54页第三十七页，共54页。 该DFA从初态到终态有三条路径：b|c|a(a|c)*b，而且(r qi)是这三条路径的至少一次重复，故正规式为：(b|c|a(a|c)*b)+第38页/共54页第三十八页，共54页。设计一文法G，使得L(G)=|是不以0开始的正奇数思路：首先根据集合的描述设计几个句子，然后从句子中找出规律（或共性），把它们(t men)的性质用产生式表示出来。解：正规式：个位：13579 个位以上：0-9* 最高位：1-9三段连起来：1-90-9*13579两种情况： 1-90-9*13579 | 13579产生式：SACB|BA1|2|3|4|5|6|7|8|

28、9B1|3|5|7|9C|0C|AC第39页/共54页第三十九页，共54页。(3) S aA | Aa A b |(4) S iCtS | iCtSeS | a C b(1) S Ra | a R Sb | b(2) S aAc | b A a | b | 下述四个文法，无需(wx)构造预测分析表，指出哪一个是LL(1)文法，并指出其他文法为什么不是LL(1)文法。解：(1) 不是LL(1)文法，因为它是左递归的：S=Ra=Sba。(2) 是LL(1)文法。(3) 不是LL(1)文法，因为对于S的两个候选(hu xun)项Aa和Aa，FIRST(aA)FIRST(Aa)=a不满足推论3.2的条

29、件。(4) 不是LL(1)文法，因为S的前两个候选(hu xun)项中含有左公因子iCtS，不满足推论3.2的条件。第40页/共54页第四十页，共54页。文法G如下: SaABeAb|Abc Bd(1) 改写G为等价的LL(1)文法；(2) 求每个非终结符的FIRST集合和FOLLOW集合；(1) 构造识别活前缀的DFA；(2) 指出DFA中的冲突(如果(rgu)有的话)；解：(3.11) (1) 改写(gixi)后的文法：SaABe AbA AbcA| Bd(2) FIRST(S) = a, FOLLOW(S)=# FIRST(A) = b, FOLLOW(A)=d FIRST(A) = b

30、, FOLLOW(A)=d FIRST(B) = d, FOLLOW(B)=e第41页/共54页第四十一页，共54页。解：(3.18) (1) SaABeAb|Abc Bd 的DFA如下(rxi)。(2) 无冲突。第42页/共54页第四十二页，共54页。43认真复习、迎接(yngji)考试（结 束 2010年5月27日）第43页/共54页第四十三页，共54页。对于文法(wnf)G3.4和它所产生的句子-id+id*id 和 -(id+id)*idE E+T|TT T*F|F (G3.4)F (E) |-F|id（1）构造基于LR(0)项目集的识别活前缀的DFA（2）指出DFA中所有含有冲突的项

31、目集，并说明这些冲突可以用SLR(1)方法解决；（3）构造文法(wnf)G3.4的SLR(1)分析表（4）用分析表对句子-id+id*id 和 -(id+id)*id进行分析（以格局变化的方式）（5）根据（4）的分析给出-id+id*id的分析树和剪句柄的过程解：第44页/共54页第四十四页，共54页。（1）构造基于LR(0)项目集的识别活前缀的DFA（2）指出(zh ch)DFA中所有含有冲突的项目集，并说明这些冲突可以用SLR(1)方法解决； 冲突的项目(xingm)集:I2，I11 计算FOLLOW(E)，看*是否在其中（略）第45页/共54页第四十五页，共54页。1可移进项直接从DFA

32、上看：actionI,a:=sjgotoI,A:=k2可归约项分两步走：若在I状态(zhungti)中有A.，首先计算：FOLLOW(A),然后填写：actionI,b:=Ri其中：bFOLLOW(A)且A是第i个产生式。 第46页/共54页第四十六页，共54页。 设字母表=0,1,设计下述语言的文法。对于正规语言，可用正规式表示。（1）每个0后面至少跟随一个1的字符串（2）0和1个数相等的字符串（3）0和1个数不相等的字符串（4）不以(b y)011作为子串的字符串解：（1）(01|1)* （2）S0S1S|1S0S| （3）SA0A|B1B A0A1A|1A0A|0A|（0不少(b sho

33、)于1） B0B1B|1B0B|1B|（1不少(b sho)于0） （4）1*(0|01)*第47页/共54页第四十七页，共54页。构造SLR(1)分析表的算法3.9基于的假设是LR(0)项目集中可能有冲突(chngt)。如果基于的假设是LR(0)项目集中没有冲突(chngt)，则构造方法可以简化（无需计算FOLLOW集合），得到的是LR(0)分析表。试修改算法3.9成为构造LR(0)分析表的算法。1.if DFA中有不能解决(jiju)的移进/归约和归约/归约冲突 then error; else for 每个状态转移Dtrani,x=j loop if xT then actioni,x:

34、=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; 每个终结符aA.状态i：B. .x x第48页/共54页第四十八页，共54页。假定下述程序分别采用值调用，引用调用，复写-恢复和换名调用，请给出它们的打印结果。 program main(input output); procedure p(x,y,z); b

35、egin y:=y+1; z:=z+x end; begin a:=2; b:=3; p(a+b, a, a); print a end;两种解题的思路：1. 把自己当作计算机，按照参数传递的实现方式“运行”一遍程序，得出结果；2. 找台机子把程序敲进去试试（辅助手段）困惑的是：表达式a+b如何作为引用调用和复写-恢复的实参？解决方案：忽略(hl)返回值问题。其实这一思想可以推广到任何不支持某种方式的情况（放心，考试中不会有这种很困惑的问题）具体结果（略）第49页/共54页第四十九页，共54页。设整型数组声明的形式为int Ad1,d2,d3，并且假设每个整型数占据4个字节(z ji)。（1）试导出以列为主存储时计算c和v的递推公式；（2）*设计数组声明的语法制导翻译（包括语法和语义），以使得在对数组声明从左到右分析的同时，正确填写符号表和内情向量的所有信息。解：（1）n=1时，addr(Ai1)=a+(i1-1)*4n=2时，addr(Ai1,i2)=a+(i2-1)*d1*4+(i1-1)*4addr(Ai1,i2,in)=?第5