《编译原理—姜守旭@哈工大》由会员分享，可在线阅读，更多相关《编译原理—姜守旭@哈工大（912页珍藏版）》请在金锄头文库上搜索。
1、编译原理编译原理 Compiler Principles and Techniques主讲： 姜守旭博士主讲： 姜守旭博士/教授教授/教学带头人教学带头人/博导 助教： 林世荣 办公室：综合楼博导 助教： 林世荣 办公室：综合楼808 办公电话：办公电话： 86403492-808 手机：手机：13936168008 email： 课程网站：课程网站：http:/ 博客：博客：http:/ 答疑地点：综合楼答疑地点：综合楼808室 答疑时间：室 答疑时间：?School of Computer Science a=1234h; b=5678h; c=a+b; return 0; assume
2、cs:code, ds:data data segment dw 1234h,5678h data ends code segment start:mov ax, data mov ds, ax mov ax, ds:0 mov bx, ds:2 mov cx, 0 add cx, ax add cx, bx mov cx, ds:4 mov ax, 4c00h int 21h code ends end start 程序设计语言的分类程序设计语言的分类?强制式（命令式）语言强制式（命令式）语言(Imperative Language)?通过指明一系列可执行的运算及运算的次序来描 述计算过程的
3、语言；通过指明一系列可执行的运算及运算的次序来描 述计算过程的语言；?FORTRAN(段结构段结构)、BASIC、Pascal(嵌套结构嵌套结构)、 C?程序的层次性和抽象性不高程序的层次性和抽象性不高2012-4-2621程序设计语言的分类程序设计语言的分类?申述式语言（申述式语言（Declarative Language）?着重描述要处理什么，而非如何处理的非命令式 语言着重描述要处理什么，而非如何处理的非命令式 语言?函数函数(应用应用)式语言式语言(Functional Language)?基本运算单位是函数，如基本运算单位是函数，如LISP、ML?逻辑式逻辑式(基于规则基于规则)语言
4、语言(Logical Language)?基本运算单位是谓词，如基本运算单位是谓词，如Prolog，Yacc2012-4-2622程序设计语言的分类程序设计语言的分类?面向对象语言面向对象语言(Object-Oriented Language)?以对象为核心，如以对象为核心，如Smalltalk、C+ 、Java、 Ada(程序包程序包)?具有识认性（对象）、类别性（类）、多态性和 继承性具有识认性（对象）、类别性（类）、多态性和 继承性2012-4-26231.2 程序设计语言的翻译程序设计语言的翻译?翻译程序翻译程序(Translator)将某一种语言描述的程序将某一种语言描述的程序(源程
5、序源程序Source Program)翻译成等价的另一种语言描述的程 序翻译成等价的另一种语言描述的程 序(目标程序目标程序Object Program)的程序。的程序。翻译程序翻译程序源程序目标程序源程序目标程序 (*.C / *.PAS)(*.OBJ / *.EXE)2012-4-26242012-4-26251.2 程序设计语言的翻译程序设计语言的翻译?解释程序解释程序(Interpreter)?一边解释一边执行的翻译程序一边解释一边执行的翻译程序?口译与笔译（单句提交与整篇提交）口译与笔译（单句提交与整篇提交）源程序源程序输入数据计算结果输入数据计算结果解释程序解释程序解释程序解释程序
6、2012-4-26261.2 程序设计语言的翻译程序设计语言的翻译?编译程序编译程序(Compiler)?将源程序完整地转换成机器语言程序或汇编 语言程序，然后再处理、执行的翻译程序将源程序完整地转换成机器语言程序或汇编 语言程序，然后再处理、执行的翻译程序?高级语言程序汇编高级语言程序汇编/机器语言程序机器语言程序源程序源程序目标程序目标程序编译程序编译程序编译程序编译程序2012-4-26271.2 程序设计语言的翻译程序设计语言的翻译SPCompilerS-Source O-Object OPP-ProgramInputRSRS-Run Sys.Output? ?编译系统编译系统编译系统
7、编译系统(Compiling System)(Compiling System)?编译系统编译系统编译系统编译系统= =编译程序编译程序编译程序编译程序+ +运行系统运行系统运行系统运行系统支撑环境、支撑环境、支撑环境、支撑环境、运行库等运行库等运行库等运行库等2012-4-26281.2 程序设计语言的翻译程序设计语言的翻译?其它翻译程序：其它翻译程序：?汇编程序汇编程序(Assembler)?交叉汇编程序交叉汇编程序(Cross Assembler)?反汇编程序（反汇编程序（Disassembler)?交叉编译程序（交叉编译程序（Cross Compiler)?反编译程序（反编译程序（De
8、compiler）?可变目标编译程序（可变目标编译程序（Retargetable Compiler)?并行编译程序（并行编译程序（Parallelizing Compiler）?诊断编译程序（诊断编译程序（Diagnostic Compiler)?优化编译程序（优化编译程序（Optimizing Compiler)2012-4-26291.2 程序设计语言的翻译程序设计语言的翻译汇总汇总解释程序数据结果编译系统机器语言程 序机器语言程序机器语言程序汇编语言程 序高级语言程序汇编语言程序汇编语言程序高级语言程序高级语言程序汇编程序反汇编程序编译程序反编译程序汇编程序反汇编程序编译程序反编译程序汇
9、编程序编译程序交叉汇编程序交叉编译程序可变目标编译程序图1.5 主要翻译程序汇总运行系统2012-4-26301.3 编译程序总体结构编译程序总体结构目标代码生成器目标代码生成器目标代码生成器目标代码生成器代码优化器代码优化器代码优化器代码优化器语义分析与中间代码生成器语义分析与中间代码生成器语义分析与中间代码生成器语义分析与中间代码生成器语法分析器语法分析器语法分析器语法分析器表表表表格格格格管管管管理理理理出出出出错错错错处处处处理理理理中间代码中间代码中间代码中间代码中间代码中间代码中间代码中间代码目标代码目标代码目标代码目标代码语法单位语法单位语法单位语法单位单词符号单词符号单词符号单
10、词符号词法分析器词法分析器词法分析器词法分析器源程序源程序源程序源程序2012-4-26311、词法分析、词法分析?例：例： sum=(10+20)*(num+square); 结果结果?(标识符，标识符，sum)?(赋值号，赋值号，=)?(左括号，左括号， ( )?(整常数，整常数，10)?(加号，加号，+ )?(整常数，整常数，20)?(右括号，右括号， ) )?(乘号，乘号，* )?(左括号，左括号， ( )?(标识符，标识符，num)?(加号，加号，+ )?(标识符，标识符，square)?(右括号，右括号， ) )?(分号，分号，; )2012-4-26321、词法分析、词法分析?词
11、法分析由词法分析器词法分析由词法分析器(Lexical Analyzer)完 成，词法分析器又称为扫描器完 成，词法分析器又称为扫描器(Scanner)?词法分析器从左到右扫描组成源程序的字符 串，并将其转换成单词词法分析器从左到右扫描组成源程序的字符 串，并将其转换成单词(记号记号token)串；同 时要：查词法错误，进行标识符登记串；同 时要：查词法错误，进行标识符登记符 号表管理。符 号表管理。?输入：字符串输入：字符串?输出：输出：(种别码，属性值种别码，属性值)序对序对?属性值属性值token的机内表示的机内表示2012-4-26332、语法分析、语法分析?语法分析由语法分析器语法分
12、析由语法分析器(Syntax Analyzer)完成，语 法分析器又叫完成，语 法分析器又叫Parser。?功能：功能：?Parser实现实现“组词成句组词成句”?将词组成各类语法成分：表达式、因子、项，语句，子程序将词组成各类语法成分：表达式、因子、项，语句，子程序?构造分析树构造分析树?指出语法错误指出语法错误?指导翻译指导翻译?输入：输入：token序列序列?输出：语法成分输出：语法成分2012-4-26342、语法分析、语法分析sum=(10+20)*(num+square);2012-4-26353、语义分析、语义分析?语义分析语义分析(semantic analysis)一般和语法
13、 分析同时进行，称为一般和语法 分析同时进行，称为语法制导翻译语法制导翻译 (syntax-directed translation)?功能：分析由语法分析器识别出来的语 法成分的语义功能：分析由语法分析器识别出来的语 法成分的语义?获取标识符的属性：类型、作用域等获取标识符的属性：类型、作用域等?语义检查：运算的合法性、取值范围等语义检查：运算的合法性、取值范围等?子程序的静态绑定：代码的相对地址子程序的静态绑定：代码的相对地址?变量的静态绑定：数据的相对地址变量的静态绑定：数据的相对地址2012-4-26364、中间代码生成、中间代码生成?中间代码中间代码(intermediate Cod
14、e)?例例:sum=(10+20)*(num+square); 后缀表示后缀表示后缀表示后缀表示( (逆波兰逆波兰逆波兰逆波兰AntiAnti- - Polish Notation) Polish Notation) sum 10 20 + num square +*=sum 10 20 + num square +*=前缀表示前缀表示前缀表示前缀表示( (波兰波兰波兰波兰Polish Polish Notation) Notation) = sum *+10 20+num square= sum *+10 20+num square四元式表示四元式表示四元式表示四元式表示( (三地址码三地址
15、码三地址码三地址码) )(+(+，1010，2020，T T1 1) )(+(+，numnum，squaresquare，T T2 2) )(*(*， T T1 1， T T2 2， T T3 3) )(=(=， T T3 3， ， sum)sum)三元式表示三元式表示三元式表示三元式表示 (+(+，1010，20)20) (+(+，numnum，square)square) (*(*，) ) (=(=， sumsum，) )语法树语法树语法树语法树2012-4-2637波兰表示问题波兰表示问题Lukasiewicz 1929年发明年发明?中缀表示中缀表示(Infix notation):(a+b)*(-c+d)+e/f?波兰表示（波兰表示（Polish / Prefix / Parenthesis-free / Lukasiewicz notation）也就是前缀表示也就是前缀表示?+*+a b+c d/ef?逆波兰表示逆波兰表示(Reverse Polish / Suffix / Postfix notation) 也就是后缀表示也就是后缀表示?a b +c d +*ef/+ 运算顺序从左向右运算顺序从左向右2012-4-26384、中间代码生成、中间代码生成?中间代码的特点中间代码的特点?简单规范简单规范?与机器无关与机器无关?易于优化与
