第一章 引论 一、程序设计语言
•程序设计语言 –高级语言 –汇编语言 –机器语言 •在计算机上如何执行一个高级语言程序？ –把高级语言程序翻译成机器语言程序 –运行所得的机器语言程序求得计算结果
第一章 引论 二、程序设计语言的转换与编译
•翻译 –在不改变语义的条件下，把某种语言的源程序 转换成另一种语言程序——目标语言程序。 •解释 –接受某高级语言的一个语句输入，进行解释并 控制计算机执行，马上得到这句的执行结果，然 后再接受下一句。
第一章 引论 三、编译程序 4.优化
• 任务 对产生的中间代码进行加工变换，以期在最 后阶段能产生更为高效（省时间、省空间）的 目标代码 • 依据原则：程序的等价变换规则 • 主要优化内容 删除公共子表达式、合并已知量、删除无用 赋值语句、循环优化等
第一章 引论 三、编译程序 5.目标代码生成
• 任务：把中间代码程序转化成具体机器的指令序列 • 注：转换过程需涉及具体机器的指令系统以及寄存 器分配等硬件功能。
第一章 引论 三、编译程序 8. 遍
• 遍：指对源程序或源程序的中间结果从头到尾扫描一次， 并做有关的加工处理，生成新的中间结果或目标代码的过 程。 –注：遍与阶段的含义毫无关系。 • 多遍扫描的好处 –节省内存空间，提高目标代码质量，使编译的逻辑结构 清晰。 • 多遍扫描的缺点 –编译时间较长。 –注：在内存许可情况下，还是遍数尽可能少些为好。
词 源程序 法 分 析 器
语 法 代 码 生 成
优 化
目 标 代 目标代码 码 生 成
出错处理
第一章 引论 三、编译程序 1.词法分析
• 任务 –输入源程序，对构成源程序的字符串进行扫 描和分解，依照词法规则，识别出一个个的 单词，并转化为机器易于使用的内码形式。 • 单词 –是高级语言中有实在意义的最小语法单位， 它由字符构成。
第一章 引论 三、编译程序 1.词法分析
• 注：1)一般内码可用二元式（类号、内码）表 示。对于标识符与常数是由用户任意使用的， 数目无限，解决办法是给标识符分配一个类号， 不同的标识符用它的符号表入口地址（或变量 地址）来区分，将这些地址当作内码给出。 2)描述词法规则的有效工具是正规式和有限自 动机
如何讲解编译原理？
语法 程序 语言 语义 语用 语言 汇编语言 机器语言 翻译：口译 编译：笔译 翻译 高级语言 人 反编 译
编译
机器
本课程基本框架 1、引论 2、基础知识：文法 3、词法分析 理论模型——正规文法与有限自动机 实现——词法分析程序 4、语法分析 理论模型：自上而下分析——下推自动机 自下而上分析——优先分析和LR分析 实现——递归下降分析法、YACC 5、中间代码生成 语法制导翻译 6、运行时数据区的管理：静态存储管理、栈式存储管理、 堆式存储管理 7、中间代码优化：局部优化、循环优化、全局优化 8、目标代码生成
第一章 引论 五、编译程序构造
• 在某机器上为某种语言构造编译程序要掌握： –源语言 –目标语言 –编译方法
第一章 引论 六、编译原理的学习
• 注意各章节之间的关联 • 注意理论联系实际，多实践 –实验安排：4次实验，实验内容见附录
• 符号表：用来登记 源程序中的常量名、 变量名、数组名、 过程名等的性质、 定义和引用状况。
NAME INFORMATION m n 整型、变量地址 整型、变量地址
k
整型、变量地址
常数表
值 1
标号表
NAME …… 10 INFORMATION ……. 四元式序号4
4
登记各类常量(直接量)值 (登记标号的定义与引用) 注：标号表可与符号表合并
• 编译的转换过程 –两阶段转换：编译——运行
源 程 序
编 译 程 序
编译时
目 标 代 码
初 始 数 据
目运 标行 代子 码程 序 运行时
计 算 结 果
第一章 引论 二、程序设计语言的转换与编译
• 编译的转换过程 –三个阶段的转换：编译——汇编——运行 目运 标行 代子 码程 序 运行时
源 程 序
一遍扫描（以语法分析为中心）
语法分析
源程序
扫描器
编译程序
语义 子程 序
目 标 代 码
第一章 引论 四、编译程序生成
• 1.直接用机器语言编写编译程序 • 2.用汇编语言编写编译程序 –注：编译程序核心部分常用汇编语言编写 • 3.用高级语言编写编译程序 –注：这是普遍采用的方法 • 4.自编译 • 5.编译工具:LEX(词法分析)与YACC(用于自动产生 LALR分析表) • 6.移植（同种语言的编译程序在不同类型的机器之 间移植）
第一章 引论 三、编译程序 6.表格与表格管理
• 表格作用： –用于记录源程序的各种信息以及编译过程中的各种状况， 以便后续阶段使用。 • 与编译前三阶段有关的表格有： –符号表、常数表、标号表、分程序入口表、中间代码表 等。 –注：在编译过程中，随着源程序的不断被改造，编译的 各阶段常常需要不同的表格，编译过程的绝大多数时间 是花在查表、造表和更新表格的事务上。在大多数的编 译程序中，表格专门由表格管理程序来处理。
• 入口名表：登记过程的层号，分程 序符号表的入口(指分程序结构的语 言)等
NAME …… INCWAP
INFORMATION ……. 二目子程序、四元式序号1
中间代码表：记录四元式序列的表
序号 （1） （2） （3） （4） （5） （6） （7） （8） （9） OP ＝ = = J< + + + j return ARG1 I j 1 100 m n k ARG2 RESULT m n k (9) m n k (4)
第一章 引论 三、编译程序 2.语法分析
• 语法分析方法：推导（derive)和归约(reduce) –推导：从文法的开始符号开始，按照语法规则，每 次选择某规则右部的一个候选式取代左部，直至识 别了语句或者找到错误为止。其过程可用语法树描 述 –归约：按照语法规则，每次选择某规则左部取代右 部的一个候选式 –注：语法＝词法规则＋语法规则
编 译 程 序 编译时
汇 编 语 言
汇 编 程 序
汇编时
目 标 代 码
初 始 数 据
计 算 结 果
第一章 引论 三、编译程序
• 编译程序的工作 –从输入源程序开始到输出目标程序为止的整 个过程。可分为五个阶段：词法分析、语法 分析、中间代码生成、优化和目标代码生成 –注：也可加入语义分析。
表格管理
• 语法树
A V x = E E + T
T
F V a
T
F V b
*
F
C 50
第一章 引论 三、编译程序 3.中间代码生成
• 任务 在语法分析正确的基础上，按照相应语义规则，产生介于源 代码和目标代码之间的一种代码。 注：这种中间代码不依赖于机器，但又便于产生依赖于机器的 目标代码。 • 两阶段工作 –对每种语法范畴进行静态语义检查 –若语义正确，就进行中间代码的翻译 • 中间代码形式 –四元式、三元式、逆波兰式 –注：1）中间代码是为后续的优化和目标代码生成提供方便， 因此中间代码的选择往往与所采用的优化技术和计算机硬 件结构有关。2）用得最广的是四元式。
第一章 引论 二、程序设计语言的转换与编译
• 解释 –以源程序作为输入，不产生目标程序，一边 解释一边执行。 –优点：直观易懂，结构简单，易于实现人机 对话 –缺点：效率低
第一章 引论 二、程序设计语言的转换与编译
• 编译 –由高级语言转换为低级语言,然后对编译出 来的目标程序进行运行计算
第一章 引论 二、程序设计语言的转换与编译
第一章 引论 三、编译程序 2.语法分析
• 任务： 1）组词成句——在词法分析的基础上，根据语言 的语法规则或文法，把单词符号组成各类的语法单 位，如：短语、子句、语句、过程、程序。 2）通过语法分解，确定整个输入串是否构成语法 上正确的句子、程序等。 • 语法规则的表示：BNF <Word>::={} • 注：语法分析对说明语句的处理是要填符号表，而 对一般语句处理规则是构造语法树。
编译原理及编译程序构造
翟玉庆 yqzhai@
主要参考资料 主要参考资料：
1、编译原理及编译程序构造，秦振松，东 南大学出版社 2、编译原理，陈火旺，国防工业出版社 3、编译原理及实践，Kenneth C. Louden，冯 博琴译，机械工业出版社
为什么要设置编译原理课程？
1、加深对程序内部执行过程的理解 2、为了进一步编好程序
k 10 10 1
第一章 引论 三、编译程序 7.出错处理
• 任务 如果源程序有错误，编译程序应设法发现错 误，并报告给用户。 注：查错无形式化的办法解决。 • 完成：由专门的出错处理程序来完成 • 错误类型: –语法错误:在词法分析和语法分析阶段检测 出来。 –语义错误：一般在语义分析阶段检测。