编译原理第一章绪论

1、编译原理编译原理山东科技大学信息学院张鹏张鹏v本课程主要内容涉及：本课程主要内容涉及：高级程序设计语言高级程序设计语言形式语言理论的基本概念形式语言理论的基本概念构造编译程序的基本概念、原理和技术构造编译程序的基本概念、原理和技术基于基于形式语言理论形式语言理论有关概念来讨论有关概念来讨论编译实现问题编译实现问题即：即： 编译原理编译原理=形式语言理论形式语言理论+ +编译技术编译技术1. 1. 主要内容主要内容2.2.编译理论与其他课程关系编译理论与其他课程关系编译理论编译理论自动机和形式语言离散数学数据结构操作系统信息的表示和组织信息的表示和组织 理论支持理论支持 控制对象控制对象高级语言

2、实施实施基础基础3.编译程序在计算机系统中的地位v编译系统是一种系统软件。软件：计算机系统中的程序及其文档。系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。和具体的应用领域无关，如编译系统和操作系统等。语言处理系统：把软件语言书写的各种源代码处理成可在计算机上执行的程序，如编译系统。裸机操作系统语言处理系统应用软件层计算机系统计算机系统v用于编译器编译器的设计v一般的软件设计：文本编辑器、自动排版、模式识文本编辑器、自动排版、模式识别、程序自动验证、程序自动调试、别、程序自动验证、程序自动调试、v程序格式化工具程序格式化工具：使程序呈现清晰的结构(Source

3、insight, Editplus)v编译原理在反病毒技术反病毒技术中的研究和应用 v交叉编译交叉编译技术：如嵌入式应用嵌入式应用v硬件描述语言硬件描述语言及其编译技术：如芯片设芯片设计v为计算机分析和理解自然语言提供参考为计算机分析和理解自然语言提供参考4.为什么要学习编译原理？5.课程考核方法v闭卷考试,同时作业完成情况和上机实践的结果占一定的比例。 v考试成绩 = v 80%考试成绩+考勤考勤和作业 （20%）v（1）编译原理（第二版），编译原理（第二版），清华大学出版社，张素琴，吕映芝等编著，2005。v（2）陈火旺等，程序设计语言编译原理程序设计语言编译原理 （第3版），国防工业出版

4、社，2000v（3 3）陈意云、张昱，编译原理编译原理，高等教育出版社， 2003v（4 4）编译原理及实践）编译原理及实践 冯博琴译 机械工业出版社 2000 年 3 月(lex and yacc 介绍，Tiny语言)6. 教材和参考书编译原理的经典书籍龙书，虎书，鲸书v龙书龙书(Dragon book)Alfred V.Aho, Ravi Sethi Jeffrey D .Ullman , Compilers:Principles, Techniques, and Tools, Addison-Wesly,1986 。v第二版已经出版。v国内教材的主要参考。英文第一版中文第一版红龙书本科教

5、学版 英文第二版中文第二版紫龙书英文第三版？绿龙书vAlfred VAho 哥伦比亚大学，美国科学与艺术学院及国家工程学院院士，曾获得IEEE的冯诺伊曼奖。 Jeffrey D. Ullman 斯坦福大学的计算机科学教授。杰出教育家，出版了15本著作，发表了170篇技术论文 v鲸书鲸书(Whale book)Steven S.MuchnickSteven S.MuchnickAdvanced Compiler Design and Advanced Compiler Design and ImplementationImplementationv高级编译器设计与实现 赵克佳译 机械工业出版社

6、2005年7月 v本书涵盖了现代微处理器编译器的设计和实现方面的所有高级主题。v深入阐述优化问题v虎书虎书(Tiger book)书名是：Modern Compiler Implementation Modern Compiler Implementation in Java/C+/ML, Second Editionin Java/C+/ML, Second Edition作者是：Andrew W.AppelAndrew W.Appel, with Jens Palsberg 现代编译原理-C语言描述 赵克佳译 人民邮电出版社 2006年4月 v书中专门提供了一个用C语言编写的实习项目，包括

7、前端和后端设计，可以在一学期内创建一个功能完整的编译器。 1.1 程序设计语言概述 程序设计语言：程序设计语言：用来编写计算机程序的语言。 JAVASCRIPT, ASP, PHP, PERL20其他面向特定应用领域的语言1互连网应用：HTML、XML2计算机辅助设计：MATLAB3集成电路设计：VHDL、Verilog4虚拟现实：VRML问题： 如何将形形色色的语言翻译成可以在计算机上运行的0、1串低级语言低级语言v在1940年左右，电子数字计算机刚出现，程序设计都是用机器语言（Machine Language） v机器语言机器语言：直接用计算机能够识别的二进制代码指令来编写程序的语言。由二

8、进制的指令代码组成。v1 + 3 1 + 3 表示为表示为 10000001 10000001 00000001 00000001 1000001110000011v属性：最底层的语言，不需要翻译就可以直接被计算机硬件识别。对应不同的计算机硬件有不同的机器语言。v特点：执行速度快，但编写程序的难度大，修改、调试不方便，直观性差，不易移植.v汇编语言汇编语言：又称为符号语言。与机器语言一一对应，采用能帮助记忆的英文缩写符号（指令助记符）来代替机器语言指令中的操作码，用地址符号来代替地址码。v用指令助记符及地址符号书写的指令称为汇编指令，用汇编指令编写的程序称为汇编语言源程序。v X+Y X+Y

9、表示为表示为 ADD X YADD X Yv机器不能直接识别汇编语言程序，必须把它翻译为机器语言程序才能执行。 汇编语言特点汇编语言特点v优点：优点：大大提高了编程的速度和准确度，人们至今仍在使用，在编码需要极快的速度和极高的简洁程度时尤为如此。v缺点：缺点：编写不容易，阅读和理解困难；严格依赖于特定的机器，为一种计算机编写的代码在应用于另一种计算机时必须完全重写。低级语言特点低级语言特点( (缺点缺点) )： 低级语言是依赖于具体的计算机硬件的语言，使用起来既繁琐又容易出错，程序不便于阅读和交流，实用性差。高级语言高级语言v高级语言高级语言：与具体的计算机硬件无关，是面向：与具体的计算机硬件

10、无关，是面向问题的程序设计语言，其表达方式接近于自然问题的程序设计语言，其表达方式接近于自然语言和数学语言，易于人们接受和掌握。语言和数学语言，易于人们接受和掌握。 v采用类似于采用类似于数学公式数学公式的书写方式：的书写方式：x x = 1 + 3 = 1 + 3v特点特点：独立于具体的计算机硬件，程序的编制：独立于具体的计算机硬件，程序的编制和调试方便，通用性和可移植性好。和调试方便，通用性和可移植性好。v在计算机执行之前，需要通过编译程序翻译成在计算机执行之前，需要通过编译程序翻译成目标语言程序，或需要通过解释程序边解释，目标语言程序，或需要通过解释程序边解释，边执行。边执行。v时间与空

11、间效率比较低。时间与空间效率比较低。 比较比较 机器语言机器语言汇编语言汇编语言高级语言高级语言硬件识别硬件识别是唯一可以识是唯一可以识别的语言别的语言不可识别不可识别不可识别不可识别是否可直是否可直接执行接执行 可直接执行可直接执行不可，需汇不可，需汇编、连接编、连接不可，需编译不可，需编译/ /解解释、连接释、连接 特点特点面向机器面向机器占用内存少占用内存少执行速度快执行速度快使用不方便使用不方便面向机器面向机器占用内存少占用内存少执行速度快执行速度快较为直观较为直观与机器语言与机器语言一一对应一一对应v面向问题面向问题/ /对象对象v占用内存大占用内存大v执行速度相对慢执行速度相对慢v

12、标准化程度高标准化程度高v便于程序交换，便于程序交换，使用方便使用方便 定位定位低级语言，极低级语言，极少使用少使用低级语言，低级语言，很少使用很少使用高级语言，种类多，高级语言，种类多，常用常用各级语言的比较各级语言的比较什么是编译程序v编译程序是现代计算机系统的基本组成部分。编译程序是现代计算机系统的基本组成部分。编译程序的功能：把高级语言程序翻译成等编译程序的功能：把高级语言程序翻译成等价的低级语言程序。价的低级语言程序。v源程序源程序( (称作源语言称作源语言) ) v目标程序目标程序( (称作目标语言称作目标语言) )编译程序高级语言源程序的执行通常分两个阶段:源程序(高级语言)编译

13、程序计算机目标程序(机器语言)编译阶段编译阶段初始数据目标程序计算机运行系统计算结果运行阶段运行阶段源程序源程序目标程序目标程序可执行程序可执行程序 编辑编辑 程序程序汇编或汇编或编译程序编译程序连接连接 程序程序用于编写高用于编写高级语言程序级语言程序把目标程序以及所需的功能库等转换成一个可执行的装入程序。完成此功能的程序叫连接程序。编译方式是将源程序整个地编译方式是将源程序整个地翻译成目标程序的方式。完翻译成目标程序的方式。完成此功能的程序叫编译程序。成此功能的程序叫编译程序。解释型的语言解释型的语言-脚本语言脚本语言 1.脚本语言脚本语言(JavaScript,VBscript等等)介于

14、介于HTML和和C, C+, Java, C#等编程语言之间。等编程语言之间。 HTML是格式化和链结文本。是格式化和链结文本。 编程语言通常用于向机器发出一系列复杂的指编程语言通常用于向机器发出一系列复杂的指令。令。 2.脚本语言与编程语言也有很多相似地方，其脚本语言与编程语言也有很多相似地方，其函数与编程语言比较相象一些。但是编程语函数与编程语言比较相象一些。但是编程语言的语法和规则更为严格和复杂一些言的语法和规则更为严格和复杂一些. v3. 脚本语言一般都有相应的脚本引擎（虚脚本语言一般都有相应的脚本引擎（虚拟机）来解释执行。比如：拟机）来解释执行。比如：JAVASCRIPT, ASP,

15、 PHP,PERL要解释器才能运行，都是要解释器才能运行，都是脚本语言。脚本语言。v4.脚本语言是一种解释性的语言脚本语言是一种解释性的语言, 不象不象cc+等可以编译独立执行的等可以编译独立执行的exe 文件。文件。v5.脚本语言代码一般都是以文本形式存在脚本语言代码一般都是以文本形式存在,类似于一种命令的序列。类似于一种命令的序列。编译和解释程序的运行方式：功能功能工作结果工作结果实现技术上实现技术上编译编译程序程序源程序的一个转换转换系统源程序的目标代码目标代码把中间代码转换成目标程序解释解释程序程序源程序的一个执行执行系统源程序的执行结果执行结果执行中间代码解释程序和编译程序的区别编译

16、相当于全文翻译，全部翻译完才执行。解释就相当于同声翻译，边翻译边执行。 特点：v1编译器：工作效率高，即时间快、空间省；交互性与动态特性差、可移植性差。大多数采用此种方法翻译；v2解释器：工作效率低，即时间慢、空间费；交互性与动态特性好、可移植性好。基本功能：二者相同；v所采用的技术：从翻译的角度来讲，两种方式所涉及的原理、方法、技术相似。注意：注意：v编译结果不一定编译成机器代码，只需要编编译结果不一定编译成机器代码，只需要编译成机器可以运行的代码，这里的机器也可译成机器可以运行的代码，这里的机器也可以是虚拟机。通常编译的结果是以是虚拟机。通常编译的结果是exeexe文件或文件或中间代码文件

17、。中间代码文件。vJavaJava可以看作是半编译半解释的语言，可以看作是半编译半解释的语言，通过通过把把javajava源代码编译成源代码编译成javajava虚拟机可以识别的虚拟机可以识别的字节码；字节码；再通过虚拟机解释执行，可以称作再通过虚拟机解释执行，可以称作是一种折中。是一种折中。vJavaJava虚拟机的初衷是因为虚拟机的初衷是因为跨平台跨平台而不是效率而不是效率的考虑。的考虑。 程序设计语言特点和发展程序设计语言特点和发展语言发展阶段语言发展阶段：1. 1.机器语言机器语言 0101码码 2.2.符号语言符号语言 汇编语言汇编语言3.3.高级语言高级语言 第一种高级语言-For

18、tranFortranFortran ：19531953年年1212月，月， IBMIBM公司程序师约翰公司程序师约翰巴科斯巴科斯(J. (J. Backus1924Backus1924年年1212月月3 3日日20072007年年3 3月月1717日）日） ：背景：背景：“程序设计相当昂贵，租借机器要花去好几百万，程序设计相当昂贵，租借机器要花去好几百万，而程序设计的费用却只多不少。而程序设计的费用却只多不少。” ” 1 9 5 41 9 5 4年年 ，第一个完全脱离机器硬件的高级语言，科学，第一个完全脱离机器硬件的高级语言，科学计算语言的计算语言的,“,“公式翻译语言公式翻译语言”( FO

19、Rmula ( FORmula TRANslatorTRANslator）, ,注重科学计算、注重执行效率注重科学计算、注重执行效率 . .19661966年，美国统一了它的标准，称为年，美国统一了它的标准，称为FORTRAN 66FORTRAN 66语言。语言。 4040多年过去，多年过去，FORTRANFORTRAN仍然是科学计算选用的语言仍然是科学计算选用的语言之一之一(Fortran 77(Fortran 77，Fortran 90/95 )Fortran 90/95 )。巴科斯因此获得了巴科斯因此获得了19771977年度年度“图灵奖图灵奖”。20042004年年5 5月，月，For

20、tran 2003Fortran 2003，FortranFortran语言新标准语言新标准 . .AlgolAlgol 60 60 ，1960 1960 年年, , 国际代数语言，首次引进了局部变量和国际代数语言，首次引进了局部变量和递归的概念。没有被广泛运用，但它演变为其他程序语递归的概念。没有被广泛运用，但它演变为其他程序语言的概念基础言的概念基础 COBOLCOBOL语言语言 ：面向商业的通用语言面向商业的通用语言(COmmon(COmmon Business Business Oriented Language) 1959Oriented Language) 1959年年5 5月，格

21、雷斯月，格雷斯. .霍波霍波（G.HopperG.Hopper）博士领导设计。）博士领导设计。正式发布于正式发布于19601960年年4 4月，称为月，称为Cobol-60Cobol-60， 最新最新COBOL 2002COBOL 2002。 仅有加、减、乘、除及乘方这五种简单的算术运算，不仅有加、减、乘、除及乘方这五种简单的算术运算，不适于适于科学计算科学计算。用在财会工作、统计报表、计划编制、。用在财会工作、统计报表、计划编制、情报检索、人事管理等数据管理及商业数据处理领域。情报检索、人事管理等数据管理及商业数据处理领域。 用用COBOLCOBOL写作的软件，要比其他语言多得多。只要写作的

22、软件，要比其他语言多得多。只要大型大型机机存在，存在，COBOLCOBOL就不会消失就不会消失 曾经产生巨大影响曾经产生巨大影响-“-“千年虫千年虫”（Y2KY2K）事件。）事件。 vBASICBASIC :1960年代中期，美国达特默斯学院(Dartmouth)约翰凯梅尼（J.Kemeny）和托马斯卡茨（T.Kurtz）认为，象FORTRAN那样的语言都是为专业人员设计，希望能为无经验的人提供一种简单的语言，非计算机专业的学会使用电脑。v 在简化FORTRAN语言的基础上，研制出一种“初学者通用符号指令代码”（Beginners All purpose Symbolic Intruction

23、 Code），简称BASIC。v基本BASICBASIC 只有17条语句，12个函数和3个命令，由于BASIC语言易学易用，很快成为最流行的语言之一。v经过不断改进后， 它一直沿用至今，出现了象QBASIC、VB、VB.net等新一代BASIC版本。结构化高级语言（结构化高级语言（1 9 7 01 9 7 0 ）PascalPascal：瑞士联邦技术学院尼克劳斯瑞士联邦技术学院尼克劳斯沃尔斯沃尔斯(N. (N. Wirth) Wirth) 教授教授发明了一种简单明晰的语言-PASCAL语言。PASCAL语言语法严谨，层次分明，程序易写，可读性好，是第一个结构化的编程语言。用作教学语言，系统程序

24、设计语言等。 后继语言Delphi。 Wirth Wirth 获获19841984年度年度“图灵奖图灵奖”。Pascal:法国著名的数学家、物理学家、 哲学家和散文家 C C 语言：语言：AT&TAT&T贝尔实验室的邓尼斯贝尔实验室的邓尼斯里奇里奇 (D.Ritchie(D.Ritchie) ) 和肯和肯汤姆森汤姆森(K. Thompson)(K. Thompson)，（里奇最初的贡献是开，（里奇最初的贡献是开发了发了UnixUnix操作系统）。操作系统）。 19701970年，作为年，作为UnixUnix的一项的一项“副产品副产品”，完成了，完成了C C语语言的开发（原型言的

25、开发（原型ALGOL 60ALGOL 60 ），为了用它编写），为了用它编写UnixUnix。这种语言结合了汇编语言和高级语言的优点，大受程这种语言结合了汇编语言和高级语言的优点，大受程序设计师的青睐序设计师的青睐 。 里奇用里奇用C C语言重写了语言重写了UNIXUNIX，使得，使得UNIXUNIX成为第一个成为第一个用高级语言写作的操作系统。正因为如此，用高级语言写作的操作系统。正因为如此，UNIXUNIX才才大为流行，因为大为流行，因为C C语言代码要比用机器码易读易懂，语言代码要比用机器码易读易懂，更方便地移植到任何机器上去。更方便地移植到任何机器上去。 19831983年度的年度的“

26、图灵奖图灵奖” ” 面向对象高级语言面向对象高级语言 SIMULA 67SIMULA 67: 20: 20世纪世纪6060年代开发的年代开发的SimulaSimula 67 67，它是面向对象语言的鼻祖。它将它是面向对象语言的鼻祖。它将AlgolAlgol 60 60中中的块结构向前推进了一大步，提出了对象的的块结构向前推进了一大步，提出了对象的概念。概念。 Smalltalk-80: Smalltalk-80: 是最有影响的面向对象的语言是最有影响的面向对象的语言之一。它丰富了面向对象的概念。该语言并之一。它丰富了面向对象的概念。该语言并入了入了SimulaSimula语言的许多面向对象的特

27、征，包语言的许多面向对象的特征，包括类和继承等。括类和继承等。 v C+ C+v比加尼比加尼斯楚士舒普斯楚士舒普 （Bjarne StroustrupBjarne Stroustrup） AT&T、贝尔实验室和ACM成员。 v 1979年，B. S开始开发一种语言，当时称为“C with Class”， 19831983年正式取名为年正式取名为C+C+，在经历了不断修订后，于在经历了不断修订后，于19941994年制定了年制定了ANSI ANSI C+C+标准的草案；标准的草案；v 1998年，ANSI/ISO C+标准建立，同年， B. S推出了其经典著作The C+ Program

28、ming Language的第三版。Python1. 1.PythonPython是一种面向对象的解释性的计算机程序设是一种面向对象的解释性的计算机程序设计语言，也是一种功能强大而完善的通用型语言；计语言，也是一种功能强大而完善的通用型语言；2.2.已经具有十多年的发展历史，成熟且稳定；已经具有十多年的发展历史，成熟且稳定；3.3.具有脚本语言中最丰富和强大的类库，足以支持具有脚本语言中最丰富和强大的类库，足以支持绝大多数日常应用；绝大多数日常应用；4.4.具有非常简捷而清晰的语法特点，适合完成各种具有非常简捷而清晰的语法特点，适合完成各种高层任务，几乎可以在所有的操作系统中运行。高层任务，几

29、乎可以在所有的操作系统中运行。vPythonPython的创始人为的创始人为Guido van RossumGuido van Rossum。19891989年圣诞节期间，在阿姆斯特丹，年圣诞节期间，在阿姆斯特丹，GuidoGuido为了打发圣诞节的无趣，决心开发一个新的为了打发圣诞节的无趣，决心开发一个新的脚本解释程序，做为脚本解释程序，做为 ABC ABC 语言的一种继承。语言的一种继承。之所以选中之所以选中 PythonPython（大蟒蛇的意思）作为（大蟒蛇的意思）作为程序的名字，是因为他是一个程序的名字，是因为他是一个Monty Monty PythonPython的飞行马戏团的爱好

30、者。的飞行马戏团的爱好者。v现在现在googlegoogle工作，工作， PythonPython是是googlegoogle的开发语言之一的开发语言之一 （C C，JavaJava）Python 优点优点vPythonPython是免费的是免费的vPythonPython是可移植的是可移植的 vPythonPython的强大功能的强大功能 vPythonPython的可扩展性：的可扩展性：PythonPython和和C C可以一起工可以一起工作。它可以嵌入到作。它可以嵌入到C C或者或者C+C+的应用程序当中的应用程序当中v PythonPython的简单性：语言的核心很小，语义和的简单性：

31、语言的核心很小，语义和样式非常简单。样式非常简单。 vJAVAv詹姆斯高斯林（James Gosling）等人于1990年代初开发。v最初被命名为Oak，用于解决诸如电视机、电话、闹钟、烤面包机等家用电器的控制和通讯问题。由于这些智能化家电的市场需求没有预期的高，Sun放弃了该项计划。v就在Oak几近失败之时，随着互联网的发展，Sun看到了Oak在计算机网络上的广阔应用前景，于是改造了Oak，在1995年5月以“Java”的名称正式发布了。 JavaJava伴随着互联网的迅猛发展而发展，逐伴随着互联网的迅猛发展而发展，逐渐成为重要的网络编程语言。渐成为重要的网络编程语言。 软件的发展2020世

32、纪世纪7070年代：因受益于结构化程序设年代：因受益于结构化程序设计，美国导弹预警系统达计，美国导弹预警系统达385385万句。万句。2020世纪世纪8080年代：借助软件工程的方法美年代：借助软件工程的方法美国航天飞机监控系统达国航天飞机监控系统达40004000万句。万句。 2020世纪世纪9090年代：可视化和面向对象的编年代：可视化和面向对象的编程语言，以其迅捷的编译速度、强大的程语言，以其迅捷的编译速度、强大的功能和易学灵活的特点功能和易学灵活的特点 。Windows 98有有1800万行代码；万行代码；Windows XP为为3500万行；万行；Windows Vista的代码行数

33、达到了的代码行数达到了5000万行。万行。 v2 2 高级语言的参数传递高级语言的参数传递v 过程（或函数）的定义和调用是程序设计语过程（或函数）的定义和调用是程序设计语言的主要特征之一，也是模块化程序设计的主要言的主要特征之一，也是模块化程序设计的主要手段和节省程序代码、扩充语言能力的主要途径。手段和节省程序代码、扩充语言能力的主要途径。v 过程（或函数）在定义之后就可以在程序的过程（或函数）在定义之后就可以在程序的其它地方调用它。调用与被调用者之间的信息交其它地方调用它。调用与被调用者之间的信息交流可以通过全局量或由参数传递来实现。流可以通过全局量或由参数传递来实现。v参数：参数：v形式参

34、数（定义）形式参数（定义）v实在参数（调用）实在参数（调用）程序设计语言中参数传递的实现 #include “stdio.h#include “stdio.h”int max(int x, intint max(int x, int y) /x y) /x和和y y称为形式参数，简称形参。称为形式参数，简称形参。 int int z; z; if (xy) z=x; if (xy) z=x; else z=y; else z=y; return(z return(z); ); void main()void main() int a,b,c int a,b,c; ; scanf(“%d%d”,

35、&a,&b scanf(“%d%d”,&a,&b); ); c=max(a,b c=max(a,b); /); /其中的其中的a a和和b b称为实在参数称为实在参数 printf(“max=%dn”,cprintf(“max=%dn”,c); ); v2 2 参数传递参数传递v参数传递分类参数传递分类(1) (1) 传地址传地址 (2)(2)传值传值 (3) (3) 传名字传名字 (4)(4)传结果传结果 除以上四种参数传递方法之外，还有其他参数传除以上四种参数传递方法之外，还有其他参数传递的方式。递的方式。 (1)(1)传地址传地址 把实在参数的地址传递给相

36、应的形式参数。把实在参数的地址传递给相应的形式参数。 过程（或函数）的每个形式参数都对应一个相应过程（或函数）的每个形式参数都对应一个相应的内存空间，称为形式单元。形式单元用来存放的内存空间，称为形式单元。形式单元用来存放相应的实在参数的地址。当调用一个过程（或函相应的实在参数的地址。当调用一个过程（或函数）时，调用段首先把数）时，调用段首先把实在参数的地址实在参数的地址传递到一传递到一个个临时设置的工作单元临时设置的工作单元中。中。 当程序转入被调用段之后，被调用段再把临时当程序转入被调用段之后，被调用段再把临时设置的工作单元中的实参地址取进自己相应的设置的工作单元中的实参地址取进自己相应的

37、形形式单元式单元中，中，过程（或函数）体对形式参数的任何过程（或函数）体对形式参数的任何引用或赋值都被处理成为引用或赋值都被处理成为对形式单元的间接访问对形式单元的间接访问，形参的值发生变化，等价于与之对应实参发生变形参的值发生变化，等价于与之对应实参发生变化。化。 在调用语句执行过程中完成下列操作：在调用语句执行过程中完成下列操作： 把实参把实参x x和和y y的地址分别传递到已准备好（由的地址分别传递到已准备好（由编译分配）的两个单元（编译分配）的两个单元（t1 t1和和t2t2）中；）中； s:=t1 s:=t1 且且 r:= t2r:= t2，使形参得到对应实参的地，使形参得到对应实参

38、的地址；址； 将将s s所指向的单元的内容（所指向的单元的内容（x x）与）与r r所指向的单所指向的单元的内容（元的内容（y y）相加，完成表达式）相加，完成表达式s+rs+r的计算；的计算； 将表达式将表达式s+rs+r的运算结果送到的运算结果送到s s所指的内存单所指的内存单元（元（x x）中；）中； 返回主程序。返回主程序。 (2) (2)传值传值 把实在参数的值计算出来传递给相应的形把实在参数的值计算出来传递给相应的形式参数。式参数。 v 最简单的参数传递方式，工作过程：最简单的参数传递方式，工作过程：v调用段（）调用段（）把实在参数的值计算出来把实在参数的值计算出来, ,被调用被调

39、用段（函数）段（函数）能能取取到。到。v 被调用段被调用段（函数）（函数）开始工作时，首先把这些开始工作时，首先把这些值抄进自己的形式单元，然后跟使用值抄进自己的形式单元，然后跟使用局部量局部量一样使用这些形式单元。一样使用这些形式单元。v在上面关于传地址的例子中，如果把过程add的首部说明改为：vprocedure add( s: integer; r: integer);program example(outputprogram example(output); ); var varx,y:integerx,y:integer; ;procedure add(s: integer; var

40、procedure add(s: integer; var r: integer); r: integer); begin begins:=s+rs:=s+r; ; end; end; begin beginx:=0;x:=0;y:=2;y:=2;add(xadd(x, y);, y);writeln(xwriteln(x=,x)=,x) end. end. 传值方式参数传递传值方式参数传递 , ,被调用段无法改变实参的值被调用段无法改变实参的值 . .(3) (3) 传名字传名字vALGOL语言使用，传名字参数的意义：v过程调用相当于把被调用段的过程体抄到调用出现的地方，但把其中任一出现的形

41、参都替换成相应的实参（文字替换）。v替换时发现过程体中的局部名和实参中的名字不能重名 。例如，下面的ALGOL过程：procedure swap(M,N);integer M,N;begininteger L; L:=M; M:=N; N:=L;end;过程调用swap(K(I),K(J)采用传名方式进行参数传递，相当于执行了下面的语句： L:= K(I);K(I):= K(J); K(J):=L; (4) (4)传结果传结果 每个形参（函数头）对应有每个形参（函数头）对应有两个两个单元单元，第一个存放，第一个存放实参的地址实参的地址，第二个存，第二个存放放实参的值实参的值。 过程体中对形参的

42、任何引用都是对它的过程体中对形参的任何引用都是对它的第第二个单元的直接访问二个单元的直接访问。返回前把第二个单。返回前把第二个单元的内容放到第一个单元所指的实参单元元的内容放到第一个单元所指的实参单元中。中。1.2 编译过程概述v编译器内部包括了许多步骤称为编译器内部包括了许多步骤称为阶段阶段，它们执行不同的它们执行不同的逻辑操作逻辑操作。v将这些阶段设想为编译器中一个个单独将这些阶段设想为编译器中一个个单独的片断是很有用的，尽管在应用中它们的片断是很有用的，尽管在应用中它们是经常组合在一起的，但它们的代码是是经常组合在一起的，但它们的代码是单独来编写的。单独来编写的。 将编译过程划分成将编译

43、过程划分成词法分析、语法分析、词法分析、语法分析、语义分析、中间代码生成、代码优化和目语义分析、中间代码生成、代码优化和目标代码标代码生成六个阶段。生成六个阶段。 事实上某些阶段可以组合在一起。事实上某些阶段可以组合在一起。 另外还有两个重要的工作：另外还有两个重要的工作：表格管理和错表格管理和错误处理误处理，它们与编译各个阶段都有联系。，它们与编译各个阶段都有联系。词法分析词法分析语法分析语法分析语义分析语义分析目标代码生成目标代码生成中间代码生成中间代码生成代码优化代码优化目标程序目标程序源程序源程序出出 错错 处处 理理表表 格格 管管 理理英译与编译的比较1. 1.识别出句子中的单字识

44、别出句子中的单字- -词法分析词法分析2.2.分析句子的语法结构分析句子的语法结构- -语法分析语法分析3.3.初步翻译句子的含意初步翻译句子的含意- -语义分析和中间代码语义分析和中间代码生成生成4.4.译文修饰译文修饰- -优化优化5.5.写出最后译文写出最后译文- -目标代码生成目标代码生成1 1 词法分析词法分析 词法分析阶段是编译过程的第一个阶段。词法分析阶段是编译过程的第一个阶段。 单词单词是指逻辑上紧密相连的一组字符，这些字符是指逻辑上紧密相连的一组字符，这些字符具有集体含义具有集体含义. .v比如比如标识符标识符是由字母字符开头，后跟字母、数字字是由字母字符开头，后跟字母、数字

45、字符的字符序列组成的一种单词符的字符序列组成的一种单词; ;v保留字保留字（也称关键词或基本字）是一种单词（也称关键词或基本字）是一种单词; ;v此外还有此外还有算符、常数和界符算符、常数和界符（标点符号、左右括号（标点符号、左右括号等）等等。等）等等。 输入：源程序输入：源程序输出：标准单词输出：标准单词任务：从左到右一个字符一个字符的读入源程任务：从左到右一个字符一个字符的读入源程序，对构成源程序的字符串进行扫描和分解，序，对构成源程序的字符串进行扫描和分解，从而识别出一个个单词（也称单词符号）。从而识别出一个个单词（也称单词符号）。方法：状态图；方法：状态图；DFADFA；NFANFA

46、词法分析程序词法分析程序示例示例FOR K := 1 TO 100FOR K := 1 TO 100 M := I + 10 M := I + 10 * * K K N := J + 10 N := J + 10 * * K KNEXT KNEXT KTOTONEXTNEXTFORFOR K KN NM MI IJ JK KK KK K:=:=100100:=:=:=:=1 110101010+ +* * *+ +保留字保留字标识符标识符分界符分界符运算符运算符常数常数C源程序片断： int a; a = a + 2;词法分析后可能返回:单词类型单词类型 单词值单词值保留字 int标识符(变量

47、名) a界符 ;标识符(变量名) a算符(赋值) =标识符(变量名) a 算符(加) +整数 2界符 ；有关术语v词法分析(lexical analysis or scanning) -The stream of characters making up a source program is read from left to right and grouped into tokens, which are sequences of characters that have a collective meaning.v单词-tokenv保留字-reserved wordv标识符 -ident

48、ifier(user-defined name)2 2 语法分析语法分析 在编译程序的实际实现中语法分析和语义处在编译程序的实际实现中语法分析和语义处理常常是组合在一起的。称为语法制导翻译。理常常是组合在一起的。称为语法制导翻译。 输入：标准单词输入：标准单词输出：各类语法短语输出：各类语法短语任务：在词法分析的基础上将单词序列任务：在词法分析的基础上将单词序列分解成分解成各各类语法单位，如类语法单位，如“表达式表达式”、 “ “语句语句”、“程程序序”等等。等等。 方法：递归子程序法、方法：递归子程序法、LRLR分析法、优先分析法。分析法、优先分析法。v语法分析所依据的是语言的语法规则语言的

49、语法规则，即描述程序结构的规则。通过语法分析确定源程序是否构成一个语法上正确语法上正确的程序。v程序的结构通常是用递归规则递归规则表示的，例如我们可以用下面的规则来定义表达式表达式：v（1）任何标识符是表达式；v（2）任何常数（整常数、实常数）是表达式；v（3）若e1和e2都是表达式，那么，e1+e2 ，e1*e2 ，(e1)也都是表达式。 语法分析规则规则 := “:=”“:=” := “+” := “*” := “(”“)” := := := 赋值语句标识符表达式表达式+表达式表达式标识符整数标识符:=表达式*赋值语句的树形结构语句id1:= id2 + id3* 10的语法树v类似地，语

50、句也可以递归定义，如：（1）标识符 := 表达式 是语句（2）while 表达式 do 语句 （3）if（表达式then 语句 else 语句 都是语句。示例示例TOTONEXTNEXTFORFORK KN NM MI IJ JK KK KK K:=:=100100:=:=:=:=1 110101010+ +* * *+ +变量、常数及其运算结果均是表达式变量、常数及其运算结果均是表达式表达式表达式表达式表达式表达式表达式表达式表达式表达式表达式表达式表达式赋值句的形式为赋值句的形式为“变量：表达式变量：表达式”赋值句赋值句赋值句赋值句多个赋值句可构成语句块多个赋值句可构成语句块语句块语句块表

51、达式可作为循环的初值和终值表达式可作为循环的初值和终值初值初值终值终值简单数值变量可作为循环的控制变量简单数值变量可作为循环的控制变量控制变量控制变量控制变量控制变量此时可以看出上述结果符合循环语句此时可以看出上述结果符合循环语句的语法定义，故语法分析成功完成的语法定义，故语法分析成功完成术语术语v语法分析语法分析( (syntax analysissyntax analysis or or parsing parsing)( )(剖析剖析, ,分解）分解） The purpose of syntax analysis is to determine the The purpose of sy

52、ntax analysis is to determine the source programs phrase structure. This process is source programs phrase structure. This process is also called also called parsingparsing. . The source program is parsed to check whether it The source program is parsed to check whether it conforms to the source lan

53、guages syntax, and to conforms to the source languages syntax, and to construct a suitable representation of its phrase construct a suitable representation of its phrase structure.structure.语法树语法树( (推导树推导树)( )(parse treeparse tree or or derivation treederivation tree) )3 3 语义分析语义分析语义审查语义审查( (静态语义静态语

54、义) )v按照语法树的层次关系和先后次序，逐个语句按照语法树的层次关系和先后次序，逐个语句地进行语义处理。地进行语义处理。v主要任务：主要任务： 进行类型审查，审查每个算符是否进行类型审查，审查每个算符是否符合语言规范，不符合时应报告错误。符合语言规范，不符合时应报告错误。类型匹配类型匹配类型转换类型转换例:Program p(); Var rate:real; procedure initial; position := initial + rate * 60 /* error */ /* error */ /* warning */;v语义分析是在语法分析程序确定出语法单位后，审语义分析是

55、在语法分析程序确定出语法单位后，审查有无查有无语义错误语义错误，并为代码生成阶段收集类型信息。，并为代码生成阶段收集类型信息。v例如进行例如进行类型检查类型检查，检查每个算符是否具有语言规，检查每个算符是否具有语言规范允许的运算对象，当不符合语言规范时，编译程范允许的运算对象，当不符合语言规范时，编译程序应报告错误。序应报告错误。v再如，有的编译程序不允许实数作为数组下标。再如，有的编译程序不允许实数作为数组下标。v又如，某语言规定可进行强制类型转换，当二目运又如，某语言规定可进行强制类型转换，当二目运算施于一整型数和一实型数时，编译程序应该将整算施于一整型数和一实型数时，编译程序应该将整型数

56、转换成实型数而不能认为源程序发生类型错误。型数转换成实型数而不能认为源程序发生类型错误。例: Program p(); Var rate:real; Var initial :real; Var position :real ; position := initial + rate * 60 60为整数，其余量为实数。语义分析插入语义处理结点的语法树60:=+*Id1 positionId2 initialId3 rateinttoreal术语v语义分析(semantic analysis) The parsed program is further analyzed to determine

57、 whether it conforms to the source languages contextual constraints: scope rules, type rulese.g. To relate each applied occurrence of an identifier in the source program to the corresponding declaration. 4 4 中间代码生成中间代码生成 中间语言或称中间代码，是一种结构简单、中间语言或称中间代码，是一种结构简单、含义明确的记号系统。是编译程序使用的内含义明确的记号系统。是编译程序使用的内部表示

58、形式。部表示形式。输入：句子输入：句子输出：中间代码序列输出：中间代码序列任务：将各类语法单位，如任务：将各类语法单位，如“表达式表达式”、 “ “语语句句”、“程序程序”等翻译为中间代码序列。等翻译为中间代码序列。 中间代码的形式：常见的有四元式、三元式和中间代码的形式：常见的有四元式、三元式和逆波兰式等逆波兰式等 方法：语义子程序；方法：语义子程序；DAGDAG图，语法制导翻译图，语法制导翻译v四元式的形式为：四元式的形式为：v（算符，运算对象（算符，运算对象1 1，运算对象，运算对象2 2，结果）；，结果）；v对于源程序对于源程序sum:= first + count sum:= fir

59、st + count * * 10 10可以生成如下可以生成如下所示的四元式：所示的四元式：（1 1） (inttoreal(inttoreal , 10 , , 10 , , t1), t1)（2 2） ( ( * * , id3 , t1 , t2 ) , id3 , t1 , t2 ) （3 3） ( + , id2 , t2 , t3 )( + , id2 , t2 , t3 )（4 4） ( := , t3 , ( := , t3 , , id1 ) , id1 )vid1id1、id2id2、id3id3分别表示分别表示sumsum、firstfirst、countcount的机器

60、内的机器内部表示；部表示；vt1 t1、t2t2、t3t3是临时生成的名字，表示中间运算结果。是临时生成的名字，表示中间运算结果。t1 t1，t2t2，t3t3是是临时变量临时变量id2id2id1id1id3id3中间代码生成(intermediate code generation) This is where the intermediate representation of the source program is created. We want this representation to be easy to generate, and easy to translate into the target program. Th