1_编译原理绪论(1)

1教学安排与要求一.课程任务和目的程序设计语言编译程序构造的基本原理和实现方法是软件的核心技术之一。具有分析和实现编译程序的能力提高对高级程序设计语言的理解和应用能力。通过正则式、自动机和形式语言的学习，培养形式化的能力。2二、教学介绍1。作业；2。上机实验；3。课堂和实验教学与第2章和附录A的PL/0编译程序紧密结合，要求读懂源程序，完成扩充编译器的实验，为期末课程设计打好基础。3三、教学要求课前预习按时完成作业认真阅读分析PL/0编译器重视实验，交实验报告4第1章绪论1.1编译程序1.2解释程序1.3编译程序的结构1.4编译程序的设计51.1编译程序机器语言：能够被计算机的硬件系统直接执行的指令程序。汇编语言：将硬件指令用一些助记符表示。如ADD表示加法操作，SUB表示减法操作等等高级语言：使用便于理解的自然语言。61.1编译程序翻译程序：将一种语言（源语言）翻译成另一种逻辑上等价的语言（目标语言）的程序。汇编程序：将汇编语言翻译成机器语言的翻译程序。编译程序：将高级语言翻译成汇编语言或机器语言的翻译程序。编译程序低级语言程序(目标程序)高级语言程序(源程序)7机器语言──计算机指令系统低级语言语言汇编语言──符号化的指令系统高级语言──算法语言，不依赖具体机器，面向问题源程序翻译程序目标程序汇编语言程序汇编程序机器语言程序计算机高级语言程序编译程序连接程序8什么是编译程序分类–软件–系统软件–语言处理系统操作系统编译系统裸机9分类软件：计算机系统中的程序及其文档系统软件：居于计算机系统中最靠近硬件的一层，其他软件一般都通过系统软件发挥作用。和具体的应用领域无关，如编译系统和操作系统等。语言处理系统：把软件语言书写的各种程序处理成可在计算机上执行的程序。软件语言：用于书写软件的语言。它主要包括需求定义语言，功能性语言，设计性语言，程序设计语言以及文档语言。10预处理器编译器汇编器装配连接编辑框架程序源程序目标汇编程序可重定位机器代码绝对机器码可重定位目标文件库语言处理过程.c.cpp.java.pas.asm.obj.exe.dll.lib11什么是编译程序语言转(变)换系统C++翻译器C++CJavaBytecodeJava编译器12源语言实现语言目标语言汇编语言汇编程序机器语言高级语言编译程序低级语言高级语言预处理程序高级语言翻译对象翻译程序翻译结果13编译（笔译）解释（口译）产生目标程序，可多次执行，边解释边执行，不产生目标程序，优化较充分，执行效率高。优化不充分，总体效率较低。但编译器本身较大，但解释器本身较小，较复杂，不便人机对话较简单，便于人机对话源语言：Pascal，C,源语言：BASIC,LISP,Java等FORTRAN等源编结源程序解结程译目标程序释序器果初始数据器果运行库初始数据编译程序和解释程序比较14术语编译程序(compiler)编译程序的源语言(源程序)(sourcelanguage/program)编译程序的目标语言(目标程序)(objectortargetlanguage/program)编译程序的实现语言(implementationlanguage)语言处理程序(languageprocessor)语言转(变)换(languagetransformation)151.3编译程序的结构词法分析语法分析语义分析中间代码生成代码优化目标代码生成源程序目标程序161.3编译程序的结构词法分析（扫描器，Scanner）扫描、分解源程序，识别单词（基本字标识符、常数、运算符、界限符），并给予种别（属性）和内部形式（值）构成单词的内部表示。17例：源程序PROGRAMm;VARa,b,c:real;BEGINread(b,c);a:=b+c*60;write(a)；END.1.3编译程序的结构保留字，PROGRAM标识符，m分隔符,;保留字,VAR标识符,a标识符,b标识符,c分隔符,:标识符,real分隔符,;保留字,BEGIN…...标识符,a算符,:=标识符,b算符,+标识符,c算符,*整数,60……保留字,END分隔符,.源程序被分析成字符流18语法分析（分析器，Analyzer）语法检查，分析源程序的语法结构，并用明确的结构（如语法树）表示。1.3编译程序的结构对于前一个例子的单词序列：a:=b+c*60可表示为：19a:=b+c*60经语法分析得到的语法树表达式3赋值语句标识符∶=表达式1表达式2+表达式5ab标识符表达式4*60整数c标识符1.3编译程序的结构20语义分析检查程序有无语义错误，为代码生成阶段收集类型信息。21语义分析语义审查(静态语义)–上下文相关性–类型匹配–类型转换例:programp();varrate:real;procedureinitial;…position:=initial+rate*60;/*error*//*error*//*warning*/…1.3编译程序的结构22又如:intarr[2],abc;abc=arr*10;…programp();varrate:real;varinitial:real;varposition:real;…position:=initial+rate*6023语义分析60:=+*Id1positionId2initialId3rateinttoreal1.3编译程序的结构24中间代码生成语义分析，生成中间代码。便于代码优化，便于从逻辑上分出与语言或机器无关的阶段。设计原则：1、容易生成；2、容易被翻译成目标代码；1.3编译程序的结构25中间代码的生成（inttoreal60—t1）（*ct1t2）（+bt2t3）（:=t3—a）1.3编译程序的结构26代码优化──可多次局部优化：合并已知量──编译时计算常量表达式改变计算顺序──减少指令、减少中间量共享子表达式──删除多余代码降低运算强度──乘方乘1.3编译程序的结构27代码优化——可多次循环优化：循环不变部分外提下标地址计算优化降低运算强度──乘加与机器有关的优化：使用特殊指令──如计数转移指令寄存器分配1.3编译程序的结构28目标代码的生成把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。1.3编译程序的结构29代码优化和目标代码的生成（*c60.0t1）（+bt1t2）（:=t2—a）movfc,r2;mulf#60.0,r2;movfb,r1;addfr2,r1;movr1,a;1.3编译程序的结构30表格管理（符号表）为了合理的管理表格（构造、查找、更新），设立一些专门子程序称为表格管理程序负责管理表格。出错处理编译程序在各个阶段应诊断和报告源程序中的错误，包括词法错误、语法错误和语义错误等。1.3编译程序的结构31符号表名字种类类型层次偏移量m过程0a变量real1db变量real1d+4c变量real1d+81.3编译程序的结构32出错处理语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理331.4编译程序的组织前端和后端源程序中间代码目标程序分遍（趟，PASS）问题前端后端34分遍（趟，pass）问题在编译过程中，扫描源（中间）程序的次数称为该编译程序的“遍”数。决定分遍次数的因素有：（1）源语言FORTRAN、Pascal等，只需单遍扫描；ALGOL60要两遍扫描，ALGOL68要三遍扫描。若允许先使用、后说明，则通常需要多遍扫描。N.Wirth的第一个Pascal编译器是在CDC6000上实现的一遍编译器（递归子程序法）。“在一台内存相当大的高速计算机实现高效编译的关键是一遍加工方案”35（2）机器，尤其是内、外存的大小。内存小，可能需要多遍。（3）优化要求。充分优化需要多遍。多遍的结构清晰，优化好，但重复工作多，输入输出多，编译器本身代码长，且编译速度慢，出错处理较困难。本书的PL/0编译器就是一个单遍编译器。36高级语言解释系统(interpreter)功能让计算机执行高级语言（basic,lisp,prolog)与编译程序的不同1）不生成目标代码2）能支持交互环境（同增量式编译系统）源程序初始数据解释程序计算结果37解释系统直接对源程序中的语句进行分析，执行其隐含的操作。如：……b:=2;a:=b+2;编译程序writea;……解释程序直接将4的值输出（显示）Int2StbLdbAdd2Sta生成代码38编译阶段和运行阶段存储结构编译时运行时名字表目标代码缓冲区编译用源程序中间表示各种表格目标代码区数据区源程序缓冲区39解释系统存储结构解释系统源程序工作单元名字表标号表缓冲区(输入输出)栈区40《编译原理》教材内容第1章概述第2章PL/0编译系统第3章文法和语言第4章词法分析第5章自顶向下语法分析第6章自底向上语法分析第7章LR分析第8章语法制导翻译和中间代码生成第9章符号表第10章运行时的存储组织和管理第11章代码优化第12章代码生成学时：授课56上机8课程设计一周