北京工业大学廖湖声编.ppt

,北京工业大学 廖湖声编 学时：56 小时（含上机：12 小时） 主页：172.21.14.209/网上教学 参考教材： 程序设计语言编译原理 (第3版)国防工业出版社,引言,什么叫编译程序 将高级程序设计语言翻译成逻辑上等价的低级语言(汇编语言,机器语言)的翻译程序 目的：提高执行效率,编译程序,源程序,目标程序,(*.C / *.PAS),(*.OBJ / *.EXE),编译与语言,编译程序设计原理： 高级程序设计语言的实现原理 编译技术： 最具有代表性的计算机语言处理技术 计算机语言 人与计算机、计算机软件之间的交流工具 广义理解：软件之间传输的信息,各种用途的计算机语言,程序设计语言 描述程序执行的算法 数据库语言 数据定义、数据操作 机器语言 控制计算机的工作 命令语言 控制系统的工作 都是编译技术的处理对象,高级程序设计语言的一般特征,程序结构 子程序、函数 程序包 语句 条件、循环、赋值 表达式 逻辑、关系、算术 变量、常数、运算符、函数调用 数据结构 标量 整数、浮点数、字符、字符串 数组、结构（记录） 抽象数据类型 类 编译实现的任务 程序结构与数据结构的具体处理,高级语言的分类,过程式语言 Imperative FORTRAN、BASIC、Pascal、C 函数式语言 Functional LISP、ML 逻辑式语言 Logical Prolog 面向对象语言 Object-Oriented Smalltalk、C+、Java、Ada、C# 语言的实现都需要编译系统的支持,学习内容,语言结构的描述与分析 语义的描述与实现框架 程序设计语言的工作原理 用途： 计算机语言的实现与设计 复杂数据处理（广义） 特征： 十分复杂的数据处理 比较成熟的理论基础 指导软件设计实践,第一章 计算机语言的实现,程序的解释执行 如：BASIC、DOS 命令，问题：效率低下,解释程序,源程序,输入数据,计算结果,程序的编译执行,目标程序： 机器语言 汇编语言,编译程序,运行系统,目标程序,输入数据,计算结果,源程序,1.1 编译系统的需求分析,源程序的分析 词法、语法、语义 目标程序的综合 语句的翻译、代码生成 标识符的绑定(binding) 变量： 存储单元 函数： 目标代码序列,1.2 编译过程,自然语言的翻译过程： I wish you success 主语 谓语 间接宾语 直接宾语 识别单词（拼写正确）、语法检查（顺序格式）、 语义理解（合理）、组织译文（符合原文、通顺）,一个 C 程序的编译过程,源程序： main( ) printf(“hello”); 1. 词法分析 分析字符序列； 识别单词（种别、属性） 查词法错误； 标识符登记；,结果 IDN main ( ) IDN printf ( STR hello ) ; ,2. 语法分析,分析单词序列； 识别语法结构； 查语法错误； 构造分析树；,3. 语义分析,确认标识符的属性 类型、作用域等 语义检查 运算的合法性、取值范围等 子程序的静态绑定 代码存储的相对地址 变量的静态绑定 数据存储的相对地址,程序使用的内存空间,字符串常数hello 临时变量 t 目标代码 main 编译程序负责为各变量、常数和函数计算并分配必要的内存空间,4. 生成中间代码,中间语言 简单规范 机器无关 易于优化与转换 按照语法分析树生成中间语言代码,翻译例 Z=(X+0.48)*Y/W; 结果（三地址代码） T1 = X + 0.48 T2 = T1 * Y Z = T2 / W,5. 中间代码优化 中间代码的优化处理，以求提高执行效率 6. 目标代码生成 将中间代码转换成目标机上的机器指令代码或汇编代码,MOV R0, #12, ADD R0, #4 MUL R0, R2 汇编指令代码,10000001 0001 1100 10000010 0001 0100 11000100 0001 0010 机器指令代码,编译程序的结构,源程序,目标程序,其他模块,表格管理 辅助语法检查、语义检查 完成静态绑定、管理编译过程 错误处理 词法：拼写. 语法：语句结构、表达式结构. 语义：类型不匹配.,编译程序的软件结构,编译前端 目标机无关部分 词法分析、语法分析、中间代码生成 语义分析、中间代码优化 编译后端 目标机相关部分 目标代码优化 目标代码生成 多遍扫描 常见：前段1.2.和后端1.2.,程序设计环境,集成化的程序设计环境 编辑程序 编译程序 连接程序 - 将目标程序连接成可执行程序 调试工具 - 跟踪、分析 常见： Turbo C/C+ Visual Studio for C/C+, Basic 等 JBuilder, BlueJ,1.3 编译技术的通用性,把复杂数据看作一条语句 数据格式的分析 利用词法分析、语法分析方法 数据处理的框架 基于语法制导的语义处理框架 编译技术可以用于各种复杂数据的分析处理,例1-1（1/2）,DOS 命令 date 的输出格式 例：9-2-1993、09-03-1993、9-03-93 语法 date month - day - year 词法 month DIG DIG | DIG day DIG DIG | DIG year DIG DIG | DIG DIG DIG DIG,例1-1（2/2）,语义 year(年)、month(月)、day(日) 语义约束条件 0 month.value 13 0 day.value 32，31，30 0 year.value 10000,1.4 编译程序的生成方法,设计目标 目标程序小，执行速度快。 编译程序小，执行速度快。 诊断能力强，可靠性强。 可移植性，可扩充性。,表示翻译程序的 T 型图,S,T,I,源语言,目标语言,翻译用语言,1）交叉编译,条件： 机有 语言的编译程序 目的： 实现 机的 语言的编译,1. 用 语言编制编译程序（CP1.C） 机器上编译该程序，得到（CP1.EXE) 在A机器上，运行CP1.EXE编译CP1.C，得到B机的C编译程序（CP2.EXE）。,用 语言编制编译程序（CP1.C） 机器上编译该程序，得到（CP1.EXE),手写,可执行,3. 在A机器上，运行CP1.EXE编译CP1.C， 得到B机的C编译程序（CP2.EXE）。,A机可执行,B机可执行,2) 编译程序的自展技术,1. 用汇编语言实现一个 子集的编译程序 2. 用汇编程序处理该程序，得到CP1.EXE 3. 用 子集编制 语言的编译程序 4. 用CP1.EXE处理该程序，得到CP2.EXE,3) 利用编译程序自动生成器,词法分析器的自动生成程序,词法规则说明,词法分析程序,(C程序),输入： 词法（正规表达式） 识别动作（程序段） 输出： yylex( ) 函数,语法分析器的自动生成程序,语法规则说