小型编译程序介绍.ppt

《小型编译程序介绍.ppt》由会员分享，可在线阅读，更多相关《小型编译程序介绍.ppt（58页珍藏版）》请在三一办公上搜索。

1、第九章 小型编译程序介绍,9.1 小型编译程序结构9.2 小型编译程序关于高级语言的规定9.3 小型编译程序关于单词的内部定义9.4 小型编译程序的LR分析表9.5 小型编译程序执行过程,9.1 小型编译程序结构,编译程序的工作贯穿于从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的。一般来说，整个过程可以划分成五个阶段：词法分析、语法分析、中间代码生成、优化和目标代码生成。第一阶段为词法分析。词法分析的任务是输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词符号，如保留字、标识符、常数、算符和界符等。,第二阶段为语法分析。语法分析的任务是在词法分析的基础上，根据语言的语

2、法规则(文法规则)把单词符号串分解成各类语法单位(语法范畴)，如“短语”、“子句”、“句子”、“程序段”和“程序”。通过语法分析确定整个输入串是否构成一个语法上正确的“程序”。第三阶段为中间代码产生。按语言的语义将语法分析出来的语法单位翻译成中间代码。一般而言，中间代码是一种独立于具体硬件的记号系统，但它与计算机的指令形式有某种程度的接近，或者能够比较容易地把它变换成计算机的机器指令。常用的中间代码有四元式、三元式、间接三元式和逆波兰记号等。,图9-1 编译程序结构示意,第四阶段为优化。优化的任务在于对前阶段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效(节省时间和空间)的目标代码

3、。第五阶段为目标代码生成。这一阶段的任务是把中间代码(或经优化处理之后)变换成特定机器上的绝对指令代码或可重新定位的指令代码或汇编指令代码。这一阶段实现了最后的翻译，它的工作有赖于硬件系统结构和机器指令含义。,上述编译过程的五个阶段是编译程序工作时的动态特征，编译程序的结构可以按照这五个阶段的任务分模块进行设计。编译程序的结构示意如图9-1所示。我们设计的小型编译程序包含除优化以外的其余各阶段。,9.2 小型编译程序关于高级语言的规定,高级语言程序具有四种基本结构：顺序结构选择结构循环结构和过程。为了便于掌握编译的核心内容，突出重点，简化编译程序的结构，同时又涵盖高级语言程序的基本结构，我们选

4、取赋值语句if语句和while语句作为前三种结构的代表，略去了过程结构。实际上，上述三种语句已经基本满足了高级语言的程序设计。因此，我们仅考虑由下面产生式所定义的程序语句：,Sif B then S else S while B do S begin L endA LS;LS Ai:=E BBBBBB(B)i rop ii EE+EE*E(E)i,其中，各非终结符的含义如下：S语句；L语句串；A赋值句；B布尔表达式；E算术表达式。,各终结符的含义如下：i整型变量或常数，布尔变量或常数；rop六种关系运算符的代表；;起语句分隔符作用；:=赋值符号；逻辑非运算符“not”；逻辑与运算符“and”；

5、,逻辑或运算符“or”；+算术加运算符；*算术乘运算符；(左括号；)右括号。注意，六种关系运算符分别为：不等于：大于=：大于等于=：等于,关于表达式的运算，我们规定由高到低优先顺序为算术运算、关系运算、布尔运算；并且服丛左结合规则。算术运算符优先级的顺序依次为“()”“*”“+”；布尔运算符优先级的顺序依次为“”“”“”；六个关系运算符优先级相同。我们规定的程序是由一条语句或由begin和end嵌套起来的复合语句组成的，并且规定在语句末要加上“#”表示程序结束。下面给出的是符合规定的程序示例：begin A:=A+B*C;C:=A+2;,while AB do if M=N then C:=D

6、 else while A=D do A:=D end#,9.3 小型编译程序关于单词的内部定义,由于我们规定的程序语句中涉及单词较少，故在词法分析阶段忽略了单词输入错误的检查，而将编译程序的重点放在中间代码生成阶段。词法分析器的功能是输入源程序，输出单词符号。我们规定输出的单词符号格式为如下的二元式：(单词种别，单词自身的值)我们对常量，变量，临时变量，保留关键字(if、while、begin、end、else、then、do等)，关系运算符，逻辑运算符，分号，括号等，规定其内部定义如表9-1所示。,表9-1 关于单词的内部定义,9.4 小型编译程序的LR分析表,1.算术表达式的LR分析表算

7、术表达式文法GE如下：E-E+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-BBBBBi rop iI 为了便于语法分析时的加工处理，我们将上述文法改写为文法GS：BBABBOBB(B)i rop ii BA B BO B,将文法GS拓广为文法GS：(0)SB(1)BI(2)Bi rop i(3)B(B)(4)BNOT B(5)AB AND(6)BAB(7)OB OR(8)BOB由此得到

8、布尔表达式的SLR(1)分析表如表9-3所示。,表9-3 布尔表达式的SLR分析表,3.程序语句的LR分析表程序语句的文法GS如下：Sif e then S else S while e do S begin L enda LS;LS由于在编译程序设计与实现中，我们是将赋值语句与算术表达式归为一类处理的，故在此将赋值语句仅看作为程序语句文法中的一个终结符a，将布尔表达式B也看作为终结符e。将文法GS拓广为文法GS：(0)SS,(1)Sif e then S else S(2)Swhile e do S(3)Sbegin L end(4)Sa(5)LS(6)LS;L由此得到程序语句的SLR(1)

9、分析表如表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)do begin if m=n then a:=a+1else

10、while k=h do x:=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*/,/*由四元式文件生成

11、的汇编文件*/*/data segment;定义数据段 h DW k DW m DW n DW x DW y DW a DW b DW,data ends;数据段定义结束;*code segment;定义代码段main proc far;程序的执行部分 assume cs:code,ds:datastart:;为返回操作系统入栈push dssub bx,bxpush bx,;设置DS段为当前数据段mov bx,datamov ds,bx100:mov AX,a;把条件跳转指令的第一操作数读入寄存器 cmp AX,b;把条件跳转指令的第一操作数和第二操作数相减 jg 102;大于则跳转101:

12、jmp 117;产生直接跳转指令,102:mov AX,m;把条件跳转指令的第一操作数读入寄存器 cmp AX,n;把条件跳转指令的第一操作数和第二操作数相减 jge 104;大于或等于则跳转103:jmp 107;产生直接跳转指令104:mov AX,a;把在存储器中的被加数赋给结果寄存器 add AX,1D;把被加数和加数立即数相加,105:mov BX,AX;执行赋值语句，寄存器中的值赋给结果变量 mov a,BX;在跳出基本块之前保存寄存器中已改变的变量106:jmp 112;产生直接跳转指令107:mov AX,k;把条件跳转指令的第一操作数读入寄存器 cmp AX,h;把条件跳转指

13、令的第一操作数和第二操作数相减 je 109;相等则跳转,108:jmp 112;产生直接跳转指令109:mov AX,x;把在存储器中的被加数赋给结果寄存器 add AX,2D;把被加数和加数立即数相加110:mov BX,AX;执行赋值语句，寄存器中的值赋给结果变量 mov x,BX;在跳出基本块之前保存寄存器中已改变的变量,111:jmp 107;产生直接跳转指令112:mov AX,m;把在存储器中的被加数赋给结果寄存器 add AX,y;把被加数和在存储器中的加数相加113:mul x;把被乘数和在存储器中的乘数相乘,114:mov BX,n;把在存储器中的被加数赋给结果寄存器 ad

14、d BX,AX;把被加数和在寄存器中的加数相加115:mov CX,BX;执行赋值语句，寄存器中的值赋给结果变量 mov m,CX;在跳出基本块之前保存寄存器中已改变的变量116:jmp 100;产生直接跳转指令,117:retmain endpcode ends;代码段定义结束end start,9.6 小型编译程序运行实例分析,我们以高级语言源程序到四元式的翻译为例对其进行分析。待编译的PAS.DAT源程序如下：while(ab)do begin if m=n then a:=a+1 else while k=h do x:=x+2;m:=n+x*(m+y)end#,经编译程序运行后得到的

15、输出结果如下：*词法分析结果*/*注释：查单词内部定义和下面的变量名表*/30/*(sy_while,0)*/480/*(,0)*/560/*(变量,a)*/42 3/*(rop,)*/56 1/*(变量,b)*/49 0/*(),0)*/,5 0/*(sy_do,0)*/4 0/*(sy_begin,0)*/0 0/*(sy_if,0)*/56 2/*(变量,m)*/42 2/*(rop,=)*/56 3/*(变量,n)*/1 0/*(sy_then,0)*/56 0/*(变量,a)*/,38 0/*(:=,0)*/56 0/*(变量,a)*/34 0/*(+,0)*/561/*(整常量,1

16、)*/2 0/*(sy_else,0)*/3 0/*(sy_while,0)*/56 4/*(变量,k)*/,press any key to continue 42 5/*(rop,=)*/56 5/*(变量,n)*/5 0/*(sy_do,0)*/56 6/*(变量,x)*/38 0/*(:=,0)*/56 6/*(变量,x)*/,34 0/*(+,0)*/57 2/*(整常量,2)*/8 0/*(;,0)*/56 2/*(变量,m)*/38 0/*(:=,0)*/56 3/*(变量,n)*/34 0/*(+,0)*/,56 6/*(变量,x)*/36 0/*(*,0)*/48 0/*(c

17、,c)*/56 2/*(变量,m)*/34 0/*(+,0)*/56 7/*(变量,y)*/49 0/*(),0)*/6 0/*(sy_end,0)*/10 0/*(#,0)*/,程序总共9行，产生了43个二元式！*变量名表*0 a1 b2 m3 n4 k5 h6 x7 y,*状态栈分析过程及归约顺序*stack0=0 n=3 lr=3 stack1=3 n=9 lr=7 stack2=7 n=5 lr=11 stack3=11 n=4 lr=4 stack4=4 n=0 lr=2 stack5=2 n=9 lr=6 stack6=6 n=1 lr=10 stack7=10 n=7 lr=5,

18、stack8=5 n=2 lr=104s-a归约 stack7=10 n=11 lr=14 stack8=14 n=2 lr=17 stack9=17 n=3 lr=3 stack10=3 n=9 lr=7 stack11=7 n=5 lr=11 stack12=11 n=7 lr=5 stack13=5 n=8 lr=104,s-a归约 stack12=11 n=11 lr=15 stack13=15 n=8 lr=102s-while e do s 归约 stack9=17 n=11 lr=18 stack10=18 n=8 lr=101,s-if e then s else s 归约 s

19、tack4=4 n=11 lr=9 stack5=9 n=8 lr=13 stack6=13 n=7 lr=5 stack7=5 n=6 lr=104s-a归约 stack6=13 n=11 lr=9 stack7=9 n=6 lr=105,L-s归约 stack6=13 n=12 lr=16 stack7=16 n=6 lr=106L-S;L归约 stack4=4 n=12 lr=8 stack5=8 n=6 lr=12 stack6=12 n=10 lr=103s-begin L end 归约 stack3=11 n=11 lr=15 stack4=15 n=10 lr=102,s-whi

20、le e do s 归约 stack0=0 n=11 lr=1 stack1=1 n=10 lr=-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)*,程序运行结束！注意，状态栈分析过程及归约顺序显示所给出的是

21、程序语句分析使用状态栈STACK加工分析的过程，而对算术表达式和布尔表达式使用的状态栈STACK的加工分析过程则没有显示(主要是考虑显示的内容过多)。因此，在程序语句分析中，当处理到赋值语句(它与算术表达式一同处理)和布尔表达式时，其处理过程是不显示的，它在程序语句分析中只显示出已加工处理后的终结符号a(代表赋值语句)和e(代表布尔表达式)。,在状态栈分析过程及归约顺序显示中，STACK栈由栈底到当前栈顶显示了根据程序语句LR分析表(见表9-4)加工分析的所有状态，而LR栏则是根据当前扫描的单词符号(由n所指)在分析表对应的下一状态(小于100为移进状态，大于等于100为归约状态)。我们仍按LR分析表控制下的翻译格式给出状态栈STACK信息所对应的符号栈内容，这些符号栈内容可以由状态栈STACK中的信息和LR分析表分析推出。分析的结果见表9-5(状态栈STACK内容由竖向改为横向)。,表9-5 状态栈分析加工过程,