sun编译原理第5章语法制导翻译技术和中间代码生成(第19-21讲).ppt

《sun编译原理第5章语法制导翻译技术和中间代码生成(第19-21讲).ppt》由会员分享，可在线阅读，更多相关《sun编译原理第5章语法制导翻译技术和中间代码生成(第19-21讲).ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成5.1 概述概述语义分析的任务语义分析的任务语义分析的任务语义分析的任务首先编译程序审查每个语法结构的静态语义，如首先编译程序审查每个语法结构的静态语义，如果静态语义正确，再生成中间代码。果静态语义正确，再生成中间代码。词法分析：分析的预备阶段，输出是词法分析：分析的预备阶段，输出是单词符号序列单词符号序列；语法分析：分析的主要阶段，输出是语法分析：分析的主要阶段，输出是语法树语法树。但这样还不能完全确定源程序的正确性，也没有获得但这样还不能完全确定源程序的正确性，也没有获得翻译时所需的所有信息。翻译时所需的所有信息。注意：

2、有的编译程序不生成中间代码而直接生注意：有的编译程序不生成中间代码而直接生成实际的目标代码。成实际的目标代码。11/27/20221信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成5.2 属性文法属性文法词法规则的描述工具：词法规则的描述工具：语法规则的描述工具：语法规则的描述工具：语义规则的常用描述工具：语义规则的常用描述工具：属性文法属性文法正规文法或正规式正规文法或正规式上下文无关文法上下文无关文法属性属性属性属性是编程语言结构的任意特性，如：是编程语言结构的任意特性，如：是编程语言结构的任意特性，如：是编程语言结构的任意特性，如：v变量

3、的数据类型变量的数据类型变量的数据类型变量的数据类型v表达式的值表达式的值表达式的值表达式的值v存储器中变量的位置存储器中变量的位置存储器中变量的位置存储器中变量的位置v程序的目标代码程序的目标代码程序的目标代码程序的目标代码v数的有效位数数的有效位数数的有效位数数的有效位数基本概念基本概念基本概念基本概念X.aX.aX.aX.a是是是是与与与与X X X X关关关关联联联联的的的的a a a a的的的的值值值值 (X(X(X(X 是是是是一一一一个个个个文文文文法法法法符符符符号号号号，a a a a 是是是是 X X X X的的的的一一一一个个个个属属属属性性性性)。如如如如：X.type

4、(XX.type(XX.type(XX.type(X的的的的类类类类型型型型)、X.place(XX.place(XX.place(XX.place(X的的的的 存存存存 储储储储 位位位位 置置置置)、X.valX.valX.valX.val（X X X X的值）的值）的值）的值）11/27/20222信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成属性文法属性文法属性文法属性文法即：以语法分析为基础，对应文法的每个产生式，确定即：以语法分析为基础，对应文法的每个产生式，确定即：以语法分析为基础，对应文法的每个产生式，确定即：以语法分析为基础

5、，对应文法的每个产生式，确定相应的语义规则。相应的语义规则。相应的语义规则。相应的语义规则。属性文法是在上下文无关文法的基础上，允许每个文法属性文法是在上下文无关文法的基础上，允许每个文法属性文法是在上下文无关文法的基础上，允许每个文法属性文法是在上下文无关文法的基础上，允许每个文法符号符号符号符号X(X(X(X(终结符或非终结符终结符或非终结符终结符或非终结符终结符或非终结符)根据处理的需要，定义与根据处理的需要，定义与根据处理的需要，定义与根据处理的需要，定义与X X X X相相相相关联的属性。关联的属性。关联的属性。关联的属性。一个属性文法形式上定义为一个三元组一个属性文法形式上定义为一

6、个三元组一个属性文法形式上定义为一个三元组一个属性文法形式上定义为一个三元组AGAGAGAG，AG=(G,V,E)AG=(G,V,E)AG=(G,V,E)AG=(G,V,E)。其中。其中。其中。其中G G G G表示一个上下文无关文法；表示一个上下文无关文法；表示一个上下文无关文法；表示一个上下文无关文法；V V V V表表表表示属性的有穷集；示属性的有穷集；示属性的有穷集；示属性的有穷集；E E E E表示属性的断言或谓词的有穷集。表示属性的断言或谓词的有穷集。表示属性的断言或谓词的有穷集。表示属性的断言或谓词的有穷集。其中每个断言与文法某产生式相关联。其中每个断言与文法某产生式相关联。其中

7、每个断言与文法某产生式相关联。其中每个断言与文法某产生式相关联。例：例：例：例：E E E Em+nm+nm+nm+n，则与该产生式相关联的断言为：，则与该产生式相关联的断言为：，则与该产生式相关联的断言为：，则与该产生式相关联的断言为：E.valE.valE.valE.val=m.val+n.valm.val+n.valm.val+n.valm.val+n.val11/27/20223信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 文法规则文法规则文法规则文法规则语义规则语义规则语义规则语义规则 规则规则规则规则 11相关的属性等式相关的属

8、性等式相关的属性等式相关的属性等式.规则规则规则规则 nn相关的属性等式相关的属性等式相关的属性等式相关的属性等式属性文法属性文法属性文法属性文法一般地，将属性文法写成表格形式，每个文法规则一般地，将属性文法写成表格形式，每个文法规则用属性等式的集合或相应规则的语义规则列出。用属性等式的集合或相应规则的语义规则列出。注意：文法规则中同一产生式中某符号出现多次注意：文法规则中同一产生式中某符号出现多次必须使用下标进行必须使用下标进行区分区分。例：。例：number1number2digit11/27/20224信息学院信息学院孙丽云孙丽云 1)1)已知无符号数文法如下，请改写成已知无符号数文法如

9、下，请改写成已知无符号数文法如下，请改写成已知无符号数文法如下，请改写成值属性文法。值属性文法。值属性文法。值属性文法。numbernumbernumberdigit|digitnumberdigit|digitdigitdigit0|1|2|3|4|5|6|7|8|90|1|2|3|4|5|6|7|8|9 例如：例如：例如：例如：文法规则文法规则文法规则文法规则语义规则语义规则语义规则语义规则numbernumber1 1numbernumber2 2digitdigit numbernumber1 1.val.val=numbernumber2 2.val*10+digit.val.val

10、*10+digit.valnumbernumber digitdigitnumber.valnumber.val=digit.valdigit.valdigitdigit 00digit.valdigit.val=0=0digitdigit 11digit.valdigit.val=1=1digitdigit 22digit.valdigit.val=2=2digitdigit 33digit.valdigit.val=3=3digitdigit 44digit.valdigit.val=4=4digitdigit 55digit.valdigit.val=5=5digitdigit 66di

11、git.valdigit.val=6=6digitdigit 77digit.valdigit.val=7=7digitdigit 88digit.valdigit.val=8=8digitdigit 99digit.valdigit.val=9=9解解解解：11/27/20225信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成grammarrulegrammarrulesemanticrulessemanticrulesexpexp1 1 expexp2 2+termexp+termexp1 1.val=exp.val=exp2 2.val+

12、term.val.val+term.valexpexp1 1 expexp2 2-termexp-termexp1 1.val=exp.val=exp2 2.val-erm.val.val-erm.valexpexptermtermexp.valexp.val=term.valterm.valtermterm1 1 termterm2 2*factor*factor termterm1 1.val=term.val=term2 2.val*.val*factor.valfactor.val termterm factorfactorterm.valterm.val=factor.valfact

13、or.val factorfactor(exp)(exp)factor.valfactor.val=exp.valexp.val factorfactor numbernumberfactor.valfactor.val=number.valnumber.val 2)2)简单的整数算术表达式文法如下，请改写成值属性文法。简单的整数算术表达式文法如下，请改写成值属性文法。简单的整数算术表达式文法如下，请改写成值属性文法。简单的整数算术表达式文法如下，请改写成值属性文法。expexpexp+term|exp-term|termexp+term|exp-term|termtermtermterm*f

14、actor|factorterm*factor|factorfactorfactor(exp)|number(exp)|number解解解解：11/27/20226信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成1.1.简单的整数算术表达式文法如下，请改写成简单的整数算术表达式文法如下，请改写成值属性文法。值属性文法。E E E+T|T E+T|T T T T*F|F T*F|FF F (E)|I(E)|I2.2.已知无符号数文法如下，请改写成值属性已知无符号数文法如下，请改写成值属性文法。文法。N NND|DND|D D D0|1|2|3|4

15、|5|6|70|1|2|3|4|5|6|7|8|9|8|9练习练习练习练习11/27/20227信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成使用属性文法来计算属性值，即把属性等式转化成计算规则使用属性文法来计算属性值，即把属性等式转化成计算规则使用属性文法来计算属性值，即把属性等式转化成计算规则使用属性文法来计算属性值，即把属性等式转化成计算规则可用依赖图（或称相关图）来决定属性值的计算顺序。可用依赖图（或称相关图）来决定属性值的计算顺序。属性的计算属性的计算属性的计算属性的计算关键：如何决定属性值的计算顺序关键：如何决定属性值的计算顺序关

16、键：如何决定属性值的计算顺序关键：如何决定属性值的计算顺序例例例例：属性等式：属性等式：属性等式：属性等式numbernumber1 1.val=number.val=number2 2.val*10+digit.val.val*10+digit.val则，文法规则则，文法规则则，文法规则则，文法规则numbernumber1 1numbernumber2 2digitdigit的依赖图：的依赖图：的依赖图：的依赖图：numbernumber2 2.valvalnumbernumber1 1.valvaldigit.valdigit.val11/27/20228信息学院信息学院孙丽云孙丽云第第

17、5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成例例例例:已知无符号数属性文法已知无符号数属性文法已知无符号数属性文法已知无符号数属性文法,请画出属性等式及请画出属性等式及请画出属性等式及请画出属性等式及345345的依赖图。的依赖图。的依赖图。的依赖图。grammarrulegrammarrulesemanticrulessemanticrulesnumbernumber1 1numbernumber2 2digitdigit numbernumber1 1.val=number.val=number2 2.val*10+digit.val*10+digit.valvaln

18、umbernumber digitdigitnumber.valnumber.val=digit.valdigit.val解解解解：(1)(1)属性等式属性等式属性等式属性等式numbernumber1 1.val=.val=numbernumber2 2.val*10+digit.val.val*10+digit.val文法规则文法规则文法规则文法规则numbernumber1 1numbernumber2 2digitdigit的依赖图：的依赖图：的依赖图：的依赖图：numbernumber2 2.valvalnumbernumber1 1.valvaldigit.valdigit.val

19、(2)(2)属性等式属性等式属性等式属性等式number.valnumber.val=digit.valdigit.val文法规则文法规则文法规则文法规则numbernumberdigitdigit的依赖图：的依赖图：的依赖图：的依赖图：numbernumber .valvaldigit.valdigit.val11/27/20229信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成所以字符串所以字符串所以字符串所以字符串345345对应的语法树对应的语法树对应的语法树对应的语法树的依赖图：的依赖图：的依赖图：的依赖图：number.valnum

20、ber.valnumber.valnumber.valdigit.valdigit.valnumber.valnumber.valdigit.valdigit.valdigit.valdigit.val依赖图以属性等式为最小结构单位。一个文法依赖图以属性等式为最小结构单位。一个文法的依赖图就是全部属性等式依赖图的总和。的依赖图就是全部属性等式依赖图的总和。11/27/202210信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成例例例例2:2:已知无符号数属性文法，请画出属性等式及已知无符号数属性文法，请画出属性等式及已知无符号数属性文法，请画出

21、属性等式及已知无符号数属性文法，请画出属性等式及floatx,yfloatx,y的依赖图。的依赖图。的依赖图。的依赖图。grammarrulegrammarrulesemanticrulessemanticrulesdecldecltypetype varvar-list-listvar-list.dtypevar-list.dtype=type.dtypetype.dtypetypetypeintinttype.dtypetype.dtype=integer=integertypetypefloatfloattype.dtypetype.dtype=real=realvar-listvar-

22、list1 1id,var-listid,var-list22id.dtypeid.dtype=var-list=var-list1 1.dtype.dtypevar-listvar-list2 2.dtype=var-list.dtype=var-list1 1.dtype.dtypevar-listvar-listididid.dtypeid.dtype=var-list.dtypevar-list.dtype解解解解：属性等式：属性等式：属性等式：属性等式id.dtypeid.dtype=var-list=var-list1 1.dtype.dtypevar-listvar-list2

23、2.dtype=var-list.dtype=var-list1 1.dtype.dtype文法规则文法规则文法规则文法规则var-listvar-list1 1id,var-listid,var-list2 2的依赖图：的依赖图：的依赖图：的依赖图：id.dtypeid.dtypevar-listvar-list1 1.dtype.dtypevar-listvar-list2 2.dtype.dtype11/27/202211信息学院信息学院孙丽云孙丽云属性等式属性等式属性等式属性等式id.dtypeid.dtype=var-list.dtypevar-list.dtype文法规则文法规则文

24、法规则文法规则var-listvar-listidid的依赖图：的依赖图：的依赖图：的依赖图：id.dtypeid.dtypevar-list.dtypevar-list.dtype属性等式属性等式属性等式属性等式var-list.dtypevar-list.dtype=type.dtypetype.dtype文法规则文法规则文法规则文法规则decldecltypetype varvar-list-list的依赖图：的依赖图：的依赖图：的依赖图：typetype.dtypedtypedecldecl var-listvar-list.dtypedtype字符串字符串字符串字符串floatx,y

25、floatx,y的依赖图：的依赖图：的依赖图：的依赖图：typetype.dtypedtypefloat float id id.dtypedtype(x)(x)decldecl var-listvar-list.dtypedtypevarvar-list-list.dtypedtypeid id.dtypedtype(y)(y)，11/27/202212信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成typetype(dtypedtype=real)=real)float float idid(x)(x)(dtypedtype=real)=r

26、eal)decldecl varvar-list-list(dtypedtype=real)=real)varvar-list-list(dtypedtype=real)=real)idid(y)(y)(dtypedtype=real)=real)，依据依赖图，利用依据依赖图，利用依据依赖图，利用依据依赖图，利用拓扑排序算法拓扑排序算法拓扑排序算法拓扑排序算法，可按顺序计算出，可按顺序计算出，可按顺序计算出，可按顺序计算出字符串字符串字符串字符串floatfloatx,yx,y中各属性的值中各属性的值中各属性的值中各属性的值字符串字符串字符串字符串floatx,yfloatx,y的依赖图：的依

27、赖图：的依赖图：的依赖图：typetype.dtypedtypefloat float id id.dtypedtype(x)(x)decldecl var-listvar-list.dtypedtypevarvar-list-list.dtypedtypeid id.dtypedtype(y)(y)，11/27/202213信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成属性分为两类：属性分为两类：属性分为两类：属性分为两类：1.1.合成属性（或称综合属性）合成属性（或称综合属性）合成属性（或称综合属性）合成属性（或称综合属性）2.2.继承属

28、性继承属性继承属性继承属性属性的分类属性的分类属性的分类属性的分类1.1.一个属性是合成的，如果在语法树中它所有的相关一个属性是合成的，如果在语法树中它所有的相关一个属性是合成的，如果在语法树中它所有的相关一个属性是合成的，如果在语法树中它所有的相关都从子节点指向父节点。都从子节点指向父节点。都从子节点指向父节点。都从子节点指向父节点。number.valnumber.valnumber.valnumber.valdigit.valdigit.valnumber.valnumber.valdigit.valdigit.valdigit.valdigit.val例：例：11/27/202214信

29、息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成2.2.一个属性如果不是合成的，则称作继承属性。一个属性如果不是合成的，则称作继承属性。一个属性如果不是合成的，则称作继承属性。一个属性如果不是合成的，则称作继承属性。继承属性依赖的两种基本种类继承属性依赖的两种基本种类继承属性依赖的两种基本种类继承属性依赖的两种基本种类a a A Aa aa aB BC CA Aa aa aB BC C从祖先到子孙的从祖先到子孙的从祖先到子孙的从祖先到子孙的继承继承继承继承 同属之间的继承同属之间的继承同属之间的继承同属之间的继承 属性的分类属性的分类属性的分类属

30、性的分类typetype.dtypedtypefloat float id id.dtypedtype(x)(x)decldecl var-listvar-list.dtypedtypevarvar-list-list.dtypedtypeid id.dtypedtype(y)(y)，例：例：11/27/202215信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成5.3 语法制导翻译概述语法制导翻译概述语义分析阶段的语义分析阶段的2个主要任务：个主要任务：1、分析语言的含义；、分析语言的含义；2、用一种中间代码将这种含义描述出来。、用一种中间代

31、码将这种含义描述出来。目前常用过的语义分析方法：语法制导翻译法。目前常用过的语义分析方法：语法制导翻译法。所谓所谓语法制导翻译法语法制导翻译法就是在语法分析过程中，随着就是在语法分析过程中，随着分析的逐步进展，根据相应文法的每一规则所对应分析的逐步进展，根据相应文法的每一规则所对应的语义子程序进行翻译的方法。的语义子程序进行翻译的方法。语法制导翻译法可分为自下向上语法制导翻译和语法制导翻译法可分为自下向上语法制导翻译和自上向下语法制导翻译。自上向下语法制导翻译。11/27/202216信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成 语法分析时

32、属性的计算语法分析时属性的计算语法分析时属性的计算语法分析时属性的计算每步每步归约归约时，计算相应的属性值时，计算相应的属性值;在分析栈中使用在分析栈中使用一个一个附加的域附加的域来存放综合属性值来存放综合属性值例：例：例：例：对对对对3*4+53*4+5进行进行进行进行LRLR分析的过程进行属性值的计算：分析的过程进行属性值的计算：分析的过程进行属性值的计算：分析的过程进行属性值的计算：EEE+E|EE+E|EE|EE|E*E|(E)|numberE|(E)|number 语法规则语法规则语法规则语法规则语义规则语义规则语义规则语义规则E E1 1E E2 2+E+E3 3EE1 1.val

33、=E.val=E2 2.val+E.val+E3 3.val.valE E1 1E E2 2-E-E3 3EE1 1.val=E.val=E2 2.val-E.val-E3 3.val.valE E1 1E E2 2*E*E3 3EE1 1.val=E.val=E2 2.val*E.val*E3 3.val.valE E1 1(E(E2 2)E)E1 1.val=E.val=E2 2.val.valE EnumbernumberE.valE.val=number.valnumber.val解解解解：11/27/202217信息学院信息学院孙丽云孙丽云例：例：例：例：对对对对3*4+53*4+5

34、进行进行进行进行LRLR分析并进行属性值的计算：分析并进行属性值的计算：分析并进行属性值的计算：分析并进行属性值的计算：EEE+E|EE+E|EE|EE|E*E|(E)|numberE|(E)|number 解解解解：grammarrulegrammarrulesemanticrulessemanticrulesE E1 1E E2 2+E+E3 3EE1 1.val=E.val=E2 2.val+E.val+E3 3.val.valE E1 1E E2 2-E-E3 3EE1 1.val=E.val=E2 2.val-E.val-E3 3.val.valE E1 1E E2 2*E*E3 3

35、EE1 1.val=E.val=E2 2.val*E.val*E3 3.val.valE E1 1(E(E2 2)E)E1 1.val=E.val=E2 2.val.valE EnumbernumberE.valE.val=number.valnumber.valParsingstackinputparsingactionvaluestacksemanticactionParsingstackinputparsingactionvaluestacksemanticaction1 1$3*4+5$3*4+5$ShiftShift$2 2$n$n*4+5$*4+5$ReduceEReduceEn

36、n$n$nE.valE.val=n.valn.val3 3$E$E*4+5$*4+5$ShiftShift$3$34 4$E*$E*4+5$4+5$ShiftShift$3*$3*5 5$E*n$E*n+5$+5$ReduceEReduceEn n$3*n$3*nE.valE.val=n.valn.val6 6$E*E$E*E+5$+5$ReduceEReduceEE*EE*E$3*4$3*4E1.val=E2.val*E3.valE1.val=E2.val*E3.val7 7$E$E+5$+5$ShiftShift$12$12 8 8$E+$E+5$5$ShiftShift$12+$12+9

37、 9$E+n$E+n$ReduceEReduceEn n$12+n$12+nE.valE.val=n.valn.val1010$E+E$E+E$ReduceEReduceEE+EE+E$12+5$12+5E1.val=E2.val+E3.valE1.val=E2.val+E3.val1111$E$E$17$1711/27/202218信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成例：已知无符号数文法如下，请改写成例：已知无符号数文法如下，请改写成例：已知无符号数文法如下，请改写成例：已知无符号数文法如下，请改写成值属性文法值属性文法值属性文法

38、值属性文法，并对，并对，并对，并对345345进行语义分析。进行语义分析。进行语义分析。进行语义分析。numbernumbernumberdigit|digitnumberdigit|digitdigitdigit0|1|2|3|4|5|6|7|8|90|1|2|3|4|5|6|7|8|9文法规则文法规则文法规则文法规则语义规则语义规则语义规则语义规则number1number2digitnumberdigitdigit0digit1digit8digit9numbernumber1 1.val=number.val=number2 2.val*10+digit.val.val*10+digi

39、t.valnumber.val=digit.valdigit.val=0digit.val=1digit.val=8digit.val=911/27/202219信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成numbernumber(valval=3*10+4=34)=3*10+4=34)numbernumber(valval=3)=3)digitdigit(valval=4)=4)numbernumber(valval=34*10+5=345)=34*10+5=345)digitdigit(valval=5)=5)digitdigit(va

40、lval=3)=3)3 34 45 5语法树表示语法树表示语法树表示语法树表示345345的属性等式的计算的属性等式的计算的属性等式的计算的属性等式的计算采用自底向上的语法分析采用自底向上的语法分析采用自底向上的语法分析采用自底向上的语法分析11/27/202220信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成例：例：例：例：已知简单的整数算术表达式文法如下，请改写已知简单的整数算术表达式文法如下，请改写已知简单的整数算术表达式文法如下，请改写已知简单的整数算术表达式文法如下，请改写成值属性文法，并对成值属性文法，并对成值属性文法，并对成值属

41、性文法，并对(34-3)*42(34-3)*42进行语义分析。进行语义分析。进行语义分析。进行语义分析。expexpexp+term|exp-term|termexp+term|exp-term|termtermtermterm*factor|factorterm*factor|factorfactorfactor(exp)|number(exp)|numbergrammarrulegrammarrulesemanticrulessemanticrulesexpexp1 1 expexp2 2+termexp+termexp1 1.val=exp.val=exp2 2.val+term.val

42、.val+term.valexpexp1 1 expexp2 2-termexp-termexp1 1.val=exp.val=exp2 2.val-erm.val.val-erm.valexpexptermtermexp.valexp.val=term.valterm.valtermterm1 1 termterm2 2*factor*factor termterm1 1.val=term.val=term2 2.val*.val*factor.valfactor.val termterm factorfactorterm.valterm.val=factor.valfactor.val f

43、actorfactor(exp)(exp)factor.valfactor.val=exp.valexp.val factorfactor numbernumberfactor.valfactor.val=number.valnumber.val解解解解：11/27/202221信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成termterm(valval=31)=31)factorfactor(valval=31)=31)termterm(valval=31*42=1302)=31*42=1302)factorfactor(valval=42

44、)=42)expexp(valval=34-3=31)=34-3=31)-(numbernumber(valval=42)=42)theparsetree(34-3)*42theparsetree(34-3)*42expexp(valval=1302)=1302)*expexp(valval=34)=34)termterm(valval=34)=34)factorfactor(valval=34)=34)termterm(valval=3)=3)factorfactor(valval=3)=3)numbernumber(valval=3)=3)numbernumber(valval=34)=3

45、4)11/27/202222信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成语法制导翻译举例语法制导翻译举例语法制导翻译举例语法制导翻译举例1、有一属性文法为：、有一属性文法为：（1）P bQbbQbprint:”1”print:”1”（2 2）QQ cRcRprint:”2”print:”2”（3 3）QQa aprint:”3”print:”3”（4 4）RR QadQadprint:”4”print:”4”输入串为输入串为输入串为输入串为bccaadadbbccaadadb，且采用自底向上语法分析方法时，则输，且采用自底向上语法分析方法时

46、，则输，且采用自底向上语法分析方法时，则输，且采用自底向上语法分析方法时，则输出序列是？出序列是？出序列是？出序列是？2、试给出下列文法的适合自下而上翻译的语义动作，使得当输、试给出下列文法的适合自下而上翻译的语义动作，使得当输入串是入串是aacbb时，其输出串是时，其输出串是12020。（1）AaB（2）Ac（3）BAb342421print:”1”print:”2”print:”0”11/27/202223信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成词法规则的描述工具：词法规则的描述工具：语法规则的描述工具：语法规则的描述工具：语义规则

47、的常用描述工具：语义规则的常用描述工具：属性文法属性文法正规文法或正规式正规文法或正规式上下文无关文法上下文无关文法小结小结小结小结属性文法是在上下文无关文法的基础上，允许每属性文法是在上下文无关文法的基础上，允许每个文法符号个文法符号X(X(终结符或非终结符终结符或非终结符)根据处理的需根据处理的需要，定义与要，定义与X X相关联的属性。相关联的属性。一般地，将属性文法写成表格形式，每个文法规一般地，将属性文法写成表格形式，每个文法规则用属性等式的集合或相应规则的语义规则列出。则用属性等式的集合或相应规则的语义规则列出。11/27/202224信息学院信息学院孙丽云孙丽云第第5章章语法制导翻

48、译技术和中间代码生成语法制导翻译技术和中间代码生成例：例：简单简单表达式文法表达式文法：EE+E|EE|E*E|(E)|number语法规则语法规则语义规则语义规则E1E2+E3E1.val=E2.val+E3.valE1E2-E3E1.val=E2.val-E3.valE1E2*E3E1.val=E2.val*E3.valE1(E2)E1.val=E2.valEnumberE.val=number.val该文法对应的属性文法为：该文法对应的属性文法为：11/27/202225信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成小结小结小结小结属性

49、分为两类：属性分为两类：1.1.合成属性（或称综合属性）合成属性（或称综合属性）2.2.继承属性继承属性目前常用过的语义分析方法目前常用过的语义分析方法语法制导语法制导翻译法：在语法分析过程中，随着分析的翻译法：在语法分析过程中，随着分析的逐步进展，根据相应文法的每一规则所对逐步进展，根据相应文法的每一规则所对应的语义子程序进行翻译的方法。应的语义子程序进行翻译的方法。11/27/202226信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成语法制导翻译举例语法制导翻译举例语法制导翻译举例语法制导翻译举例有一属性文法为：有一属性文法为：（1）Pb

50、Qbprint:”1”（2）QcRprint:”2”（3）Qaprint:”3”（4）RQadprint:”4”输入串为输入串为bab，且采用自底向上语法分析方法时，且采用自底向上语法分析方法时，则输出序列是？则输出序列是？3111/27/202227信息学院信息学院孙丽云孙丽云第第5章章语法制导翻译技术和中间代码生成语法制导翻译技术和中间代码生成例：例：利用下列属性文法对利用下列属性文法对(3+6)*9进行语义分析。进行语义分析。语法规则语法规则语义规则语义规则E1E2+E3E1.val=E2.val+E3.valE1E2-E3E1.val=E2.val-E3.valE1E2*E3E1.va