《第6章 语法制导翻译和中间代码生成.ppt》由会员分享，可在线阅读，更多相关《第6章 语法制导翻译和中间代码生成.ppt（28页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第6章 语法制导翻译和中间代码生成 n语法分析和语义分析的区别n语义分析主要工作n建立符号表和常数表。n诊察和报告源程序中的语义错误。n根据语言的语义产生中间代码（或机器指令），或直接解释执行。6.1 语法制导翻译概述语法制导翻译概述 n语法制导翻译方法简介语法制导翻译方法简介n为每一个产生式配一个语义子程序。在为每一个产生式配一个语义子程序。在语法分析过程中，当一个产生式获得匹语法分析过程中，当一个产生式获得匹配或用于归约时，此产生式相应的语义配或用于归约时，此产生式相应的语义子程序进入工作，完成既定的翻译任务。子程序进入工作，完成既定的翻译任务。6.1 语法制导翻译概述语法制导翻译概述n实
2、现方法（以实现方法（以SLR分析器为例）分析器为例）n分析表不变分析表不变n改造工作栈改造工作栈n状态栈状态栈n符号栈符号栈 n单词值栈：用于保存单词的值（字符串形式）。单词值栈：用于保存单词的值（字符串形式）。n语义栈：用于记录分析过程中需保留的语义值。例，值（语义栈：用于记录分析过程中需保留的语义值。例，值（val）、）、地址（地址（addr）、）、种属（种属（cat）、）、类型（类型（type）等。等。n修改总控程序修改总控程序n在移进时，除移进状态和单词的种别外，还需移进单词的值。在移进时，除移进状态和单词的种别外，还需移进单词的值。n在用某个产生式进行归约时，除需执行归约动作外，还需
3、调用相在用某个产生式进行归约时，除需执行归约动作外，还需调用相应语义子程序。应语义子程序。6.1 语法制导翻译概述语法制导翻译概述n解释执行例解释执行例n文法及语义子程序文法及语义子程序nSLR分析表分析表n手工计算手工计算n7+9*5 6.2 符号表和常数表符号表和常数表 n符号表符号表n引入符号表的意义引入符号表的意义n符号表的结构（略有修改）符号表的结构（略有修改）nstruct nvoid*addr;/标号或变量的地址标号或变量的地址nchar id5;/标识符名标识符名nunsigned cat:4;/种属（种属（4个二进制位）个二进制位）nunsigned type:4;/类型（类
4、型（4个二进制位）个二进制位）n sym_tableNS;/NS表示符号表长度表示符号表长度n符号表的使用符号表的使用n符号表地址使用说明符号表地址使用说明6.2 符号表和常数表符号表和常数表n常数表常数表n常数表结构常数表结构nunsigned short const_int_tableNI;/NI表示整常数表长度表示整常数表长度nfloat const_real_tableNR;/NR表示实常数表长度表示实常数表长度n常数表使用常数表使用n常数表地址使用说明常数表地址使用说明6.3 中间代码中间代码n6.3.1 三元式三元式n格式格式nOP ARG1 ARG2n运算符运算符 第一运算量第一
5、运算量 第二运算量第二运算量n优点优点n代码生成无需引进临时变量。代码生成无需引进临时变量。n缺点缺点n调整困难。调整困难。6.3 中间代码中间代码n6.3.2 四元式四元式n格式格式nOP ARG1 ARG2 RESULTn运算符运算符 第一运算量第一运算量 第二运算量第二运算量 运算结果运算结果n优点优点n调整方便。调整方便。n缺点缺点n在生成中间代码时引进大量临时变量。在生成中间代码时引进大量临时变量。n临时变量的处理临时变量的处理n将将Ti作为标识符存入符号表作为标识符存入符号表n设置临时变量表设置临时变量表6.4 说明语句（简单变量）的翻译说明语句（简单变量）的翻译n文法及修改文法及
6、修改ninteger SaVnreal ScVn,标识符标识符VV,in标识符标识符Vi6.4 说明语句（简单变量）的翻译说明语句（简单变量）的翻译n语义子程序nVainfill_sym_table(wval,0,0);/填写符号表（标识符名，简单变量，整型）nV.cat=0;/保存语义值（简单变量）nV.type=0;/保存语义值（整型）nnVcinfill_sym_table(wval,0,1);/填写符号表（标识符名，简单变量，整型）nV.cat=0;/保存语义值（简单变量）nV.type=1;/保存语义值（实型）nnVV(1),infill_sym_table(wval,V(1).ca
7、t,V(1).type);/继承V(1)的语义信息nV.cat=V(1).cat;nV.type=V(1).type;nnSV;/空n语义变量.cat和.typenfill_sym_table函数6.5 整型算术表达式及赋值语句的整型算术表达式及赋值语句的翻译翻译n文法n标识符=Si=Xn+XX+YnXYn*YY*ZnYZn()Z(X)n-Z-Zn标识符Zin无符号整常数Zx6.5 整型算术表达式及赋值语句的整型算术表达式及赋值语句的翻译翻译n语义子程序nSi=X ngen_code(=,X.addr,0,sym_entry(wval);/产生四元式。nnXX(1)+Y nX.addr=get
8、_tmpvar(0);/申请临时变量（整型）ngen_code(+,X(1).addr,Y.addr,X.addr);/产生四元式nnXY nX.addr=Y.addr;/传递语义值 nnYY(1)*Z nY.addr=get_tmpvar(0);/申请临时变量（整型）ngen_code(*,Y(1).addr,Z.addr,Y.addr);/产生四元式nnYZ nY.addr=Z.addr;/传递语义值nnZ(X)nZ.addr=X.addr;/传递语义值nnZ-Z(1)nZ.addr=get_tmpvar(0);/申请临时变量（整型）ngen_code(-,Z(1).addr,0,Z.ad
9、dr)/产生四元式nnZi nZ.addr=sym_entry(wval);/wval表示单词的值nnZx nZ.addr=const_int_entry(atoi(wval);/wval表示单词的值，atoi为C语言系统函数。nnget_tmpvar函数nsym_entry函数ngen_code函数nconst_int_entry(wval)函数6.6 混合型算术表达式及赋值语句混合型算术表达式及赋值语句的翻译的翻译n文法n标识符=Si=Xn+XX+YnXYn*YY*ZnYZn()Z(X)n-Z-Zn标识符Zi n无符号整常数Zxn无符号实常数Zy6.6 混合型算术表达式及赋值语句混合型算术
10、表达式及赋值语句的翻译的翻译n语义子程序（XX+Y）nvoid*t;nXX(1)+Y nif(X(1).type=Y.type)/类型相同nif(X(1).type=0)/int op int nX.addr=get_tmpvar(0);ngen_code(+i,X(1).addr,Y.addr,X.addr);/产生四元式nX.type=0;nnelse/real=realnX.addr=get_tmpvar(1);ngen_code(+r,X(1).addr,Y.addr,X.addr);/产生四元式nX.type=1;nnelse/类型不相同nX.type=1;/结果类型均为实型nt=g
11、et_tmpvar(1);/申请临时变量（实型），用于类型转换。nX.addr=get_tmpvar(1);nif(X(1).type=0)/int op realngen_code(itr,X(1).addr,0,t);ngen_code(+r,t,Y.addr,X.addr);nnelse/real op int ngen_code(itr,Y.addr,0,t);ngen_code(+r,X(1).addr,t,X.addr);nnn6.7 布尔表达式的翻译布尔表达式的翻译n布尔表达式作用n控制语句的条件if x+yyn程序设计语言的优先级和结合性n标准Fortran语言（按表达式类别分
12、级）nPascal语言（共分4级，同级运算优先性相同）nC语言（共分17级，同级运算优先性相同）n描述布尔表达式文法n以标准FORTRAN语言为基础，适当化简。nEEE|EE|(E)|E|XrX|XnXX+X|X*X|(X)|-X|i|x6.7 布尔表达式的翻译布尔表达式的翻译n语义子程序nEX n E.tc=nxq;ngen_code(jnz,X.addr,0,0);nE.fc=nxq;n gen_code(jmp,0,0,0);nnErXrX(1)nE.tc=nxq;nE.tc:=nxq+1;ngen_code(jr,X.addr,X(1).addr,0);n gen_code(jmp,0
13、,0,0)nnEE(1)/真假出口链链首互换nE.tc=E(1).fc;E.fc=E(1).tc;nnE(E(1)/传递真假出口链链首nE.tc=E(1).tc;E.fc=E(1).fc;nnEAE nbackpatch(E.tc,nxq);/可填真出口（下一个四元式地址）nEA.fc=E.fc;/传递假出口链链首nnEEAE(2)nE.tc=E(2).tc;/传递真出口链链首nE.fc=merge(EA.fc,E(2).fc);/合并假出口链nnEOE(1)nEO.tc=E(1).tc;/传递真出口链链首nbackpatch(E(1).fc,nxq);/可填假出口（下一个四元式地址）nnEE
14、OE(2)nE.tc=merge(EO.tc,E(2).tc);/合并真出口链nE.fc=E(2).fc;/传递假出口链链首nnXinX.addr=sym_entry(wval);/wval表示单词的值。nnXxnX.addr=const_int_entry(atoi(wval);/wval表示单词的值。n6.8 标号和无条件转移语句的翻译标号和无条件转移语句的翻译n文法及修改n标识符:Si:Sngoto 标识符Sgin标号用于标领一个语句，为了能及时填写标号的地址，将文法修改如下：nSFSn标识符：Fi:ngoto 标识符Sgi6.8 标号和无条件转移语句的翻译标号和无条件转移语句的翻译n语
15、义子程序（不考虑出错情况）nFi:nif(sym_entry(wval)=0)/标号未进入符号表，属先定位后使用。nfill_sym_table(wval,1,1);/将标号名填入符号表且标记已定位n (*sym_entry(wval).addr=nxq;/nxq为标号i标领的语句第一个四元式地址nnelse/标号已进入符号表，属先使用后定位，此时应回填。nbackpatch(*sym_entry(wval).addr,nxq);/回填n(*sym_entry(wval).addr=nxq;n(*sym_entry(wval).type=1;/标号已定位nnnSgi nif(sym_entry
16、(wval)=0)/*标号未进入符号表，属先使用后定位且是第一个向前转移语句，此时产生新链，链中仅有一个四元式。*/nfill_sym_table(wval,1,0);/将标号名填入符号表且标记为未定位n (*sym_entry(wval).addr=nxq;/下一个无条件转移四元式地址（编号）ngen_code(jmp,0,0,0);/产生不完全四元式nnelse/标号已进入符号表nif(*sym_entry(wval).type=1)/标号已进入符号表且定位，直接产生四元式。ngen_code(jmp,0,0,(*sym_entry(wval).addr);nelse/*标号已进入符号表，
17、但未定位，即有以该标号为转移目标的单向链存在，将新产生的四元式插入单向链。*/nvoid*t;nt=(*sym_entry(wval).addr;n(*sym_entry(wval).addr=nxq;ngen_code(jmp,0,0,t);nnnnSFS;/暂时可认为是空6.9 控制语句的翻译控制语句的翻译n6.9.1 if-then语句的翻译 n文法及修改nifthenendifSfEtS(1)jn标识符=Si=Xn为了能及时回填真出口，文法修改如下：nCifthenCfEtnCendifSCS(1)jn标识符=Si=X6.9.1 if-then语句的翻译语句的翻译n语义子程序nCfEt
18、 nbackpatch(E.tc,nxq);/回填真出口nC.chain=E.FC;/假出口是离开if-then语句nnSCS(1)j nS.chain=merge(C.chain,S(1).chain);/S(1)中可能含有离开if_then的四元式nnSi=X/赋值语句按顺序执行，它的四元式代码中不存在需回填转移目标的四元式。nS.chain=0;ngen_code(=,X.addr,0,sym_entry(wval);nn手工计算nif a then b=d endifn6.9.2 if-then-else语句的翻译语句的翻译n文法及修改nifthenelseSfEtS(1)eS(2)n
19、当扫描到then可填真出口，当扫描到else可填假出口，当S(1)执行完毕，应离开if-then-else语句。为了能及时回填四元式，修改如下：nTPSTPS(2)nTPCelseTPCS(1)enCifthenCfEtn语义子程序nTPCS(1)e /TP可理解为then-processednvoid*t;nt=nxq;/t为下一条四元式地址，即(jmp,0,0,0)的地址（编号）。ngen_code(jmp,0,0,0);/执行完S(1)后，离开if-then-else语句。nbackpatch(C.chain,nxq);/回填假出口，这里C.chain相当于E.FC，此时nxq=t+1。
20、nTP.chain=merge(S(1).chain,t);/S(1)中可能含有离开if_then-else的四元式nnSTPS(2)nS.chain=merge(TP.chain，S(2).chain);/S(2)中可能含有离开if_then-else的四元式nnCfEt /见6.9.16.9.2 if-then-else语句的翻译语句的翻译n文法及修改nifthenelseSfEtS(1)eS(2)n当扫描到then可填真出口，当扫描到else可填假出口，当S(1)执行完毕，应离开if-then-else语句。为了能及时回填四元式，修改如下：nTPSTPS(2)nTPCelseTPCS(1
21、)enCifthenCfEt6.9.2 if-then-else语句的翻译语句的翻译n语义子程序nTPCS(1)e /TP可理解为then-processednvoid*t;nt=nxq;/t为下一条四元式地址，即(jmp,0,0,0)的地址（编号）。ngen_code(jmp,0,0,0);/执行完S(1)后，离开if-then-else语句。nbackpatch(C.chain,nxq);/回填假出口，这里C.chain相当于E.FC，此时nxq=t+1。nTP.chain=merge(S(1).chain,t);/S(1)中可能含有离开if_then-else的四元式nnSTPS(2)n
22、S.chain=merge(TP.chain，S(2).chain);/S(2)中可能含有离开if_then-else的四元式nnCfEt 6.9.3 while-do语句的翻译语句的翻译n文法及修改nwhiledoSwEdS(1)n为了便于语义分析，修改如下：nWwhileWw nWdWdoWdWEd nWd SWd S(1)6.9.3 while-do语句的翻译语句的翻译n语义子程序nWw nW.quad=nxq;/记录E的第一个四元式编号nnWdWEd/Wd可理解为while-donbackpatch(E.TC,nxq);/回填真出口nWd.chain=E.fc;/传递假出口、即whil
23、e-do的出口。nWd.quad=W.quad;/传递E的第一个四元式地址nnSWdS(1)nbackpatch(S(1).chain,Wd.quad);/*回填S(1).chain链，因S(1)可能是控制语句，离开S(1)的四元式的转移目标是E的第一个四元式。*/ngen_code(jmp,0,0,Wd.quad);/生成转向E首址的无条件转移指令nS.chain=Wd.chain;/传递假出口、即while-do的出口。n6.9.4 复合语句的翻译 n文法及修改nbegin end SLn;LL(1);SnLSn分号意味着一个语句的结束，当扫描到分号，就可回填转移目标。为了能及时回填chain链，文法修改如下：nbegin end SLnLSLLSSnLS;LSL;nLS6.9.4 复合语句的翻译n语义子程序nLS nL.chain=S.chain;/传递nnLsL;nbackpatch(L.chain,nxq);/回填nnLLsS/LS表示L-SnL.chain=S.chain/因前一语句L已回填，而当前语句S尚未回填，故需传递。nnSL nS.chain=L.chain;/传递nnPL nbackpatch(L.chain,nxq);/填写最后一个语句的chain链ngen_code(halt,0,0,0);/产生停机指令n