编译原理6-4.2-4.3--自顶向下翻译-递归下降翻译

6.4L-属性文法和自顶向下翻译6.4.1翻译模式6.4.2自顶向下翻译6.4.3递归下降翻译器的设计6.4.2自顶向下翻译为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归。现在我们把前面讨论过的消除左递归的算法加以扩充，当消除一个翻译模式的基本文法的左递归时同时考虑属性。这种方法适合带综合属性的翻译模式。这样，许多属性文法可以使用自顶向下分析来实现。算术表达式的左递归文法相应的翻译模式E→E1+T{E.val:=E1.val+T.val}E→E1-T{E.val:=E1.val-T.val}E→T{E.val:=T.val}T→(E){T.val:=E.val}T→num{T.val:=num.val}图6.13带左递归的文法的翻译模式消除左递归，构造新的翻译模式ET{R.i:=T.val}R{E.val:=R.s}R+T{R1.i:=R.i+T.val}R1{R.s:=R1.s}R－T{R1.i:=R.i－T.val}R1{R.s:=R1.s}R{R.s:=R.i}T(Ｅ){T.val:=E.val}Tnum{T.val:=num.val}图6.14消除左递归后的翻译模式图6.15计算表达式9–5+2对于自顶向下分析，我们假定动作是在处于相同位置上的符号被展开（匹配成功）时执行的。ET.val=9R.i=9num.val=9－T.val=5R.i=4+T.val=2R.i=6num.val=5num.val=2下面我们把转换左递归翻译模式的方法推广到一般，以便进行自顶向下分析。假设我们有下面的翻译模式，它的每个文法符号都有一个综合属性，用小写字母表示，g和f是任意函数。A→A1Y{A.a：＝g(A1.a,Y.y)}A→X{A.a：＝f(X.x)}(6.1)消除左递归，转换为如下文法:A→XRR→YR|考虑语义动作，翻译模式变为A→X{R.i:=f(X.x)}R{A.a:=R.s}R→Y{R1.i:=g(R.i,Y.y)}R1{R.s:=R1.s}R{R.s:=R.i}(6.2)(6.3)XA.a:=f(X.x)A.a:=g(f(X.x),Y1.y)Y1A.a:=g(g(f(X.x),Y1.y),Y2.y)Y2(a)按(6.1)自下而上计算A.aXR.i:=f(X.x)Y1R.i:=g(f(X.x),Y1.y)Y2R.i:=g(g(f(X.x),Y1.y),Y2.y)R.sR.sR.s(b)按(6.3)自上而下计算图6.16计算属性值的两种方法例6.11如果把构造抽象语法树的属性文法定义（见表6.4)转化成翻译模式，那么关于E的产生式和语义动作就变为：EE1+T｛E.nptr:=mknode(‘+’,E1.nptr,E2.nptr)｝EE1-T｛E.nptr:=mknode(‘-’,E1.nptr,E2.nptr)｝ET｛E.nptr:=T.nptr)｝T(E){T.nptr:=E.nptr}Tnum{T.nptr:=mkleaf(‘NUM’,num.val)}Tid{T.nptr:=mkleaf(‘ID’,id.entry)}ET{R.i:=T.nptr}R{E.nptr:=R.s}R+T{R1.i:=mknode(‘+’,R.i,T.nptr)}R1{R.s:=R1.s}R-T{R1.i:=mknode(‘-’,R.i,T.nptr)}R1{R.s:=R1.s}R{R.s:=R.i}//返回最终语法树（其余不变，略）删除左递归后：引入非终结符R图6.17构造抽象语法树的翻译模式ETnptrTnptridR-+Tnptridnumididnum4+-toentryforatoentryforciRsRi图6.18使用继承属性构造语法树R.i指向根结点6.4.3递归下降翻译器的设计对给定的适合于自顶向下翻译的翻译模式，下面给出设计递归下降翻译器的方法。1.对每个非终结符A构造一个函数过程，对A的每个继承属性设置一个形式参数，函数的返回值为A的综合属性（作为记录，或指向记录的一个指针，记录中有若干域，每个属性对应一个域）。为了简单，我们假设每个非终结只有一个综合属性。A对应的函数过程中，为出现在A的产生式中的每一个文法符号的每一个属性都设置一个局部变量。2.非终结符A对应的函数过程中，根据当前的输入符号决定使用哪个产生式候选。3.每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号（终结符）、非终结符和语义动作分别作以下工作。o(1)对于带有综合属性x的终结符X，把x的值存入为X.x设置的变量中。然后产生一个匹配X的调用，并继续读入一个输入符号advance。o(2)对于每个非终结符B，产生一个右边带有函数调用的赋值语句c＝B(b1，b2，…，bk），其中，b1，…，bk是为B的继承属性设置的变量，c是为B的综合属性设置的变量。o(3)对于语义动作，把动作的代码抄进分析器中，用代表属性的变量来代替对属性的每一次引用。o(4)函数结尾：returnA的综合属性。例6.12图6.17中的文法是LL(1)的,因此适合于自顶向下分析。根据文法非终结符的属性，得到关于非终结符E，R，T的函数及其参数的类型，具体如下：functionE：↑AST-node；functionR(in：↑AST-node)：↑AST-node；functionT：↑AST-node；R.in:继承属性作为R的参数把图6.17中的两个R产生式结合起来使翻译程序更小，新的产生式中用addop代表+和-。R→addopT{R1.i:=mknode(addop.lexme，R.i，T.nptr）｝R1{R.s:=R1.s}R→ε{R.s：＝R.i｝procedureR;beginifsym=addopthenbeginadvance;T;Rendelsebegin/*什么也不做*/endend;图6.19产生式RaddopTR|的分析过程functionR(in:AST-node):AST-node;varnptr,i1,s1,s:AST-node;addoplexeme:char;beginifsym=addopthenbegin/*产生式RaddopTR*/addoplexeme:=lexval;advance;nptr:=T;i1:=mknode(addoplexme,in,nptr);s1:=R(i1);s:=s1endelses:=in;/*产生式R*/returnsend;图6.20递归下降构造抽象语法树nptr:T.nptri1:R1.is1:R1.ss:R.saddoplexeme:addop(+|-)