《编译原理讲义(54)》由会员分享，可在线阅读，更多相关《编译原理讲义(54)（150页珍藏版）》请在金锄头文库上搜索。
1、编译原理编译原理讲义孙 清西安财经学院 信息学院 计算机系2007 年 1 月教材：教材：程序设计语言编译原理程序设计语言编译原理 （第（第 3 3 版）版）陈火旺编陈火旺编 国防工业出版社国防工业出版社 20002000 年年 1 1 月月参考教材：1.编译原理蒋立源 康慕宁 西北工业大学出版社 2004 年 1 月2.编译原理吕映芝 张素琴 蒋维杜 清华大学出版社 2002 年 5 月3.Compiler Construction Principles and Practice, Kenneth C. Louden, Thomson Press 2003.2学时：学时：5454 学时分配：
2、周 3 学时章节学时第一章：引论 3第二章 高级语言及其语法描述3第三章 词法分析6第四章 语法分析-自上而下分析6第五章 语法分析-自下而上分析6第六章 属性文法和语法制导翻译6第七章 语义分析和中间代码产生6第八章 符号表 3第九章 运行时存储空间组织 3第十章 优化3第十一章 目标代码生成 3第十二章 并行编译基础 3总复习3 编译原理课程在计算机科学技术中的地位编译原理课程在计算机科学技术中的地位程序设计语言离散数学数据结构编译原理操作系统系统软件应用软件软件工程信息系统电子商务算法分析计算基础第一章：引论第一章：引论什么是编译程序编译过程概述编译程序的结构编译程序的生成1 11 1
3、什么叫编译程序什么叫编译程序程序翻译的两种方式：程序翻译的两种方式：一、编译程序：编译程序： 把高级语言源程序转换成低级语言目标语言程序，并且后者与前者逻辑上是等价的，这样的程序即为编译程序。二、解释程序：解释程序： 以源程序作为输入，但不产生目标程序，边解释边执行源程序的程序。编译程序的分类：编译程序的分类：诊断编译程序：诊断编译程序：专用于帮助程序开发和调试的编译程序。优化编译程序：优化编译程序：着重于提高目标代码效率的编译程序。交叉编译程序：交叉编译程序：产生不同于其宿主机的机器代码的编译程序。可变目标编译程序：可变目标编译程序：不需要重写编译程序中与机器无关的部分就能改变目标机的编译程
4、序。1 12 2 编译过程概述编译过程概述以中英文翻译为例，翻译所需步骤：1)识别出句子中的一个个单词识别出句子中的一个个单词.词法分析2)分析句子的语法结构分析句子的语法结构.语法分析3) 根据句子的含义进行初步翻译根据句子的含义进行初步翻译 .语义分析与中间代码产生4)对译文进行修饰对译文进行修饰.优化5) 写出最后的译文写出最后的译文.目标代码生成一、词法分析输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词。例 1.1 for (i=0;i He me a gave book上述语法规则中 He,me,book,gave,a 称为终结符号终结符号；，等称为非终结符号非终结
5、符号；是这个文法最终要定义的语法结构，称为开始符号开始符号； 这种书写形式称为产生式产生式。可以推导推导出句子：He gave me a book 是一个语法上正确的句子。推导方法：反复把规则中“”左边的成分替换成右边的成分。语法树终结符号：终结符号：是一个语言不可再分的基本符号，如：标示符、常数、算符、界符等。Hegavemeabook非终结符号：非终结符号：用来代表语法范畴，是由终结符号和非终结符号组成的符号串，如：表达式、语句、子程序、函数等。开始符号：开始符号：是一个特殊的非终结符号，代表语言中我们最感兴趣的语法范畴。产生式：产生式：也称规则，形式是：A形式上说，上下文无关文法形式上说
6、，上下文无关文法 G G 是一个四元式是一个四元式，其中，其中),(SVVNT是一个非空有限集，它的每个元素称为终结符号；是一个非空有限集，它的每个元素称为终结符号；TV是一个非空有限集，它的每个元素称为非终结符号，是一个非空有限集，它的每个元素称为非终结符号，和和不含公共不含公共NVTVNV的元素，即的元素，即 ；NTVV是一个非终结符号，称为开始符号，至少在某个产生式左部出现一次；是一个非终结符号，称为开始符号，至少在某个产生式左部出现一次；S 是一个产生式集合（有限）是一个产生式集合（有限） ，每个产生式的形式是，每个产生式的形式是* NVP,）（，其中，NTVVP若干个左部相同的产生式
7、，如21 PP. . . .nP可合并为一个产生式，缩写成：nP|.|21其中，每个称为 P 的一个候选式候选式。i例例 2.22.2：一个上下文无关文法： Ei|EAEA+|*推导与归约：推导：推导：使用产生式的右部取代左部的过程。是从开始符号开始，最终产生一个语言的句子。归约：归约：使用产生式的左部取代右部的过程。是从给定的句子开始，最终到达开始符号。* NTVVAA）（、是一个产生式，且仅当，即直接推出A如果，则称这个序列是的一个推导推导n.21n到1表示，从出发经 1 步或若干步可推导出n 11n表示，从出发经 0 步或若干步可推导出n*11n假定 G 是一个文法，S 是它的开始符号。
8、如果，则称是一个句型句型。* S仅含终结符号的句型是一个句子句子。文法 G 所产生的句子的全体是一个语言，记为 L（G） 词法分析器给出的输出为：通常将词法分析器作为子程序调用，而不将词法分析作为独立的一遍处理。3.23.2 词法分析器的设计词法分析器的设计（单词种别，属性值）预处理子程序输 入 缓冲区源程序扫描器 半扫描缓冲区半扫描缓冲区起点指示器搜索指示器符号表超前搜索：超前搜索：为了识别出相应的关键字，扫描器必须超前扫描多个字符，超前到能够肯定词性的地方为止。例 3.2：FORTRAN 源程序：1 DO99K=1，102 IF（5.EQ.M）I=103 DO99K=1.104 IF(5)
9、=55状态转换图：状态转换图：只包含有限个状态，其中一个是初态，初态，至少要有一个终态。终态。状态用圆圈表示，有向弧上的标记表示状态迁移时出现的字符。例例 3.33.3：12字母其它字母或数字*大多数程序语言的单词符号都可以用状态转换图进行识别。大多数程序语言的单词符号都可以用状态转换图进行识别。例例 3.43.4：构造一个简单语言的所有单词符号：单词符号单词符号种别编码种别编码助忆符助忆符内码值内码值DIM1$DIM-IF2$IF -DO3$DO-STOP4$STOP-END5$END-标识符6$ID内部字符串常数（整）7$INT标准二进制形式=8$ASSIGN-+9$PLUS-*10$ST
10、AR-I给出该语言的单词识别状态转换图。 II状态转换图的实现：每个状态对应一个程序。终态结点对应 return(code,value)int code，value； strToken=“”；GetChar(); GetBC();/*看字符是否为空格,若是则调用 GetChar()，直至为非空字符*/ if（IsLetter()）*11$POWER-，12$COMMA-（13$LPAR-）14$RPAR-while (IsLetter()|IsDigit() Concat(); GetChar(); Retract();/*回调一个字符位*/ code=Reserve();/*是否保留字*/
11、if(code=0) value=InsertId(strToken); return ($ID,value); else return(code,-); else if (IsDigit() while(IsDigit() Concat();GetChar(); Retract(); value=InsertConst(strToken); return($INT,value); else if(ch=)return($ASSIGN,-); else if(ch=+)return($PLUS,-); else if(ch=*) GetChar(); if(ch=*)return($POWER
12、,-); Retract(); return($STAR,-) else if(ch=;)return($SIMICOLON,-); else if(ch=()return($LPAR,-); else if(ch=)return($RPAR,-); else ProcError();3.33.3 正规表达式与有限自动机正规表达式与有限自动机正规文法、正规式、正规文法、正规式、DFADFA、NFANFA 在在接受语言能力接受语言能力上是上是互相等价的互相等价的。12)0空白数字3非数字4*数字5*=6*+1字母其它2*字母或数字10,11(13其它7非*8*9*正规式与正规集：正规式与正规集：
13、1) 和 都是上的正规式，它们所表示的正规集分别为和 ；2) 任何 a，a 是上的一个正规式，它所表示的正规集为a；3) 假定 U 和 V 都是上的正规式，它们所表示的正规集分别记为 L(U)和 L(V),那么，(U|V)、(UV)和(U)*也都是正规式，它们所表示的正规集分别为 L(U)L(V)、L(U)L(V)和(L(U)* 。仅由有限次使用上述三步骤而得到的表达式才是上的正规式正规式。仅由这些正规式所表示的字集才是上的正规集正规集。运算符的优先顺序为：*、 、|。DFA最小化NFA正规文法正规式例例 3.5:3.5: 有=a,b，则 正规式：对应的正规集：ba* 上以 b 为首后跟任意多
14、 a 的字。 a(a|b)*上以 a 为首的字。 (a|b)*(aa|bb)(a|b)*上所有含两个连续 a 或两个连续 b 的字。若两个正规式 U,V 所表示的正规集相同，则认为二者等价,记为 U=V。例 3.6：b(ab)*=(ba)*b,(a|b) *=(a*b*)* 令 U、V 和 W 均为正规式，有下列规律：U|V=V|UU|V=V|UU|(V|W)=(U|V)|WU|(V|W)=(U|V)|WU(VW)=(UV)WU(VW)=(UV)WU(V|W)=UV|UWU(V|W)=UV|UW(V|W)U=VU|WU(V|W)U=VU|WUU=U=UU=U=U确定有限自动机（确定有限自动机（
15、DFADFA）一个确定有限自动机 M 是一个五元式：，其中)F,s , S(M01) S 是一个有限集，它的每个元素称为一个状态。2) 是一个有穷字母表，它的每个元素称为一个输入字符。3)是一个从 S至 S 的单值部分映射。,s)a , s (4)是唯一的初态。Ss05)，是一个终态集（可空） 。SF 有限自动机有限自动机可以用状态转换矩阵状态转换矩阵表示。例例 3.73.7：有 DFA，其中为：3),0,b,a,(0,1,2,3M1)a , 0(2)b, 0(3)a , 1 (2)b, 1 (1)a , 2(3)b, 2(3)a , 3(3)b, 3(状态状态a ab b 0 012 1 132 2 213 3 333能识别上所有含有相继两个 a 或相继两个 b 的字。有限自动机有限自动机也可以表示成状态转换图。状态转换图。a|bbbaab0312a对于*中的任何字，若存在一条从初始态结点到某一终态结点的通路，且这条通路上所有弧的标记符连
