编译原理第1章

第一章引论课程简介、编译程序的基本概念、典型的编译过程§1.0课程简介课程基本信息课程中文名称：编译原理课程英文名称：CompilePrinciple课程主要内容：编译程序的工作原理与开发设计方法课程类别：必修适用专业：信息工程学院计算机科学与技术专业总学时：48学时（其中理论40学时，上机8学时）总学分：3§1.0课程简介本课程在教学计划中的地位、作用和任务计算机科学与技术专业高年级学生的专业必修课。先修课程：程序设计方法、高级程序设计语言(PASCAL、C、…)、数据结构、离散数学等。作用和任务专业素质与能力的训练与培养；从事与编译系统相关的工作；提高软件开发的能力；一个难度很大的系统软件的实例；大量实用的工具和方法；考研需要。§1.0课程简介三、参考书：1.《编译原理》（原版名：CompilerPrinciples,Techniques,andTools）阿霍（Aho,A.V.）等著，李建中等译机械工业出版社（龙书）2.《现代编译原理-C语言描述》（原版名：ModernCompilerImplementationinC）AndrewW.Appel等著，陈明译电子工业出版社（虎书）3.《高级编译器设计与实现》（原版名：

AdvancedCompilerDesignandImplementation）StevenS.

Muchnick等著机械工业出版社（鲸书）理论技术实现§1.1什么是编译程序§1.1什么是编译程序翻译程序：把源语言程序逻辑等价的转换成目标语言程序的程序；编译程序：源语言是高级语言，目标程序是低级语言的翻译程序；编译程序的分类诊断编译程序：用于帮助程序开发和调试；优化编译程序：着重于提高目标代码的效率；交叉编译程序：运行编译程序的计算机为宿主机，运行编译程序所产生的目标代码的计算机为目标机，如果编译程序产生不同于其宿主机的机器代码，称为交叉编译程序；可变目标编译程序：若不需重写编译程序中与机器无关部分就能改变目标机，则该编译程序为可变目标编译程序；§1.2编译程序工作过程§1.2编译程序工作过程自然语言的翻译过程：编译程序的工作过程：

§1.2编译程序工作过程词法分析（扫描程序）任务：输入源程序，对构成源程序的字符串扫描和分解，识别出其中的单词（如标识符、常数、算符、界限符等）；输入：源程序字符串；输出：单词串，也就是等长的内部形式（即属性字）；依据：词法规则；词法规则的研究和描述工具：正规式、自动机；例：C语言源程序片段inta;a=a+3;词法分析后结果如右图

单词类型 单词值保留字

int标识符

a界符

;标识符

a算符

=标识符

a算符

+整数

3界符

;

§1.2编译程序工作过程语法分析（识别程序）任务：在词法分析的基础上，把单词符号串分解成各类语法单位（语法范畴），并确定整个输入串是否构成语法上正确的程序；输入：单词符号串；输出：语法单位（语法树）；依据：语法规则；语法规则的描述：上下文无关文法，下推自动机；例：id1=id2+id3*10的语法树赋值语句id1表达式表达式id2id310=+*=+*=+§1.1什么是编译程序语义分析与中间代码生成任务：分析各类语法范畴的含义，进行静态语义检查（类型检查、控制流检查、一致性检查和相关名字检查）并进行初步翻译；输入：语法树或中间表示输出：中间代码（四元式）；依据：语义规则；语义规则的描述：属性文法。例：语义分析类型检查，有错误吗？

inta,*p; a=10; p=a;§1.2编译程序工作过程中间代码中间代码是一种独立于具体硬件的记号系统，或者与现代计算机的指令形式有某种程度的接近，或者能比较容易地变换成机器指令。中间代码主要有三元式、间接三元式、逆波兰记号、树形表示，常用的中间代码是四元式。例1：id1=id2+id3*50的四元式

(1) (inttoreal 50 - t1) (2) (* id3 t1 t2) (3) (+ id2 t2 t3) (4) (= t3 - id1)§1.1什么是编译程序优化对中间代码进行加工变换，以期在最后阶段产生更高效的目标代码；输入：优化前的中间代码；输出：优化后的中间代码；依据：程序的等价变换规则；常用技术：基本块优化、循环优化等。例：id1=id2+id3*50的四元式优化处理

(1) (inttoreal 50 - t1) (2) (* id3 t1 t2) (3) (+ id2 t2 t3) (4) (= t3 - id1)优化结果：

(1) (* id3 60.0 t1) (2) (+ id2 t1 id1)§1.1什么是编译程序目标代码生成

任务：把优化后的中间代码变换成特定机器上的低级语言代码（目标代码）；输入：中间代码；输出：目标代码；依据：硬件系统的结构和机器指令的含义；目标代码种类：绝对指令代码：目标代码可立即执行；汇编指令代码：需汇编器汇编之后才能运行；可重定位的指令代码：必须借助连接转配程序把各个模块连接在一起，确定变量（或常数）在内存的位置，转入内存中指定的起始地址，使之成为可运行的绝对指令代码程序；§1.2编译程序工作过程例：生成汇编指令代码

(1) (* id3 60.0 t1) (2) (+ id2 t1 id1)汇编代码如下：

movfid3,R2

mulf #60.0,R2

movfid2,R1

addfR2,R1

movfR1,id1§1.1什么是编译程序§1.3编译程序的结构编译程序总框符号表§1.3编译程序的结构表格与表格管理：

用各类表格登记源程序的各类信息和编译各阶段的进展情况，在编译的各阶段都涉及到构造、查找、更新有关的表格；出错处理： 由专门的一组出错处理程序发现源程序中的错误并将错误信息报告给用户；遍（Pass）

对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。通常每“遍”的工作从外存上获得前一遍的中间结果开始，完成所含的有关工作，直到结果纪录与外存为止；§1.3编译程序的结构编译前端与后端 编译过程中与源语言有关与目标机无关的部分称为编译前端，通常包括词法分析、语法分析、语义分析与中间代码生成，有的代码优化工作也可包括在前端。后端包括编译程序中与目标机有关的部分，如与目标机有关的代码优化和目标代码生成；§1.3编译程序的结构§1.4编译程序与程序设计环境

程序设计环境 编译程序、编辑程序、连接程序、调试工具等支持程序设计人员进行程序开发的工具；IDE

将相互独立的程序设计工具集成起来，形成程序的集成开发环境。如：TurboPascal、TurboC、VisualBasic、VisualC++、Delphi……§1.4编译程序与程序设计环境§1.5编译程序的生成

T形图：

表示源语言（S）、目标语言（T）、编译程序实现语言（I）之间的关系；

§1.5编译程序的生成1）交叉编译(CrossCompiling)/移植问题一：A机上有一个C语言编译器，是否可利用此编译器实现B机上的C语言编译器？条件：Ａ机有Ｃ语言的编译程序目的：实现Ｂ机的Ｃ语言的编译1.

(人)用Ｃ语言编制B机的Ｃ编译程序P0(C→B)(Ａ机的C编译P1)编译P0，得到在A机上可运行的P2(C→B)Ｃ语言Ｃ语言Ｂ机器Ｃ语言Ａ机器A机器Ｃ语言A机器Ｂ机器P0P1P2§1.1什么是编译程序3.(Ａ机的P2)编译P0，得到在B机上可运行的P3(C→B)Ｃ语言Ｂ机器Ｂ机器P3Ｃ语言Ｃ语言Ｂ机器Ｃ语言Ａ机器A机器Ｃ语言A机器Ｂ机器P0P1P2P2Ｃ语言Ａ机器Ｂ机器Ｃ语言Ｃ语言Ｂ机器P0获得一个工具§1.1什么是编译程序2)本机编译器利用问题二：A机上有一个C语言编译器，现要实现一个新语言NEW的编译器？能利用交叉编译技术么？用C编写NEW的编译，并用C编译器编译它NEW语言Ｃ语言A机器Ｃ语言Ａ机器A机器NEW语言A机器A机器P0(编写)P1(原有)P2(生成)NEW语言Ｃ语言A机器Ｃ语言Ａ机器A机器NEW语言A机器A机器P0(编写)P1(原有)P2(生成)NEW语言Ｃ语言A机器Ｃ语言Ａ机器A机器NEW语言A机器A机器P0(编写)P1(原有)P2(生成)NEW语言Ｃ语言A机器Ｃ语言Ａ机器A机器NEW语言A机器A机器P0(编写)P1(原有)P2(生成)NEW语言Ｃ语言A机器Ｃ语言Ａ机器A机器NEW语言A机器A机器P0(编写)P1(原有)P2(生成)§1.1什么是编译程序问题三：直接在一个机上实现C语言编译器，还有别的技术么？解决：用汇编语言实现一个Ｃ子集的编译程序(P0—人)用汇编程序处理该程序,得到P2(P2:可直接运行)用Ｃ子集编制Ｃ语言的编译程序(P3—人)用P2编译P3，得到P43)编译程序的自展技术§1.1什么是编译程序4.用P2编译P3，得到P4Ｃ语言机器语言机器语言P4Ｃ子集汇编语言机器语言P01.用汇编语言实现一个Ｃ子集的编译程序(P0—人)汇编语言机器语言机器语言Ｃ子集机器语言机器语言P1P22.用汇编程序(P1)处理该程序,得到P2(P2:可直接运行)P2Ｃ子集机器语言机器语言获得一个工具Ｃ语言Ｃ子集机器语言P33.用Ｃ子集编制Ｃ语言的编译程序(P3—人)§1.1什么是编译程序二、利用编译程序自动生成器词法分析器的自动生成程序词法规则说明词法分析程序(C程序)输入： 词法（正规表达式） 识别动作（Ｃ程序段）输出：

yylex()函数LEX§1.1什么是编译程序语法分析器的自动生成程序语法规则说明语法分析程序(C程序)输入： 语法规则（产生式） 语义动作（Ｃ程序段）输出：

yyparse()函数ＹＡＣＣ§1.1什么是编译程序用高级语言编写编译程序： 如果A机器上已有用A机器代码实现的某高级语言L1的编译程序，则可以用L1语言编写另一种高级语言L2的编译程序，把写好的L2编译程序经L1编译程序编译后就可得到A机器代码实现的L2编译程序；§1.5编译程序的生成编译程序的