编译原理与技术.ppt

1、1,编译原理与技术,西安电子科技大学 软件工程研究所 刘坚,2,教学内容与要求, 内容 本课程的内容是建立在本科基础上的，尽量避免重复本科已有的内容。 为了整个课程的一致性，而且由于学习方法的螺旋式特性，一些已学过的内容也会有所涉及，但会在原有基础上提高一步。重点放在本科课程中没有涉及的领域。 主要介绍如下内容，并在兼顾理论与实现两个方面上进行讨论。,编译程序编写工具-lex和yacc：学会使用lex和yacc进行程序设计； 词/语法分析器核心算法：有限自动机的有效构造算法和LALR（1）分析器的构造算法； 语法制导翻译：属性、L属性的自下而上计算；,3,教学内容与要求（续1）,类型检查：类型

2、理论的发展、类型与类型检查、多态处理、封装与继承的实现技术等，类型系统的形式化方法简介； 动态语义：指称语义入门，原理及其应用； 代码优化：局部与循环优化，全局数据流分析技术。, 要求,做适当作业，期末统一收缴一次，并进行一次作业讲解（在课程总复习中进行）。作业要求独立做（不计分）；也可以不做，但不要抄；若合作做，则几个人合交一份。 做上机作业，实现一个Pascal子集编译程序的全过程：两个学生一组，可以采用任何类似的Lex/Yacc工具。上机作业计分（15左右），重点考核上机报告和完成的软件。 期终考试：闭卷考试。严格要求（按真实成绩给分） 适当读参考文献。 选一个课代表。,4,参考文献,A

3、.V.Aho，J.D.Ullman，“The Theory of Parsing，Translation，and Compiling，Volume I：Parsing，” Prentice-Hall Inc. 1972 A.V.Aho，J.D.Ullman，“The Theory of Parsing， Translation，and Compiling，Volume ：Compiling，” Prentice-Hall Inc. 1973 人民邮电出版社， Aho等， “编译原理 技术与工具”（影印版）（主要参考书，可作教材，上机作业题目） 高等教育出版社，Andrew W.Appel，“现

4、代编译程序实现Java语言”（影印版） 机械工业出版社，Steven S.Muchnick，“高级编译器设计与实现” （影印版）, 编译的相关理论与技术,5,参考文献（续）, 程序设计语言原理与设计,R.W.SebestaConcepts of Programming Languages,机械工业出版社（影印版） Terrence W.Pratt, Marvin V.Zelkowitz Programming Languages - Design and Implementation, third edition, Prentice-Hall International, Inc. 1996

5、David A. Watt “Programming Language Syntax and Semantics，”Prentice Hall Inc. 1991, 编译器构造 Axel T.Schreiner, H.George Friedman, Jr. Introduction to Compiler Construction with UNIX, Prentice Hall，Englewood Cliffs,NJ07632，1985 杨作梅译，(Jobn R.Levine, Tony Mason 并把上述语句存放在一个字符串sql_stmt中。而系统提供下述机制： EXEC SQL P

6、REARE s FROM :sql_stmt; EXEC SQL EXECUTE s .;,DBMS的处理方法是：在运行系统中嵌入一段解释程序，它首先对sql_stmt进行分析（检查是否语法语义正确），形成串s的中间表示，然后执行s，从而实现动态查询。若 sql_stmt=“EXEC SQL SELECT name, amount FROM f_table WHERE term12” 则最后结果是查出所有存期大于一年的人的姓名和帐号。,16,1.4 程序设计语言的语法与语义,编译器的设计与实现，首先是对所要进行编译的语言进行描述，只有精确地描述语言，才能有效地实现语言。 完整的程序设计语言，包

7、括两部分描述：语法（syntax）和语义（semantics）描述。,1.4.1 语法 程序设计语言的语法可以用上下文无关文法（Context-free Grammar，CFG）描述，它是一种很好的描述方法，而且已有很成熟的技术构造十分有效的上下文无关文法的分析器，因此可以利用工具自动生成这类语法分析器。 由于程序设计语言的语法是决定程序基本特性（如可读性、可维护性、可编译性等）的基础，因此程序设计语言语法设计的好坏就成为程序设计语言好坏的重要因素之一。 随着程序设计语言的发展，语法的设计也形成了一些公认的准则,下述是一些典型的例子。,17,1.4.1 语法（续）, 自由书写格式：FORTRA

8、N、LEX/YACC都不是自由书写格式。 设立保留字： PL/1中：IF THEN THEN THEN=ELSE; ELSE ELSE=THEN 符合科学的、或历史形成的习惯性描述： C/C+中：a=b和a=b 其他语言：a:=b和a=b 避免超前扫描： FORTRAN：DO 5 I = 1.25 (1) DO 5 I = 1, 25 (2) 对于DO5I = 1.25;要超前扫描到.时才确定是赋值句。 对于DO 5 I = 1,25;要超前扫描到,时才确定是循环语句。 减少可能的书写错误： C的注释：/* this is a comment */ C+的注释：/ this is a comm

9、ent 大小写不敏感：Pascal、Ada等大小写不敏感，而C是敏感的。,18,1.4.2 语义,语义用于确定语言的意义，一般被分为两类：静态语义（static semantics）和动态语义（run-time semantics）。, 静态语义 静态语义主要是为了解决上下文无关文法不能应付的问题，它实际上是一组上下文限制（Contextual Restrictions，有些文献中就是把静态语义称为上下文限制），用来确定语法上正确的程序是否实际上也是有意义的。静态语义主要用于检查：,被引用的标识符是否被说明; 运算符和操作数是否类型兼容，操作数之间是否类型兼容等； 过程调用时参数的个数及类型是

10、否与过程定义时的相容，等等。,19,1.4.2 语义（续）, 动态语义 动态语义用来规定程序做什么，也就是如何动作。,原理上讲，无论是语法还是语义，均应进行形式化的描述。但是由于种种原因，语言的文本往往是对文法进行形式化描述，而对语义进行非形式化的描述，带来的问题是不能精确描述语义。,20,1.4.3 为什么要精确定义语义,对于一个语言的定义，一定要严格、准确，否则就不可能写出精确反映该语言实际意义的编译程序。,例1.2 对于语句： L： goto L; 一般语言定义中只是简单说goto语句的作用是把控制转向其所指的标号所在位置。如果这样看，上述语句就是合法的。但是很明显，一旦程序执行起来就会

11、陷入死循环，永不停机。 在这种情况下，上述语句应该是非法的。在实际处理上，有的编译程序禁止这样的goto语句，而有的编译程序却不与理睬。,例1.3 对于Pascal语句：（i0） and （k div i 10） 该语句的语法完全正确，但是当语句被执行时，情况就不同了。考虑i=0的情况下，若编译时对条件语句采用的是短路计算，语句就可以正确执行; 若不采用短路计算，则会出现致命错误（0作为除数）。 但在原始的Pascal定义中，对是否采用短路计算并没有明确规定，因此有的编译程序采用短路计算，而有的不采用。,21,2005年2月25日（第一次课）,22,1.4.3 为什么要精确定义语义（续）,从某

12、种意义上讲，编译器本身实际上起着定义语言的作用。即对于某种语言，编译器选择如何接受和翻译该语言。这就使得一段程序在一个机器上可以正确运行，在另一个机器上就不可以，而这恰恰违背了通用程序设计语言的初衷。,23,1.4.4 语义的形式化描述,语义的形式化描述至少在下述三个方面起重要作用： 精确描述语义 程序的正确性验证 程序自动生成, 静态语义 静态语义形式化描述最常采用的是属性文法（attribute grammars），它实际上是为产生式中的符号扩充属性。因此，也可以认为属性文法是对上下文无关文法的扩充，二者结合起来，完整地定义出合法的程序。 由于属性文法对静态语义的描述并不是独立的，需要与文

13、法捆绑在一起，因此被认为是半形式化的描述。 静态语义的形式化描述，特别是类型系统的形式化描述，是当前的一个研究热点。 下边来看两个属性文法的例子。,24, 静态语义（续）,例1.4 对于产生式EE1+E2，我们可以为E添加属性E.type（类型）、E.val（值）等，然后，可以对属性进行下述计算： if E1.type=integer and E2.type=integer then E.type:=integer; gen(+,E1.val, E2.val, E.val); else E.type=type_error;,例1.5 SL1 : goto L2; 引入属性.val，则： if

14、L1.val = L2.val then S.type := type_error else gen(jmp, , , L2.val);,上述两个例子中，可以看出，不管是.type还是.val，一般均是静态可确定的（对于静态可编译语言来说），因此可以采用属性文法的方式来描述这些语义。 但是对于表达式的动态特性，此描述方法就失效了。例如x+y的结果超出了计算机的表示范围，或者是x/y在运行时y的值为0等。,25, 动态语义,动态语义的形式化描述没有静态语义成熟。多年来人们也一直在动态语义形式化描述的领域中进行研究。比较典型的形式化描述方法包括： 操作语义（operational or interpreter modes） 公理语义（Axiomatic definitions） 指称语义（Denotational modes） 其中指称语义得到较多的关注。从某种意义上讲，指称语义也可以被认为是对上下文无关文法的扩充，或者是一种语法制导