《语法制导翻译和中间代码学时.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译和中间代码学时.ppt（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、语法制导翻译和中间语法制导翻译和中间代码学时代码学时现在学习的是第1页，共50页n8.1概述概述n8.2属性文法属性文法n8.3语法制导翻译语法制导翻译n8.4中间代码的形式中间代码的形式逆波兰式、三元式、树形表示、四元式逆波兰式、三元式、树形表示、四元式n8.5一些语句的翻译一些语句的翻译赋值语句赋值语句布尔表达式布尔表达式控制语句中的布尔表达式控制语句中的布尔表达式For循环语句循环语句n8.6数组的翻译数组的翻译现在学习的是第2页，共50页概述概述n程序设计语言的语义程序设计语言的语义静态语义静态语义是对程序约束的描述，这些约是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，
2、实束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分质上就是语法规则的良形式条件，它可以分为类型规则和作用域为类型规则和作用域/可见性规则两大类可见性规则两大类动态语义动态语义程序单位描述的计算程序单位描述的计算n编译程序的语义处理工作编译程序的语义处理工作静态语义审查静态语义审查解释解释执行动态语义（计算）生成代码执行动态语义（计算）生成代码.现在学习的是第3页，共50页语义处理语义处理n静态语义分析：审查语法结构的静态语义静态语义分析：审查语法结构的静态语义确定标识符的数据类型确定标识符的数据类型类型检查和转换类型检查和转换：检查运算对象的数据类型是：检查运算对象
3、的数据类型是否合法，必要时进行类型转换否合法，必要时进行类型转换一致性检查一致性检查：一个对象只能被声明一次：一个对象只能被声明一次作用域检查作用域检查控制流检查控制流检查：控制语句转到合法的地方继续执：控制语句转到合法的地方继续执行行n翻译（若静态语义分析正确后才翻译）翻译（若静态语义分析正确后才翻译）现在学习的是第4页，共50页概述概述n语义形式化语义形式化语义建模语义建模n文法模型文法模型属性文法属性文法n命令式或操作式模型命令式或操作式模型操作语义学操作语义学n应用式模型应用式模型指称语义学指称语义学n公理式模型公理式模型公理语义学公理语义学现在学习的是第5页，共50页属性文法属性文法
4、n表达式文法表达式文法ET+T|TorTTn|bnET1+T2nT1.type=intT2.type=T1.typeE.type:=intnET1orT2nT1.type=boolT2.type=T1.typenE.type:=boolnTnnT.type:=intnTbnT.type:=bool现在学习的是第6页，共50页操作语义学操作语义学n通过执行该段程序所改变的计算机状态来反映通过执行该段程序所改变的计算机状态来反映语义。语义。n包括变量的所有值，可执行程序本身，各种系统定包括变量的所有值，可执行程序本身，各种系统定义的内部数据结构。用一组形式定义的操作来说明义的内部数据结构。用一组形
5、式定义的操作来说明执行一条指令相应的状态怎样变化。执行一条指令相应的状态怎样变化。nFor(expr1;expr2;expr3)expr1;nLoop:ifexpr2=0gotooutn。nexpr3;ngotoloopnout:.现在学习的是第7页，共50页指称语义学指称语义学n基本概念是给每一段程序实体定义一个数学意义上的对象，基本概念是给每一段程序实体定义一个数学意义上的对象，和一个从实体实例向数学意义对象的映射的函数和一个从实体实例向数学意义对象的映射的函数n特点：不但对全部程序赋予全文而且对程序设计语法特点：不但对全部程序赋予全文而且对程序设计语法每一个语法成分短语（表达式，命令，声
6、明每一个语法成分短语（表达式，命令，声明）都给予含）都给予含义。义。n每一个语法成分（短语）的含义是以它的自身成分的每一个语法成分（短语）的含义是以它的自身成分的含义的术语来定义的。含义的术语来定义的。n语义函数：语义函数：程序设计语言的语义利用映射函数来证明。语义程序设计语言的语义利用映射函数来证明。语义函数将短语映射到它的指称。函数将短语映射到它的指称。现在学习的是第8页，共50页nValuation101表示把表示把Valuation施用于施用于101ValuationN-把它施用于把它施用于N定义:Valuation（用四个方程（用四个方程)因为有四个形式因为有四个形式numeralV
7、aluation0 0Valuation1 1ValuationN0 2 ValuationNValuationN1 2 ValuationN+1所以：Valuation110=2 Valuation11=2(2 Valuation1+1)=2(2 1+1)=6现在学习的是第9页，共50页公理语义学公理语义学n一个语言的每个语法成分的含义定义为公理和演绎一个语言的每个语法成分的含义定义为公理和演绎规则，用于推导出该成分执行的效果。规则，用于推导出该成分执行的效果。n公理语义概念是随着程序正确性的证明而发展的。公理语义概念是随着程序正确性的证明而发展的。当正确性证明能构造时表明程序执行它的规格说
8、当正确性证明能构造时表明程序执行它的规格说明所描述的计算。在一个证明中，每一个语句之明所描述的计算。在一个证明中，每一个语句之前之后都有一个逻辑表达式对程序的变量进行约前之后都有一个逻辑表达式对程序的变量进行约束束,以此说明这个语句的含义。以此说明这个语句的含义。n一般的记号一般的记号PSQn如果在语句如果在语句S执行前执行前P为真，则在语句为真，则在语句S执行并终止后执行并终止后Q为真。为真。现在学习的是第10页，共50页n演绎规则的例子演绎规则的例子n赋值：赋值：x:=exprP(expr)x:=exprP(x)nWhile:P BSPPwhileBdoSendP(notB)nif-the
9、n-elseB PS1Q,(notB)PS2QPifBthenS1elseS2Q现在学习的是第11页，共50页8.2 8.2 属性文法属性文法预备知识预备知识n源程序与目标程序，源程序与目标程序，语法结构完全不同语法结构完全不同，但语义相同，所，但语义相同，所以以表达的结果完全相同表达的结果完全相同。n语义分析的语义分析的2种处理方法：种处理方法：1）语法分析之后，直接调用相应的）语法分析之后，直接调用相应的“语义子程序语义子程序”进行语义处进行语义处理理2）语法分析之后，先生成）语法分析之后，先生成“语法树语法树”或其他形式，再进行语义处或其他形式，再进行语义处理理n语义分析的处理结果：语义
10、分析的处理结果：1）目标代码）目标代码2）中间代码：复杂性介于源程序语言和机器语言之间）中间代码：复杂性介于源程序语言和机器语言之间现在学习的是第12页，共50页常用的语义分析方法常用的语义分析方法语法制导翻译语法制导翻译语法制导翻译：语法制导翻译：n首先，使用首先，使用属性文法属性文法为工具，描述程序设计语言的语义为工具，描述程序设计语言的语义规则。规则。n在语法分析时，每应用一个产生式（推导或归约），同时在语法分析时，每应用一个产生式（推导或归约），同时完成该产生式上所附的语义规则描述的动作，从而完成语完成该产生式上所附的语义规则描述的动作，从而完成语义处理。义处理。语义分析的方法语义分析
11、的方法 现在学习的是第13页，共50页n用于描述语义规则的文法。用于描述语义规则的文法。n对文法的对文法的每个符号引入一些属性每个符号引入一些属性，这些，这些属性代表与文法符号相关的信息，例如：属性代表与文法符号相关的信息，例如：类型、值、代码序列、符号表内容等。类型、值、代码序列、符号表内容等。n属性属性值值可以在语法分析过程中进行可以在语法分析过程中进行计算计算和传递和传递。n属性的加工过程就是语义的处理过程。属性的加工过程就是语义的处理过程。属性文法属性文法(attribute grammar)(attribute grammar)现在学习的是第14页，共50页n属性文法的组成：属性文法
12、的组成：一个一个上下文无关文法上下文无关文法 一系列一系列语义规则语义规则（附在文法的每个产生式上）（附在文法的每个产生式上）n属性文法的形式：三元组属性文法的形式：三元组 A=(G,V,F)A=(G,V,F)G G:是一个是一个上下文无关文法上下文无关文法V V:有穷有穷属性集属性集,每个属性与文法的一个终结符每个属性与文法的一个终结符或非终结符关联或非终结符关联F F:关于属性的关于属性的断言或谓词集断言或谓词集.每个断言与一个每个断言与一个产生式关联产生式关联.而此断言只引用该产生式的终结而此断言只引用该产生式的终结符或非终结符相关联的属性符或非终结符相关联的属性属性文法属性文法(att
13、ribute grammar)(attribute grammar)现在学习的是第15页，共50页属性文法属性文法 举例举例例例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.t
14、ype:=float T.type:=float L L1 1.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)现在学习的是第16页，共50页属性文法属性文法 举例举例例例2 2 表达式表达式类型检查类型检查和和求值求值的语义规则：的语义规则：假设：类型不同的两个变量进行运算则语义错误。假设：类型不同的两个变量进行运算则语义错误。产生式产生式语义规则语义规则(1)(1)L LE E(2)(2)E EE E1 1+T+T(3)(3)E
15、 ET T(4)(4)T TT T1 1*F*F(5)(5)T 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,i
16、d.entry);getType(F.type,id.entry);F.val:=id.lexval;F.val:=id.lexval;现在学习的是第17页，共50页语法制导翻译的语法制导翻译的实质实质：根据每个产生式所对应的语义规则，随语法分析的每根据每个产生式所对应的语义规则，随语法分析的每一步（推导或归约），执行相应的语义动作。一步（推导或归约），执行相应的语义动作。语法制导翻译的语法制导翻译的过程过程：1)对单词符号串进行语法分析，构造语法分析树；对单词符号串进行语法分析，构造语法分析树；2)然后根据需要构造属性依赖图，遍历语法树，并在语法树然后根据需要构造属性依赖图，遍历语法树，并在
17、语法树的各结点处按语义规则进行计算。的各结点处按语义规则进行计算。8.3 8.3 语法制导翻译概论语法制导翻译概论现在学习的是第18页，共50页n属性：属性：综合属性综合属性：可以在分析输入串的同时，可以在分析输入串的同时，自自下而上下而上地来计算。如：地来计算。如：valval继承属性继承属性：一个结点的继承属性值是由此一个结点的继承属性值是由此结点的父结点和（或）兄弟结点的某些属结点的父结点和（或）兄弟结点的某些属性来决定的。如：性来决定的。如：L.inn属性文法的计算：属性文法的计算：可以是普通意义上可以是普通意义上的数学运算，也可以是打印输出等动的数学运算，也可以是打印输出等动作。作。
18、属性文法的类型和计算属性文法的类型和计算现在学习的是第19页，共50页设表达式为设表达式为35+4，则，则语义动作语义动作打印数值打印数值19.LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树的带注释的分析树现在学习的是第20页，共50页 DL.in=realL.in=realL.in=realT.type=realrealid2id1id3.Real id1,id2,id3，现在学习的是第21页，共50页语法
19、制导的翻译语法制导的翻译n一个一个翻译是符号串对的一个集合。在是符号串对的一个集合。在一个编译程序定义的翻译中，符号串一个编译程序定义的翻译中，符号串对是源程序和目标程序。各个编译阶对是源程序和目标程序。各个编译阶段定义一个翻译，词法分析：（字符段定义一个翻译，词法分析：（字符串，单词串）语法分析：（单词串，串，单词串）语法分析：（单词串，语法树）代码生成（语法树，汇编语语法树）代码生成（语法树，汇编语言）言）现在学习的是第22页，共50页 n把下述产生式定义的算术表达式映射到后缀波兰表示：把下述产生式定义的算术表达式映射到后缀波兰表示：EE+T E T T TF T F F(E)F a E=
20、ET+E=T T=TF T=F F=E F=a 产生式 翻译规则翻译规则现在学习的是第23页，共50页 n确定输入确定输入a+a a的输出：的输出：(E,E)(E+T,ET+)(T+T,TT+)(F+T,FT+)(a+T,aT+)(a+T F,aFF+)(a+F F,aFF+)(a+a F,aaF+)(a+a a,aaa+)现在学习的是第24页，共50页8.4 8.4 中间代码的形式中间代码的形式中间代码的常见形式：中间代码的常见形式：逆波兰记号逆波兰记号三元式三元式树形表示树形表示四元式四元式现在学习的是第25页，共50页逆波兰记号（后缀式）逆波兰记号（后缀式）特点：特点：将运算对象写在前面
21、，把运算符号写在后面将运算对象写在前面，把运算符号写在后面标识符顺序与表达式中的一致标识符顺序与表达式中的一致 运算符顺序与计算顺序一致运算符顺序与计算顺序一致 无括号无括号 表达式表达式逆波兰式逆波兰式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+=n 为什么要使用逆波兰式？为什么要使用逆波兰式？更易于计算机处理，表示简洁、计算方便。更易于计算机处理，表示简洁、计算方便。现在学习的是第26页，共50页n 逆波兰式的复杂性：逆波兰式的复杂性：压栈的可能是地址（如变量赋值），不是值；压栈的可能是地址（如变量赋值），不是值；栈中不一定产生结果。栈中不一定
22、产生结果。n 逆波兰式的计算机处理方法：逆波兰式的计算机处理方法：自左向右扫描逆波兰式，遇到运算对象入栈，遇到算符则自左向右扫描逆波兰式，遇到运算对象入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈。将相应数目的运算对象出栈计算后结果入栈。现在学习的是第27页，共50页三元式和树形表示三元式和树形表示n三元式的格式：三元式的格式：(算符算符,第一运算对象第一运算对象,第二运算对象第二运算对象)n如：如：a=b*c+b*d a=b*c+b*d 的三元式和树形表示的三元式和树形表示(1)(1)(*,b,c)(*,b,c)(2)(2)(*,b,d)(*,b,d)(3)(3)(+,(1),(2)
23、(+,(1),(2)(4)(4)(=,(3),a)(=,(3),a)=a+*bcbd现在学习的是第28页，共50页四元式四元式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:=t3或或n特点：利于代码优化和目标代码生成特点：利于代码优化和目标代码生成 n特例：特例：goto Lgoto L 的四元式为的四元式为（jump,-
24、,-,Ljump,-,-,L）if B rop C goto Lif B rop C goto L的四元式为的四元式为(jrop,B,C,L)(jrop,B,C,L)现在学习的是第29页，共50页8.5 8.5 简单语句的翻译简单语句的翻译说明：说明：1 1）id.nameid.name 表示表示idid所表示的单词，用作语义变量所表示的单词，用作语义变量2 2）lookup(id.name)lookup(id.name)审查审查id.nameid.name是否出现在符号表是否出现在符号表是：返回指向该登录项的指针是：返回指向该登录项的指针否：返回否：返回 nilnil3 3）emitemit
25、 将四元式输出到中间文件（或目标文件）上将四元式输出到中间文件（或目标文件）上4 4）newtempnewtemp 生成一临时变量生成一临时变量5 5）E.placeE.place 存放存放 E E值的变量名在符号表的登录项值的变量名在符号表的登录项 若变量为临时变量，则直接存放一整数码若变量为临时变量，则直接存放一整数码 现在学习的是第30页，共50页简单赋值语句的翻译简单赋值语句的翻译例例3 3 将将赋值语句翻译成四元式赋值语句翻译成四元式的语义描述：的语义描述：(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 E
26、2 2(4)(4)E E -E-E1 1(5)(5)E E (E(E1 1)(6)(6)E E idid现在学习的是第31页，共50页(1)Sid:=E P:=lookup(id.name);ifP nilthenemit(P,“:=”,E.place);elseerror();现在学习的是第32页，共50页(2)EE1+E2E.place:=newtemp;emit(E.place,“:=”,E1.place,“+”,E2.place);(3)EE1*E2E.place:=newtemp;emit(E.place,“:=”,E1.place,“*”,E2.place);现在学习的是第33页，
27、共50页(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();现在学习的是第34页，共50页布尔表达式的翻译布尔表达式的翻译1 1、布尔表达式的作用：、布尔表达式的作用：计算逻辑值计算逻辑值 （返回真（返回真/假假 ）控制流语句中的条件表达式控制流语句中的条件表达式 if()thenwhile()2 2、布尔表达式的文法布尔表达式的文法
28、EEandEEEorEEnotEEidropidEtrueEfalse现在学习的是第35页，共50页n3.计算布尔表达式通常采用两种方法:(1).如同计算算术表达式一样,一步步算 1 or(not 0 and 0)or 0 =1 or(1 and 0)or 0 =1 or 0 or 0 =1 or 0 =1(2).采用某种优化措施 把A or B解释成 if A then true else B 把A and B解释成 if A then B else false 把 A解释成 if A then false else true现在学习的是第36页，共50页例如例如 a or b and no
29、t 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)布尔表达式的翻译布尔表达式的翻译现在学习的是第37页，共50页 关于布尔表达式的数值表示法的翻译模式 n过程emit将三地址代码送到输出文件中nnextstat给出输出序列中下一条三地址语句的地址索引n每产生一条三地址语句后，过程emit便把nextstat加1 现在学习的是第38页，共50页 关于布尔表达式的数值表示法的翻译模式 EE1
30、 or E2 E.place:=newtemp;emit(E.place:=E 1.place or E2.place)EE1 and E2 E.place:=newtemp;emit(E.place:=E 1.place and E2.place)Enot E1 E.place:=newtemp;emit(E.place:=not E 1.place)E(E1)E.place:=E1.place现在学习的是第39页，共50页关于布尔表达式的数值表示法的翻译模式Eid1 relop id2 E.place:=newtemp;emit(if id1.place relop.op id2.plac
31、e goto nextstat+3);emit(E.place:=0);emit(goto nextstat+2);emit(E.place:=1)Eid E.place:=id.place ab翻译成翻译成100:ifabgoto103101:T:=0102:goto104103:T:=1104:现在学习的是第40页，共50页布尔表达式ab or cd and ef的翻译结果 100:if ab goto 103101:T1:=0102:goto 104103:T1:=1104:if cd goto 107105:T2:=0106:goto 108107:T2:=1108:if ec or
32、b c goto L2 “真”出口 goto L1L1:if bd goto L2 “真”出口 goto L3 “假”出口 L2:(关于S1的三地址代码序列)goto LnextL3:(关于S2的三地址代码序列)Lnext:现在学习的是第43页，共50页n每次调用函数newlabel后都返回一个新的符号标号n对于一个布尔表达式E，引用两个标号E.true是E为真时控制流转向的标号E.false是E为假时控制流转向的标号 现在学习的是第44页，共50页产生布尔表达式三地址代码的语义规则 产生式语义规则 EE1 or E2 E1.true:=E.true;E1.false:=newlabel;E2
33、.true:=E.true;E2.false:=E.false;E.code:=E1.code|gen(E1.false:)|E2.code E1.codeTo E.trueTo E1.falseE2.codeTo E.trueTo E.false现在学习的是第45页，共50页产生布尔表达式三地址代码的语义规则 产生式语义规则EE1 and E2 E1.true:=newlabel;E1.false:=E.false;E2.true:=E.true;E2.false:=E.fasle;E.code:=E1.code|gen(E1.true:)|E2.codeE1.codeTo E.falseT
34、o E1.trueE2.codeTo E.trueTo E.false现在学习的是第46页，共50页产生布尔表达式三地址代码的语义规则 产生式语义规则Enot E1 E1.true:=E.false;E1.false:=E.true;E.code:=E1.code E(E1)E1.true:=E.true;E1.false:=E.false;E.code:=E1.code现在学习的是第47页，共50页产生布尔表达式三地址代码的语义规则 产生式语义规则 Eid1 relop id2 E.code:=gen(if id1.place relop.op id2.place goto E.true)|gen(goto E.false)EtrueE.code:=gen(goto E.true)Efalse E.code:=gen(goto E.false)现在学习的是第48页，共50页考虑如下表达式：ab or cd and ef假定整个表达式的真假出口已分别置为Ltrue和Lfalse，则按定义将生成如下的代码：if ab goto Ltruegoto L1L1:if cd goto L2goto LfalseL2:if ef goto Ltruegoto Lfalse现在学习的是第49页，共50页8.6 数组的翻译数组的翻译现在学习的是第50页，共50页