《编译原理chapter1绪论》由会员分享，可在线阅读，更多相关《编译原理chapter1绪论（54页珍藏版）》请在金锄头文库上搜索。
1、编译原理,第一章 绪论 哈尔滨工业大学 陈鄞,1.1 什么是编译 1.2 编译系统的结构 1.3 为什么要学习编译原理 1.4 编译技术的应用,本章内容,1.1 什么是编译？,C706 0000 0002,MOV X, 2,x = 2,可以被计算机直接理解,与人类表达习惯相去甚远 难记忆 难编写、难阅读 易写错,依赖于特定机器，非计算机专业人员使用受限制 编写效率依然很低,引入助记符,接近人类表达习惯 与任何机器无关 编写效率高,类似于数学定义或 自然语言的简洁形式,编译：将高级语言程序翻译成汇编语言或机器语言程序的过程,源程序,目标程序,编译器在语言处理系统中的位置,把存储在不同文件中的源程
2、序聚合在一起 把被称为宏的缩写语句转换为原始语句,编译器在语言处理系统中的位置,预处理器 (Preprocessor),源程序,编译器,经过预处理的源程序,汇编器 (Assembler),汇编语言程序,链接器 (Linker) /加载器 (Loader),可重定位的机器代码,目标机器代码,可重定位(Relocatable)： 在内存中存放的起始位置L不是固定的,起始地址 +相对地址=绝对地址,加载器： 修改可重定位地址； 将修改后的指令和数据放到内存中适当的位置,编译器在语言处理系统中的位置,预处理器 (Preprocessor),源程序,编译器,经过预处理的源程序,汇编器 (Assemble
3、r),汇编语言程序,链接器 (Linker) /加载器 (Loader),可重定位的机器代码,目标机器代码,库文件； 其它可重定位目标程序,链接器 将多个可重定位的机器代码文件（包括库文件）连接到一起 解决外部内存地址问题,1.1 什么是编译 1.2 编译系统的结构 1.3 为什么要学习编译原理 1.4 编译技术的应用,提纲,1.2 编译系统的结构,高级语言程序,汇编语言程序/ 机器语言程序,编译器,计算机是怎么实现 自动翻译的？,In the room , he broke a window with a hammer .,人工英汉翻译的例子,第1步 分析源语言,源语言句子,句子的语义,第2
4、步 生成目标语言,目标语言句子,语义分析（Semantic Analysis）,在房间里，他用锤子砸了一扇窗户。,中间表示，独立于具体的语言,补语,状语,主语,谓语,宾语,In the room , he broke a window with a hammer .,人工英汉翻译的例子,源语言句子,句子的语义,第2步 生成目标语言,目标语言句子,语义分析（Semantic Analysis）,补语,状语,主语,谓语,宾语,介短 名短 动短 名短 介短,介词 冠词 名词 代词 动词 冠词 名词 介词 冠词 名词,第1步 分析源语言,In the room , he broke a window
5、with a hammer . 词法分析,人工英汉翻译的例子,In the room , he broke a window with a hammer . 词法分析 语法分析,人工英汉翻译的例子,In the room , he broke a window with a hammer . 词法分析 语法分析 语义分析,人工英汉翻译的例子,编译器的结构,词法分析的主要任务 从左向右逐行扫描源程序的字符，识别出各个单词，确定单词的类型。将识别出的单词转换成统一的机内表示词法单元(token)形式 token：,Phase 1：词法分析/扫描(Scanning),一字一码,统一作为一种单词,一型
6、一码,一符一码,一符一码,输入 while(value!=100)num+; 输出 1 while 2 ( 3 value 4 != 5 100 6 ) 7 8 num 9 + 10 ; 11 ,例：词法分析后得到的token序列,如何实现词法分析器？,编译器的结构,语法分析器（parser）从词法分析器输出的token序列中识别出各类短语，并构造句子的分析树(parse tree) 分析树描述了句子的语法结构,Phase 2：语法分析(Parsing),position := initial + rate * 60 ,例1：赋值语句的分析树,;,文法： ; int | real | char
7、 | bool id | , id 输入： int a , b , c ;,例2：变量声明语句的分析树,如何根据语法规则为输入句子构造分析树？,编译器的结构,语义分析的主要任务 获取标识符的属性 种属 (Kind) 简单变量、复合变量（数组、记录、）、过程、,Phase 3：语义分析,语义分析的主要任务 获取标识符的属性 种属 (Kind) 类型 (Type) 整型、实型、字符型、布尔型、指针型、,Phase 3：语义分析,语义分析的主要任务 获取标识符的属性 种属 (Kind) 类型 (Type) 存储位置、长度,Phase 3：语义分析,例： begin real x8; integer
8、i, j; end,0 8 56 64 68,语义分析的主要任务 获取标识符的属性 种属 (Kind) 类型 (Type) 存储位置、长度 值 (Value) 作用域 (Scope) 参数和返回值信息 参数个数、参数类型、参数传递方式、返回值类型、,Phase 3：语义分析,语义分析的主要任务 获取标识符的属性 种属 (Kind) 类型 (Type) 存储位置、长度 值 (Value) 作用域 (Scope) 参数和返回值信息,Phase 3：语义分析,符号表(Symbol Table),符号表是用于存放标识符的属性信息的数据结构,字符串表,NAME字段为什么要这样设计数据结构？,语义分析的主
9、要任务 获取标识符的属性 语义检查 变量或过程是否未经声明就使用 变量或过程名是否重复声明 运算分量类型是否不匹配 操作符与操作数之间的类型是否不匹配 对整型变量使用数组访问或过程调用操作符 数组下标不是整数 过程调用参数类型或数目不匹配 函数返回类型有误,Phase 3：语义分析,编译器的结构,常用的中间表示形式 三地址码 (Three-address Code) 语法结构树/语法树 (Syntax Trees) 三地址码由类似于汇编语言的指令序列组成，每个指令最多有三个操作数（ operand）,Phase 4：中间代码生成,常用的三地址指令,地址可以具有如下形式之一 源程序中的名字（na
10、me） 常量（constant） 编译器生成的临时变量(temporary),四元式 (Quadruples) (op, y, z, x) 三元式 (Triples) 间接三元式 (Indirect triples),三地址指令的表示,x = y op z （ op , y , z , x ） x = op y （ op , y , _ , x ） x = y （ := , y , _ , x ） if x relop y goto n ( relop , x , y , n ） goto n （ goto , _ , _, n ） param x （param , _ , _, x ） ca
11、ll p, n （ call , p , n, _ ） return x （return , _ , _, x ） x = yi （ = , y , i , x ） xi = y （ = , y , x , i ） x = &y （ & , y , _ , x ） x = *y （ =* , y , _ , x ） *x = y （ *= , y , _ , x ）,四元式表示,三地址指令序列唯一确定了运算完成的顺序,while ay do z=x+1; else x=y;,100: ( j, x , y , 106 ) 105: ( j , - , - , 100 ) 106: ( + ,
12、x , 1 , t1 ) 107: ( = , t1 , - , z ) 108: ( j , - , - , 104 ) 109: ( j , - , - , 100 ) 110: ( = , y , - , x ) 111: ( j , - , - , 100 ) 112:,?,例,编译器的结构,目标代码生成以源程序的中间表示形式作为输入，并把它映射到目标语言 目标语言需要为程序使用的每个变量选择寄存器或内存位置 目标代码生成的一个至关重要的方面是合理分配寄存器以存放变量的值,编译器的结构,代码优化 为改进代码所进行的等价程序变换，使其运行得更快一些、占用空间更少一些，或者二者兼顾,1.1
13、 什么是编译 1.2 编译系统的结构 1.3 为什么要学习编译原理 1.4 编译技术的应用,提纲,编写编译器的原理和技术具有十分普遍的意义，以至于在每个计算机科学家的研究生涯中，本课程中的原理和技术都会反复用到。 Alfred V.Aho,1.3 为什么要学习编译原理,更深刻地理解高级语言程序的内部运行机制 教给我们如何严谨地去思考、编写程序 编译原理蕴含了计算机科学解决问题的思路和方法，即“形式化自动化”。所涉及的理论和方法在很多领域都会被用到 自然语言处理、模式识别、人工智能、 很多应用软件都会用到编译技术,1.1 什么是编译 1.2 编译系统的结构 1.3 为什么要学习编译原理 1.4
14、编译技术的应用,提纲,结构化编辑器（Structure editors） 引导用户在语言的语法约束下编制程序 能自动地提供关键字和与其匹配的关键字,1.4 编译技术的应用,结构化编辑器（Structure editors） 智能打印机（Pretty printers） 对程序进行分析，打印出结构清晰的程序 注释以一种特殊的字体打印 根据各个语句在程序的层次结构中的嵌套深度进行缩进,1.4 编译技术的应用,结构化编辑器（Structure editors） 智能打印机（Pretty printers） 静态检查器（Static checkers） 检测出程序中永远不能被执行的语句,1.4 编译技
15、术的应用,结构化编辑器（Structure editors） 智能打印机（Pretty printers） 静态检查器（Static checkers） 文本格式器（Text formatters） 文本格式器处理的字符流中除了需要排版输出的字符以外，还包含一些用来说明字符流中的段落、图表或者上标和下标等数学结构的命令,1.4 编译技术的应用,结构化编辑器（Structure editors） 智能打印机（Pretty printers） 静态检查器（Static checkers） 文本格式器（Text formatters） 数据库查询解释器（ Database Query Interpreters ） 数据库查询语句由包含了关系和布尔运算的谓词组成。查询解释器把这些谓词翻译成数据库命令，在数据库中查询满足条件的记录。,1.4 编译技术的应用,结构化编辑器（Structure editors） 智能打印机（Pretty printers） 静态检查器（Static checkers） 文本格式器（Text formatters） 数据库查询解释器（ Database Query Interpreters ） 高级语言的翻译工具,1.4 编译技术的应用,什么是编译 编译系统的结构 为什么要学习编译原理 编译技术的应用,
