编译原理 1 绪论学习课件

编译原理第一章绪论哈尔滨工业大学陈鄞1.1什么是编译1.2编译系统的结构1.3为什么要学习编译原理1.4编译技术的应用本章内容1.1什么是编译？机器语言(MachineLanguage)汇编语言

(AssemblyLanguage)高级语言(HighLevelLanguage)汇编器

(Assembler)编译器

(Compiler)C70600000002MOVX,2x=2编译器

(Compiler)可以被计算机直接理解与人类表达习惯相去甚远难记忆难编写、难阅读易写错依赖于特定机器，非计算机专业人员使用受限制编写效率依然很低引入助记符接近人类表达习惯与任何机器无关编写效率高类似于数学定义或自然语言的简洁形式编译：将高级语言程序翻译成汇编语言或机器语言程序的过程源程序目标程序编译器在语言处理系统中的位置预处理器

(Preprocessor)源程序编译器经过预处理的源程序汇编器

(Assembler)

汇编语言程序链接器(Linker)/加载器

(Loader)可重定位的机器代码目标机器代码把存储在不同文件中的源程序聚合在一起把被称为宏的缩写语句转换为原始语句编译器在语言处理系统中的位置预处理器

(Preprocessor)源程序编译器经过预处理的源程序汇编器

(Assembler)

汇编语言程序链接器(Linker)/加载器

(Loader)可重定位的机器代码目标机器代码可重定位(Relocatable)：在内存中存放的起始位置L不是固定的起始地址

+相对地址=绝对地址加载器：修改可重定位地址；将修改后的指令和数据放到内存中适当的位置编译器在语言处理系统中的位置预处理器

(Preprocessor)源程序编译器经过预处理的源程序汇编器

(Assembler)

汇编语言程序链接器(Linker)/加载器

(Loader)可重定位的机器代码目标机器代码库文件；其它可重定位目标程序链接器将多个可重定位的机器代码文件（包括库文件）连接到一起解决外部内存地址问题1.1什么是编译1.2编译系统的结构1.3为什么要学习编译原理1.4编译技术的应用提纲1.2编译系统的结构高级语言程序汇编语言程序/机器语言程序编译器计算机是怎么实现自动翻译的？Intheroom,hebrokeawindowwithahammer.

人工英汉翻译的例子第1步分析源语言源语言句子句子的语义第2步生成目标语言目标语言句子语义分析（SemanticAnalysis）~~~~~~~~~~[]<>在房间里，他用锤子砸了一扇窗户。中间表示，独立于具体的语言补语状语主语谓语

宾语Intheroom,hebrokeawindowwithahammer.

人工英汉翻译的例子源语言句子句子的语义第2步生成目标语言目标语言句子语义分析（SemanticAnalysis）~~~~~~~~~~[]<>补语状语主语谓语

宾语介短

名短动短名短介短介词冠词名词代词动词冠词名词介词冠词名词语法分析（SyntaxAnalysis）词法分析（LexicalAnalysis）第1步分析源语言Intheroom,hebrokeawindowwithahammer.词法分析人工英汉翻译的例子Intheroom,hebrokeawindowwithahammer.词法分析语法分析人工英汉翻译的例子Intheroom,hebrokeawindowwithahammer.词法分析语法分析语义分析人工英汉翻译的例子编译器的结构分析部分/前端（Frontend）：与源语言相关综合部分/后端（Backend）：与目标语言相关词法分析的主要任务从左向右逐行扫描源程序的字符，识别出各个单词，确定单词的类型。将识别出的单词转换成统一的机内表示——词法单元(token)形式token：<种别码，属性值>Phase1：词法分析/扫描(Scanning)一字一码统一作为一种单词一型一码一符一码一符一码单词类型种别种别码1关键字program、if、else、then、…一词一码2标识符变量名、数组名、记录名、过程名、…多词一码3常量整型、浮点型、字符型、布尔型、…一型一码4运算符算术（+-*/++--）关系（>

<

==

!=

>=

<=）逻辑（&

|

~）一词一码或一型一码5界限符;

(

)

=

{

}

…一词一码输入while(value!=100){num++;}输出 1 while <WHILE,_ > 2( <SLP,_

> 3value <IDN

,value > 4!= <

NE

,_

> 5100 <CONST,100 > 6) <SRP,_

> 7{ <LP,_

> 8num <IDN

,num > 9++ <

INC,_ > 10; <SEMI,_ > 11} <RP,_ >例：词法分析后得到的token序列如何实现词法分析器？编译器的结构语法分析器（parser）从词法分析器输出的token序列中识别出各类短语，并构造句子的分析树(parsetree)分析树描述了句子的语法结构Phase2：语法分析(Parsing)position:=initial+rate*60<id,position><:=><id,initial><+><id,rate><*><num,60>例1：赋值语句的分析树;文法：<D>→<T><IDS>;<T>→int|real|char|bool<IDS>→id|<IDS>,id输入：inta,b,c;例2：变量声明语句的分析树，;<D><IDS>id(a)<T><IDS>id(c)int，<IDS>id(b)如何根据语法规则为输入句子构造分析树？编译器的结构语义分析的主要任务获取标识符的属性种属

(Kind)简单变量、复合变量（数组、记录、…）、过程、…Phase3：语义分析语义分析的主要任务获取标识符的属性种属

(Kind)类型

(Type)整型、实型、字符型、布尔型、指针型、…Phase3：语义分析语义分析的主要任务获取标识符的属性种属

(Kind)类型

(Type)存储位置、长度Phase3：语义分析例：begin realx[8]; integeri,j;……end名字相对地址x0i64j68x[1]x[2]……x[8]ij08566468语义分析的主要任务获取标识符的属性种属

(Kind)类型

(Type)存储位置、长度值(Value)作用域

(Scope)参数和返回值信息参数个数、参数类型、参数传递方式、返回值类型、…Phase3：语义分析语义分析的主要任务获取标识符的属性种属

(Kind)类型

(Type)存储位置、长度值(Value)作用域

(Scope)参数和返回值信息Phase3：语义分析符号表(SymbolTable)符号表是用于存放标识符的属性信息的数据结构字符串表NAME字段为什么要这样设计数据结构？语义分析的主要任务获取标识符的属性语义检查变量或过程是否未经声明就使用变量或过程名是否重复声明

运算分量类型是否不匹配

操作符与操作数之间的类型是否不匹配对整型变量使用数组访问或过程调用操作符数组下标不是整数过程调用参数类型或数目不匹配函数返回类型有误Phase3：语义分析编译器的结构常用的中间表示形式三地址码

(Three-addressCode)语法结构树/语法树

(SyntaxTrees)三地址码由类似于汇编语言的指令序列组成，每个指令最多有三个操作数（operand）Phase4：中间代码生成常用的三地址指令序号指令类型指令形式1赋值指令x=y

op

zx=op

y

2复制指令x

=

y3条件跳转ifx

relop

y

goto

n

4非条件跳转goto

n

5参数传递param

x

6过程调用call

p,n

7过程返回return

x

8数组引用x

=

y[i]9数组赋值x[i]

=

y10地址及指针操作x

=&y

x

=*y

*x

=

y地址可以具有如下形式之一源程序中的名字（name）常量（constant）编译器生成的临时变量(temporary)四元式

(Quadruples)

(op,y,z,x)三元式

(Triples)间接三元式(Indirecttriples)三地址指令的表示x=y

op

z

（op

,y,z ,x

）x=op

y

（op

,y,_ ,x）x

=

y

（:=

,y,_ ,x）ifx

relop

ygoton(

relop

,x,y ,n

）goto

n

（goto

,_,_,n）param

x

（param

,_,_,x

）

callp,n

（

call

,p,n,_）

return

x

（return

,_,_,x

）x

=

y[i]

（=[]

,y,i ,x

）

x[i]=y

（[]=

,y,x ,i

）x

=&y

（

&

,y,_ ,x）

x

=*y

（=*

,y,_ ,x

）

*x

=

y

（*=

,y,_ ,x

）四元式表示三地址指令序列唯一确定了运算完成的顺序while

a<b

do

ifc<5then

while

x>y

do

z=x+1;else

x=y;100: (j<,a,b,102

)101:

(j,-,-,-)102:

(j<,c,5,104)103:

(j,-,-,110)104:

(j>,x,y,106)105:

(j,-,-,100)106:

(+,x,1,t1

)107:

(=,t1

,-,z)108:

(j,-,-,104)109:

(j,-,-,100)110:

(=,y,-,x)111:

(j,-,-,100)112:?Sid(a)whileB

do

SErelopEif

B

then

S

else

Sid(b)(<)id(c)ErelopEwhile

B

do

SErelopEid=

E

;(z)E

+

Eid=

E

;(x)(<)num(5)id(x)id(y)(>)id(x)num(1)id(y)例编译器的结构目标代码生成以源程序的中间表示形式作为输入，并把它映射到目标语言目标语言需要为程序使用的每个变量选择寄存器或内存位置目标代码生成的一个至关重要的方面是合理分配寄存器以存放变量的值编译器的结构代码优化为改进代码所进行的等价程序变换，使其运行得更快一些、占用空间更少一些，或者二者兼顾1.1什么是编译1.2编译系统的结构1.3为什么要学习编译原理1.4编译技术的应用提纲

编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机科学家的研究生涯中，本课程中的原理和技术都会反复用到。——AlfredV.Aho1.3为什么要学习编译原理更深刻地理解高级语言程序的内部运行机制教给我们如何严谨地去思考、编写程序编译原理蕴含了计算机科学解决问题的思路和方法，即“形式化→自动化”。所涉及的理论和方法在很多领域都会被用到自然语言处理、模式识别、人工智能、……很多应用软件都会用到编译技术1.1什么是编译1.2编译系统的结构1.3为什么要学习编译原理1.4编译技术的应用提纲结构化编辑器（Structureeditors）引导用户在语言的语法约束下编制程序能自动地提供关键字和与其匹配的关键字1.4编译技术的应用结构化编辑器（Structureeditors）智能打印机（Prettyprinters）对程序进行分析，打印出结构清晰的程序注释以一种特殊的字体打印根据各个语句在程序的层次结构中的嵌套深度进行缩进1.4编译技术的应用结构化编辑器（Structureeditors）智能打印机（Prettyprinters）静态检查器（Staticcheckers）检测出程序中永远不能被执行的语句1.4编译技术的应用结构化编辑器（Structureeditors）智能打印机（Prettyprinters）静态检查器（Staticcheckers）文本格式器（Textformatters）文本格式器处理的字符流中除了需要排版输出的字符以外，还包含一些用来说明字符流中的段落、图表或者上标和下标等数学结构的命令1.4编译技术的应用结构化编辑器（Structureeditors）智能打印机（Prettyprinters）静态检查器（Staticcheckers）文本格式器（Textformatters）数据库查询解释器（

DatabaseQueryInterpreters）数据库查询语句由包含了关系和布尔运算的谓词组成。查询解释器把这些谓词翻译成数据库命令，在数据库中查询满足条件的记录。1.4编译技术的应用结构化编辑器（Structureeditors）智能打印机（Prettyprinters）静态检查器（Staticcheckers）文本格式器（Textformatters）数据库查询解释器（

DatabaseQueryInterpreters）高级语言的翻译工具1.4编译技术的应用什么是编译编译系统的结构为什么要学习编译原理编译技术的应用本章小结1．绪论 （2学时）2.语言及其文法

（2学时）3．词法分析 （4学时）4．语法分析 （9学时）5．语法制导翻译

（6学时）6．中间代码生成

（7学时）7．运行时的存贮组