ch1引论_(张素琴)

《ch1引论_(张素琴)》由会员分享，可在线阅读，更多相关《ch1引论_(张素琴)（71页珍藏版）》请在金锄头文库上搜索。

1、编译原理（48学时）,计算机与通信工程学院 2014级计算机专业 王翠荣综合楼1430,2018/9/5计算机学院,辛明影,2,参考书,2018/9/5计算机学院,辛明影,3,2018/9/5计算机学院,辛明影,4,2018/9/5计算机学院,辛明影,5,课外资料： 编译原理(第二版)清华大学-答案详解； 编译原理授课计划2016； Stanford大学课程讲稿: http:/www.stanford.edu/class/cs143/,课程架构：,理论和实践并重的课程 理论部分的题目出现于书面练习，课堂小测和期中、末考试 实践题目（Project） Project1: 用高级语言（C或Pasc

2、al）实现扩充的PL/0编译程序 各部分权重 作业 10% 实验 10% 期中考试10% 期末考试 70%,编译原理教学目的与要求,应清楚理解一个编译程序是如何工作的； 应了解如何用形式语言文法定义一门高级语言； 应具有一定的使用编译构造工具开发编译程序的经验； 会将所学的常用技术和算法应用于类似的软件的设计和实现中。,Why Study Languages and Compilers ?,1. Increase capacity of expression 2. Improve understanding of program behavior 3. Increase ability to

3、learn new languages 4. Learn to build a large and reliable system 5. See many basic CS concepts at work,第1章 概述,1.1 什么是编译程序 1.2 程序设计语言的实现 1.3 处理源程序的软件工具 1.4 编译技术的发展,11,编译器就是一个程序，它读入用某种语言编写的源程序，并翻译成一个与之等价的另一种语言编写的源(目标)程序。,编译器,源程序,目标程序,错误信息,Fortran、Cool、Pascal、Java、 C Python,汇编语言、机器语言,1.1 什么是编译程序(Compi

4、ler),12,编译器的各个阶段：,编译器是分 阶段执行的。,每个阶段将源程序从一种表示转换成另一种表示,源程序,词法分析器,错 误 处 理 器,符 号 管 理 表,语法分析器,语义分析器,中间代码生成器,代码优化器,代码生成器,编译的各个阶段,内存管理,目标代码优化,芯片指令集合语言定义(形式语言)语言的编译系统(词法、语法、语义、优化、翻译)编辑器调试器,分类 软件 系统软件 语言处理系统,分类,软件：计算机系统中的程序及其文档 系统软件：居于计算机系统中最靠近硬件的一层，其它软件一般都通过系统软件发挥作用，和具体的应用程序无关。编译系统和操作系统等都是系统软件。,语言处理系统：把高级语言

5、书写的各种程序处理成可在计算机上执行的程序。 高级语言：用于书写软件的语言。它主要包括需求定义语言，功能性语言，设计性语言，程序设计语言以及文档语言。,语言转换系统,C+编译器,C+,C,Java,Bytecode,Java编译器,术语,编译程序(compiler) 编译程序的源语言(源程序) (source language)(source program) 编译程序的目标语言(目标程序) (object or target language)(object or target program) 编译程序的实现语言(implementation language),词法分析第一步识别单词,英

6、文句子由单词构成 This line is a longer sentence. 句子开头的单词第一个字母要大写 空格是单词分隔符 句点是句子结尾 单词是字母组成的有含义的最小成分 ist his linealo gerse nte nce.,词法分析,从左至右扫描字符流的源程序、分解构成源程序的字符串，识别出(拼)一个个的单词（符号） 单词符号是语言中具有独立意义的最基本结构。多数程序语言中，单词符号一般包括 各类型的常数、保留字、标识符、运算符、界符等等。 例如 double f = sqrt(-1);,词法分析,double f = sqrt(-1); TDOUBLE (“double”

7、) TIDENT (“f”) TOP (“=“) TIDENT (“sqrt”) TLPAREN (“(“) TOP (“-”) TINTCONSTANT (“1”) TRPAREN (“)”) TSEP (“;”),词法分析,词法分析(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 c

8、ollective meaning. 单词-token 保留字-reserved word 标识符 -identifier(user-defined name),例,程序文本If x = y then z := 1 else z := 2; 经词法分析，变成一个个单词 if, x, =, y, then, z, :=, 1, else, z, :=, 2, ; 语言的单词符号是由词法规则所确定的。词法规则规定了字母表中哪样的字符串是一个单词符号。,词法分析 position := initial + rate * 60;,单词类型 单词值 标识符1(id1) position 算符(赋值) :

9、= 标识符2(id2) initial 算符(加) + 标识符3(id3) rate 算符(乘) * 整数 60 分号 ；,语法分析 Syntax Analysis 功能: 层次分析 依据源程序的语法规则把源程序的单词序列组成语法短语(表示成语法树).,也称为 “parsing” 使用 context-free grammars 结构上的合法性Structural validation （可生成语法树或推导Creates parse tree or derivation）,This line is a longer sentence,分析源程序的语法成分,If x=y then z=1 els

10、e z=2,例： position := initial + rate * 60 ; （Pascal）规则 :=“:=” :=“+” :=“*” :=“(”“)” := := :=,语言的语法规则规定了如何从单词符号形成更大的结构（即语法单位）,赋值语句,标识符,表达式,表达式,+,表达式,表达式,标识符,整数,标识符,:=,表达式,*,id1:=id2+id3*N,程序设计语言靠严格约束规则解决二义性, int jack=3; int jack=4; cout jack; ,语义分析-语言的规定和实现,语义分析 进一步分析语法结构正确的程序是否符合源程序的上下文约束、运算相容性等规定。,审查

11、静态语义 使用的变量声明了吗？ 允许操作运算对象吗？ 类型正确吗？ ,例: Program p(); Var rate:real; procedure initial; position := initial + rate * 60 /* error */ /* error */ /* warning */; ,Program p(); Var rate:real; Var initial :real; Var position :real ; position := initial + rate * 60 /*warning*/,语义分析(处理）,中间代码（中间表示）生成(翻译）,源程序的内

12、部(中间)表示 三元式、四元式、逆波兰表示、bytecode ( * id3 t1 t2 ) t2 = id3 * t1 的四元组表示,id1:= id2 + id3 * 60的四元式 (1) (int to real, 60 - t1 ) (2) (* , id3 t1 t2 ) (3) (+ , id2 t2 t3 ) (4) (:= , t3 - id1 ),例：将下面语句翻译为三地址码(三元式)中间代码,Three-address code,j = 2 * i + 1; if (j = n) j = 2 * i + 3; return aj;,t1 = 2 * i t2 = t1 +

13、1 j = t2 t3 = j n if t3 goto L0 t4 = 2 * i t5 = t4 + 3 j = t5 L0: t6 = aj return t6,代码优化Code Optimization： 应用一些技术对代码进行变换以使得编译产生的目标代码高效。,例（中间代码级优化）,t1 = 2 * i t2 = t1 + 1 j = t2 t3 = j n if t3 goto L0 t4 = 2 * i t5 = t4 + 3 j = t5 L0: t6 = aj return t6,t1 = 2 * i j = t1 + 1 t3 = j n if t3 goto L0 j =

14、 t1 + 3 L0: t6 = aj return t6,将四元组序列优化为较少的四元组序列,id1:= id2 + id3 * 60 (1) (inttoreal 60 - t1 ) (2) ( * id3 t1 t2 ) (3) ( + id2 t2 t3 ) (4) ( := t3 - id1 ) 变换 （1） ( * id3 60.0 t1 ) ( 2）（ + id2 t1 id1 ),目标代码生成Object code generation： 将优化后的中间代码生成目标机汇编或者机器指令,t1 = 2 * i j = t1 + 1 t3 = j n if t3 goto L0 j

15、= t1 + 3 L0: t6 = aj return t6,sll R1, 1, R1 add R1, 1, J cmp J,R2 blt .LL3 add R1, 3, J .LL3: ld R0+J, Rt retr,目标代码生成,(* , id3 60.0 t1 ) (+ , id2 t1 id1 ),movf id3,R2 mulf #60.0,R2 movf id2,R1 addf R2,R1 movf R1,id1,编译阶段的划分前端（front end）和后端（back end） 编译的前端 与源语言有关但与目标机无关的那些部分组成 编译的后端 与目标机有关的那些部分组成 遍（

16、趟）从头到尾扫描源程序（各种形式） (pass),出 错 处 理 程 序,表 格 管 理 程 序,符号表,记录源程序中使用的名字 收集每个名字的各种属性信息 类型、作用域、分配存储信息,name: I kind：常量 value：35 name:object kind：变量 type：实 level：2 add: dx 符号表管理(登录，查找） symbol table management,出错处理(error handling ）,检查错误、报告出错信息、排错、恢复编译工作 (error reporting and error recovery),1.2程序设计语言的实现 有些语言基本通过解释程序 Java的Bytecode 有些环境同时提供编译程序和解释系统 Lisp,