编译原理基本知识.docx

编译原理基本知识基本概念程序生成过程源程序---用汇编语言或高级语言编写的程序称为源程序。目标程序---用目标语言所表示的程序。可以是介于源语言和机器语言之间的“中间语言”，可以是某种机器的机器语言,也可以是某机器的汇编语言。翻译程序---将源程序转换为目标程序的程序称为翻译程序。它是指各种语言的翻译器，包括汇编程序和编译程序，是汇编程序、编译程序以及各种变换程序的总称。诊断编译程序优化编译程序交叉编译程序可变目标编译程序汇编程序：若源程序用汇编语言书写，经过翻译程序得到用机器语言表示的程序，这时的翻译程序就称之为汇编程序，这种翻译过程称为“汇编”(Assemble）。编译程序：若源程序是用高级语言书写，经加工后得到目标程序，这种翻译过程称“编译”（Compile)。编译器编译器就是一个程序，它读入用某种语言编写的源程序，并翻译成一个与之等价的另一种语言编写的源程序。编译过程的基本阶段编译过程是指将高级语言程序翻译为等价的目标程序的过程。其一般包含5个基本阶段：词法分析任务：分析和识别单词。描述：源程序是由字符序列构成的，词法分析扫描源程序(字符串)，根据语言的词法规则分析并识别单词，并以某种编码形式输出。方法：词法分析依照词法规则，识别出正确的单词，转换成统一规格备用。转换：—对基本字，运算符，界符的转换—标识符的转换—常数的转换—转换完成后的格式（类号，内码）工具：正规式和有限自动机例子1：X1:= ( 2.0 + 0.8 ) * C11 2 3 4 5 6 7 8 9例子2：Void jisuan( ){ int y,c,d;float x,a,b;x=a+b*50;y=c+d*(x+b);}基本字：Void,int,float标识符：a,b,c,d,x,y,jisuan常数：50运算符：*,+,=,-界限符：{ } ; , ( )例子3：position = initial + rate * 60第一步：识别出单词（关键字、标识符、常数、算符和界符）。position、=、initial、+ 、rate、*、60第二步：并用记号表示识别出的单词（记号表示逻辑上相关的字符序列，常用整数来表示）。id1、id2、id3表示position、initial、rate第三步：输出结果（得到记号流）。id1=id2+id3*60语法分析任务：根据语法规则（即语言的文法），分析并识别出各种语法成分，如表达式、各种说明、各种语句、过程、函数等，并进行语法正确性检查。方法：推导（derive)和归约（reduce)。过程：具体地说，语法分析是在记号流的基础上建立一个层次结构——建立语法树。例子1：X1:= ( 2.0 + 0.8 ) * C1赋值语句的文法：赋值语句→变量赋值操作符表达式 变量→简单标识符 赋值操作符→:= 表达式→……例子2：id1=id2+id3*60语法树数据结构语义分析与生成中间代码任务：对识别出的各种语法成分进行语义分析，并产生相应的中间代码。主要工作包含（1）完成静态语义审查和处理；（2）上下文相关性审查；（3）类型匹配审查；（4）类型转换。中间代码：一种介于源语言和目标语言之间的中间语言形式。编译程序设计者可以自己设计，常用的有四元式、三元式、逆波兰表示等。四元式：四元式实际上是一种“三地址语句”的等价表示。它的一般形式为：(op,arg1,arg2,result)其中，op为一个二元 (也可是一元或零元)运算符；arg1,arg2分别为它的两个运算 (或操作)对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入result中。四元式还可写为类似于PASCAL语言赋值语句的形式：result ∶= arg1 op arg2。例子1：position = initial + rate * 60例子2：X1:= ( 2.0 + 0.8 ) * C1运算符左运算对象右运算对象结果(1) + 2.0 0.8T1(2) * T1 C1T2(3) :=X1T2其中T1和T2为编译程序引入的工作单元四元式的语义为： 2.0 + 0.8 → T1 T1 * C1 → T2 T2 → X1这样所生成的四元式与原来的赋值语句在语言的形式上不同，但语义上等价。目标代码优化任务：目的是为了得到高质量的目标程序。例子1：目的是为了得到高质量的目标程序。优化前：（1）2.0 + 0.8 → T1 （2）T1 * C1 → T2 （3）T2 → X1前面的四元式中第一个四元式是计算常量表达式值，该值在编译时就可以算出并存放在工作单元中，不必生成目标指令来计算，这样四元式可优化为：2.0 + 0.