zys-13编译原理kj-5

1、2022年3月7日星期一版权所有 勿复制传播 1主讲 周有顺(适用于2013级计算机本科软件工程专业)2022年3月7日星期一版权所有 勿复制传播 2第五讲 语义分析与中间代码产生 属性文法属性文法(G,V,F)(G,V,F)、语法制导翻译与语义子程序的设计语法制导翻译与语义子程序的设计2022年3月7日星期一版权所有 勿复制传播 3一、 语义分析与属性文法二、 语法制导翻译法与中间代码产生三、 典型执行语句语义子程序设计选四、 典型说明语句语义子程序设计选*五、 自上而下语法分析中的制导翻译2022年3月7日星期一版权所有 勿复制传播 4 通过本章的学习，不仅可以了解编译程序的语义分析子程序

2、的构造和设计方法，并且可以学习到很多编程思想及技术。如：动态与静态问题的处理方法、局部与整体关系的统一、高级语言各种语句符号语义的还原方法、无一不让人惊讶，真正让人体会到软件设计中的智慧等。因此，学好本章，对提高大家的程序设计能力，开拓思维，增加自信心都将会起到不可低估的作用。2022年3月7日星期一版权所有 勿复制传播 5一、语义分析与属性文法引子：程序设计语言的语义 静态语义和动态语义： 静态语义 是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则。它可以分为类型规则和作用域/可见性规则两大类。如：类型相容性变量先声明后引用、名称相关要求等。 动态语义 程序单

3、位描述的计算 编译程序的语义处理工作（语义分析）： 静态语义审查 解释执行动态语义 即（计算）生成代码2022年3月7日星期一版权所有 勿复制传播 6语义的形式化-语义建模 文法模型 - 属性文法例如：表达式文法 ET+T| T or TTn | b 属性文法： ET1 + T2 T1.type := int ；T2.type := T1.type ；E.type := int E T1 or T2 T1.type := bool ；T2.type := T1.type ；E.type := bool T n T.type := int T b T.type := bool 2022年3月7日

4、星期一版权所有 勿复制传播 7属性文法和语法制导翻译方法 虽然形式语义学 (如指称语义学、公理语义学、操作语义学等)的研究已取得了许多重大的进展，但目前在实际应用中比较流行的语义描述和语义处理的方法主要还是属性文法和语法制导翻译方法 属性文法的定义： 属性文法(attribute grammar)是一个三元组： A=(G,V,F) 其中：G 是一个上下文无关文法。 V 有穷的属性集，每个属性与文法的一个终结符或非终结符相连，这些属性代表与文法符号相关信息，如：它的类型、值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。属性加工的过程即是语义处理

5、的过程。 F 关于属性的属性断言或一组属性的计算规则（称为语义规则）。断言或语义规则与一个产生式相联，只引用该产生式左端或断言或语义规则与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。右端的终结符或非终结符相联的属性。2022年3月7日星期一版权所有 勿复制传播 8属性文法中的语义规则F 产生式 语义规则 L E Print(E.val) E E1+T E.val:=E1.val+T.val E T E.val:=T.val T T1*F T.val:=T1.val*F.val T F T.val:=F.val F (E) F.val:=E.val Fdigit F.v

6、al:=digit.lexval 设表达式为35+4，则语义动作打印数值19。产生式 语义规则设表达式为35+4，则语义动作打印数值19。2022年3月7日星期一版权所有 勿复制传播 9例子：（我们只考虑中间代码的产生）产生式 语义规则 (语义动作或称属性计算规则) 语义动作子程序（LR分析归约时制导翻译）L E Print(E.val) gen(Print , E.val , , ) E E1+T E.val:=E1.val+T.val newtemp(Temp)； gen (+ , E1.val , T.val , Temp )； E.val:= TempE T E.val:=T.val

7、E.val:=T.valT T1*F T.val:=T1.val*F.val newtemp(Temp)； gen (* , T1.val , F.val , Temp )；T.val:= TempT F T.val:=F.val T.val:=F.valF (E) F.val:=E.val F.val:=E.valF digit F.val:=digit.lexval F.val:=Entry(digit)2022年3月7日星期一版权所有 勿复制传播 10二、 语法制导翻译法与中间代码产生语法制导翻译方法语义动作或翻译子程序 方法：语法制导下的翻译即为每一个产生式配上一个语义子程序(语义动作

8、翻译子程序），在语法分析的同时（自上而下-匹配；自下而上-归约）执行这些语义子程序，从而产生中间代码。 如：产生式 E E(1) + E(2) 配上 产生（ + ，E(1) , E(2) ,T ）的语义子程序。2022年3月7日星期一版权所有 勿复制传播 11中间代码形式 四元式： （ op , A , B , Z ） 如：A:=B*(C+D) 翻译成 （+，C，D，T1） （*，B，T1，T2） （:=，T2， ，A）考察一个实例： 文法： SA:=E EE+E|E*E|(E)|-E|i 语义：赋值语句，简单算术表达式 目标结构： （op，E，A）; 和（OP，E(1)，E(2)，T）;20

9、22年3月7日星期一版权所有 勿复制传播 12考察一个实例： 文法： SA:=E EE+E|E*E|(E)|-E|i 语义：赋值语句，简单算术表达式 目标结构： （op，E，A）; 和（OP，E(1)，E(2)，T）; 语义子程序： 语法分析与产生中间代码的过程： 注意：在编写语义子程序的过程中，会产生改写原文法来达到适应目标设计的需要的问题。因为先归约再执行语义子程序，这样要一些文法符号的语义值（变量如E.PLACE），要保证执行语义子程序时能拿到栈中正确的当前值。 2022年3月7日星期一版权所有 勿复制传播 13三、 典型执行语句语义子程序设计选讲布尔表达式的翻译文法： EEE|EE|E

10、|（E）|i rop i| i rop | |语义： 1 求值；（如A:=E） 2 作为控制语句执行的条件 （如 if E then S(1) else S(2) ）目标结构：-设计成一系列的转移指令。 对一个布尔变量i: q (JNZ，真的时候的转移位置E.TC) q+1 (J，假的时候的转移位置E.FC) 我们可以把真假转移位置（出口）作为文法符号的语义值。记为：E.TC、E.FC 考察产生式： E E(1) E(2)2022年3月7日星期一版权所有 勿复制传播 14改写文法： 当用产生式： E E(1) E(2) 归约时，E(2)目标（中间代码）的第一条位置已经不知道了！ 因此当分析到逻

11、辑加时要停下来（E E(1) |E(2)），即把文法改写成： E(0) E(1) E E(0)E(2) 2022年3月7日星期一版权所有 勿复制传播 15语义子程序：(用NXQ指示将要存放四元式的位置)2022年3月7日星期一版权所有 勿复制传播 16控制语句的翻译P.186188分情形语句的翻译P.189复合语句的翻译略！2022年3月7日星期一版权所有 勿复制传播 17四、 典型说明语句语义子程序设计选讲P.1962022022年3月7日星期一版权所有 勿复制传播 18*五、 自上而下语法分析中的制导翻译略！2022年3月7日星期一版权所有 勿复制传播 19第五讲 复习题 一、什么是属性文法？有哪两类属性？ 二、 语义分析包含的内容有哪些? 三、 设计语义规则的方法怎么样? 编写语义子程序的步骤主要有哪些？四、 为什么有些设计之前要文法改造? 为什么要进行目标结构的设计？ 五、 什么叫属性断言? 举例说明? 六、 掌握布尔表达式、循环、复合语句的语义子程序设计方法？ 它们的文法属性断言如何下（既文法如何改造）？ 七、 实习题：请为自己前面设计的LL分析器改造成语法制导翻译系统。2022年3月7日星期一版权所有