编译原理第1章(刘磊 机械工业出版社)

1、课程说明 课程性质：专业方向课 必修 考试形式： 考查 学时：48学时，理论：32学时，实验 16学时 成绩评定方法： 上机：30分 出勤：20分 作业：20分 考试：30分 第第1章章 编译引论编译引论 11 程序设计语言和编译程序程序设计语言和编译程序 12 编译程序的结构编译程序的结构 13 编译程序和程序设计环境编译程序和程序设计环境 14 编译程序的实现编译程序的实现 11 程序设计语言和编译程序程序设计语言和编译程序 程序设计语言的演变：程序设计语言的演变： （1）机器语言）机器语言 （2）汇编语言）汇编语言 （3）高级语言）高级语言 13DE:0000 0E PUSH CS 13

2、DE:0001 1F POP DS 13DE:0002 BA0E00 MOV DX,000E 13DE:0005 B409 MOV AH,09 13DE:0007 CD21 INT 21 13DE:0009 B8014C MOV AX,4C01 13DE:000C CD21 INT 21 int main(int argc, char *argv) int a=100,b=200; a=a+b; couta bTOKEN 形式（单词的内部表示）。 例子：源程序片段： main() float i1,i2,i3;i3=i1+i2*10; 词法分析的结果： 类型 值类型 值 类型 值 保留字 ma

3、in 界符 （ 界符 ） 界符 保留字 float 标识符 i1 界符 ， 标识符 i2 界符 ， 标识符 i3 界符 ； 标识符 i3 运算符 = 标识符 i1 运算符 + 标识符 i2 运算符 * 常数 10 界符 ； 界符 单词的类别：保留字、界符、运算符、常数和标识符。单词的类别：保留字、界符、运算符、常数和标识符。 语法分析语法分析：是编译过程的第二个阶段。 任务任务：是在词法分析的基础上将单词分解成各类语法短语 （语法单位，TOKEN序列），同时检查程序中是否有错。 依据依据：语言的语法规则。通过语法分析确定整个输入串是 否构成一个语法上的程序。 如 i3=i1+i2*10 为赋值

4、表达式，语法构成方式为（即语法树）： 赋值表达式 标识符 =表达式 i3 表达式+ 表达式 标识符 i1 标识符 * 常数 i2 10 语义分析阶段语义分析阶段：对语法分析所识别出的各类与反范畴， 分析其含义，并检查静态语义错误，为代码生成阶段收集类 型信息。 如语义分析的一个工作是进行类型检查，审查每个算符是 否具有语言规范允许的运算对象，当不符合语言规范时， 编译程序应报告错误。 如 i3=i1+i2*10 插入语义结点的树为： = id3 id1 inttofloat + id2 10 * 中间代码生成中间代码生成：编译程序将原程序变成一种内部码（称为 中间代码）。 优点：优点：便于移植

5、、修改、优化。 设计原则设计原则：1.容易生成； 2.容易将它翻译成目标代码 常用的中间代码：常用的中间代码：后缀式、三地址（三元、四元）、图结构 （树、DAG） 一般形式为四元式一般形式为四元式： （运算符，运算对象1，运算对象2，结 果） 如 i3=i1+i2*10可生成的四元式序列： （1） （inttofloat 10 - t1) (2) (* id2 t1 t2) ( 3) ( + id1 t2 t3 ) (4) ( = t3 - id3) （* id2 10.0 t1) ( + id1 t1 id3) 一般的优化方法有一般的优化方法有：1常量表达式优化 2. 公共子表达式优化 3削

6、减运算强度 4不变表达式的循环外提等 代码优化代码优化：对前一阶段生成的中间代码进行变换或进 行改造。 目的目的：使生成的代码更为高效，即省时间和空间。 如上述的中间代码优化为： 目标代码生成目标代码生成：把目标代码变换成特定机器上的指令 代码或可重定位的指令代码或汇编指令。 如上述语句的汇编代码为： mov al,id2 mov bl ,10 mul bl add ax, id1 mov id3,ax 7表格管理表格管理 编译过程中的建表、查表和填表。编译过程中的建表、查表和填表。 8错误处理错误处理 如果源程序有错误，编译程序应设法发现错误，并把相如果源程序有错误，编译程序应设法发现错误，

7、并把相 关错误信息报告给用户。关错误信息报告给用户。 错误：词法错误、语法错误、静态语义错误、动态语义错误：词法错误、语法错误、静态语义错误、动态语义 错误。错误。 22 遍遍 “遍遍(Pass)”：对源程序或源程序的中间表示形式从头：对源程序或源程序的中间表示形式从头 到尾扫描一次，并做加工处理，生成新的中间结果或目标到尾扫描一次，并做加工处理，生成新的中间结果或目标 程序。程序。 源程序前端中间代码后端目标代码 与具体的语言有关与具体的机器有关 1编译程序的前端和后端编译程序的前端和后端 3 编译程序和程序设计环境编译程序和程序设计环境 编泽程序同如下程序一起构成程序设计环境。编泽程序同如

8、下程序一起构成程序设计环境。 1编辑器编辑器(Editer) 2预处理器预处理器Preprocessor) 3连接程序连接程序(Linker) 4装入程序装入程序(Loader) 5调试程序调试程序(Debugger) 4 编译程序的实现编译程序的实现 要实现一个编译程序，通常需要做到：要实现一个编译程序，通常需要做到： （1）对源语言的语法和语义要有准确无误的理解。）对源语言的语法和语义要有准确无误的理解。 （2）对目标语言和编译技术也要有很好的了解。）对目标语言和编译技术也要有很好的了解。 （3）确定对编译程序的要求。）确定对编译程序的要求。 （4）根据编译程序的规模，确定编译程序的扫描次

9、数、每）根据编译程序的规模，确定编译程序的扫描次数、每 次扫描的具体任务和所要采用的技术。次扫描的具体任务和所要采用的技术。 （5）设计各遍扫描程序的算法并加以实现。）设计各遍扫描程序的算法并加以实现。 一般开发编译程序有如下几种可能途径：一般开发编译程序有如下几种可能途径： 1转换法转换法(预处理法预处理法) 2移植法移植法 3自展法：自展法： 1971年：PASCAL语言编译程序用自展技术生成，影响重大。 4工具法工具法 如如Bell实验室推出的实验室推出的LEX、 YACC至今还在广泛使用。至今还在广泛使用。 自动生成法如自动生成法如YACC 编译程序的发展：编译程序的发展： （）（） 20世纪世纪50年代早期：多数是将算术公式翻译成机器代码。年代早期：多数是将算术公式翻译成机器代码。 （）（） 20世纪世纪50年代中期：高级语言出现，编译技术的发展。年代中期：高级语言出现，编译技术的发展。 （）（）20世纪世纪50年代末期：研究编译程序的自动生成工具。年代末期：研究编译程序的自动生成工具。 如词法分析程序的生成系统如词法分析程序的生成系统LEX。 （）（）