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

语法制导翻译和中间代码生成㈠语法分析和语义分析的区别①语法分析利用产生式推导或归约，验证符号串是否为文法的一个句子，并没有考虑符号和符号串的意义。②语义分析规定每个符号和符号串的意义，同时完成符号串所规定的语义动作，显然这是以语法正确为前提。例文法G E→E(1)+T|T T→T(1)*F|F F→(E)|i|x|yi：语法分析认为i是一个终结符，代表标识符；而语义分析认为它不仅是一个标识符，还具有标识符名、种属和类型等。i可能是一个简单变量，也可能是一个标号。标识符名由单词二元式中的值给出，种属和类型可从符号表获取。x：语法分析认为它是一个终结符，代表整常数；而语义分析认为它不仅是一个整常数，还具有值，值由单词二元式中的值给出。第2页,共60页，2024年2月25日，星期天y：语法分析认为y是一个终结符,代表实常数；而语义分析认为它不仅是一个实常数，还具有值，值由单词二元式中的值给出。F：语法分析认为F是一个非终结符，代表语法单位<因子>，F由i、x、y或(E)归约而得；而语义分析认为F还具有值、类型等属性。为了保存值和类型，引入语义变量F.val、F.type。T：语法分析认为T是一个非终结符，代表语法单位<项>，由F或T*F归约而得；而语义分析认为T还具有值、类型等属性。为了保存值和类型，引入语义变量T.val、T.type。E：语法分析认为E是一个非终结符，代表语法单位<算术表达式>，由T或E+T归约而得；而语义分析认为E还具有值、类型等属性。为了保存值和类型，引入语义变量E.val、E.type。+：语法分析认为它是一个终结符，代表算术加；而语义分析认为它可能是一个实数加运算符，也可能是一个整数加运算符，视运算对象而定。*：语法分析认为它是一个终结符，代表算术乘；而语义分析认为它可能是一个实数乘运算符，也可能是一个整数乘运算符，视运算对象而定。第3页,共60页，2024年2月25日，星期天E→E(1)+T：在语法分析时认为它是一个<算术表达式>的产生式，而在语义分析时认为：应将E(1)的值（用E(1).val表示）加上T的值（用T.val表示），结果放在E.val中。若数据类型有实型和整型之分，在运算前还需检查它们的类型。若类型不同，根据语言的语义规定，或者拒绝运算，或者将它们转换成相同类型（例实型），然后再进行实数加运算。T→T(1)*F：在语法分析时认为它是一个<项>的产生式，而在语义分析时认为：应将T(1)的值（用T(1).val表示）乘上F的值（用F.val表示），结果放在T.val中。若数据类型有实型和整型之分，在运算前还需检查它们的类型。若类型不同，根据语言的语义规定，或者拒绝运算，或者将它们转换成相同类型（例实型），然后再进行实数乘运算。㈡语义分析主要工作①建立符号表和常数表。②诊察和报告源程序中的语义错误。③根据语言的语义产生中间代码（或机器指令），或直接解释执行。第4页,共60页，2024年2月25日，星期天6.1语法制导翻译概述㈠语法制导翻译方法简介为每一个产生式配一个语义子程序。在语法分析过程中，当一个产生式获得匹配或用于归约时，此产生式相应的语义子程序进入工作，完成既定的翻译任务。㈡实现方法（以SLR分析器为例）

SLR分析器是由工作栈（状态栈和符号栈）、分析表和总控程序三部分构成，只要适当修改工作栈和总控程序，就可将SLR分析器用于语义分析。①分析表不变②改造工作栈为了保存语义信息，在状态栈、符号栈的基础上增加单词值（wval）栈和语义（semantic）栈。状态栈符号栈单词值栈语义栈第5页,共60页，2024年2月25日，星期天

statesymbolwval.val.addr .cat.type …SmX……X.valX.addrX.catX.type……Sm-1Y……Y.valY.addrY.catY.type…………………………………………S0#"NUL"③修改总控程序在移进时，除移进状态和单词的种别外，还需移进单词的值。在用某个产生式进行归约时，除需执行归约动作外，还需调用相应语义子程序。状态栈不变符号栈不变增加单词值栈，用于保存单词的值（字符串形式）。增加语义栈，用于记录分析过程中需保留的语义值。例，值（.val）、地址（.addr）、种属（.cat）、类型（.type）等。经改造后，工作栈如下所示：第6页,共60页，2024年2月25日，星期天㈢解释执行例①文法及语义子程序

struct{charcode;charval[20];}t;0.S→E {cout<<E.val}1.E→E(1)+E(2) {E.val=E(1).val+E(2).val;}2.E→E(1)*E(2) {E.val=E(1).val*E(2).val;}3.E→(E(1)) {E.val=E(1).val;}4.E→x {E.val=atoi(t.val);}//atoi为C语言系统函数

假定语义动作是紧接着归约之后执行，语义子程序改写如下：0.S→E {cout<<semantic[top].val;}1.E→E(1)+E(2) {semantic[top].val=semantic[top].val+semantic[top+2].val;}2.E→E(1)*E(2) {semantic[top].val=semantic[top].val*semantic[top+2].val;}3.E→(E(1)) {semantic[top].val=semantic[top+1].val.val;}4.E→x {semantic[top].val=atoi(wval[top]);}第7页,共60页，2024年2月25日，星期天+*()x#E0s2s311s4s5Acc2s2s363r4r4r4r44s2s375s2s386s4s5s97r1s5r1r18r2r2r2r29r3r3r3r3③手工计算假设源程序为：7+9*5。经词法分析，单词二元式序列为

(x,"7")(+,"NUL")(x,"9")(*,"NUL")(x,"5")(#,"NUL")分析过程如黑板所示（在语义栈中，“NUL”改用‘-’表示）：step

state栈

symbol栈

wval栈

.val栈

输入串②SLR分析表第8页,共60页，2024年2月25日，星期天6.2符号表和常数表在编译过程中，编译程序需要不断汇集和反复查证出现在源程序中各种符号名（标识符）和常数，以及符号名的属性，这些信息通常记录在符号表和常数表中。㈠符号表①引入符号表的意义可用符号名表示内存地址（变量）和语句的地址（标号）。符号表的引入使得中间代码生成（包括目标代码生成）与机器的内存地址无关。可在机器码最终定位阶段，甚至在程序运行过程中，对变量进行地址分配。在对变量进行内存地址分配时，符号表是地址分配的依据。转移语句的翻译是借助符号表来完成的。第9页,共60页，2024年2月25日，星期天②符号表的结构（略有修改）符号表由记录构成，相当于一个结构数组，模型语言的符号表定义如下：

struct{ void*addr; //标号或变量的地址

charid[5]; //标识符名

unsignedcat:4; //种属（4个二进制位）

unsignedtype:4; //类型（4个二进制位）

}sym_table[NS]; //NS表示符号表长度1）addr

存放内存地址（2字节），地址标识范围为0-65535。变量的值并不存放于符号表，而是存储在内存的另外一个区域中，通过该地址指示，addr的值是在地址分配时填入。addr为结构第一分量，结构的地址值（&sym_table[i]）和结构的第一分量地址值（&sym_table[i].addr）相等，结构地址通常称为变量在符号表中的入口。2）id

存放标识符名，标识符最多可由5个字符构成。第10页,共60页，2024年2月25日，星期天②符号表的结构（略有修改）符号表由记录构成，相当于一个结构数组，模型语言的符号表定义如下：

struct{ void*addr; //标号或变量的地址

charid[5]; //标识符名

unsignedcat:4; //种属（4个二进制位）

unsignedtype:4; //类型（4个二进制位）

}sym_table[NS]; //NS表示符号表长度3）cat

用于记录标识符的种属（如简单变量、标号、数组、函数、…），共有4个二进制位，暂用1位。

0表示简单变量、1表示标号4）type

用于记录标识符的类型（如整型、实型、布尔型、…），共有4个二进制位，暂用1位。 简单变量：0表示整型，1表示实型。 标号：0表示标号未定义，1表示标号已定义。第11页,共60页，2024年2月25日，星期天③符号表的使用1）说明语句每当识别出一个标识符，就在符号表中为该标识符建立一条记录，并填入标识符名、种属、类型等语义信息。若符号表中已有记录，说明标识符被重定义，报错。2）非说明语句每当识别出一个标识符，就根据标识符名去查符号表，并由此获得该标识符在符号表的入口。若标识符名在符号表中不存在，分情况处理：变量：报错。标号：在符号表中创建一个记录，将标识符名等信息填入符号表。④符号表地址使用说明在中间代码生成时，若操作数是变量，则应在操作数（operand）位置上填入该变量在符号表中的入口。根据中间代码生成的目标代码，是通过间址寻址方式对变量进行存取（**operand）。借助间址寻址方式，使得中间代码所使用的地址和实际存放数据的内存地址相互独立。第12页,共60页，2024年2月25日，星期天内存地址（2字节）符号名（5字节）种属（4Bit）类型（4Bit）…………………………未分配a99\0\0简单整型…………………………值12345100符号表示意图常数表示意图第13页,共60页，2024年2月25日，星期天㈡常数表可设置一张常数表，同时记录各种类型的常数；也可按类型设置多张常数表，按类型分表记录。①常数表结构

unsignedshortconst_int_table[NI]; //NI表示整常数表长度

floatconst_real_table[NR]; //NR表示实常数表长度②常数表使用每当识别出一个常数，将字符串转换成数值后查常数表：若无，将常数填入常数表，获取表中地址。若常数在表中已存在，直接获取常数在表中地址。③常数表地址使用说明在中间代码生成时，若操作数是常数，则应在操作数(operand)位置上填入常数在常数表中的地址(&const_int_table[i]或&const_real_table[i])。目标代码运行时，根据该地址（*operand）可获得常数值，无需间址访问。目标代码生成器可根据地址范围来区分是符号表地址还是常数表地址，从而使用不同的寻址方式。第14页,共60页，2024年2月25日，星期天6.3中间代码常用的中间代码有三元式和四元式，在本书以后讨论中，中间代码采用四元式形式。6.3.1三元式㈠格式

(i)（OP，ARG1，ARG2）①三元式相当于二地址指令,计算结果用三元式序号i表示。②ARG1、ARG2均为指示器（三元式的序号、常数表地址或符号表入口）。③若为一目运算，ARG2不使用。例表达式a+b*2可表示为：⑴ * &b &2 //⑴代表子表达式b*2的计算结果

⑵ + &a ⑴ //&b表示变量b在符号表中的入口

//&2表示整常数2在整常数表中的地址

第15页,共60页，2024年2月25日，星期天㈡优点代码生成无需引进临时变量。㈢缺点调整困难。在中间代码优化中，常常需要调整运算顺序、增减代码，重新排列三元式。由于三元式通过指示器相联系，调整相当困难，有时甚至是不可能的。例，设源程序为： x=(a+b)*c; y=-d 它的三元式代码为：⑴ + &a &b⑵ * ⑴ &c⑶ = &x ⑵⑷ - &d⑸ = &y ⑷若将源程序中的二条语句互换，改为：y=-d;x=(a+b)*c需修改三元式中一系列指示器，如下所示：⑴ - &d⑵ = &y ⑷⑴⑶ + &a &b⑷ * ⑴⑶ &c⑸ = &x ⑵⑷第16页,共60页，2024年2月25日，星期天6.3.2四元式㈠格式

（OP，ARG1，ARG2，RESULT）①相当于三地址指令。②ARG1、ARG2及RESULT均为指示器，或者指向常数表，或者是符号表和临时变量表的入口。③若为一目运算，ARG2不使用。考虑输入和处理方便，将ARG2标记为0（变量或常数的地址不可能是0）。例表达式a+b*2可表示为： ⑴* &b &2 &T1

⑵+ &a &T1 &T2说明：T1是临时变量，&T1表示T1在临时变量表中的入口，同理&T2。第17页,共60页，2024年2月25日，星期天㈡优点调整方便。例，设源程序为 x=(a+b)*c; y=-d 它的四元式代码为⑴ + &a &b &T1 ⑵ * &T1 &c &T2⑶ = &T2 0 &x⑷ - &d 0 &T3⑸ = &T3 0 &y若将源程序中的二条语句互换，改为y=-d;x=(a+b)*c它的四元式代码只要简单交换原二条语句相应的四元式即可，无需再作任何修改。⑴- &d 0 &T3 ⑵= &T3 0 &y ⑶+ &a &b &T1 ⑷* &T1 &c &T2⑸= &T2 0 &x第18页,共60页，2024年2月25日，星期天㈢缺点在生成中间代码时引进大量临时变量。㈣临时变量的处理在形成四元式时，考虑代码生成方便，不加限制地引进临时变量Ti（i=1,2,……）。在代码优化和目标代码生成阶段，可将它们的数量压缩到最低。关于临时变量Ti有二种处理方法：①将Ti作为标识符存入符号表，通过符号表入口对它们进行引用。由于不加限制地引进临时变量，在随后进行的代码优化和目标代码生成中，有部分临时变量有可能被删除，采用此方法不是最合适。②临时变量用于记录运算过程中的中间结果，必然是简单变量，可另外设置临时变量表（无需设置种属一栏），将Ti存入临时变量表，而不是存入符号表。在以后讨论中，采用第二种方案。第19页,共60页，2024年2月25日，星期天6.4 说明语句（简单变量）的翻译说明语句用于定义变量，大多数高级语言都要求变量先定义后使用。说明语句的翻译并不产生中间代码，而是将变量的名字、种属、类型等信息填入符号表。㈠文法及修改

<语句>→integer<标识符表> S→aV <语句>→real<标识符表> S→cV <标识符表>→<标识符表>,标识符

V→V,i <标识符表>→标识符

V→i用这个文法来制导翻译存在一个问题，只有把所有标识符归约成<标识符表>，才能把变量名、种属、类型等信息填入符号表，需使用一个队列来保存这些变量名。为了避免使用队列，文法修改如下：

<语句>→<说明> S→V <说明>→<说明>,标识符

V→V,i <说明>→integer

标识符

V→ai <说明>→real

标识符

V→ci

用这个文法来制导翻译，每当读进一个标识符，就可把它的变量名及其性质填入符号表，没有必要集中起来成批处理。第20页,共60页，2024年2月25日，星期天㈡语义子程序V→ai{ fill_sym_table(wval,0,0);//填写符号表（标识符名，简单变量，整型）

V.cat=0; //保存语义值（简单变量）

V.type=0; //保存语义值（整型）

}V→ci{ fill_sym_table(wval,0,1);//填写符号表（标识符名，简单变量，整型）

V.cat=0; //保存语义值（简单变量）

V.type=1; //保存语义值（实型）

}V→V(1),i{ fill_sym_table(wval,V(1).cat,V(1).type); //继承V(1)的语义信息

V.cat=V(1).cat; V.type=V(1).type;}S→V{;} //暂且为空①语义变量.cat和.type

当ai归约为V，ai的所蕴含的语义信息（整型、简单变量）随之消失。由于在一个说明语句中可定义多个变量，此时可使用语义变量V.cat和V.type保存语义信息。当将V(1),i归约为V时，i将继承V(1)的语义信息。第21页,共60页，2024年2月25日，星期天㈡语义子程序V→ai{ fill_sym_table(wval,0,0);//填写符号表（标识符名，简单变量，整型） V.cat=0; //保存语义值（简单变量） V.type=0;} //保存语义值（整型） V→ci{ fill_sym_table(wval,0,1);//填写符号表（标识符名，简单变量，整型） V.cat=0; //保存语义值（简单变量） V.type=1;} //保存语义值（实型） V→V(1),i{fill_sym_table(wval,V(1).cat,V(1).type); //继承V(1)的语义信息 V.cat=V(1).cat; V.type=V(1).type;}S→V{;} //暂且为空②fill_sym_table函数 voidfill_sym_table(char*,int,int); //变量名，种属，类型根据标识符的单词值(变量名)查符号表。若无，则为其创建一个记录，将变量名、种属及类型等信息填入符号表；若已存在，说明变量名被重复定义，报错。㈢手工计算设源程序说明语句为：intergera,b。经词法分析，源程序的单词二元式序列为：(a,"NUL")(i,"a")(,,"NUL")(i,"b")(#,"NUL") 语法制导翻译过程如黑板所示：

step

symbol栈

wval栈

.cat栈

.type栈

输入串第22页,共60页，2024年2月25日，星期天6.5 整型算术表达式及赋值语句的翻译㈠文法<语句>→标识符=<整型算术表达式> S→i=X<整型算术表达式>→<整型算术表达式>+<项> X→X+Y<整型算术表达式>→<项> X→Y<项>→<项>*<因子> Y→Y*Z<项>→<因子> Y→Z<因子>→(<整型算术表达式>) Z→(X)<因子>→-<因子> Z→-Z<因子>→标识符

Z→i<因子>→无符号整常数

Z→x第23页,共60页，2024年2月25日，星期天㈡语义子程序S→i=X {gen_code(=,X.addr,0,sym_entry(wval));}X→X(1)+Y {X.addr=get_tmpvar(0); gen_code(+,X(1).addr,Y.addr,X.addr);} X→Y {X.addr=Y.addr;} Y→Y(1)*Z {Y.addr=get_tmpvar(0); gen_code(*,Y(1).addr,Z.addr,Y.addr);} Y→Z {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)} Z→i {Z.addr=sym_entry(wval);} Z→x {Z.addr=const_int_entry(atoi(wval));} gen_code函数：voidgen_code(char*,void*,void*,void*);sym_entry函数：void*sym_entry(char*);get_tmpvar函数：void*get_tmpvar(int);const_int_entry函数：void*const_int_entry(unsignedshort);第24页,共60页，2024年2月25日，星期天①get_tmpvar函数

void*get_tmpvar(int);

每调用一次，可获得一个新的临时变量，并将该变量在临时变量表中的入口作为返回值。临时变量名依次为T1、T2、…。1）get_tmpvar(0)表示申请一个整型临时变量（2字节）2）get_tmpvar(1)表示申请一个实型临时变量（4字节）②sym_entry函数

void*sym_entry(char*);

根据单词值（变量名）查符号表。若找到，则返回变量在符号表中的入口；若无，则返回0。③gen_code函数

voidgen_code(char*,void*,void*,void*);根据参数产生四元式(OP,ARG1,ARG2,RESULT)，并填入四元式表，表的指示器加1，函数无返回值。初始时四元式表空，指示器指向表的第一个空白位置。在本书中，四元式的算符OP由一个或多个字符构成，例+，jmp、itr等，故OP用字符串表示。④const_int_entry(wval)函数

void*const_int_entry(unsignedshort);

根据无符号整常数的单词值（atoi(wval)）查无符号整常数表。若找到，则返回它在表中的地址；若无，则在表中创建该常数的记录，然后返回表中地址。第25页,共60页，2024年2月25日，星期天S→i=X {gen_code(=,X.addr,0,sym_entry(wval));} //产生四元式X→X(1)+Y {X.addr=get_tmpvar(0); //申请临时变量(整型) gen_code(+,X(1).addr,Y.addr,X.addr);} //产生四元式X→Y {X.addr=Y.addr;} //传递语义值

Y→Y(1)*Z {Y.addr=get_tmpvar(0); //申请临时变量(整型) gen_code(*,Y(1).addr,Z.addr,Y.addr);} //产生四元式Y→Z {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)} //产生四元式Z→i {Z.addr=sym_entry(wval);} //wval表示单词的值Z→x {Z.addr=const_int_entry(atoi(wval));}//atoi为C系统函数㈢手工计算设源程序为：a=-b*(c+2)。经词法分析，源程序的单词二元式序列为：(i,"a")(=,"Nul")(-,"Nul")(i,"b")(*,"Nul")((,"Nul")(i,"c")(+,"Nul")(x,"2")(),"Nul")(#,"Nul")。语法制导翻译过程如黑板所示：

step

symbol栈

wval栈

.addr栈

输入串第26页,共60页，2024年2月25日，星期天6.6混合型第27页,共60页，2024年2月25日，星期天6.7 布尔表达式的翻译㈠布尔表达式作用①控制语句的条件 ifx+y<10gotoL②计算逻辑值 d=x>y㈡程序设计语言的优先级和结合性①标准Fortran语言（按表达式类别分级）第一级：算术表达式算术运算符优先级依次为： **,-（乘方/一元负）、*,/（乘/除）、+,-（加/减）第二级：关系表达式关系运算符不相邻，优先性略。

<（.LT.）、<=（.LE.）、>（.GT.）、>=（.GE.）、<>（.NE.）、=（.EQ.）第三级：逻辑表达式逻辑运算符优先级依次为：～(.NOT.)、∧(.AND.)、∨(.OR)注：单目运算服从右结合，双目运算服从左结合。第28页,共60页，2024年2月25日，星期天例Fortran语言表达式((A+B).GT.(C+D)).AND.(E.EQ.F) ((A+B)>(C+D))∧(E=F) 等价于

A+B>C+D∧E=F②Pascal语言（共分4级，同级运算优先性相同）第一级（一目运算符）：

NOT、-（一元负） 服从右结合第二级（乘法运算符）： *、/、DIV、MOD、AND服从左结合第三级（加法运算符）：

+、-、OR 服从左结合第四级（关系运算符）：

<、<=、>、>=、<>、= 不相邻例Pascal语言表达式((A+B)>(C+D))AND(E=F) ((A+B)>(C+D))∧(E=F) 等价于 (A+B>C+D)∧(E=F)③C语言（共分17级，同级运算优先性相同）略第29页,共60页，2024年2月25日，星期天㈢描述布尔表达式文法以标准FORTRAN语言为基础，适当化简。 E→E∨E|E∧E|(E)|～E|XrX|X X→X+X|X*X|(X)|-X|i|xE表示布尔表达式。X表示算术表达式。r是终结符，是关系运算符(＞、≥、＜、≤、＝、≠)的抽象。文法G是一个二义文法。㈣布尔表达式计算方法①根据优先性和结合性按步计算

例：1∨～0∧0∨0②优化计算法a∨b解释为：ifathentureelse计算b a∧b解释为：ifathen计算belsefalse ～a解释为：ifathenfalseelseture (～不计算)㈤布尔表达式的第一种翻译法（同算术表达式） 例：a∨b∧～c＞2第30页,共60页，2024年2月25日，星期天㈥布尔表达式的第二种翻译法①概述布尔表达式E的作用在于控制对语句S1和S2的选择，它的值无须保留。可赋予布尔表达式E二个出口：真出口：转向语句S1假出口：转向语句S2控制语句中的布尔表达式E，可译成下述三种四元式的代码序列：(jnz,&a,0,p) 若a为真（非0）转移至四元式p，否则 顺序执行。(jr,&a,&b,p) 若arb为真（r为关系运算符）转移至 四元式p，否则顺序执行。(jmp,0,0,p) 无条件转移至四元式p第31页,共60页，2024年2月25日，星期天②实例引入例：ifa∨b<cthenS1elseS2

翻译成如下四元式序列：

(1) (jnz,&a,0,5) //对应于布尔变量a (2) (jmp,0,0,3) //对应于布尔变量a (3) (j<,&b,&c,5) //对应于布尔表达式b<c (4) (jmp,0,0,m+1) //对应于布尔表达式b<c (5) 语句S1的四元式代码开始

… …………… (m-1) 语句S1的四元式代码结束

(m) (jmp,0,0,n+1) (m+1) 语句S2的四元式代码开始

… …………… (n) 语句S2的四元式代码结束1）每个布尔变量或关系表达式对应二个四元式，条件和无条件转移四元式各一。四元式⑴⑵对应于布尔变量a，四元式⑶⑷对应于关系表达式b<c，原布尔运算消失。2）四元式⑴至⑷中含有多余的四元式，如⑵是不需要的。第32页,共60页，2024年2月25日，星期天3）布尔表达式的真假出口（转移目标地址）E(1)∨E(2): E(1)的真出口是整个布尔表达式E(1)∨E(2)真出口

E(2)的第一个四元式地址是E(1)的假出口

E(2)的真假出口是整个布尔表达式E(1)∨E(2)的真假出口E(1)∧E(2): E(1)的假出口是整个布尔表达式E(1)∧E(2)假出口

E(2)的第一个四元式地址是E(1)的真出口

E(2)的真假出口是整个布尔表达式E(1)∧E(2)的真假出口～E(1)： 只要调换E(1)的真假出口就可得到～E(1)的真假出口第33页,共60页，2024年2月25日，星期天若后继输入符号为'∧'，则可将⑴式的第四项置为3；若后继输入符号为'∨'，可将⑵式的第四项置为3。另外一个未填转移地址的四元式的地址只能作为语义值保存下来。当整个布尔式处理完毕，再来回填它的真出口；当处理到else，再回填它的假出口。③问题的提出在自下而上的分析过程中，语法分析器是自左至右扫描输入符号串，一个布尔表达式的真假出口，往往不能在产生四元式的同时填入。接上例，首先将i归约为X，X.addr保留变量a在符号表中的入口地址。然后将X归约为E时，产生二个四元式如下：

(jnz,&a,0,?) (jmp,0,0,?) 第34页,共60页，2024年2月25日，星期天④解决办法1）修改文法

E→EAE|EOE|～E|(E)|XrX|X EA→E∧ //A表示and EO→E∨ //O表示or X→X+X|X*X|(X)|-X|i|x通过文法修改解决了一半问题。EA→E∧

当E∧归约为EA时，可填真出口，真出口为下一个四元式地址，而假出口无法填写。E0→E∨

当E∨归约为E0时，可填假出口，假出口为下一个四元式地址，而真出口无法填写。2）引进语义变量.tc和.fc保存未填转移目标的四元式地址布尔表达式由若干子表达式构成，转移目标地址只有二个，或为真出口、或为假出口。为了记录和回填方便，利用四元式的第四项（改称为next）构成二条单向链。赋予E、EA和EO另外二个语义值.tc和.fc，分别记录需回填真假出口单向链的链首。第35页,共60页，2024年2月25日，星期天假定布尔表达式E的四元式中需回填真出口的有p、q和r三个四元式，这三个四元式可构成一单向链，链首由E.tc指出。当X或XrX归约为E时，将产生二个四元式。用E.tc指向第一个四元式，用E.fc指向第二个四元式，并将四元式的第四项置为0，表示链尾。如下所示：在分析过程中，利用语义值传递和合并链的方法，最终完成两根真假出口链的构造。在if-then-else语句中，当翻译完布尔表达式，就可找到真出口，利用E.tc进行回填。当翻译完语句S1，就可知道假出口，利用E.fc进行回填。第36页,共60页，2024年2月25日，星期天3）变量和函数nxq指示器

nxq指向下一个将要形成但尚未形成的四元式地址（编号）。nxq初值为1，每执行一次gen_code函数之后，nxq自动增1。链合并函数merg(p1,p2)

将以p1和p2为链首的二条单向链合并为一条，并且将合并后的链首作为返回值。若p2为空，则以p1为合并后的链首；若p2非空，则以p2为合并后的链首。回填函数backpatch(p,t)

将以p为链首的单向链中的每个四元式的第四项置为t。例a∨b<c∨d解：第一步（a∨）第37页,共60页，2024年2月25日，星期天第二步（b<c∨） 第三步（d）第38页,共60页，2024年2月25日，星期天第四步（布尔表达式处理完，回填真出口，语义动作在控制语句中实现）因(1)、(3)和(5)式转移地址相同，故由三式构成真出口链，链首由.tc指出，当布尔表达式E处理完（开始处理S1前），可回填真出口。假出口链由(6)式单独构成，链首由.fc指出，当处理到S2时，才可回填假出口。第39页,共60页，2024年2月25日，星期天E→X{E.tc=nxq;gen_code(jnz,X.addr,0,0);E.fc=nxq;gen_code(jmp,0,0,0); }Er→XrX(1){E.tc=nxq;E.tc:=nxq+1;gen_code(jr,X.addr,X(1).addr,0);gen_code(jmp,0,0,0) }E→～E(1){//真假出口链链首互换

E.tc=E(1).fc;E.fc=E(1).tc;}E→(E(1)){//传递

E.tc=E(1).tc;E.fc=E(1).fc;}EA→E∧{

backpatch(E.tc,nxq);//可填真出口EA.fc=E.fc; //传递}E→EAE(2){E.tc=E(2).tc;//传递真出口链链首

E.fc=merge(EA.fc,E(2).fc);//合并}E→EOE(2){E.tc=merge(EO.tc,E(2).tc);//合并

E.fc=E(2).fc;//传递假出口链链首}EO→E(1)∨{EO.tc=E(1).tc;//传递

backpatch(E(1).fc,nxq);//可填假出口}X→i{//wval表示单词的值

X.addr=sym_entry(wval);}X→x{X.addr=const_int_entry(atoi(wval));}⑤语义子程序。第40页,共60页，2024年2月25日，星期天⑥手工计算设源程序为a∨b∨c。经词法分析，它的单词二元式序列为

(i,"a")(∨,"NUL")(i,"b")(∨,"NUL")(i,"c")(#,"NUL")语法制导翻译过程如黑板所示：step

symbol

wval

.addr

.tc

.fc

输入串

nxq=1第41页,共60页，2024年2月25日，星期天6.8 标号和无条件转移语句的翻译㈠标号和goto语句标号和变量不同，标号不是通过说明语句来定义的，而是用

<标号>:<语句>的形式来定义的，这种定义方式决定了标号的使用范围是局部的。只有少数程序设计语言（例Pascal）是用说明语句来定义标号的。标号是以“goto<标号>”形式来使用的。标号既可以先定位后使用（向后转移），也可以先使用后定位（向前转移）。②向前转移①向后转移第42页,共60页，2024年2月25日，星期天㈡文法及修改

<语句>→标识符:<语句> S→i:S <语句>→goto标识符

S→gi

标号用于标领一个语句，为了能及时填写标号的地址，将文法修改如下：

<语句>→<标号><语句> S→FS <标号>→标识符： F→i: <语句>→goto

标识符

S→gi

当i:归约为F时，可将标号名（L99）填入符号表，转移地址为nxq的当前值p（S的第1个四元式地址），种属为1（标号），类型为1（已定位）。符号表如下所示：内存地址（2字节）符号名（5字节）种属类型…………………………………pL9911…第43页,共60页，2024年2月25日，星期天㈢问题的提出和解决办法①gotoL99是一个向后转移语句处理到gotoL99时，L99已定位。可通过查符号表获得它的地址p，产生四元式(jmp,0,0,p)。②gotoL99是一个向前转移语句L99第一次出现在符号表中创建一个记录，符号名为“L99”，种属为1（标号），类型为0（未定位）,将nxq（设为q）作为链首填入L99的地址栏，产生四元式：

(q)(jmp,0,0,0)L99非第一次出现说明以标号L99为目标的向前转移语句不止一个，可利用四元式的第4项构成一单向链。把L99的地址栏中的四元式编号（设为q）取出，把nxq（设为r）填入地址栏，然后产生四元式：

(r)(jmp,0,0,q)第44页,共60页，2024年2月25日，星期天第45页,共60页，2024年2月25日，星期天6.9控制语句的翻译㈠概述在说明语句、赋值语句和无条件转移语句的基础上，增加了条件语句、循环语句和复合语句。

<语句>→if<布尔表达式>then<语句>endif S→fEtSj<语句>→if<布尔表达式>then<语句>else<语句> S→fEtSeS<语句>→while<布尔表达式>do<语句> S→wEdS<语句>→begin<语句串>end S→{L}<语句串>→<语句串>;<语句> L→L;S<语句串>→<语句> L→S

E的真出口只有扫描到then才明了，而E的假出口需处理完S1并且到达else才可进行回填。这就是说必须把E.fc传递下去，以便到达else时回填。㈡语义变量E.fc的传递

布尔表达式E具有二个语义值E.tc和E.fc，分别指出尚待回填真假出口的四元式。第46页,共60页，2024年2月25日，星期天㈢引进语义变量.chain

当语句S1执行完，意味着整个if-then-else语句执行完毕。因此，在S1的编码之后应产生一条无条件转移指令，这条转移指令将导致程序控制离开整个if-then-else语句。但是，在完成S2的翻译之前，这一无条件转移指令的转移目标是不知道的。甚至在翻译完S2，转移目标仍有可能无法确定，这种情况是由语句的嵌套性所引起的。在S1代码之后的那条无条件转移指令不仅要跨越S2，而且还要跨越S3。参照布尔表达式的处理方法，让非终结符S含有一项语义值S.chain。把所有的要离开控制语句的四元式构成一条单向链，链首由S.chain指示。这些四元式期待在翻译完语句S之后回填转移目标，语句翻译完的标志就是看到分号（;）。第47页,共60页，2024年2月25日，星期天6.9.1if-then语句的翻译㈠文法及修改

<语句>→if<布尔表达式>then<语句>endif S→fEtS(1)j<语句>→标识符=<算术表达式> S→i=X为了能及时回填真出口，文法修改如下：

C→if<布尔表达式>then C→fEt<语句>→C<语句>endif S→CS(1)j<语句>→标识符=<算术表达式> S→i=X㈡语义子程序

C→fEt{ backpatch(E.tc,nxq); //回填真出口

C.chain=E.FC;} //假出口是离开if-then语句

S→CS(1)j{ //S(1)中可能含有离开if_then的四元式

S.chain=merge(C.chain,S(1).chain);}S→i=X{ //赋值语句的四元式代码中不存在需回填转移目标的四元式

S.chain=0; gen_code(=,X.addr,0,sym_entry(wval));}第48页,共60页，2024年2月25日，星期天㈢手工计算设输入串为：ifathenb=dendif。经词法分析，它的单词二元式序列为：(f,"NUL")(i,"a")(t,"NUL")(i,"b")(=,"NUL")(i,"d")(j,"NUL")(#,"NUL")语法制导翻译过程如下所示：step

symbol

wval

.addr

.tc

.fc

.chain

输入串

nxq=1第49页,共60页，2024年2月25日，星期天6.9.2if-then-else语句的翻译㈠文法及修改

if-then-else语句的产生式

<语句>→if<布尔表达式>then<语句>else<语句> S→fEtS(1)eS(2)

当扫描到then可填真出口，当扫描到else可填假出口，当S(1)执行完毕，应离开if-then-else语句。为了能及时回填四元式，修改如下：

<语句>→TP<语句> S→TPS(2)TP→C<语句>else TP→CS(1)eC→if<布尔表达式>then C→fEt注：TP可理解为then-processed第50页,共60页，2024年2月25日，星期天㈡语义子程序TP→CS(1)e{

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的四元式}S→TPS(2){//S(2)中可能含有离开if_then-else的四元式

S.chain=merge(TP.chain，S(2).chain);}C→fEt{ backpatch(E.tc,nxq);C.chain=E.FC;}第51页,共60页，2024年2月25日，星期天㈢手工计算设输入串为：ifathenb=celseb=d。经词法分析，它的单词二元式序列为：(f,"NUL")(i,"a")(t,"NUL")(i,"b")(=,"NUL")(i,"c")(e,"NUL")(i,"b")(=,"NUL")(i,"d")(#,"NUL")语法制导翻译过程如下所示：step

symbol

wval

.addr

.tc

.fc

.chain

输入串

nxq=1第52页,共60页，2024年2月25日，星期天6.9.3while-do语句的翻译㈠文法及修改①布尔表达式E的真出口为S的第一个四元式地址。②E的假出口导致程序控制离开while-do语句，然而这个转移目标地址在整个while-do语句翻译完也未必明确。将该四元式的地址作为S的语义值S.chain保存下来，以便在外层环境中伺机回填。③在S的代码最后应有一条无条件转移四元式，转向测试布尔表达式E，构成循环。需引进新的语义变量.quad，用于记录E的第一个四元式地址。第53页,共60页，2024年2月25日，星期天

while-do语句的产生式如下所示：

<语句>→while<布尔表达式>do<语句> S→wEdS(1)

为了便于语义分析，修改如下：

W→while W→w Wd→W<布尔表达式>do Wd→WEd <语句>→Wd<语句> S→WdS(1)㈡语义子程序

W→w{ W.quad=nxq;} //记录E的第一个四元式编号

Wd→WEd{ //Wd可理解为while-do backpatch(E.TC,nxq); //回填真出口

Wd.chain=E.fc; //传递假出口、即while-do的出口。

Wd.quad=W.quad; //传递E的第一个四元式地址

}S→WdS(1){ backpatch(S(