语法制导和中间代码生成10年.ppt

《语法制导和中间代码生成10年.ppt》由会员分享，可在线阅读，更多相关《语法制导和中间代码生成10年.ppt（94页珍藏版）》请在三一办公上搜索。

1、第八章 语法制导翻译和中间代码生成,学习目标：掌握：常见语法成分的中间代码形式；常见语法成分的属性文法或翻译方案理解：属性文法、语法制导翻译方法,语义分析基础,语义分析的内容主要是类型相容检查，有以下几种：各种条件表达式的类型是不是boolean型？运算符的分量类型是否相容？赋值语句的左右部的类型是否相容？形参和实参的类型是否相容?下标表达式的类型是否为所允许的类型？函数说明中的函数类型和返回值的类型是否一致？,其它语义检查：VE中的V是不是变量，而且是数组类型？V.i中的V是不是变量，而且是记录类型？i是不是该记录的域名？x+f()中的f是不是函数名？形参个数和实参个数是否一致？每个使用性标

2、识符是否都有声明？有无标识符的重复声明？,在语义分析同时产生中间代码，在这种模式下，语义分析的主要功能如下：语义审查在扫描声明部分时构造标识符的符号表在扫描语句部分时产生中间代码语义分析方法语法制导翻译方法使用属性文法为工具来说明程序设计语言的语义。,8.1属性文法8.2语法制导翻译概论8.3中间代码形式8.4基本语言成分的自下而上语法制导翻译8.5自上而下的语法制导翻译,8.1 属性文法(Attribute Grammar),属性对文法的每一个符号，引进一些属性，这些属性代表与文法符号相关的信息，如类型、值、存储位置等。语义规则为文法的每一个产生式配备的计算属性的计算规则，称为语义规则。属性

3、文法是带属性的一种文法它的主要思想：首先对于每个文法符号引进相关的属性符号；其次对于每个产生式写出计算属性值的语义规则,属性文法的形式定义一个属性文法是一个三元组,A(G,V,F)G是一个上下文无关文法；V是属性的有穷集；F是关于属性的断言的有穷集。说明：每个属性与文法符号相联，N.t表示文法符号N的属性t。属性值又称语义值。存储属性值的变量又称语义变量。每个断言与文法的某个产生式相联，写在 内。属性的断言又称语义规则，它所描述的工作可以包括属性计算、静态语义检查、符号表的操作、代码生成等，有时写成函数或过程段。,例 完成类型检查的属性文法ET1+T2T1.tint AND T2.tintET

4、1 or T2T1.tbool AND T2.tboolTnumT.t:intTtrueT.t:boolTfalseT.t:bool,属性的分类：综合属性：从语法树的角度来看，如果一个结点的某一属性值是由该结点的子结点的属性值计算来的，则称该属性为综合属性。内在属性是综合属性。用于“自下而上”传递信息,继承属性从语法树的角度来看，若一个结点的某一属性值是由该结点的兄弟结点和（或）父结点的属性值计算来的，则称该属性为继承属性。用于“自上而下”传递信息说明：终结符只有综合属性，它们由词法分析器提供非终结符既有综合属性也有继承属性，但文法开始符没有继承属性,例 简单算术表达式求值的属性文法LE Pr

5、int(E.val)EE1+T E.val:E1.val+T.val ET E.val:T.val TT1*F T.val:T1.val*F.val TF T.val:F.val F(E)F.val:E.val Fdigit F.val:digit.lexval,E.val、T.val、F.val都是综合属性终结符digit只有综合属性，它的值由词法分析提供,例 描述变量类型说明的属性文法DTL L.in:T.type Tint T.type:int Treal T.type:real LL1,id L1.in:L.in；addtype(id.entry，L.in)Lid addtype(id

6、.entry，L.in),L.in是继承属性T.type是综合属性,int id1,id2的语法树:,用表示属性的传递情况,8.2 语法制导翻译概论,语法制导翻译基本思想：在语法分析过程中，随着分析的步步进展，每当使用一条产生式进行推导（对于自上而下分析）或归约（对于自下而上分析），就执行该产生式所对应的语义动作，完成相应的翻译工作。语法制导翻译法不论对自上而下分析或自下而上分析都适用,例 简单算术表达式求值的属性文法EE1+T E.val:E1.val+T.val ET E.val:T.val TT1*digit T.val:T1.val*digit.lexval Tdigit T.val:

7、digit.lexval,2+3*5的语法树：,T.val=2,T.val=3,T.val=15,E.val=2,E.val=17,自下而上语法制导翻译过程：,一旦语法分析确认输入符号串是一个句子，它的值也同时由语义规则计算出来,语法制导翻译的实现途径以自下而上（LR分析）的语法制导翻译来说明将LR分析器能力扩大，增加在归约后调用语义规则的功能增加语义栈，语义值放到与符号栈同步操作的语义栈中，多项语义值可设多个语义栈，栈结构为：,例 简单算术表达式求值的属性文法L Eprint(E.val)EE1+T E.val:E1.val+T.val ET E.val:T.val TT1*digit T.

8、val:T1.val*digit.lexval Tdigit T.val:digit.lexval,S5,*5,#E+,-2-,014,6,acc,#,#,-,0,10,1,r2,#,#E+,-2-,014,9,7,7,1,2,GOTO,r4,S6,r5,S3,S4,r3,r5,S3,Action,#E+T*5,-2-3-5,014756,8,5,#E+T*,-2-3-,01475,7,*5,#E+3,-2-,0143,5,3*5,#E+,-2-,014,4,3*5,#,-,0,3,3*5,#,-,0,2,3*5,#2,-,03,1,23*5,#,-,0,0,剩余输入串,符号栈,语义栈,状态栈

9、,步骤,分析并计算23*5的过程如下:,2,2,T,1,2,E,7,3,T,7,T,15,1,17,E,8.3 中间代码的形式,定义：中间代码是一种复杂性介于源程序语言和机器语言之间的一种表示形式。使用中间代码的好处：中间代码与具体机器无关对中间代码进行与机器无关的优化形式：逆波兰记号、三元式、间接三元式、四元式和树形表示,8.3.1 逆波兰记号,逆波兰表示法将运算对象写在前面，把运算符写在后面，因而也称后缀式。例如：,后缀式的计算机处理后缀式的最大优点是易于计算机处理处理过程：从左到右扫描后缀式，每碰到运算对象就推进栈；碰到运算符就从栈顶弹出相应目数的运算对象施加运算，并把结果推进栈。最后的

10、结果留在栈顶。,t1=-b,t2=c*d,t3=t1+t2,例：表达式bc*d的后缀式 bcd*+的计值过程,逆波兰表示法的扩充逆波兰表示法很容易扩充到表达式以外的范围 例如：,8.3.2 三元式和树形表示,三元式(算符op，第一个运算对象ARG1,第二个运算对象ARG2),说明：三元式的某些运算对象是另一个三元式的编号（代表其结果）一目算符只需选用一个运算对象（ARG1）多目算符可用连续几个三元式表示,例：a:b*c+b*d表示为(1)(*,b,c)(2)(*,b,d)(3)(+,(1),(2)(4)(:,(3),a),树形表示二目运算对应二叉子树，多目运算对应多叉子树，但通常通过引入新结点

11、表示成二叉子树。例如：a:b*c+b*d 表示成,四元式,四元式表示四元式是一种比较普遍采用的中间代码形式(算符op，ARG1，ARG2，运算结果RESULT）,例如：a:b*c+b*d的四元式表示如下：(*,b,c,t1)(*,b,d,t2)(+,t1,t2,t3)(:,t3,a)其中t i（i1,2,3）是编译程序引入的临时变量,四元式的优点：四元式比三元式更便于优化。优化要求改变运算顺序或删除某些运算，引起编号的变化。三元式通过编号引用中间结果，编号的变化引起麻烦；四元式通过临时变量引用中间结果，编号变化无影响。四元式对生成目标代码有利。四元式表示很类似于三地址指令，很容易转换成机器代码

12、。,四元式的另一种表示有时为了更直观，把四元式写成简单赋值形式或更易理解的形式,8.4 基本语言成分的自下而上语法制导翻译,8.4.1简单赋值语句的翻译8.4.2布尔表达式的翻译8.4.3控制结构的翻译8.4.4 简单说明语句的翻译,8.4.1 简单赋值语句的翻译,简单赋值语句是指不含复杂数据类型（如数组，记录等）的赋值语句。赋值语句的语义审查包括：每个使用性标识符是否都有声明？运算符的分量类型是否相容？赋值语句的左右部的类型是否相容？赋值语句的翻译目标：在赋值语句右部表达式产生的四元式序列后加一条赋值四元式,1属性和语义规则中用到的变量、过程和函数属性：用id.name表示单词id的名字。用

13、E.place表示存放E值的变量名在符号表的入口地址或临时变量编码。变量、函数和过程：用nextstat变量给出在输出序列中下一个四元式的序号用lookup（id.name）函数审查id.name是否出现在符号表中，是则返回id的入口地址，否则返回nil。用emit过程向输出序列输出一个四元式，emit每调用一次，nextstat的值增加1用newtemp函数生成临时变量，每次调用生成一个新的临时变量，如t1,t2,用error过程进行错误处理。,Sid:E p:lookup(id.name);if pnil then emit(:,E.place,-,p)else error,2简单赋值语句

14、的翻译（假定变量只有一种类型）,EE1+E2 E.place:newtemp;emit(+,E1.place,E2.place,E.place),此情况下的语义审查只有：每个使用性标识符是否都有声明？,EE1 E.place:newtemp;emit(,E1.place,-,E.place),E(E1)E.place:E1.place,Eid p:lookup(id.name);if pnil then E.place:p else error,EE1*E2 E.place:newtemp;emit(*,E1.place,E2.place,E.place),例 翻译赋值语句A:B+C,E1.p

15、laceB,E2.placeC,E.placet1；(,B,C,t1),(:,t1,-,A),(为了直观，用B和C分别表示B和C在符号表的入口地址),表达式中可能出现不同类型的变量和常量语义审查包括：每个使用性标识符是否都有声明？运算符的分量类型是否相容？若不接受不同类型的运算对象混合运算，则应指出错误；若接受混合运算则要进行类型转换处理。例：假定表达式可以有混合运算，id可以是整型和实型，且当两个不同类型的id进行运算时先把整型id转换成实型，再进行运算。用E.type表示E的类型信息，其值为int或real。用+i,*i 表示整型运算，用+r,*r 表示实型运算。用一目算符 itr 表示将

16、整型量转换成实型量的运算。,3 简单赋值语句的四元式翻译,E.place:newtemp;if E1.typeint AND E2.typeint thenbegin emit(+i,E1.place,E2.place,E.place);E.type:int endelse if E1.typereal AND E2.typereal thenbegin emit(+r,E1.place,E2.place,E.place);E.type:real end else if E1.typeint then begin t:newtemp;emit(itr,E1.place,-,t);emit(+r

17、,t,E2.place,E.place);E.type:real end else begin t:newtemp;emit(itr,E2.place,-,t);emit(+r,E1.place,t,E.place);E.type:real end;,产生式EE1+E2的包含类型属性的语义规则为：,属性文法的构造属性：根据语义处理的需要，设计文法符号的相应属性（包括：属性的个数和属性的符号表示）语义规则：满足语义处理的要求，并生成相应的中间代码,8.4.2 布尔表达式的翻译,布尔表达式的作用与结构布尔表达式的两个作用：计算逻辑值作为控制语句(如if-then,while)的条件表达式布尔表达式

18、的语法：or|and|not|()|true|false（布尔表达式）relop|()（关系表达式）op|-|()|id|num（算术表达式）其中：relop是关系算符(如,=)op是算术算符(+,-,*,/),只考虑如下形式的布尔表达式的翻译EE or E|E and E|not E|(E)|id rop id|true|false布尔算符的优先顺序（从高到低）为：not,and,or，且and和or都服从左结合，not服从右结合关系算符的优先级都相同，而且高于任何布尔算符，低于任何算术算符。,布尔表达式的计算方法：采用两种方法：数值表示的直接计算与逻辑表示的短路计算直接计算与算术表达式计算

19、方法基本相同如：1 or 0 and 1=1 or 0=1短路计算即布尔表达式计算到某一部分就可以得到结果，而无需对布尔表达式进行完全计算。可以用if-then-else来解释A or B if A then 1 else BA and Bif A then B else 0not Aif A then 0 else 1,直接计算的语法制导翻译,对关系表达式，如ab，可翻译成如下固定的三地址代码序列：(1)(j,a,b,(4)(2)(:=,0,-,t1)(3)(jump,-,-,(5)(4)(:=,1,-,t1)(5),如：A or B and not C被翻译成：(not,C,-,t1)(a

20、nd,B,t1,t2)(or,A,t2,t3),PC,直接计算的翻译方案(1)EE1 or E2 E.place:newtemp;emit(or,E1.place,E2.place,E.place)(2)EE1 and E2 E.place:newtemp;emit(and,E1.place,E2.place,E.place)(3)Enot E1 E.place:newtemp;emit(not,E1.place,E.place)(4)E(E1)E.place:E1.place(5)Eid1 rop id2 E.place:newtemp;emit(jrop,id1.place,id2.pla

21、ce,nextstat+3);emit(:,0,E.place);emit(jump,nextstat+2);emit(:,1,E.place)(6)Etrue E.place:newtemp;emit(:=,1,-,E.place)(7)EfalseE.place:=newtemp;emit(:=,0,-,E.place),例：布尔表达式af的翻译,E.place=t5,E1.place=t1,E2.place=t4,E2.place=t3,E1.place=t2,(1)(j,a,b,(4)(2)(:=,0,-,t1)(3)(jump,-,-,(5)(4)(:=,1,-,t1),(5)(j,

22、c,d,(8)(6)(:=,0,-,t2)(7)(jump,-,-,(9)(8)(:=,1,-,t2),(9)(j,e,f,(12)(10)(:=,0,-,t3)(11)(jump,-,-,(13)(12)(:=,1,-,t3),(13)(and,t2,t3,t4),(14)(or,t1,t4,t5),作为条件控制的布尔表达式的翻译基本翻译方法当布尔表达式用于控制条件时，并不需要计算表达式的值，而是一旦确定了表达式为真或为假，就将控制转向相应的代码序列。,为布尔表达式E引入两个新的属性：E.true：表达式的真出口，它指向表达式为真时的转向E.false：表达式的假出口，它指向表达式为假时的转

23、向,把E翻译成下述形式的条件转移和无条件转移的四元式序列：(jnz,A,-,p)若A为真，则转向四元式p(jrop,A,B,p)若A rop B为真，则转向四元式p(jump,-,-,p)无条件转向四元式p,(1)(jnz,A,-,5)A的真出口为5(2)(jump,-,-,3)A的假出口为3(3)(j,B,D,5)BD的真出口为5(4)(jump,-,-,p+1)BD的假出口为(p+1)(5)(关于S1的四元式序列)(p)(jump,-,-,q)跳过S2的代码段(p+1)(关于S2的四元式序列)(q),(1)-(4)是布尔式A or BD 翻译产生的代码，全部是条件转移和无条件转移四元式，没

24、有布尔运算。,例：if A or BD then S1 else S2翻译成如下四元式序列,具体说明如下：用E.true和E.false 分别表示E的“真”和“假”出口转移目标，在翻译E时并未能确定。对于E为 a rop b 形式，生成代码如下：(jrop,a,b,E.true)(jump,E.false)以结构图表示：,对于E为 E1 or E2的形式，生成代码结构如下：,若E1为真，则可知E为真，即E1的真出口和E的真出口一样；若E1为假，则必须计算E2，因此E1的假出口应是E2代码的第一个四元式序号；E2的真出口和假出口分别与E的真出口和假出口一样,对于E为 E1 and E2的形式，生

25、成代码结构如下：,对于E为 not E1形式，只需调换E1的真假出口，即可得到E的真假出口。,例：E 为 af，翻译为四元式序列：（1）(j,e,f,E.true)（6）(jump,-,-,E.false),真假出口的拉链与回填原因在把布尔式翻译成一串条件转和无条件转四元式时，真假出口未能在生成四元式时确定；而且多个四元式可能有相同的出口,说明：E.true和E.false不能在产生四元式的同时确定，要等将来目标明确时再回填，为此要记录这些要回填的四元式。通常采用“拉链”的办法，把需要回填E.true的四元式拉成一条“真”链，把需要回填E.false的四元式拉成一条“假”链。,if af th

26、en S1 else S2翻译为四元式序列：（1）(j,e,f,(7)（6）(jump,-,-,(p+1)（7）(关于S1的四元式)（p）(jump,-,-,q)(p+1)(关于S2的四元式)(q),拉链方式：,则链接成为：(10)goto(0)(20)goto(10)(30)goto(20),把地址（30）作为链首，地址（10）作为链尾,0为链尾标志。四元式的第四个区段存放链指针。E.true 和E.false用于存放“真”链和“假”链的链首。,若有四元式序列：(10)goto E.true(20)goto E.true(30)goto E.true,为了完成拉链和回填工作，设计以下语义变量

27、和过程（函数）：函数merge(p1,p2)用于把P1和p2为链首的两条链合并成1条，返回合并后的链首值。其算法为：当P2为空链时，返回P1；当P2不为空链时，把P2的链尾第四区段改为P1，返回P2。过程backpatch(p,t)用于把链首P所链接的每个四元式的第四区段都填为转移目标t。语义变量E.codebegin表示表达式E的第一个四元式的序号。,EE1 or E2 E.codebegin:E1.codebegin;backpatch(E1.false,E2.codebegin);E.true:merge(E1.true,E2.true);E.false:E2.false,自下而上分析中

28、布尔表达式的一种翻译方案,EE1 and E2 E.codebegin:E1.codebigin;backpatch(E1.true,E2.codebegin);E.true:E2.true;E.false:merge(E1.fasle,E2.false),Enot E1 E.codebegin:E1.codebigin;E.true:E1.false;E.false:E1.true,E(E1)E.codebegin:E1.codebegin;E.true:E1.true;E.false:E1.false,Eid1 rop id2 E.codebegin:nextstat;E.true:nex

29、tstat;E.false:nextstat+1;emit(jrop,id1.place,id2.place,1);emit(jump,0),Etrue E.codebegin:nextstat;E.true:nextstat;E.false:0;emit(jump,1),Efalse E.codebegin:nextstat;E.false:nextstat;E.true:0;emit(jump,0),例 ab or cd and ef 的翻译过程假定四元式编号从100开始，即开始时nextstat100,E,E1,or,E2,E1,and,E2,a,b,c,d,e,f,E1.begin=1

30、00E1.true=100E1.false=101,E1.begin=102E1.true=102E1.false=103,E2.begin=104E2.true=104E2.false=105,E2.begin=102E2.true=104E2.false=103,105=105,E.begin=100E.true=100,104=104E.false=105,100:(j,a,b,1),101:(jump,0),102:(j,c,d,1),103:(jump,0),104:(j,e,f,1),105:(jump,0),102(j,c,d,104),105(jump,103),101(jum

31、p,102),104(j,e,f,100),最终结果：100：(j,a,b,1)101：(jump,102)102：(j,c,d,104)103：(jump,0)104：(j,e,f,100)105：(jump,103)“真”链首E.true104,“假”链首E.false105。,8.4.3 控制结构的翻译,以if 语句，while语句为例说明控制语句的翻译方法,S if E then Sif语句|if E then S else Sif语句|while E do Swhile语句|begin L end 复合语句|A赋值语句A id:=EL L;S语句序列|S 语句,条件转移语句的共同特点

32、是：根据布尔表达式取值，分别执行不同的语句序列。问题：不同的语句序列结束后，如何使控制转向语句的结束。例如：if E1 then if E2 then S1 else S2 else S3,参照布尔表达式的翻译方法，对非终结符S(和L)，设立语义变量S.CHAIN（和L.CHAIN），用于记住需要在翻译完S(L)后回填转移目标的一串四元式,1.代码结构,2文法的改写原因：在自下而上的语法制导翻译中，语义动作的执行是在使用产生式进行归约之后，并不允许在产生式的中间执行。为了能及时地执行语义动作（比如回填转移目标），需对源文法改写方法：在需要执行语义动作的地方把产生式分段，引入新的非终结符来表示它

33、需要改写的产生式：,把 Sif E then S1改写成Cif E then(回填E.true)SC S1,把 Sif E then S1 else S2改写成Cif E then(回填E.true)TpC S1 else(产生转移，回填E.false)STp S2,把 Swhile E do S3 改写成 Wwhile(记住入口)WdW E do(回填E.true)S Wd S3,把 LL;S改写成LsL;(回填前一语句的出口)LLs S,改写后的文法(1)S C S1(2)S Tp S2 S Wd S3(4)S begin L end S A(6)L Ls S L S C if E the

34、n Tp C S1 else W while Wd W E do Ls L;,源文法：S if E then SS if E then S else SS while E do SS begin L end S AL L;SL S,(8)(1),(8)(9)(2),(10)(11)(3),(4),(5),(12)(6),(7),3安排语义动作,Wwhile,W.codebegin:nextstat,例：翻译语句 while AB do if CD then X:Y+Z 设nextstat=100,Wd.begin=100Wd.chain=101,W.begin=100,E1.begin=100

35、E1.true=100E1.false=101,S3.chain=103,E2.begin=102E2.true=102E2.false=103,S1.chain=0（空链）,S.chain=101,C.chain=103,106(jump,100),while AB do if CD then X:Y+Z 的最终翻译结果为：100(j,A,B,102)101(jump,0)102(j,C,D,104)103(jump,100)104(,Y,Z,t1)105(:,t1,X)106(jump,100)S.CHAIN101,while AB do if CD then X:Y+Z 的翻译过程：(1

36、)把while归为W，记住while语句的入口为100(2)把AB归为E1，产生：100(j,A,B,0)E1.true100101(jump,0)E1.false101(3)把W E do归为Wd，回填E1.true 得到 100(j,A,B,102)Wd.CHAINE1.false101(4)把CD归为E2，产生：102(j,C,D,0)E2.true102103(jump,0)E2.false103,(5)把if E2 then 归为C，回填E2.true得 102(j,C,D,104)C.CHAINE2.false103(6)把X:Y+Z归为S1，产生：104(,Y,Z,t1)105(

37、:,t1,X)S1.CHAIN0(7)把C S1归为S2，S2.CHAINmerge(103,0)103(8)把Wd S2归为S，回填S2.CHAIN得 103(jump,100)产生四元式 106(jump,100)S.CHAIN:Wd.CHIAN101,8.4.4 简单说明语句的翻译,说明语句的作用：定义各种形式的有名实体，如常量、变量、数组、记录、过程、子程序等说明语句种类：变量说明，常量说明，类型说明，过程说明等说明语句的翻译：简单说明语句的翻译不产生中间代码，编译程序把说明语句中定义的名字和属性登记在符号表中，用以检查名字的引用和说明是否一致,符号表,符号表及其作用符号表(Symbo

38、l Table)符号表是存放标识符信息的一种表，其中的信息表示的是标识符的属性(语义)。符号表的作用符号表是连接声明与引用的桥梁。一个名字在声明时，相关信息被填写进符号表，而在引用时，根据符号表中的信息生成相应的可执行语句。它的作用主要有：辅助语义的正确性检查辅助代码生成,符号表的设计如何有效记录各类符号的属性，以便在编译的各个阶段对符号表进行快速、有效的查找、插入、修改、删除等操作，是符号表设计的基本目标。符号表的组成表项分两部分，其中前者是标识符的名字（或在名表中的地址），而后者是属性部分（不同种类的标识符属性不同）。符号表的组织方式和查找方法符号表的组织方式可以是数组也可以是链表等等，查

39、找算法可以是顺序查表法、平分查表法、散列查表法等合理的组织和查找，将使得符号表的操作更高效,过程的说明部分：CONST A=35,B=49;VAR C,D,E;PROCEDURE P;VAR G,TABLE表中的信息,变量相对本过程基地址的偏移量,符号表的生存期在编译过程中，每当遇到标识符时，就要查填符号表：若是新的标识符时，就向符号表中填入一个新的表项；否则，根据情况向符号表中的已有表项增填信息（如填入分析的存储地址）或者查获信息（如进行语义检查等）符号表的信息将在词法分析、语法分析的过程中陆续填入，将用于语义检查、产生中间代码以及生成目标代码等不同的阶段。,1简单说明语句文法描述 D in

40、teger|real,id|id该文法描述了以integer和real定义的一串名字翻译目标把名字及类型信息填入符号表。,翻译中存在的问题：例:real A,B,第步归约A和第步归约B时，因未有类型信息而未能填入符号表只有当第步归约real后得到类型信息才能把所有名字及类型信息一起填入符号表为此必须用队列（或栈）来保存归约出的名字,2.文法的改写,改写后文法：D integer id|real id|D,id句子real A,B的规范归约过程如下：,在第步归约类型real和A，即可把名字A和类型填入符号表在第步归约B时，利用已知类型信息便可把名字B和类型一起填入符号表不需要另设队列（或栈）。,

41、3语义动作,用到的语义变量和过程：用语义变量D.ATT记录D的性质（int还是real）用过程enter(id,ATT)把名字id和性质ATT填入符号表改写后的说明语句的语义动作：,(1)D integer identer(id,int);D.ATT:int(2)D real id enter(id,real);D.ATT:real(3)D Dl,id enter(id,D1.ATT);D.ATT:Dl.ATT,8.5 自上向下的语法制导翻译,自上向下语法制导翻译的最大优点是：可根据需要在产生式右部的任何位置上调用语义动作，属性的计算更直接、方便递归下降法和LL(1)分析法的易实现性使自顶向下

42、的语法制导翻译法更受欢迎。,8.5.1 递归下降的语法制导翻译,对递归下降子程序的主要修改涉及：递归子程序可以设计为函数，用于返回必要的属性适当设计子程序中的临时变量，用于保存属性值；将语义动作嵌入在子程序的适当位置，正确计算属性值，并能产生一定的四元式,例：id:=|repeat until,function S(TOKEN):pointer;begin case TOKEN of id:begin GETNEXT(TOKEN);if TOKEN:=then ERROR;GETNEXT(TOKEN);E.place:=AE(TOKEN);P:=lookup(id.name);if p nil

43、 then emit(:=,E.place,-,p)else ERROR;S.CHAIN:=0;return(S.CHAIN)end;,repeat:beginR.codebegin:=nextstat;GETNEXT(TOKEN);S1.CHAIN:=S(TOKEN);if TOKEN until then ERROR;backpatch(S1.CHAIN,nextstat);GETNEXT(TOKEN);(BE.ture,BE.false):=BE(TOKEN);backpatch(BE.false,R.codebegin);S.CHAIN:=BE.ture;return(S.CHAIN)

44、;endend case;end;,i:=|repeat until,8.5.2 LL(1)语法制导翻译,基本思想：LL(1)分析法是让产生式右部逐个文法符号与输入串匹配，每当一个文法符号获得匹配，就可以执行语义动作。实现办法：预先在源文法中的相应位置上嵌入语义动作符，当语法分析到达该位置时，调用与该动作符相应的语义动作。带有动作符的文法称为动作文法（Action Grammar）,例：文法:L D L|D a|bL代表的由a和b组成的串或空串,要构造的是这样一个语义处理器，它将输入L串并将其中b的个数打印出来。,动作文法：L D L L OutD a D b Add,动作符Add和Out对应

45、的动作子程序分别如下：Add:S:=S+1Out:Print(S),LL(1)语法制导翻译的实现途径控制程序增加识别动作符和调用语义动作的功能；每当动作符成为栈顶符号时，就执行相应的语义子程序 语义值的保存：增加语义栈。自顶向下的分析栈中的文法符号是待匹配的符号(无语义值)，一旦匹配(获得语义值)则弹出。因此用于保存语义值的语义栈必须单独操作。,输入符号串“bab”，LL(1)分析法实现上述动作文法的过程如下：,动作,产生式,剩余输入,分析栈,步骤,14,13,12,11,10,9,8,7,例：while 语句的动作文法和语义子程序S while w1 E w2 do S1 w3,w2：/*E

46、匹配后，E.ture在栈顶，E.false在次栈顶*/pop E.ture;backpatch(E.ture,nextstat);,w1：/*记住入口位置*/W.codebegin:=nextstat;push W.codebegin;,w3：/*S1匹配后，S1.CHAIN在栈顶*/pop S1.CHAIN;pop E.false;pop W.codebegin;backpatch(S1.CHAIN,W.codebegin);emit(jump,-,-,W.codebegin);S.CHAIN:=E.false;push S.CHAIN;,S while w1 E w2 do S1 w3,本章小结属性文法和语法制导翻译：简单赋值语句的翻译布尔表达式的翻译控制结构的翻译简单说明语句的翻译,