《小型编译程序介绍》PPT课件.ppt

第九章小型编译程序介绍,9.1小型编译程序结构9.2小型编译程序关于高级语言的规定9.3小型编译程序关于单词的内部定义9.4小型编译程序的LR分析表9.5小型编译程序执行过程,9.1小型编译程序结构,编译程序的工作贯穿于从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的。一般来说，整个过程可以划分成五个阶段：词法分析、语法分析、中间代码生成、优化和目标代码生成。第一阶段为词法分析。词法分析的任务是输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号，如保留字、标识符、常数、算符和界符等。,第二阶段为语法分析。语法分析的任务是在词法分析的基础上，根据语言的语法规则(文法规则)把单词符号串分解成各类语法单位(语法范畴)，如“短语”、“子句”、“句子”、“程序段”和“程序”。通过语法分析确定整个输入串是否构成一个语法上正确的“程序”。第三阶段为中间代码产生。按语言的语义将语法分析出来的语法单位翻译成中间代码。一般而言，中间代码是一种独立于具体硬件的记号系统，但它与计算机的指令形式有某种程度的接近，或者能够比较容易地把它变换成计算机的机器指令。常用的中间代码有四元式、三元式、间接三元式和逆波兰记号等。,图9-1编译程序结构示意,第四阶段为优化。优化的任务在于对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效(节省时间和空间)的目标代码。第五阶段为目标代码生成。这一阶段的任务是把中间代码(或经优化处理之后)变换成特定机器上的绝对指令代码或可重新定位的指令代码或汇编指令代码。这一阶段实现了最后的翻译，它的工作有赖于硬件系统结构和机器指令含义。,上述编译过程的五个阶段是编译程序工作时的动态特征，编译程序的结构可以按照这五个阶段的任务分模块进行设计。编译程序的结构示意如图9-1所示。我们设计的小型编译程序包含除优化以外的其余各阶段。,9.2小型编译程序关于高级语言的规定,高级语言程序具有四种基本结构：顺序结构选择结构循环结构和过程。为了便于掌握编译的核心内容，突出重点，简化编译程序的结构，同时又涵盖高级语言程序的基本结构，我们选取赋值语句if语句和while语句作为前三种结构的代表，略去了过程结构。实际上，上述三种语句已经基本满足了高级语言的程序设计。因此，我们仅考虑由下面产生式所定义的程序语句：,SifBthenSelseSwhileBdoSbeginLendALS;LSAi:=EBBBBBB(B)iropiiEE+EE*E(E)i,其中，各非终结符的含义如下：S语句；L语句串；A赋值句；B布尔表达式；E算术表达式。,各终结符的含义如下：i整型变量或常数，布尔变量或常数；rop六种关系运算符的代表；;起语句分隔符作用；:=赋值符号；逻辑非运算符“not”；逻辑与运算符“and”；,逻辑或运算符“or”；+算术加运算符；*算术乘运算符；(左括号；)右括号。注意，六种关系运算符分别为：不等于：大于=：大于等于=：等于,关于表达式的运算，我们规定由高到低优先顺序为算术运算、关系运算、布尔运算；并且服丛左结合规则。算术运算符优先级的顺序依次为“()”“*”“+”；布尔运算符优先级的顺序依次为“”“”“”；六个关系运算符优先级相同。我们规定的程序是由一条语句或由begin和end嵌套起来的复合语句组成的，并且规定在语句末要加上“#”表示程序结束。下面给出的是符合规定的程序示例：beginA:=A+B*C;C:=A+2;,whileABdoifM=NthenC:=DelsewhileAE+EE*E(E)I将文法GE拓广为文法GE：(0)SE(1)EE+E(2)EE*E(3)E(E)(4)Ei由此得到算术表达式的SLR(1)分析表如表9-2所示。,表9-2算术表达式的SLR(1)分析表,2布尔表达式的LR分析表布尔表达式的文法如下：B-BBBBBiropiI为了便于语法分析时的加工处理，我们将上述文法改写为文法GS：BBABBOBB(B)iropiiBABBOB,将文法GS拓广为文法GS：(0)SB(1)BI(2)Biropi(3)B(B)(4)BNOTB(5)ABAND(6)BAB(7)OBOR(8)BOB由此得到布尔表达式的SLR(1)分析表如表9-3所示。,表9-3布尔表达式的SLR分析表,3.程序语句的LR分析表程序语句的文法GS如下：SifethenSelseSwhileedoSbeginLendaLS;LS由于在编译程序设计与实现中，我们是将赋值语句与算术表达式归为一类处理的，故在此将赋值语句仅看作为程序语句文法中的一个终结符a，将布尔表达式B也看作为终结符e。将文法GS拓广为文法GS：(0)SS,(1)SifethenSelseS(2)SwhileedoS(3)SbeginLend(4)Sa(5)LS(6)LS;L由此得到程序语句的SLR(1)分析表如表9-4所示。,表9-4程序语句的SLR分析表,9.5小型编译程序执行过程,小型编译程序执行分两个阶段：第一个阶段，将高级语言源程序翻译成四元式程序；第二个阶段，将四元式程序翻译成汇编语言目标程序。执行过程示意如图9-2所示。,图9-2执行过程示意,下例为一个名为PAS.DAT的高级语言源程序经过PAS的编译，产生名为PAS.MED的四元式(中间代码)程序；PAS.MED经过COMPILER编译生成8086/8088汇编语言目标程序PAS.ASM。/*/*pas.dat*/*高级语言源程序*/*/,while(ab)dobeginifm=nthena:=a+1elsewhilek=hdox:=x+2;m:=n+x*(m+y)end#,/*/*pas.med*/*高级语言生成的四元式文件*/*/100(j,a,b,102)101(j,117)102(j=,m,n,104)103(j,107)104(+,a,1,T1),105(:=,T1,a)106(j,112)107(j=,k,h,109)108(j,112)109(+,x,2,T2)110(:=,T2,x)111(j,107),112(+,m,y,T3)113(*,x,T3,T4)114(+,n,T4,T5)115(:=,T5,m)116(j,100)/*/*pas.asm*/,/*由四元式文件生成的汇编文件*/*/datasegment;定义数据段hDWkDWmDWnDWxDWyDWaDWbDW,dataends;数据段定义结束;*codesegment;定义代码段mainprocfar;程序的执行部分assumecs:code,ds:datastart:;为返回操作系统入栈pushdssubbx,bxpushbx,;设置DS段为当前数据段movbx,datamovds,bx100:movAX,a;把条件跳转指令的第一操作数读入寄存器cmpAX,b;把条件跳转指令的第一操作数和第二操作数相减jg102;大于则跳转101:jmp117;产生直接跳转指令,102:movAX,m;把条件跳转指令的第一操作数读入寄存器cmpAX,n;把条件跳转指令的第一操作数和第二操作数相减jge104;大于或等于则跳转103:jmp107;产生直接跳转指令104:movAX,a;把在存储器中的被加数赋给结果寄存器addAX,1D;把被加数和加数立即数相加,105:movBX,AX;执行赋值语句，寄存器中的值赋给结果变量mova,BX;在跳出基本块之前保存寄存器中已改变的变量106:jmp112;产生直接跳转指令107:movAX,k;把条件跳转指令的第一操作数读入寄存器cmpAX,h;把条件跳转指令的第一操作数和第二操作数相减je109;相等则跳转,108:jmp112;产生直接跳转指令109:movAX,x;把在存储器中的被加数赋给结果寄存器addAX,2D;把被加数和加数立即数相加110:movBX,AX;执行赋值语句，寄存器中的值赋给结果变量movx,BX;在跳出基本块之前保存寄存器中已改变的变量,111:jmp107;产生直接跳转指令112:movAX,m;把在存储器中的被加数赋给结果寄存器addAX,y;把被加数和在存储器中的加数相加113:mulx;把被乘数和在存储器中的乘数相乘,114:movBX,n;把在存储器中的被加数赋给结果寄存器addBX,AX;把被加数和在寄存器中的加数相加115:movCX,BX;执行赋值语句，寄存器中的值赋给结果变量movm,CX;在跳出基本块之前保存寄存器中已改变的变量116:jmp100;产生直接跳转指令,117:retmainendpcodeends;代码段定义结束endstart,9.6小型编译程序运行实例分析,我们以高级语言源程序到四元式的翻译为例对其进行分析。待编译的PAS.DAT源程序如下：while(ab)dobeginifm=nthena:=a+1elsewhilek=hdox:=x+2;m:=n+x*(m+y)end#,经编译程序运行后得到的输出结果如下：*词法分析结果*/*注释：查单词内部定义和下面的变量名表*/30/*(sy_while,0)*/480/*(,0)*/560/*(变量,a)*/423/*(rop,)*/561/*(变量,b)*/490/*(),0)*/,50/*(sy_do,0)*/40/*(sy_begin,0)*/00/*(sy_if,0)*/562/*(变量,m)*/422/*(rop,=)*/563/*(变量,n)*/10/*(sy_then,0)*/560/*(变量,a)*/,380/*(:=,0)*/560/*(变量,a)*/340/*(+,0)*/561/*(整常量,1)*/20/*(sy_else,0)*/30/*(sy_while,0)*/564/*(变量,k)*/,pressanykeytocontinue425/*(rop,=)*/565/*(变量,n)*/50/*(sy_do,0)*/566/*(变量,x)*/380/*(:=,0)*/566/*(变量,x)*/,340/*(+,0)*/572/*(整常量,2)*/80/*(;,0)*/562/*(变量,m)*/380/*(:=,0)*/563/*(变量,n)*/340/*(+,0)*/,566/*(变量,x)*/360/*(*,0)*/480/*(c,c)*/562/*(变量,m)*/340/*(+,0)*/567/*(变量,y)*/490/*(),0)*/60/*(sy_end,0)*/100/*(#,0)*/,程序总共9行，产生了43个二元式！*变量名表*0a1b2m3n4k5h6x7y,*状态栈分析过程及归约顺序*stack0=0n=3lr=3stack1=3n=9lr=7stack2=7n=5lr=11stack3=11n=4lr=4stack4=4n=0lr=2stack5=2n=9lr=6stack6=6n=1lr=10stack7=10n=7lr=5,stack8=5n=2lr=104s-a归约stack7=10n=11lr=14stack8=14n=2lr=17stack9=17n=3lr=3stack10=3n=9lr=7stack11=7n=5lr=11stack12=11n=7lr=5stack13=5n=8lr=104,s-a归约stack12=11n=11lr=15stack13=15n=8lr=102s-whileedos归约stack9=17n=11lr=18stack10=18n=8lr=101,s-ifethenselses归约stack4=4n=11lr=9stack5=9n=8lr=13stack6=13n=7lr=5stack7=5n=6lr=104s-a归约stack6=13n=11lr=9stack7=9n=6lr=105,L-s归约stack6=13n=12lr=16stack7=16n=6lr=106L-S;L归约stack4=4n=12lr=8stack5=8n=6lr=12stack6=12n=10lr=103s-beginLend归约stack3=11n=11lr=15stack4=15n=10lr=102,s-whileedos归约stack0=0n=11lr=1stack1=1n=10lr=-2*四元式分析结果*100(j,a,b,102)101(j,117),102(j=,m,n,104)103(j,107)104(+,a,1,T1)105(:=,T1,a)106(j,112)107(j=,k,h,109)108(j,112)109(+,x,2,T2),110(:=,T2,x)111(j,107)112(+,m,y,T3)113(*,x,T3,T4)114(+,n,T4,T5)115(:=,T5,m)116(j,100)*,程序运行结束！注意，状态栈分析过程及归约顺序显示所给出的是程序语句分析使用状态栈STACK加工分析的过程，而对算术表达式和布尔表达式使用的状态栈STACK的加工分析过程则没有显示(主要是考虑显示的内容过多)。因此，在程序语句分析中，当处理到赋值语句(它与算术表达式一同处理)和布尔表达式时，其处理过程是不显示的，它在程序语句分析中只显示出已加工处理后的终结符号a(代表赋值语句)和e(代表布尔表达式)。,在状态栈分析过程及归约顺序显示中，STACK栈由栈底到当前栈顶显示了根据程序语句LR分析表(见表9-4)加工分析的所有状态，而LR栏则是根据当前扫描的单词符号(由n所指)在分析表对应的下一状态(小于100为移进状态，大于等于100为归约状态)。我们仍按LR分析表控制下的翻译格式给出状态栈STACK信息所对应的符号栈内容，这些符号栈内容可以由状态栈STACK中的信息和LR分析表分析推出。分析的结果见表9-5(状态栈STACK内容由竖向改为横向)。,表9-5状态栈分析加工过程,