编译原理第一章

编译原理编译原理这门课程主要介绍程序设计语言编译程序构造的一般原理、基本设计方法、主要实现技术和一些自动构造工具。基础知识：计算机工作原理一门高级语言（C，C++，Java等）汇编语言思考：为什么要学习编译原理汇编语言简介汇编执行指令是机器指令的符号化表示，其操作码用记忆符表示，地址码直接用标号、变量名字、常数等表示。汇编执行指令经汇编程序翻译为机器指令，二者之间基本上保持一一对应的关系。汇编语言编写程序虽不如高级程序设计语言简便、直观，但是汇编出的目标程序占用内存较少、运行效率较高，且能直接引用计算机的各种设备资源。它通常用于编写系统的核心部分程序，或编写需要耗费大量运行时间和实时性要求较高的程序段。第一章引论什么是编译程序编译过程和编译程序的结构编译过程概述编译程序的结构编译阶段的组合解释程序和一些软件工具程序设计语言泛型1.1什么是编译程序编译程序是现代计算机系统的基本组成部分。1.1什么是编译程序编译程序是一个语言翻译程序。翻译程序把一种语言（源语言）书写的程序翻译成另一种语言（目标语言）的等价程序。编译程序把高级语言所写的源程序翻译成等价的机器语言或汇编语言的目标程序。高级语言程序（源程序）机器（汇编）语言程序（目标程序）编译程序采用编译方式在计算机上执行用高级语言编写的程序，需分阶段进行。第一种情况源程序编译程序机器语言目标程序初始数据运行系统结果编译阶段运行阶段1.1什么是编译程序第二种情况1.1什么是编译程序源程序编译程序机器语言目标程序初始数据运行系统结果编译阶段运行阶段汇编程序汇编语言目标程序汇编阶段把汇编语言书写的程序翻译成与之等价的机器语言程序的翻译程序。语言处理过程

C程序#include<stdio.h>#include<stdlib.h>#defineMAX_LINES75Enumbooleans(FALSE,TRUE);Main(intargc,char*argv[]*)…

预处理器编译器汇编器装配连接编辑骨架程序

源程序

目标汇编程序

可重定位机器代码

绝对机器码可重定位目标文件库语言处理过程第一章引论什么是编译程序编译过程和编译程序的结构编译过程概述编译程序的结构编译阶段的组合解释程序和一些软件工具程序设计语言泛型1.2编译过程和编译程序的结构将英文句子“Iwishyousuccess”翻译成中文句子的大致过程是：分析一个个单词分析语法结构分析语义简单调整翻译成文1.2编译过程和编译程序的结构编译程序的工作过程：词法分析语法分析语义分析中间代码生成代码优化目标代码生成1.2编译过程和编译程序的结构源程序：PROGRAMm;VARa,b,c:real;BEGINread(b,c);a:=b+c*60;write(a)END.

词法分析阶段的任务是对构成源程序的字符串从左到右进行扫描和分解，根据语言的词法规则，识别出一个一个具有独立意义的单词(也称单词符号,简称符号)。词法分析

词法规则是单词符号的形成规则,它规定了哪样的字符串构成一个单词符号。词法规则<保留字，PROGRAM><标识符，m><分隔符,;><保留字,VAR><标识符,a><标识符,b><标识符,c><分隔符,:><标识符,real><分隔符,;><保留字,BEGIN>…...<标识符,a><算符,:=><标识符,b><算符,+><标识符,c><算符,*><常数,60>……<保留字,END><分隔符,.>语法分析

语法分析的任务是在词法分析的基础上,根据语言的语法规则从单词符号串中识别出各种语法单位(如表达式、说明、语句等),并进行语法检查,即检查各种语法单位在语法结构上的正确性。语法规则

语言的语法规则规定了如何从单词符号形成语法单位。表达式规则任何标识符都是表达式任何常数（整常数、实常数都是表达式）若表达式1和表达式2都是表达式，那么：表达式1+表达式2表达式1*表达式2（表达式1）都是表达式语法规则语句规则标识符:=表达式是语句While(表达式)do语句是语句If(表达式)then语句else语句是语句赋值语句经语法分析生成分析树赋值语句变量:=表达式表达式+项项因子b项*因子因子

c60a语义分析

语义分析的任务是首先对每种语法单位进行静态的语义审查，然后分析其含义。例如：

类型检查，审查每个运算符是否具有语言规范允许的运算对象赋值语句经语义分析生成语法树:=a+b*cinttoreal60特点：结构简单，含义明确的记号系统。设计原则：一容易生成，二被翻译成目标代码。常见的是近似“三地址指令”的“四元式”中间代码例如中间代码生成temp1:=inttoreal(60);temp2:=c*temp1;temp3:=b+temp2;a:=temp3;(:=60—temp1)(*ctemp1temp2)(+btemp2temp3)(:=temp3—a)不同层次的中间代码源语言（高级语言）中间代码（高级）中间代码（中级）中间代码（低级）floata[10][20];a[i][j+2];t1=a[i,j+2]t1=j+2t2=i*20t3=t1+t2t4=4*t3t5=addrat6=t5+t4t7=*t6r1=[fp-4]r2=[r1+2]r3=[fp-8]r4=r3*20r5=r4+r2r6=4*r5r7=fp–216f1=[r7+r6]代码优化

代码优化的任务是对前阶段产生的中间代码进行等价变换或改造，以期获得更为高效即省时间和空间的目标代码。优化主要包括局部优化和循环优化等，例如上述四元式经局部优化后得：temp1:=c*60.0a:=b+temp1(*c60temp1)(+btemp1a)目标代码生成

特点：将中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。该工作与硬件系统结构和指令含义有关。

movfc,r2;mulf#60.0,r2;movfb,r1;addfr2,r1;movfr1,a;编译程序结构(components)出错处理程序语法分析程序语义分析程序目标代码生成程序词法分析程序中间代码生成程序代码优化程序表格管理程序表格管理程序编译程序在工作过程中需要建立一些表格，以登记源程序中所提供的或在编译过程中所产生的一些信息，编译各个阶段的工作都涉及到构造、查找、修改或存取有关表格中的信息，因此，在编译程序中必须有一组管理各种表格的程序。出错处理程序编译程序在各个阶段应诊断和报告源程序中的错误，包括词法错误，语法错误，语义错误。编译程序应报告出错地点，并给出简明准确的提示信息。编译阶段的组合分析(analysis)和综合(synthesis)源程序的分析线性分析、层次分析、语义分析目标程序的综合编译阶段的划分前端（frontend）和后端（backend）－—编译的前端与源语言有关但与目标机无关的那些部分组成—编译的后端与目标机有关的那些部分组成编译阶段的组合遍（趟）：对输入文件（源程序或其等价的中间形式）从头到尾扫视，完成预定的处理。

遍输入文件输出文件把前端组织成一遍扫描词法分析语法分析语义分析和中间代码生成源程序中间代码符号表管理错误的诊查处理设计编译程序应首先研究的问题首先研究源程序的语法和语义及运行模型，源是设计编译程序的出发点。研究目标计算机，设计目标代码的指令系统，它是由目标计算机扩充而成，扩充后的计算机称作抽象计算机。目前的通用计算机往往和源语言执行模型不一致。。编译程序源程序目标程序抽象目标第一章引论什么是编译程序编译过程和编译程序的结构编译过程概述编译程序的结构编译阶段的组合解释程序和一些软件工具程序设计语言泛型

1.3解释程序和一些软件工具主要的途径有两个：通过编译程序和解释程序有些语言基本通过解释程序Java的Bytecode有些环境同时提供编译程序和解释系统Lisp编译程序低级语言程序高级语言程序高级语言程序解释程序计算结果编译程序和解释程序编译程序和解释程序区别执行过程：编译方式把源程序的执行过程严格地分成两大步：编译和运行。即先把源程序全部翻译成目标代码，然后再运行此目标代码，获执行结果。解释方式则不然。它是按照源程序中语句的动态顺序，直接地逐句进行分析解释，并立即执行。代码独立性：在编译方式下，机器上运行的是与源程序等价的目标程序，源程序和编译程序都不再参与目标程序的执行过程，而在解释方式下，解释程序和源程序(或某种等价表示)要参与到程序的运行过程中，运行程序的控制权在解释程序。编译程序和解释程序区别存储方式编译程序处理时,在源语言程序被编译阶段,存储区中要为源程序(中间形式)和目标代码开辟空间,要存放编译用的各种各样表格,比如符号表.在目标代码运行阶段,存储区中主要是目标代码和数据,编译所用的任何信息都不再需要.解释程序一般是把源程序一个语句一个语句的进行语法分析,转换为一种内部表示形式,存放在源程序区,因为解释程序允许在执行用户程序时修改用户程序,这就要求源程序,符号表等内容始终存放在存储区中,并且存放格式要设计的易于使用和修改.编译阶段和运行阶段存储结构编译时运行时名字表目标代码缓冲区编译用源程序中间表示各种表格目标代码区数据区源程序缓冲区解释系统存储结构解释系统源程序临时工作单元名字表标号表缓冲区(输入输出)栈区Java语言环境1.3处理源程序的软件工具1.语言的结构化编辑器2.语言程序的调试工具3.程序格式化工具

4.语言程序测试工具5.程序理解工具

6.高级语言之间的转换工具第一章引论什么是编译程序编译过程和编译程序的结构编译过程概述编译程序的结构编译阶段的组合解释程序和一些软件工具程序设计语言泛型4程序设计语言范型不同的应用侧重:数值计算--Fortran系统程序设计---C事务处理--Cobol人工智能---LISP自然语言处理---Prolog大型嵌入式实时处理---Ada其它---支持的计算模式:强制(命令)式语言---C,Fortran,Pascal应用(函数)式语言---ML，Lisp基于规则(逻辑）的语言---Prolog,Yacc面向对象语言---Ada,C++,Java

强制式语言(ImperativeLanguage)特点：过程式语言，语言面向动作，即一个计算过程看做是一系列动作。其特点是命令驱动，以语句形式表示，每个语句的执行引起若干存储单元中的值的改变语法形式；

语句1；语句2；语句3；

特点：应用式语言，更注重程序所表示的功能，而不是一个语句接一个语句地执行。程序执行过程是执行一个个函数施用在数据上的变换最终得到的结果语法形式:

functionn(