语法制导翻译

第语法制导翻译优选第语法制导翻译语义处理的功能1审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。 类型检查、控制流检查、一致性检查、上下文相关性检查、名字的作用域分析2如果静态语义正确，语义处理则要执行真正的翻译，即要么生成程序的中间代码表示，要么生成机器语言或汇编语言的目标代码。 直接生成机器语言或汇编语言形式的目标代码的优点是编译时间短且无需中间代码到目标代码的翻译，而中间代码的优点是使编译结构在逻辑上更为简单明确，特别是使目标代码的优化比较容易实现。 6.1语法制导翻译动机语义形式化是个专门的研究课题，目前有各种各样的方法和记号不断推出，例如操作语义学、公理语义学、指称语义学和代数语义学等。不论哪种方法，其本身的符号系统比较繁杂，其描述文本不易读，尚不便借助这些形式系统自动完成语义处理任务。现在有很多编译系统采用语法制导翻译方法。这仍不是一种形式系统，但是比较接近形式化。这种方法使用属性文法为工具来说明程序设计语言的语义。语法制导翻译在语法分析的每一步中，通过执行每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的方法。在语法分析过程中，当一个产生式获得匹配（对于自顶向下分析）或用于归约（对于自底向上分析）时，此产生式相应的语义子程序就进入工作，完成既定的翻译任务。分类自底向上语法制导翻译自顶向下语法制导翻译语法制导定义使用上下文无关文法描述输入的语法结构，并且每一个文法符号和一个属性集合相关联，每一个产生式和一个语义规则集合相关联。语法制导定义说明程序设计语言中各种结构的翻译。属性程序设计语言结构的类型、目标代码中第一条指令的位置、生成的指令个数等信息。语义规则规定怎样计算与产生式中出现的文法符号相关联的属性的值的规则。文法和语义规则集合构成了语法制导定义。属性分类继承属性：用于“自顶向下”传递信息。继承属性的值由相应分析树中结点的父结点及兄弟结点的属性值计算得到。继承属性可以很方便地用来表示程序语言上下文结构的依赖性。综合属性：用于“自底向上”传递信息。综合属性的值由相应分析树中结点的子结点的属性值计算得到，其传递方向与继承属性相反，即沿分析树向上传递，从分枝结点到根结点。语法制导定义的形式在语法制导定义中，每个产生式A

与一个形如b:=f(c1,c2,,ck)的语义规则集合相关联，其中f是函数，并且满足下面两种情况之一：1.b是A的一个综合属性，且c1,c2,,ck是该产生式文法符号的属性；2.b是产生式右部某个文法符号的一个继承属性，且c1,c2,,ck也是该产生式文法符号的属性。这两种情况都称属性b依赖于属性c1,c2,,ck

。例6-1简单算术表达式求值的属性文法产生式 语义规则(1)S

E print(E.val)(2)E

E(1)+T

E.val=E(1).val+T.val(3)E

T E.val=T.val(4)T

T(1)*F T.val=T(1).val*F.val(5)T

F T.val=F.val(6)F

(E) F.val=E.val(7)F

i F.val=i.lexval其中，属性皆为综合属性，并且可以认为第一条语义规则定义了S的一个虚综合属性。例6-2简单变量类型声明语句的属性文法产生式 语义规则(1)D

TL L.in=T.type(2)T

int

T.type=int(3)T

float T.type=float(4)L

L(1),id L(1).in=L.in; addtype(id.entry,L.in)(5)L

id addtype(id.entry,L.in)其中，T.type为综合属性，其值由声明中的关键字来确定；L.in为继承属性，其值由分析树中左边的兄弟节点或父节点的属性值计算得到。属性信息传递情况示意6.2属性文法属性文法是一个语法制导定义，其中语义规则中的函数不能有副作用。语义规则中的函数通常被写成表达式的形式。有时，语法制导定义中某个规则的目的就是为了产生副作用。这种语义归则一般被写成过程调用或程序段。在这种情况下，可以把它看作是定义产生式左部非终结符的虚综合属性，但这种语义规则中的虚属性和符号:=都不给出来。属性文法S-属性文法只含有综合属性的属性文法S-属性文法的翻译器通常可借助LR分析器实现。把LR分析器的能力加以扩大，使它能在用某个产生式进行归约的同时调用相应的语义子程序进行有关的翻译工作；每个产生式的语义子程序执行之后，某些结果(语义信息)必须作为此产生式的左部符号的语义值暂时保存下来，以便以后语义子程序引用这些信息。原LR分析器的分析栈也加以扩充，存放三类信息：分析状态、文法符号及文法符号对应的语义值。扩充后的LR分析栈例6-3考虑下面的语法制导定义 产生式 语义规则

(0)S'→E printval[top] (1)E→E(1)+E(2) val[ntop]=val[top]+val[top–2] (2)E→E(1)*E(2) val[ntop]=val[top]*val[top–2] (3)E→(E(1)) val[ntop]=val[top–1] (4)E→i val[ntop]=lexval

其中，lexval为i的整型内部值，由词法分析给出。top和ntop分别是归约前和归约后的栈顶指针。表达式7＋9*5#的语义分析和计值过程步骤状态栈符号栈语义栈输入串主要动作10#_7＋9*5#s3203#7__＋9*5#r4301#E_7＋9*5#s44014#E+_7_9*5#s350143#E+9_7__*5#r460147#E+E_7_9*5#s5701475#E+E*_7_9_5#s38014753#E+E*5_7_9__#r49014758#E+E*E_7_9_5#r2100147#E+E_7_45#r11101#E_52#acc属性文法在语法分析过程中进行语义分析和翻译，属性的计算顺序受到语法分析建立分析树结点顺序的限制。一种自然的计算属性的顺序是按深度优先访问分析树结点的顺序，它适应多种自底向上和自顶向下的翻译方法。L-属性文法可用于按深度优先顺序计算属性值。intT_val,R_i,R_s;intE_val;(3)E→(E(1)) val[ntop]=val[top–1]使用标记非终结符M和N改写为例6-4非L-属性的语法制导定义文法和语义规则集合构成了语法制导定义。原LR分析器的分析栈也加以扩充，存放三类信息：分析状态、文法符号及文法符号对应的语义值。计算这种属性的动作通常可放在产生式右端的未尾。R{E.标记非终结符也可以用于模拟不是复写规则的语义规则可看成是分析过程中翻译的注释。intT_val,R_i,R_s;returnT_val;计算这种属性的动作通常可放在产生式右端的未尾。表达式7＋9*5#的语义分析和计值过程L-属性文法一个属性文法称为L-属性文法，如果对于每个产生式AX1X2Xn，其中每条语义规则中的每个属性或者是综合属性，或者是Xj（1jn）的一个继承属性且这个继承属性仅依赖于(1)X1，X2，，Xj-1的属性(2)A的继承属性S-属性文法一定是L-属性文法L-属性文法允许一次遍历就计算出所有属性值例6-4非L-属性的语法制导定义产生式语义规则A

LML.i:=l(A.i)M.i:=m(L.s)A.s:=f(M.s)A

QRR.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s)翻译模式翻译模式是语法制导定义的一种便于翻译的书写形式。其中属性与文法符号相对应，语义规则或语义动作用花括号{}括起来，可被插入到产生式右部的任何合适的位置上。一种语法分析和语义动作交错的表示法，表达在按深度优先遍历分析树的过程中何时执行语义动作。翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。 例6-5一个简单的翻译模式，把中缀表达式翻译成后缀表达式。E→TRR→opT{print(op.lexeme)}R(1)|

T→num{print(num.val)}把语义动作看成终结符号，输入9–5+2，按深度优先遍历分析树，执行遍历中访问的语义动作，将输出表达式9–5+2的后缀式95–2+ET9Tprint(´9´)Rprint(´–´)print(´+´)R–5print(´5´)+T2print(´2´)R

9–5+2的带语义动作的分析树设计翻译模式（根据语法制导定义）语法制导定义是L-属性文法保证语义动作不会引用还没有计算的属性值。只需要综合属性的情况为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。例如：T

T(1)*FT.val:=T(1).val*F.valT

T(1)*F{T.val:=T(1).val*F.val}既有综合属性又有继承属性产生式右边的符号的继承属性的值必须在这个符号以前的动作中计算出来。一个动作不能引用这个动作右边符号的综合属性。产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的未尾。例如，下面的翻译模式不满足要求：

S

A(1)A(2){A(1).in:=1;A(2).in:=2}A

a{print(A.in)}(1)SE print(E.把LR分析器的能力加以扩大，使它能在用某个产生式进行归约的同时调用相应的语义子程序进行有关的翻译工作；计算这种属性的动作通常可放在产生式右端的未尾。match('num');N{print(‘–’)}Tint{T.Aa{print(A.语义形式化是个专门的研究课题，目前有各种各样的方法和记号不断推出，例如操作语义学、公理语义学、指称语义学和代数语义学等。SbABC C.L(1),id{addtype(id.(2)如果按照AM1X1…MnXn进行归约，A.(3)Tfloat T.(5)Lid addtype(id.(2)EE(1)+T E.R_i=T_val;例6.6从L-属性制导定义建立一个满足上面要求的翻译模式。 数学排版语言EQN，例如，

Esub1.val

编排结果E1.val产生式语义规则S

BB.ps:=10S.ht:=B.htB

B(1)B(2)B(1).ps:=B.psB(2).ps:=B.psB.ht:=max(B(1).ht,B(2).ht)B

B(1)subB(2)B(1).ps:=B.psB(2).ps:=shrink(B.ps)B.ht:=disp(B(1).ht,B(2).ht)B

textB.ht:=text.h*B.ps大小和高度的语法制导定义6.5自顶向下的翻译在预测分析中实现L-属性文法使用翻译模式而不是语法制导定义，更加明确语义动作的顺序和属性计算的顺序。算法6.1预测语法制导翻译器的建立 输入：一个带有适合预测分析的基础文法的语法制导翻译模式。 输出：一个语法制导翻译器的代码。

1.对每个非终结符A，建立一个可递归调用的函数过程A。为A的每一个继承属性都设置一个形式参数，函数的返回值是A的综合属性值。出现在以A为左部的产生式中的每一个文法符号的每一个属性定义一个相应的局部变量。

2.函数过程A的代码（指用符号形式表示的数据和程序）要根据当前的输入符号来决定使用哪一个产生式。

3.与每一个产生式有关的代码，从左到右根椐产生式右部是终结符(单词符号)、非终结符号还是语义动作，分别处理：

(a)对于带有综合属性x的单词符号X，x存放在X.x中，Match(X)。

(b)对于非终结符B，编写一个赋值语句

c=B(b1,b2,…,bk)

其中，b1,b2,…,bk是继承属性，c是综合属性。

(c)对于每个语义动作，把动作的代码抄进翻译器中，用代表属性的变量来代替对属性的每一次引用。例6.7表达式的预测翻译器E

T{R.i:=T.val}R{E.val:=R.s}intE(){intE_val;intT_val,R_i,R_s;T_val=T();R_i=T_val;R_s=R(R_i);E_val=R_s;returnE_val;}R

＋

T{R(1).i:=R.i+T.val}R(1){R.s:=R(1).s}R

–T{R(1).i:=R.i–T.val}R(1){R.s:=R(1).s}R{R.s:=R.i}intR(intR_i){intR_s;intT_val,R1_s,R1_i;if(lookahead=='+'){match('+');T_val=T();R1_i=R_i+T_val;R1_s=R(R1_i);R_s=R1_s;}if(lookahead=='-'){match('-');T_val=T();R1_i=R_i-T.val;R1_s=R(R1_i);R_s=R1_s;}returnR_s;}T(E) {T.val:=E.val}T

num {T.val:=num.val}intT(){intT_val;intE_val;if(lookahead=='('){match('(');E_val=E();T_val=E_val;if(lookahead==')'){match(')');}elseerror();}elseif(lookahead=='num'){match('num');T_val=num_val;}elseerror();

returnT_val;}6.4自底向上的翻译从翻译模式中去掉嵌入的语义动作在自底向上的翻译方法中，需要把所有的翻译动作都放在产生式右端末尾。在基础文法中插入形如M

的新产生式，其中M是一个新的起标记(marker)作用的非终结符。标记非终结符M用来代替嵌入在产生式中的动作，并把这个动作放到产生式M

的末尾。例如ETRR+T{print(‘+’)}R|–T{print(‘–’)}R|Tnum{print(num.val)}使用标记非终结符M和N改写为ETRR+TMR|–TNR|Tnum{print(num.val)}M{print(‘+’)}N{print(‘–’)}分析栈中的继承属性考虑产生式AXY，X有综合属性X.s，Y有继承属性Y.i。在自底向上的分析中，按照该产生式进行归约的时候，依次把Y和X出栈。如果继承属性Y.i是由复写规则Y.i:=X.s

决定的，那么Y.i的值就等于分析栈中存储的X.s的值。例6.8变量声明语句的翻译器

DT{L.in:=T.type} L Tint{T.type:=int} Tdouble{T.type:=double} L{L(1).in:=L.in} L(1),id{addtype(id.entry,L.in)} Lid{addtype(id.entry,L.in)}步骤符号栈输入动作1#intp,q,r#移进2#intp,q,r#归约，Tint

3#Tp,q,r#移进4#Tp,q,r#归约，L

id5#TL,q,r#移进6#TL,q,r#移进7#TL,q,r#归约，LL,id8#TL,r#移进9#TL,r#移进10#TL,r#归约，LL,id11#TL#归约，DTL

12#D#接受声明语句intp,q,r的自底向上分析过程翻译模式代码实现DT{L.in:=T.type}LTint{T.type:=int}Tdouble{T.type:=double}L{L(1).in:=L.in}L(1),id{addtype(id.entry,L.in)}Lid{addtype(id.entry,L.in)}val[ntop]:=integerval[ntop]