编译原理第一章引论

殷脂Email:yzzhizhi@163.com课程简介考核方式：考试(70%)+平时成绩(30%)答疑:

每周二13:00—14:00行政楼2楼计算机系参考书籍：《编译原理》吕映芝等，清华大学出版社《CompilerConstructionPrincipleandPratice》(编译原理及实践)，KennethC.Louden，机械工业出版社《Compilers:Principles,Techniques,&Tools》(编译原理技术与工具)，Aho，A.V.，人民邮电出版社本章内容

一.什么叫编译程序二.编译过程概述三.编译程序的结构四.编译程序生成五.课程学习指导1引论一.什么叫编译程序翻译程序（Translator）是一种程序，其输入是某种语言的一系列语句，而其输出则是另一种语言的一系列语句。翻译程序源语言程序目标语言程序Translator输入输出一.什么叫编译程序编译程序（Compiler）是一种程序。它把用高级语言写的源程序作为数据接收，经过翻译转换，产生面向机器的代码作为输出。这当中代码还可能要由汇编程序或装配程序作进一步加工，得出目标程序，交给计算机执行。编译程序高级语言源程序面向机器代码Compiler目标程序代码汇编装配一.什么叫编译程序翻译与编译比较源语言程序目标语言程序转变为高级语言源程序面向机器代码编译为这种变换程序称为翻译程序编译程序有一些限制（针对输入、输出）这种变换程序称为编译程序二、编译过程编译的过程与自然语言间的翻译过程有相似之处：1.识别出每个单词（含义，性质等）2.分析语法结构3.初步翻译句子的含义，得到草稿4.译文修饰5.写出最后译文1.词法分析

2.语法分析3.语义分析中间代码生成

4.优化5.目标代码生成英文翻译成中文编译过程

编译过程概述编译过程的组成编译过程词法分析语法分析中间代码生成代码优化目标代码生成源程序单词符号中间代码语法单位目标代码中间代码（优化后）源程序目标代码二.编译过程概述1.词法分析任务所做转换依据构词规则主要理论基础自动机理论源程序字符串单词符号输入源程序；扫描、分解字符串，识别出一个个单词（定义符、标识符、运算符、界符、常数）例：源程序forI:=1to100do经词法分析被分析成一个个的单词定义符for标识符I赋值符:=整常数1定义符to整常数100定义符do二.编译过程概述1.词法分析示例FORK:=1TO100M:=I+10*KN:=J+10*KNEXTKTONEXTFORKNMIJKKK:=100:=:=11010+**+定义符标识符分界符运算符

常数二.编译过程概述2.语法分析任务所做转换依据语法规则主要理论基础上下文无关文法单词符号语法单位（语法范畴）在词法分析基础上，将单词符号串转化为语法单位（语法范畴）（表达式、语句、分程序、过程、函数、程序），并确定整个输入串是否构成语法上正确的程序。二.编译过程概述2.语法分析示例TONEXTFORKNMIJKKK:=100:=:=11010+**+变量、常数及其运算结果均是表达式表达式表达式表达式表达式表达式表达式赋值句的形式为“变量：＝表达式”赋值句赋值句多个赋值句可构成语句块语句块表达式可作为循环的初值和终值初值终值简单数值变量可作为循环的控制变量控制变量控制变量此时可以看出上述结果符合ＦＯＲ循环语句的语法定义，故语法分析成功完成二.编译过程概述3.语义分析以及中间代码生成任务所做转换依据语义规则主要理论基础属性文法语法范畴中间代码对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。第一阶段：对语法范畴进行静态语义检查，例如：变量是否定义、类型是否正确等。若语义正确，则进行第二阶段工作第二阶段：进行中间代码的翻译中间代码生成

将源程序翻译成中间代码。所谓“中间代码”是一种含义明确、便于处理的记号系统。这种记号系统与计算机的指令形式有某种程度的接近，能比较容易将其变换为计算机的机器指令。如“四元式”，其形式如下：算符左操作数右操作数结果中间代码生成例：Z=(X+0.418)*Y/W序号 算符左操作数右操作数结果(1)+X0.418T1(2)*T1YT2(3)/T2WZT1和T2是编译期间引进的临时变量3.中间代码生成示例TONEXTFORKNMIJKKK:=100:=:=11010+**+(1)(:=,1,,K)(2)(j<,100,K,)(3)(*,10,K,T1)(8)(j,,,(2))(7)(+,K,1,K)(4)(+,I,T1,M)(9)()(9)(5)(*,10,K,T2)(6)(+,J,T2,N)T1T2(1)K:=1(2)if100<Kgoto(9)(3)T1:=10*K(8)goto(2)(7)K:=K+1(4)M:=I+T1(9)(5)T2:=10*K(6)N:=J+T2生成四元式将四元式重写为另一种形式的中间代码(1)(:=,1,,K)(2)(j<,100,K,(9))(3)(*,10,K,T1)(8)(j,,,(2))(7)(+,K,1,K)(4)(+,I,T1,M)(9)()(5)(*,10,K,T2)(6)(+,J,T2,N)二.编译过程概述4.代码优化任务所做转换依据程序等价变换规则主要理论基础数据流方程中间代码中间代码（优化后）对于代码（主要是中间代码）进行加工变换，以期能够产生更为高效（省时间和空间）的目标代码。优化的主要方面有：公共子表达式的提取、循环优化、删除无用代码等二.编译过程概述4.代码优化示例(1)K:=1(2)if100<Kgoto(9)(3)T1:=10*K(8)goto(2)(7)K:=K+1(4)M:=I+T1(9)(5)T2:=10*K(6)N:=J+T2(3)K:=1(4)if100<Kgoto(9)(8)goto(4)(7)K:=K+1(9)(3)T1:=10*K(4)M:=I+T1(1)M:=I(5)M:=M+10(5)T2:=10*K(6)N:=J+T2(2)N:=J(6)N:=N+10(1)K:=1(2)if100<Kgoto(9)(8)goto(2)(7)K:=K+1(9)300次加法200次乘法300次加法二.编译过程概述5.目标代码生成任务所做转换依据硬件体系结构、指令系统中间代码目标代码将中间代码变换成特定机器上的低级语言代码目标代码形式绝对指令、可重定位指令、汇编指令二.编译过程概述6.目标代码生成LDR1,IL2:STR1,MLDR2,JSTR2,NLDR0,1L1:CMP100,R0J<L2ADDR1,10ADDR2,10ADDR0,1JL1示例(8)goto(4)(7)K:=K+1(1)M:=I(9)(6)N:=N+10(3)K:=1(2)N:=J(5)M:=M+10(4)if100<Kgoto(9)(9)(8)goto(4)(7)K:=K+1(1)M:=I(6)N:=N+10(3)K:=1(2)N:=J(4)if100<Kgoto(9)(5)M:=M+10三.编译程序的结构1.编译程序总框表格管理词法分析语法分析中间代码生成代码优化目标代码生成源程序单词符号中间代码语法单位目标代码中间代码出错处理三.编译程序的结构2.表格与表格管理编译各阶段均须维持表格并进行表格管理建表的技术支持是数据结构表格的分类、结构、处理方法决定于语言及机器，还有优化措施三.编译程序的结构2.表格与表格管理编译程序涉及的表格有：符号名表常量名、变量名、数组名、过程名、性质、引用、定义常数表标号表入口名表过程引用表各种类型常数的值标号的定义和引用情况过程的入口名和入口位置外部过程的名字、引用位置循环表等价名表公用链表格式表中间代码表三.编译程序的结构3.出错处理一个好的编译程序应该：全最大限度发现错误准准确指出错误的性质和发生地点局部化将错误的影响限制在尽可能小的范围内若能自动校正错误则更好，但其代价非常高三.编译程序的结构3.出错处理源程序中的错误通常分为：语法错误不符合语法（或词法）规则的错误语义错误不符合语义规则的错误单词拼写错误、括号不匹配...说明错误、作用域错误、类型不匹配...三.编译程序的结构4.遍遍是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。词法分析语法分析中间代码生成代码优化目标代码生成一遍语法分析器处于核心地位一遍局部优化一遍一遍全局优化三.编译程序的结构5.编译前端与后端词法分析语法分析中间代码生成代码优化目标代码生成编译前端主要由与源语言有关但与目标机无关的那些部分组成编译后端包括编译程序中与目标机有关的那些部分四.编译程序生成以往编译程序的构造大多采用机器语言或汇编语言现在编译程序的构造越来越多采用高级语言1.编译程序的构造工具有时为了充分发挥效率或满足不同需求，仍然采用机器语言或汇编语言构造编译程序（或其核心部分）四.编译程序生成2.T型图SITS表示源语言T表示目标语言I表示编译程序的实现语言四.编译程序生成3.用高级语言L1构造编译程序L1AAL2L1AL2AA已有用A机器代码实现的高级语言L1的编译程序可用高级语言L1编写另一个高级语言L2的编译程序将写好的语言L2的编译程序用L1的编译程序编译后就可得到用A机器代码实现的L2编译程序四.编译程序生成4.编译程序的移植LAA(1)LLB(2)LAB(3)已有A机器上的高级语言L编译程序（1）LBB(4)用L编写能在B机器上运行的L的编译程序（2）将(2)用(1)编译，得到A机器上运行的产生B代码的L的编译程序（3）LLB(2)再将(2)用(3)编译，即可得到B机器上运行的产生B代码的L的编译程序（4）至此，将A机器上的L的编译程序(1)移植为B机器上的L的编译程序（4）四.编译程序生成5.自编译方式先对语言的核心部分构造一个小小的编译程序（可用低级语言实现）再以它为工具构造能编译更多语言成分的较大编译程序如此不断扩展，最后形成整个编译程序（滚雪球）四.编译程序生成6.构造工具构造编译程序的工具称为编译程序-编译程序、编译程序产生器或翻译程序书写系统自动产生扫描器LEXFLEX自动产生语法分析器YACCBISON《程序设计语言编译原理》（第二版）陈火旺等国防工业出版社