语法制导翻译和中间代码生成1.ppt

第6章 语法制导翻译和中间代码生成,语法分析和语义分析的区别 语义分析主要工作 建立符号表和常数表。 诊察和报告源程序中的语义错误。 根据语言的语义产生中间代码（或机器指令），或直接解释执行。,6.1 语法制导翻译概述,语法制导翻译方法简介 为每一个产生式配一个语义子程序。在语法分析过程中，当一个产生式获得匹配或用于归约时，此产生式相应的语义子程序进入工作，完成既定的翻译任务。,6.1 语法制导翻译概述,实现方法（以SLR分析器为例） 分析表不变 改造工作栈 状态栈 符号栈 单词值栈：用于保存单词的值（字符串形式）。 语义栈：用于记录分析过程中需保留的语义值。例，值（val）、地址（addr）、种属（cat）、类型（type）等。 修改总控程序 在移进时，除移进状态和单词的种别外，还需移进单词的值。 在用某个产生式进行归约时，除需执行归约动作外，还需调用相应语义子程序。,6.1 语法制导翻译概述,解释执行例 文法及语义子程序 SLR分析表 手工计算 7+9*5,6.2 符号表和常数表,符号表 引入符号表的意义 符号表的结构（略有修改） struct void *addr; /标号或变量的地址 char id5; /标识符名 unsigned cat:4; /种属（4个二进制位） unsigned type:4; /类型（4个二进制位） sym_tableNS; /NS表示符号表长度 符号表的使用 符号表地址使用说明,6.2 符号表和常数表,常数表 常数表结构 unsigned short const_int_tableNI; /NI表示整常数表长度 float const_real_tableNR; /NR表示实常数表长度 常数表使用 常数表地址使用说明,6.3 中间代码,6.3.1 三元式 格式 OP ARG1 ARG2 运算符 第一运算量 第二运算量 优点 代码生成无需引进临时变量。 缺点 调整困难。,6.3 中间代码,6.3.2 四元式 格式 OP ARG1 ARG2 RESULT 运算符 第一运算量 第二运算量 运算结果 优点 调整方便。 缺点 在生成中间代码时引进大量临时变量。 临时变量的处理 将Ti作为标识符存入符号表 设置临时变量表,6.4 说明语句（简单变量）的翻译,文法及修改 integer SaV real ScV ,标识符 VV,i 标识符 Vi,6.4 说明语句（简单变量）的翻译,语义子程序 Vai fill_sym_table(wval,0,0); /填写符号表（标识符名，简单变量，整型） V.cat=0; /保存语义值（简单变量） V.type=0; /保存语义值（整型） Vci fill_sym_table(wval,0,1); /填写符号表（标识符名，简单变量，整型） V.cat=0; /保存语义值（简单变量） V.type=1; /保存语义值（实型） VV(1),i fill_sym_table(wval, V(1).cat, V(1).type); /继承V(1)的语义信息 V.cat= V(1).cat; V.type= V(1).type; SV ; /空 语义变量.cat和.type fill_sym_table函数,6.5 整型算术表达式及赋值语句的翻译,文法 标识符= Si=X + XX+Y XY * YY*Z YZ () Z(X) - Z-Z 标识符 Zi 无符号整常数 Zx,6.5 整型算术表达式及赋值语句的翻译,语义子程序 Si=X gen_code (=,X.addr,0,sym_entry(wval); /产生四元式。 XX(1)+Y X.addr = get_tmpvar(0); /申请临时变量（整型） gen_code(+,X(1).addr, Y.addr, X.addr); /产生四元式 XY X.addr = Y.addr; /传递语义值 YY(1)*Z Y.addr = get_tmpvar(0); /申请临时变量（整型） gen_code(*,Y(1).addr, Z.addr, Y.addr); /产生四元式 YZ Y.addr = Z.addr; /传递语义值 Z(X) Z.addr= X.addr; /传递语义值 Z-Z(1) Z.addr = get_tmpvar(0); /申请临时变量（整型） gen_code (-,Z(1).addr,0, Z.addr) /产生四元式 Zi Z.addr = sym_entry(wval); / wval表示单词的值 Zx Z.addr = const_int_entry(atoi(wval); / wval表示单词的值，atoi为C语言系统函数。 get_tmpvar函数 sym_entry函数 gen_code函数 const_int_entry(wval)函数,6.6 混合型算术表达式及赋值语句的翻译,文法 标识符= Si=X + XX+Y XY * YY*Z YZ () Z(X) - Z-Z 标识符 Zi 无符号整常数 Zx 无符号实常数 Zy,6.6 混合型算术表达式及赋值语句的翻译,语义子程序（XX+Y） void *t; XX(1)+Y if(X(1) .type=Y.type) /类型相同 if(X(1).type=0) /int op int X.addr = get_tmpvar(0); gen_code(+i,X(1).addr, Y.addr, X.addr); /产生四元式 X .type=0; else /real=real X.addr = get_tmpvar(1); gen_code(+r,X(1).addr, Y.addr, X.addr); /产生四元式 X .type=1; else /类型不相同 X .type=1; /结果类型均为实型 t=get_tmpvar(1); /申请临时变量（实型），用于类型转换。 X.addr = get_tmpvar(1); if(X(1) .type=0) / int op real gen_code (itr,X(1).addr,0,t); gen_code (+r,t,Y.addr, X.addr); else /real op int gen_code (itr,Y.addr,0,t); gen_code (+r, X(1).addr,t, X.addr); ,6.7 布尔表达式的翻译,布尔表达式作用 控制语句的条件 if x+yy 程序设计语言的优先级和结合性 标准Fortran语言（按表达式类别分级） Pascal语言（共分4级，同级运算优先性相同） C语言（共分17级，同级运算优先性相同） 描述布尔表达式文法 以标准FORTRAN语言为基础，适当化简。 EEE|EE|(E)|E|XrX|X XX+X|X*X| (X)|-X|i|x,6.7 布尔表达式的翻译,语义子程序 EX E.tc = nxq; gen_code(jnz,X.addr,0,0); E.fc = nxq; gen_code(jmp,0,0,0); ErXrX(1) E.tc = nxq; E.tc:=nxq+1; gen_code(jr,X.addr, X(1).addr,0); gen_code(jmp,0,0,0) EE(1) /真假出口链链首互换 E.tc = E(1).fc; E.fc = E(1).tc; E(E(1) /传递真假出口链链首 E.tc= E(1).tc; E.fc = E(1).fc; EAE backpatch(E.tc,nxq); /可填真出口（下一个四元式地址） EA.fc = E.fc; /传递假出口链链首 EEAE(2) E.tc = E(2).tc; /传递真出口链链首 E.fc = merge(EA.fc, E(2).fc); /合并假出口链 EOE(1) EO.tc = E(1).tc; /传递真出口链链首 backpatch(E(1).fc,nxq); /可填假出口（下一个四元式地址） EEOE(2) E.tc = merge(EO.tc, E(2).tc); /合并真出口链 E.fc = E(2).fc; /传递假出口链链首 Xi X.addr = sym_entry(wval); / wval表示单词的值。 Xx X.addr = const_int_entry(atoi(wval); / wval表示单词的值。 ,6.8 标号和无条件转移语句的翻译,文法及修改 标识符: Si:S goto 标识符 Sgi 标号用于标领一个语句，为了能及时填写标号的地址，将文法修改如下： SFS 标识符： Fi: goto 标识符 Sgi,6.8 标号和无条件转移语句的翻译,语义子程序（不考虑出错情况） Fi: if(sym_entry(wval)=0) /标号未进入符号表，属先定位后使用。 fill_sym_table(wval,1,1); /将标号名填入符号表且标记已定位 (*sym_entry(wval).addr=nxq; /nxq为标号i标领的语句第一个四元式地址 else /标号已进入符号表，属先使用后定位，此时应回填。 backpatch(*sym_entry(wval).addr,nxq); /回填 (*sym_entry(wval).addr=nxq; (*sym_entry(wval).type=1; /标号已定位 Sgi if(sym_entry(wval)=0) /*标号未进入符号表，属先使用后定位且是第一个向前转移语句，此时产生新链，链中仅有一个四元式。*/ fill_sym_table(wval,1,0); /将标号名填入符号表且标记为未定位 (*sym_entry(wval).addr=nxq; /下一个无条件转移四元式地址（编号） gen_code(jmp,0,0,0); /产生不完全四元式 else /标号已进入符号表 if (*sym_entry(wval).type=1)/标号已进入符号表且定位，直接产生四元式。 gen_code(jmp,0,0, (*sym_entry(wval).addr); else /*标号已进入符号表，但未定位，即有以该标号为转移目标的单向链存在，将新产生的四元式插入单向链。*/ void *t; t =(*sym_entry(wval).addr; (*sym_entry(wval).addr=nxq; gen_code(jmp,0,0,t); SFS ; /暂时可认为是空,6.9 控制语句的翻译,6.9.1 if-then语句的翻译 文法及修改 ifthenendif SfEtS(1)j 标识符= Si=X 为了能及时回填真出口，文法修改如下： Cifthen CfEt C endif SCS(1)j 标识符= Si=X,6.9.1 if-then语句的翻译,语义子程序 CfEt backpatch(E.tc,nxq); /回填真出口 C.chain=E.FC; /假出口是离开if-then语句 SCS(1)j S.chain=merge(C.chain, S(1).chain); /S(1)中可能含有离开if_then的四元式 Si=X /赋值语句按顺序执行，它的四元式代码中不存在需回填转移目标的四元式。 S.chain=0; gen_code(=,X.addr,0,sym_entry(wval); 手工计算 if a then b=d endif 6.9.2 if-then-else语句的翻译 文法及修改 ifthenelse SfEtS(1)eS(2) 当扫描到then可填真出口，当扫描到else可填假出口，当S(1)执行完毕，应离开if-then-else语句。为了能及时回填四元式，修改如下： TP STPS(2) TPCelse TPCS(1)e Cifthen CfEt 语义子程序 TPCS(1)e / TP可理解为then-processed void *t; t = nxq; /t为下一条四元式地址，即(jmp,0,0,0)的地址（编号）。 gen_code(jmp,0,0,0); /执行完S(1)后，离开if-then-else语句。 backpatch(C.chain, nxq); /回填假出口，这里C.chain相当于E.FC，此时nxq=t+1。 TP.chain = merge(S(1).chain, t); /S(1)中可能含有离开if_then-else的四元式 STPS(2) S.chain = merge(TP.chain，S(2).chain); /S(2)中可能含有离开if_then-else的四元式 CfEt /见6.9.1,6.9.2 if-then-else语句的翻译,文法及修改 ifthenelse SfEtS(1)eS(2) 当扫描到then可填真出口，当扫描到else可填假出口，当S(1)执行完毕，应离开if-then-else语句。为了能及时回填四元式，修改如下： TP STPS(2) TPCelse TPCS(1)e Cifthen CfEt,6.9.2 if-then-else语句的翻译,语义子程序 TPCS(1)e / TP可理解为then-processed void *t; t = nxq; /t为下一条四元式地址，即(jmp,0,0,0)的地址（编号）。 gen_code(jmp,0,0,0); /执行完S(1)后，离开if-then-else语句。 backpatch(C.chain, nxq); /回填假出口，这里C.chain相当于E.FC，此时nxq=t+1。 TP.chain = merge(S(1).chain, t); /S(1)中可能含有离开if_then-else的四元式 STPS(2) S.chain = merge(TP.chain，S(2).chain); /S(2)中可能含有离开if_then-else的四元式 CfEt ,6.9.3 while-do语句的翻译,文法及修改 whiledo SwEdS(1) 为了便于语义分析，修改如下： Wwhile Ww WdWdo WdWEd Wd SWd S(1),6.9.3 while-do语句的翻译,语义子程序 Ww W.quad=nxq; /记录E的第一个四元式编号 WdWEd / W