编译原理12编译过程阶段优秀PPT.ppt
例例:position:initial rate*10以下从源程序在不同阶段所被转换成的表示以下从源程序在不同阶段所被转换成的表示形式来介绍各个阶段的任务形式来介绍各个阶段的任务 1)词法分析 Lexical analysis,Scanning 字符流字符流 单词流单词流从左到右扫描从左到右扫描,识别出单词识别出单词单词,单词符号,符号,Token什么是单词什么是单词逻辑上紧密相连的一组字符，这些字符具有集体逻辑上紧密相连的一组字符，这些字符具有集体含义。含义。sequences of characters having collective meaning.五类单词五类单词标识符标识符保留字（关保留字（关 键字、基本字）键字、基本字）常量（常数）常量（常数）运算符（算符）运算符（算符）界符界符position:initial rate*10 单词类型单词类型单词值单词值标识符（标识符（1）position算符（赋值号）算符（赋值号）：标识符（标识符（2）initial算符（加号）算符（加号）标识符（标识符（3）rate算符（乘号）算符（乘号）*整数整数 10界符（分号）界符（分号）；字符流 单词流position:initial rate*10；id1:=id2+id3*10 词法分析程序的其他功能滤掉注释和空白滤掉注释和空白 供应出错的行号标记供应出错的行号标记宏处理宏处理 词法分析中的错误9position:=initial rate*60；9,position,:=:=词法分析阶段词法分析阶段,不会显示错误不会显示错误 关于词法分析词法分析程序的自动生成工具词法分析程序的自动生成工具LEX词法分析的依据词法分析的依据 词法规则词法规则描述词法规则的工具描述词法规则的工具正规式正规式有限自动机有限自动机2)语法分析Syntax analysis,Parsing 单词流单词流-语法短语语法短语检查源程序的结构是否符合语法规则检查源程序的结构是否符合语法规则 语法短语,语法单位表达式表达式,语句语句,函数函数,程序段程序段,程序程序 position:initial rate*10；id1:=id2+id3*10分析树分析树Parse Tree 赋值语句赋值语句标识符标识符表达式表达式表达式表达式表达式表达式id1(position)id2(initial)id3(rate)10标识符标识符标识符标识符整数整数表达式表达式表达式表达式:=+*id1:=id2+id3*10语法树语法树 Syntax Tree 词法分析和语法分析的界限 词法结构词法结构线性分析线性分析(Linear Analysis)不须要递归不须要递归语法结构语法结构层次分析层次分析(Hierarchical Analysis)须要递归须要递归 关于语法分析语法分析程序的自动生成工具语法分析程序的自动生成工具YACC语法分析的依据语法分析的依据语法规则语法规则描述语法规则的工具描述语法规则的工具文法文法BNF范式范式(BACKUS-NAUR FORM)3)语义分析Semantic analysis对结构上正确的源程序审查有无语义错误对结构上正确的源程序审查有无语义错误静态语义静态语义类型匹配审查类型匹配审查类型转换类型转换动态语义（运行语义，执行语义）动态语义（运行语义，执行语义）例如数组越界、存储空间越界例如数组越界、存储空间越界 语法正确但语义错误语法正确但语义错误 类型不匹配类型不匹配 例例1：int arr2,b;b=arr*10;例例2：Program p(input,output);Var rate:real;procedure initial;position:=initial+rate*10例例3：int arr2,c;c=arr1*10;变量没有声明变量没有声明举例举例:符合语法规则但不符合语义规则运用没有声明的变量运用没有声明的变量给一个过程名赋值给一个过程名赋值调用函数时参数类型不合适调用函数时参数类型不合适实数用作数组下标实数用作数组下标参与运算的两个变量类型不匹配参与运算的两个变量类型不匹配 Var rate:real;position:=initial+rate*10插入语义结点插入语义结点关于语义分析语义分析程序的自动生成工具语义分析程序的自动生成工具 无无语义分析的依据语义分析的依据-语义规则语义规则描述语义规则的工具描述语义规则的工具属性文法属性文法4)中间代码生成阶段 Intermediate Code Generation 中间语言中间语言,中间表示中间表示生成原则生成原则介于高级语言和低级语言之间介于高级语言和低级语言之间简洁生成简洁生成简洁将它翻译成目标代码简洁将它翻译成目标代码与目标机无关，便于优化、移植与目标机无关，便于优化、移植四元式、三元式、树结构四元式、三元式、树结构Pcode,Ccode,Bytecode 四元式(运算符，运算对象运算符，运算对象1，运算对象，运算对象2，结果，结果)(*,a,b,c)c=a*b position:initial rate*10；id1:=id2+id3*10id1:=id2+id3*inttoreal(10)id1:=id2+id3*inttoreal(10)(op，arg1，arg2，result)问题问题:运算依次是如何确定的运算依次是如何确定的?(1)(2)(3)(4)(inttoreal*+:=10 id3id2t3 t1t2 t1)t2)t3)id1)t1、t2、t3为临时工作单元为临时工作单元也可以将四元式干脆写成赋值的语句的形式也可以将四元式干脆写成赋值的语句的形式例：例：a=b*c+b*d 的四元式序列为：的四元式序列为：(1)t1=b*c(2)t2=b*d(3)t3=t1+t2(4)a=t3 例：例：if(a bif t1 goto Lt2=a ca=t2L:t3=b*cc=t35)代码优化Code Optimization 中间代码优化中间代码优化目标代码优化目标代码优化(1)(2)(3)(4)(inttoreal*+:=10 id3id2t3 t1t2 t1)t2)t3)id1)源语句源语句id1:=id2+id3*inttoreal(10)的代码序列的代码序列经优化得到优化的代码序列经优化得到优化的代码序列(1)(2)*+id3id210.0t1t1)id1)6)目标代码生成把中间代码变换成特定机器上的确定指令代把中间代码变换成特定机器上的确定指令代码或可重定位的指令代码或汇编指令代码码或可重定位的指令代码或汇编指令代码涉及到的内容涉及到的内容:硬件系统功能部件的运用硬件系统功能部件的运用机器指令的选择机器指令的选择各种数据类型变量的存储空间安排各种数据类型变量的存储空间安排关键问题是变量的寄存器安排关键问题是变量的寄存器安排(1)(2)(3)(4)(5)MOVFMULFMOVFADDFMOVFid3#10.0id2R2R1R2R2R1R1id1(1)(2)*+id3id210.0t1t1)id1)7)表格管理8)出错处理例:PL/0 语言 (PASCAL语言的子集)CONST A=35,B=49;VAR C,D,E;PROCEDURE P;VAR G;NAME:A KIND:CONSTANTVAL:35NAME:BKIND:CONSTANTVAL:49NAME:C KIND:VARIABLELEVEL:LEVADR:DXNAME:D KIND:VARIABLELEVEL:LEVADR:DX+1NAME:EKIND:VARIABLELEVEL:LEVADR:DX+2NAME:PKIND:PROCEDURE LEVEL:LEVADR:SIZE:4NAME:G KIND:VARIABLELEVEL:LEV+1 ADR:DXposition:=initial+rate*101.1.词法分析器词法分析器id1:=id2+id3*10positioninitialrate321符号表符号表2.2.语法分析器语法分析器id1:=id2+id3*103.3.语义分析器语义分析器4.4.中间代码生成器中间代码生成器(1)(2)(3)(4)(inttoreal*+:=10 id3id2t3 t1t2 t1)t2)t3)id1)5.5.代码优化器代码优化器(1)(2)*+id3id210.0t1t1)id1)6.6.目标代码生成器目标代码生成器(1)(2)(3)(4)(5)MOVFMULFMOVFADDFMOVFid3#10.0id2R2R1R2R2R1R1id1
