《第8章语法制导翻译和中间代码4学时.ppt》由会员分享，可在线阅读，更多相关《第8章语法制导翻译和中间代码4学时.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第8章语法制导翻译章语法制导翻译和中间代码和中间代码4学时学时现在学习的是第1页，共38页8.1 8.1 属性文法属性文法预备知识预备知识n源程序与目标程序，源程序与目标程序，语法结构完全不同语法结构完全不同，但语义相同，所以，但语义相同，所以表达的结果完全相同表达的结果完全相同。n语义分析的语义分析的2种处理方法：种处理方法：1）语法分析之后，直接调用相应的）语法分析之后，直接调用相应的“语义子程序语义子程序”进行语义进行语义处理处理2）语法分析之后，先生成）语法分析之后，先生成“语法树语法树”或其他形式，再进行语义或其他形式，再进行语义处理处理n语义分析的处理结果：语义分析的处理结果：1
2、）目标代码）目标代码2）中间代码：复杂性介于源程序语言和机器语言之间）中间代码：复杂性介于源程序语言和机器语言之间现在学习的是第2页，共38页n静态语义分析：审查语法结构的静态语义静态语义分析：审查语法结构的静态语义 确定标识符的数据类型确定标识符的数据类型 类型检查和转换类型检查和转换：检查运算对象的数据类型是否合法，：检查运算对象的数据类型是否合法，必要时进行类型转换必要时进行类型转换 一致性检查一致性检查：一个对象只能被声明一次：一个对象只能被声明一次 作用域检查作用域检查 控制流检查控制流检查：控制语句转到合法的地方继续执行：控制语句转到合法的地方继续执行n翻译翻译（若静态语义分析正确
3、后才翻译）（若静态语义分析正确后才翻译）语义处理的任务和功能语义处理的任务和功能 现在学习的是第3页，共38页常用的语义分析方法常用的语义分析方法语法制导翻译语法制导翻译语法制导翻译：语法制导翻译：n首先，使用首先，使用属性文法属性文法为工具，描述程序设计语言的语义规为工具，描述程序设计语言的语义规则。则。n在语法分析时，每应用一个产生式（推导或归约），同时在语法分析时，每应用一个产生式（推导或归约），同时完成该产生式上所附的语义规则描述的动作，从而完成语完成该产生式上所附的语义规则描述的动作，从而完成语义处理。义处理。语义分析的方法语义分析的方法 现在学习的是第4页，共38页n用于描述语义规
4、则的文法。用于描述语义规则的文法。n对文法的对文法的每个符号引入一些属性每个符号引入一些属性，这些，这些属性代表与文法符号相关的信息，例如：属性代表与文法符号相关的信息，例如：类型、值、代码序列、符号表内容等。类型、值、代码序列、符号表内容等。n属性属性值值可以在语法分析过程中进行可以在语法分析过程中进行计算计算和传递和传递。n属性的加工过程就是语义的处理过程。属性的加工过程就是语义的处理过程。属性文法属性文法(attribute grammar)attribute grammar)现在学习的是第5页，共38页n属性文法的组成：属性文法的组成：一个一个上下文无关文法上下文无关文法 一系列一系列
5、语义规则语义规则（附在文法的每个产生式上）（附在文法的每个产生式上）n属性文法的形式：三元组属性文法的形式：三元组 A=(G,V,F)A=(G,V,F)G G:是一个是一个上下文无关文法上下文无关文法V V:有穷有穷属性集属性集,每个属性与文法的一个终结符每个属性与文法的一个终结符或非终结符关联或非终结符关联F F:关于属性的关于属性的断言或谓词集断言或谓词集.每个断言与一个每个断言与一个产生式关联产生式关联.而此断言只引用该产生式的终结而此断言只引用该产生式的终结符或非终结符相关联的属性符或非终结符相关联的属性属性文法属性文法(attribute grammar)attribute gram
6、mar)现在学习的是第6页，共38页属性文法属性文法 举例举例例例1 1 说明语句中各种变量的类型信息的语义规则：说明语句中各种变量的类型信息的语义规则：产生式产生式语义规则语义规则(1)(1)D DTLTL(2)(2)T Tcharchar(3)(3)T Tintint(4)(4)T Tfloatfloat(5)(5)L LL L1 1,id,id(6)(6)L Lidid L.in:=T.type L.in:=T.type T.type:=char T.type:=char T.type:=int T.type:=int T.type:=float T.type:=float L L1 1
7、.in:=L.in.in:=L.in addtype(id.entry,L.in)addtype(id.entry,L.in)addtype(id.entry,L.in)addtype(id.entry,L.in)现在学习的是第7页，共38页属性文法属性文法 举例举例例例2 2 表达式表达式类型检查类型检查和和求值求值的语义规则：的语义规则：假设：类型不同的两个变量进行运算则语义错误。假设：类型不同的两个变量进行运算则语义错误。产生式产生式语义规则语义规则(1)(1)L LE E(2)(2)E EE E1 1+T+T(3)(3)E ET T(4)(4)T TT T1 1*F*F(5)(5)T
8、TF F(6)(6)F F(E)(E)(7)(7)F Fidid print(E.val);print(E.val);if(Eif(E1 1.type=T.type).type=T.type)E.type:=EE.type:=E1 1.type;.type;E.val:=EE.val:=E1 1.val+T.val;.val+T.val;else error();else error();E.type:=T.type;E.val:=T.val E.type:=T.type;E.val:=T.val getType(F.type,id.entry);getType(F.type,id.entry
9、);F.val:=id.lexval;F.val:=id.lexval;现在学习的是第8页，共38页语法制导翻译的语法制导翻译的实质实质：根据每个产生式所对应的语义规则，随语法分析的每一步根据每个产生式所对应的语义规则，随语法分析的每一步（推导或归约），执行相应的语义动作。（推导或归约），执行相应的语义动作。语法制导翻译的语法制导翻译的过程过程：1)对单词符号串进行语法分析，构造语法分析树；对单词符号串进行语法分析，构造语法分析树；2)然后根据需要构造属性依赖图，遍历语法树，并在语法然后根据需要构造属性依赖图，遍历语法树，并在语法树的各结点处按语义规则进行计算。树的各结点处按语义规则进行计算。
10、8.2 8.2 语法制导翻译概论语法制导翻译概论现在学习的是第9页，共38页使用使用“依赖图依赖图”，从依赖图的拓扑排序中得到计算语义规则的顺，从依赖图的拓扑排序中得到计算语义规则的顺序，再依照顺序对输入串进行语义分析序，再依照顺序对输入串进行语义分析。n依赖图依赖图一个有向图，用于描述分析树中的属性和属性之间的一个有向图，用于描述分析树中的属性和属性之间的相互依赖关系。相互依赖关系。构造依赖图举例：参见构造依赖图举例：参见P172图图8.4属性计算方法属性计算方法树遍历树遍历：事先建立语法树，（深度优先）遍历直至：事先建立语法树，（深度优先）遍历直至计算出所有属性值。计算出所有属性值。一遍扫
11、描一遍扫描：在语法分析的同时计算属性值。：在语法分析的同时计算属性值。计算语义规则计算语义规则现在学习的是第10页，共38页n属性：属性：综合属性综合属性：可以在分析输入串的同时，可以在分析输入串的同时，自下而上自下而上地来计地来计算。如：算。如：val继承属性继承属性：一个结点的继承属性值是由此结点的父一个结点的继承属性值是由此结点的父结点和（或）兄弟结点的某些属性来决定的。如：结点和（或）兄弟结点的某些属性来决定的。如：L.inn属性文法：属性文法：S-S-属性属性文法文法：L-属性文法的一个特例属性文法的一个特例L-L-属性文法属性文法：例例1 1就是一个就是一个L-属性文法属性文法n属
12、性文法的计算：属性文法的计算：可以是普通意义上的数学运可以是普通意义上的数学运算，也可以是打印输出等动作。算，也可以是打印输出等动作。属性文法的类型和计算属性文法的类型和计算现在学习的是第11页，共38页S-属性文法属性文法：是是L-属性文法的一个特例，只含有综合属性文法的一个特例，只含有综合属性。例属性。例2 2是一个是一个S-属性文法。属性文法。S-属性文法翻译器属性文法翻译器：可以借助可以借助LR分析器实现。分析器实现。实现原理实现原理：LR分析器中增加一个栈（分析器中增加一个栈（语义值栈语义值栈）用来）用来存存放综合属性的值放综合属性的值，进行归约的同时，栈中正在归约的产，进行归约的同
13、时，栈中正在归约的产生式右部符号的综合属性值弹栈，并调用相应语义子生式右部符号的综合属性值弹栈，并调用相应语义子程序进行相应计算（完成属性文法中的语义规则），程序进行相应计算（完成属性文法中的语义规则），产生的新值入语义值栈。产生的新值入语义值栈。举例：举例：参见参见P174图图8.78.7S-S-属性文法和属性文法和自下而上自下而上翻译翻译现在学习的是第12页，共38页L-属性文法属性文法：对于对于文法中的每个产生文法中的每个产生式式AX1X2Xn，其每个语义规则中其每个语义规则中的每个属性要么是综合属性，要么是的每个属性要么是综合属性，要么是Xj(1jn)的一个继承属性且该继承属性的一个继
14、承属性且该继承属性仅依赖于：产生式中仅依赖于：产生式中X1,X2,Xj-1的属的属性和性和A的继承属性。的继承属性。L-属性文法优点：属性文法优点：允许一次遍历就计允许一次遍历就计算出所有属性值。算出所有属性值。L-L-属性文法属性文法现在学习的是第13页，共38页L-属性文法翻译器属性文法翻译器：可以借助可以借助LL分析器实现。分析器实现。实现原理实现原理：在自顶向下分析的过程中，每应用一在自顶向下分析的过程中，每应用一个产生式进行推导，同时完成该产生式上属性文个产生式进行推导，同时完成该产生式上属性文法的计算。法的计算。LL(1)分析方法的语义描述：分析方法的语义描述：语义动作不是附在语义
15、动作不是附在产生式右部的末尾，而是嵌在两个符号之间。产生式右部的末尾，而是嵌在两个符号之间。这样的语义描述称为这样的语义描述称为翻译模式翻译模式。举例：举例：P174例例8.3例例8.4L-L-属性文法在属性文法在自上而下自上而下分析中的实现分析中的实现现在学习的是第14页，共38页翻译模式翻译模式：语义动作不是附在产生式语义动作不是附在产生式右部的末尾，而是嵌在两个符号之间。右部的末尾，而是嵌在两个符号之间。翻译模式是适合语法知道翻译的另一翻译模式是适合语法知道翻译的另一种描述形式。种描述形式。翻译模式给出了使用语义规则进行计翻译模式给出了使用语义规则进行计算的次序，可把某些实现细节表现出算
16、的次序，可把某些实现细节表现出来。来。翻译模式翻译模式现在学习的是第15页，共38页何时将属性文法改写成翻译模式？何时将属性文法改写成翻译模式？消除左递归时，原属性文法将被改成翻译消除左递归时，原属性文法将被改成翻译模式。模式。如何将属性文法改写成翻译模式？如何将属性文法改写成翻译模式？原文法：原文法：AA1YA.a=g(A1.a,Y.y)AXA.a=f(X.x)翻译模式：翻译模式：AXR.i=f(X.x)RA.a=R.s RYR1.i=g(R.i,Y.y)R1 R.s=R1.s RR.s=R.i改写成翻译模式改写成翻译模式现在学习的是第16页，共38页L-属性文法属性文法中，如何实现中，如何
17、实现自下而上自下而上计计算继承属性？算继承属性？方法方法1：去掉翻译模式中嵌入在产生式中：去掉翻译模式中嵌入在产生式中间的动作。间的动作。方法方法2：改变原文法或：改变原文法或重新构造文法，重新构造文法，用用综合属性代替继承属性。综合属性代替继承属性。自学（自学（P176,177）L-L-属性文法在属性文法在自下而上自下而上分析中的实现分析中的实现现在学习的是第17页，共38页8.3 8.3 中间代码的形式中间代码的形式中间代码的常见形式：中间代码的常见形式：逆波兰记号逆波兰记号三元式三元式树形表示树形表示四元式四元式现在学习的是第18页，共38页逆波兰记号（后缀式）逆波兰记号（后缀式）特点：
18、特点：将运算对象写在前面，把运算符号写在后面将运算对象写在前面，把运算符号写在后面标识符顺序与表达式中的一致标识符顺序与表达式中的一致 运算符顺序与计算顺序一致运算符顺序与计算顺序一致 无括号无括号 表达式表达式逆波兰式逆波兰式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+=n 为什么要使用逆波兰式？为什么要使用逆波兰式？更易于计算机处理，表示简洁、计算方便。更易于计算机处理，表示简洁、计算方便。现在学习的是第19页，共38页 逆波兰记号的扩充用途逆波兰记号的扩充用途i-iGotoLLjumpifEthenS1elseS2ES1S2￥AnmnmAsu
19、bsn 逆波兰式的复杂性：逆波兰式的复杂性：压栈的可能是地址（如变量赋值），不是值；压栈的可能是地址（如变量赋值），不是值；栈中不一定产生结果。栈中不一定产生结果。n 逆波兰式的计算机处理方法：逆波兰式的计算机处理方法：自左向右扫描逆波兰式，遇到运算对象入栈，遇到算符则自左向右扫描逆波兰式，遇到运算对象入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈。将相应数目的运算对象出栈计算后结果入栈。现在学习的是第20页，共38页三元式和树形表示三元式和树形表示n三元式的格式：三元式的格式：(算符算符,第一运算对象第一运算对象,第二运算对象第二运算对象)n如：如：a=b*c+b*d a=b*c+b
20、*d 的三元式和树形表示的三元式和树形表示(1)(1)(*,b,c)(*,b,c)(2)(2)(*,b,d)(*,b,d)(3)(3)(+,(1),(2)(+,(1),(2)(4)(4)(=,(3),a)(=,(3),a)=a+*bcbd现在学习的是第21页，共38页四元式四元式n四元式的格式：四元式的格式：(算符算符,第一运算对象第一运算对象,第二运算对象第二运算对象,结果结果)n如：如：a=b*c+b*d a=b*c+b*d 的四元式表示如下的四元式表示如下(*,a,b,t1)(*,b,d,t2)(+,t1,t2,t3)(:=,t3,-,a)t1:=a*bt2:=b*dt3:=t1+t2a
21、:=t3或或n特点：利于代码优化和目标代码生成特点：利于代码优化和目标代码生成 n特例：特例：goto Lgoto L 的四元式为的四元式为（jump,-,-,Ljump,-,-,L）if B rop C goto Lif B rop C goto L的四元式为的四元式为(jrop,B,C,L)(jrop,B,C,L)现在学习的是第22页，共38页8.4 8.4 简单赋值语句的翻译简单赋值语句的翻译说明：说明：1 1）id.nameid.name 表示表示idid所表示的单词，用作语义变量所表示的单词，用作语义变量2 2）lookup(id.name)lookup(id.name)审查审查id
22、.nameid.name是否出现在符号表是否出现在符号表是：返回指向该登录项的指针是：返回指向该登录项的指针否：返回否：返回 nilnil3 3）emitemit 将四元式输出到中间文件（或目标文件）上将四元式输出到中间文件（或目标文件）上4 4）newtempnewtemp 生成一临时变量生成一临时变量5 5）E.placeE.place 存放存放 E E值的变量名在符号表的登录项值的变量名在符号表的登录项 若变量为临时变量，则直接存放一整数码若变量为临时变量，则直接存放一整数码 现在学习的是第23页，共38页8.4 8.4 简单赋值语句的翻译简单赋值语句的翻译例例3 3 将将赋值语句翻译成
23、四元式赋值语句翻译成四元式的语义描述：的语义描述：(1)(1)S S id:=Eid:=E (2)(2)E E E E1 1+E E2 2(3)(3)E E E E1 1*E E2 2(4)(4)E E -E-E1 1(5)(5)E E (E(E1 1)(6)(6)E E idid现在学习的是第24页，共38页(1)Sid:=E P:=lookup(id.name);ifP nilthenemit(P,“:=”,E.place);elseerror();现在学习的是第25页，共38页(2)EE1+E2E.place:=newtemp;emit(E.place,“:=”,E1.place,“+”
24、,E2.place);(3)EE1*E2E.place:=newtemp;emit(E.place,“:=”,E1.place,“*”,E2.place);现在学习的是第26页，共38页(4)E-E1E.place=newtemp;emit(E.place,:=,-,E1.place);(5)E(E1)E.place=newtemp;emit(E.place,:=,E1.place);(6)Eidp:=lookup(id.name);if(p!=nil)E.place=p;elseerror();现在学习的是第27页，共38页8.5 8.5 布尔表达式的翻译布尔表达式的翻译1 1、布尔表达式的
25、作用：、布尔表达式的作用：计算逻辑值计算逻辑值 （返回真（返回真/假假 ）控制流语句中的条件表达式控制流语句中的条件表达式 if()thenwhile()2 2、布尔表达式的文法布尔表达式的文法EEandEEEorEEnotEEidropidEtrueEfalse现在学习的是第28页，共38页3 3、布尔表达式的计算方法：、布尔表达式的计算方法：一步一步计算出式中各部分真假，最终算出整个表一步一步计算出式中各部分真假，最终算出整个表达式的值达式的值采用优化措施，只计算部分表达式值即可采用优化措施，只计算部分表达式值即可例如：例如：aandb/a为为0时，时，b无论是什么表达式无论是什么表达式的
26、值都为的值都为0aorb/a为为1时，时，b无论是什么表达式无论是什么表达式的值都为的值都为18.5 布尔表达式的翻译布尔表达式的翻译现在学习的是第29页，共38页例如例如 a or b and not ca or b and not c 对应的四元式对应的四元式(1)(1)(not,c,-,t1)(not,c,-,t1)(2)(2)(and,b,t1,t2)(and,b,t1,t2)(3)(3)(or,a,t2,t3)(or,a,t2,t3)布尔表达式的翻译布尔表达式的翻译现在学习的是第30页，共38页(1)EnotE1E.true:=E1.false;E.codebegin:=E1.cod
27、ebegin;E.false:=E1.true;(2)EE1andE2backpatch(E1.true,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=E2.true;E.false:=merge(E1.false,E2.false);(3)EE1orE2backpatch(E1.false,E2.codebegin);E.codebegin:=E1.codebegin;E.true:=merge(E1.true,E2.true);E.false:=E2.false;布尔表达式译为四元式的语义描述：布尔表达式译为四元式的语义描述：现在学习的是第
28、31页，共38页(4)E(E1)E.true:=E1.true;E.codebegin:=E1.codebegin;E.false:=E1.false;(5)Eid1ropid2E.true:=nextstat;E.codebegin:=nextstat;E.false:=nextstat+1;emit(if,id1.place,rop,id2.place,goto,);emit(goto,-);(6)EidE.true:=nextstat;E.codebegin:=nextstat;E.false:=nextstat+1;emit(if,id1.place,goto,);emit(goto,
29、-);现在学习的是第32页，共38页控制语句控制语句 S S if E then Sif E then S1 1 else Selse S2 2 E.falseE的代码的代码 E.trueE.false:S2的代码的代码goto outE.true:S1的代码的代码out:控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译现在学习的是第33页，共38页举例举例 将下列控制语句翻译成将下列控制语句翻译成四元式四元式if ab or cf then S1 else S2if ab or cf then S1 else S2 控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译(1)(1)if a
30、b goto(i+1)if ab goto(i+1)/i+1/i+1是是S1S1的入口的入口(2)(2)if cd goto(4)if cf goto(i+1)if ef goto(i+1)(5)(5)关于关于S2S2的四元式的四元式(i)(i)goto(n)goto(n)/n/n是是S1S1的出口的出口(i+1)(i+1)关于关于S1S1的四元式的四元式(n)(n)现在学习的是第34页，共38页例例forI:=1step1untilNdoM:=M+I 对应的四元式对应的四元式 For循环语句的翻译循环语句的翻译(1)I:=1(2)goto(4)(3)I:=I+1(4)ifI=Ngoto(6)
31、(5)goto(9)(6)T:=M+I(7)M:=T(8)goto(3)(9)现在学习的是第35页，共38页 课堂练习课堂练习1(1)(2)(5)(6)(7)1(1)(2)(5)(6)(7)2 2 逆波兰式、三元式、四元式序列逆波兰式、三元式、四元式序列 3 3 5 5 6 6 7 7现在学习的是第36页，共38页 课后课后课后课后 1 1 1 1(1)a*(-b+c)(1)a*(-b+c)(1)a*(-b+c)(1)a*(-b+c)ababc+*c+*(2)(2)(2)(2)AAAA(C(CD)D)D)D)A A CDCDCDCD (5)-a+b*(-c+d)(5)-a+b*(-c+d)(5
32、)-a+b*(-c+d)(5)-a+b*(-c+d)a abcbcd+*+d+*+(6)(AB)(C(6)(AB)(C DE)DE)DE)DE)ABCDABCDABCDABCD EE(7)if(x+y)*z=0 then s:=(a+b)*c(7)if(x+y)*z=0 then s:=(a+b)*c(7)if(x+y)*z=0 then s:=(a+b)*c(7)if(x+y)*z=0 then s:=(a+b)*c else s:=a*b*celse s:=a*b*c现在学习的是第37页，共38页三元式序列三元式序列(1)(1)(+,(+,a,b)a,b)(2)(2)(-,(1),-)(-
33、,(1),-)(3)(3)(+,c,d)(+,c,d)(4)(4)(*,(2),(3)(*,(2),(3)(5)(5)(+,a,b)(+,a,b)(6)(6)(+,(5),c)(+,(5),c)(7)(7)(-,(4),(6)(-,(4),(6)课后课后课后课后 2 2 2 2 逆波兰式、三元式、四元式序列逆波兰式、三元式、四元式序列逆波兰式、三元式、四元式序列逆波兰式、三元式、四元式序列 逆波兰式：逆波兰式：ab+ab+cd+*ab+c+-cd+*ab+c+-四元式序列四元式序列(+,(+,a,b,t1)a,b,t1)t1:=a+bt1:=a+b(-,t1,-,t2)(-,t1,-,t2)t2:=-t1t2:=-t1(+,c,d,t3)(+,c,d,t3)t3:=c+dt3:=c+d(*,t2,t3,t4)(*,t2,t3,t4)t4:=t2*t3t4:=t2*t3(+,a,b,t5)(+,a,b,t5)t5:=a+bt5:=a+b(+,t5,c,t6)(+,t5,c,t6)t6:=t5+ct6:=t5+c(-,t4,t6,t7)(-,t4,t6,t7)t7:=t4-t6t7:=t4-t6现在学习的是第38页，共38页