《编译原理chapter8.ppt》由会员分享，可在线阅读，更多相关《编译原理chapter8.ppt（81页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、属性文法属性文法属性文法属性文法语法制导翻译概论语法制导翻译概论语法制导翻译概论语法制导翻译概论中间代码的形式中间代码的形式中间代码的形式中间代码的形式简单赋值语句的翻译简单赋值语句的翻译简单赋值语句的翻译简单赋值语句的翻译布尔表达式的翻译布尔表达式的翻译布尔表达式的翻译布尔表达式的翻译第八章第八章语法语法制导制导翻译翻译和和中间中间代码代码生成生成1 翻译程序翻译程序翻译程序翻译程序的的的的任务任务任务任务是把源程序翻译成目标程序，这个目是把源程序翻译成目标程序，这个目是把源程序翻译成目标程序，这个目是把源程序翻译成目标程序，这个目标程序必须和源程序的标程序必须和源程序的标程序必须和源程序的
2、标程序必须和源程序的语义等同语义等同语义等同语义等同。通常，在词法分析程。通常，在词法分析程。通常，在词法分析程。通常，在词法分析程序和语法分析程序对源程序的语法结构进行分析之后，序和语法分析程序对源程序的语法结构进行分析之后，序和语法分析程序对源程序的语法结构进行分析之后，序和语法分析程序对源程序的语法结构进行分析之后，要么由语法分析程序直接调用相应的语义子程序进行语要么由语法分析程序直接调用相应的语义子程序进行语要么由语法分析程序直接调用相应的语义子程序进行语要么由语法分析程序直接调用相应的语义子程序进行语义处理，要么首先生成语法树或该结构的某种表示，再义处理，要么首先生成语法树或该结构的
3、某种表示，再义处理，要么首先生成语法树或该结构的某种表示，再义处理，要么首先生成语法树或该结构的某种表示，再进行语义处理。进行语义处理。进行语义处理。进行语义处理。编译中的编译中的编译中的编译中的语义处理语义处理语义处理语义处理指指指指两个功能两个功能两个功能两个功能：第一是：第一是：第一是：第一是审查审查审查审查每个语法每个语法每个语法每个语法结构的结构的结构的结构的静态语义静态语义静态语义静态语义，即验证语法结构合法的程序是否真正，即验证语法结构合法的程序是否真正，即验证语法结构合法的程序是否真正，即验证语法结构合法的程序是否真正有意义（静态语义分析或静态审查）；第二是在静态语有意义（静态
4、语义分析或静态审查）；第二是在静态语有意义（静态语义分析或静态审查）；第二是在静态语有意义（静态语义分析或静态审查）；第二是在静态语义正确，语义处理要义正确，语义处理要义正确，语义处理要义正确，语义处理要执行真正的翻译执行真正的翻译执行真正的翻译执行真正的翻译，即要么生成程序，即要么生成程序，即要么生成程序，即要么生成程序的一种中间表示形式（中间代码），要么生成实际的目的一种中间表示形式（中间代码），要么生成实际的目的一种中间表示形式（中间代码），要么生成实际的目的一种中间表示形式（中间代码），要么生成实际的目标代码。标代码。标代码。标代码。2 有的编译程序直接生成有的编译程序直接生成有的编译
5、程序直接生成有的编译程序直接生成目标代码目标代码目标代码目标代码，有的编译程序采用，有的编译程序采用，有的编译程序采用，有的编译程序采用中间代码中间代码中间代码中间代码。中间代码也称。中间代码也称。中间代码也称。中间代码也称中间语言中间语言中间语言中间语言，是复杂性介于源程，是复杂性介于源程，是复杂性介于源程，是复杂性介于源程序语言和机器语言的序语言和机器语言的序语言和机器语言的序语言和机器语言的一种表示形式一种表示形式一种表示形式一种表示形式。一般，快速编译程。一般，快速编译程。一般，快速编译程。一般，快速编译程序直接生成目标代码，省掉了将中间代码翻译成目标代序直接生成目标代码，省掉了将中间
6、代码翻译成目标代序直接生成目标代码，省掉了将中间代码翻译成目标代序直接生成目标代码，省掉了将中间代码翻译成目标代码的额外开销。但为了使编译程序结构在逻辑上更为码的额外开销。但为了使编译程序结构在逻辑上更为码的额外开销。但为了使编译程序结构在逻辑上更为码的额外开销。但为了使编译程序结构在逻辑上更为简简简简单明确单明确单明确单明确，常采用中间代码，这样可将，常采用中间代码，这样可将，常采用中间代码，这样可将，常采用中间代码，这样可将与机器相关与机器相关与机器相关与机器相关的某些的某些的某些的某些实现实现实现实现细节细节细节细节置于代码生成阶段仔细处理，并且可以在中间置于代码生成阶段仔细处理，并且可
7、以在中间置于代码生成阶段仔细处理，并且可以在中间置于代码生成阶段仔细处理，并且可以在中间代码一级进行代码一级进行代码一级进行代码一级进行优化优化优化优化工作，使得代码优化比较容易实现。工作，使得代码优化比较容易实现。工作，使得代码优化比较容易实现。工作，使得代码优化比较容易实现。3 现在很多编译程序采用现在很多编译程序采用现在很多编译程序采用现在很多编译程序采用比较接近形式化比较接近形式化比较接近形式化比较接近形式化的的的的语法制语法制语法制语法制导翻译方法导翻译方法导翻译方法导翻译方法对对对对语义处理工作语义处理工作语义处理工作语义处理工作进行比较规范和抽象的进行比较规范和抽象的进行比较规范
8、和抽象的进行比较规范和抽象的描描描描述述述述。这种方法使用。这种方法使用。这种方法使用。这种方法使用属性文法属性文法属性文法属性文法为工具来说明程序设计语为工具来说明程序设计语为工具来说明程序设计语为工具来说明程序设计语言的言的言的言的语义语义语义语义。一个。一个。一个。一个属性文法属性文法属性文法属性文法包含一个上下文无关文法和包含一个上下文无关文法和包含一个上下文无关文法和包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每个产生一系列语义规则，这些语义规则附在文法的每个产生一系列语义规则，这些语义规则附在文法的每个产生一系列语义规则，这些语义规则附在文法的每个产生式上，所谓式
9、上，所谓式上，所谓式上，所谓语法制导翻译语法制导翻译语法制导翻译语法制导翻译是指在语法分析过程中，完是指在语法分析过程中，完是指在语法分析过程中，完是指在语法分析过程中，完成附加在所使用的产生式上的语义规则描述的动作，成附加在所使用的产生式上的语义规则描述的动作，成附加在所使用的产生式上的语义规则描述的动作，成附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。从而实现语义处理。从而实现语义处理。从而实现语义处理。属性文法属性文法4 属性属性属性属性常用来描述事物的特征等。对编译程序使用的常用来描述事物的特征等。对编译程序使用的常用来描述事物的特征等。对编译程序使用的常用来描述事物的
10、特征等。对编译程序使用的语法树语法树语法树语法树的结点的结点的结点的结点，可以用，可以用，可以用，可以用“类型类型类型类型”、“值值值值”或或或或“存储位置存储位置存储位置存储位置”等属性来等属性来等属性来等属性来描述。描述。描述。描述。形式上讲，一个形式上讲，一个形式上讲，一个形式上讲，一个属性文法属性文法属性文法属性文法是一个三元组是一个三元组是一个三元组是一个三元组A=(G,V,F)A=(G,V,F)：一个上一个上一个上一个上下文无关文法下文无关文法下文无关文法下文无关文法GG，一个属性的有穷集一个属性的有穷集一个属性的有穷集一个属性的有穷集V V，一个关于属性的断一个关于属性的断一个关
11、于属性的断一个关于属性的断言或谓词的有穷集言或谓词的有穷集言或谓词的有穷集言或谓词的有穷集F F。每个每个每个每个属性与属性与属性与属性与文法的某个文法的某个文法的某个文法的某个非终结符非终结符非终结符非终结符或或或或终终终终结符相联结符相联结符相联结符相联。每个。每个。每个。每个断言与断言与断言与断言与文法的某文法的某文法的某文法的某产生式相联产生式相联产生式相联产生式相联。如果对。如果对。如果对。如果对GG中的中的中的中的某一某一某一某一输入串输入串输入串输入串，A A中的所有中的所有中的所有中的所有断言断言断言断言对该输入串的语法树结点的对该输入串的语法树结点的对该输入串的语法树结点的对
12、该输入串的语法树结点的属属属属性性性性全为全为全为全为真真真真，则该串是，则该串是，则该串是，则该串是A A语言的语言的语言的语言的句子句子句子句子。编译程序的。编译程序的。编译程序的。编译程序的静态语义审静态语义审静态语义审静态语义审查工作查工作查工作查工作就是验证关于所编译的程序的断言是否全部为真。就是验证关于所编译的程序的断言是否全部为真。就是验证关于所编译的程序的断言是否全部为真。就是验证关于所编译的程序的断言是否全部为真。属性文法属性文法5 属性文法最早出自克努特笔下，他把属性文法最早出自克努特笔下，他把属性文法最早出自克努特笔下，他把属性文法最早出自克努特笔下，他把属性属性属性属性
13、分为两类：分为两类：分为两类：分为两类：继继继继承属性承属性承属性承属性和和和和综合属性综合属性综合属性综合属性。在分析树中，一个。在分析树中，一个。在分析树中，一个。在分析树中，一个结点的综合属性值结点的综合属性值结点的综合属性值结点的综合属性值是从其是从其是从其是从其子结点的属性值计算子结点的属性值计算子结点的属性值计算子结点的属性值计算出来的；而一个出来的；而一个出来的；而一个出来的；而一个结点的继承属结点的继承属结点的继承属结点的继承属性值性值性值性值是由该结点是由该结点是由该结点是由该结点兄弟结点和父结点的属性值计算兄弟结点和父结点的属性值计算兄弟结点和父结点的属性值计算兄弟结点和父
14、结点的属性值计算出来的。出来的。出来的。出来的。这里不对属性文法进行理论上的研究，仅将它作为工具描这里不对属性文法进行理论上的研究，仅将它作为工具描这里不对属性文法进行理论上的研究，仅将它作为工具描这里不对属性文法进行理论上的研究，仅将它作为工具描述语义分析。在编译的许多实际应用中，属性和断言以多述语义分析。在编译的许多实际应用中，属性和断言以多述语义分析。在编译的许多实际应用中，属性和断言以多述语义分析。在编译的许多实际应用中，属性和断言以多种形式出现，即与每个文法符号相联的可以是各种属性、种形式出现，即与每个文法符号相联的可以是各种属性、种形式出现，即与每个文法符号相联的可以是各种属性、种
15、形式出现，即与每个文法符号相联的可以是各种属性、断言、以及语义规则，或者某种程序设计语言的程序段等断言、以及语义规则，或者某种程序设计语言的程序段等断言、以及语义规则，或者某种程序设计语言的程序段等断言、以及语义规则，或者某种程序设计语言的程序段等等。等。等。等。属性文法属性文法6例例例例:有文法有文法有文法有文法GG：E-TE-T1 1+T+T2 2|T|T1 1orTorT2 2T-num|true|falseT-num|true|false对输入串对输入串对输入串对输入串3+43+4的的的的语法树语法树语法树语法树如图：如图：如图：如图：属性文法记号中常用属性文法记号中常用属性文法记号中
16、常用属性文法记号中常用N.tN.t的形式表示与的形式表示与的形式表示与的形式表示与非终结符非终结符非终结符非终结符N N相联的相联的相联的相联的属性属性属性属性t t。比如可把完成对上面表达式的比如可把完成对上面表达式的比如可把完成对上面表达式的比如可把完成对上面表达式的类型检查的属性文法类型检查的属性文法类型检查的属性文法类型检查的属性文法写成如下图形式。与每个非终结符写成如下图形式。与每个非终结符写成如下图形式。与每个非终结符写成如下图形式。与每个非终结符T T相联的有属性相联的有属性相联的有属性相联的有属性t t，t t要么要么要么要么是是是是intint,要么是要么是要么是要么是boo
17、lbool。与非终结符与非终结符与非终结符与非终结符E E的产生式相联的断言指明：的产生式相联的断言指明：的产生式相联的断言指明：的产生式相联的断言指明：两个两个两个两个T T的属性必须相同。下图是上面输入串的的属性必须相同。下图是上面输入串的的属性必须相同。下图是上面输入串的的属性必须相同。下图是上面输入串的语法树结点语法树结点语法树结点语法树结点带有语义信息的表示带有语义信息的表示带有语义信息的表示带有语义信息的表示。属性文法属性文法7 属性文法中，对应于属性文法中，对应于属性文法中，对应于属性文法中，对应于每个产生式每个产生式每个产生式每个产生式A-A-都都都都有一套有一套有一套有一套与
18、之相关联与之相关联与之相关联与之相关联的的的的语义规则语义规则语义规则语义规则，每条规则的形式为，每条规则的形式为，每条规则的形式为，每条规则的形式为b:=f(c1,c2,ck)b:=f(c1,c2,ck)。f f是一个是一个是一个是一个函数函数函数函数，b b和和和和c1,c2,ckc1,c2,ck是是是是该产生式文法符号的该产生式文法符号的该产生式文法符号的该产生式文法符号的属性属性属性属性。1 1）如果如果如果如果b b是是是是A A的一个属性，的一个属性，的一个属性，的一个属性，c1,c2,ckc1,c2,ck是产生式右部文法符号是产生式右部文法符号是产生式右部文法符号是产生式右部文法
19、符号的属性或的属性或的属性或的属性或A A的其他属性，则称的其他属性，则称的其他属性，则称的其他属性，则称b b是是是是A A的的的的综合属性综合属性综合属性综合属性。2 2）如果如果如果如果b b是产生式右部某个文法符号是产生式右部某个文法符号是产生式右部某个文法符号是产生式右部某个文法符号X X的一个属性，并且的一个属性，并且的一个属性，并且的一个属性，并且c1,c2,ckc1,c2,ck是是是是A A或产生式右边任何文法符号的属性，则称或产生式右边任何文法符号的属性，则称或产生式右边任何文法符号的属性，则称或产生式右边任何文法符号的属性，则称b b是是是是文法符号文法符号文法符号文法符号
20、X X的的的的继承属性继承属性继承属性继承属性。上述两种情况都说属性上述两种情况都说属性上述两种情况都说属性上述两种情况都说属性b b依赖于依赖于依赖于依赖于属性属性属性属性c1,c2,ckc1,c2,ck。注意：注意：注意：注意：1 1）非终结符非终结符非终结符非终结符既可有既可有既可有既可有综合属性综合属性综合属性综合属性也可有也可有也可有也可有继承属性继承属性继承属性继承属性，但文法，但文法，但文法，但文法开始符号没有继承属性开始符号没有继承属性开始符号没有继承属性开始符号没有继承属性；2 2）终结符终结符终结符终结符只有只有只有只有综合属性综合属性综合属性综合属性，它们由词，它们由词，
21、它们由词，它们由词法分析程序提供。法分析程序提供。法分析程序提供。法分析程序提供。8例例例例1 1：简单算术表达式求值的语义描述。：简单算术表达式求值的语义描述。：简单算术表达式求值的语义描述。：简单算术表达式求值的语义描述。产生式产生式产生式产生式语义规则语义规则语义规则语义规则0)L-E0)L-Eprint(E.valprint(E.val)1)E-E1+T1)E-E1+TE.valE.val:=E1.val+T.val:=E1.val+T.val2)E-T2)E-TE.valE.val:=:=T.valT.val3)T-T1*F3)T-T1*FT.valT.val:=T1.val*:=T
22、1.val*F.valF.val4)T-F4)T-FT.valT.val:=:=F.valF.val5)F-(E)5)F-(E)F.valF.val:=:=E.valE.val6)F-digit6)F-digitF.valF.val:=:=digit.lexvaldigit.lexval属性文法属性文法在该在该在该在该描述中，每个非终结符都有一个属性：一个整数值的描述中，每个非终结符都有一个属性：一个整数值的描述中，每个非终结符都有一个属性：一个整数值的描述中，每个非终结符都有一个属性：一个整数值的称作称作称作称作valval的属性。按照语义规则对每个产生式来说，它的左的属性。按照语义规则对每
23、个产生式来说，它的左的属性。按照语义规则对每个产生式来说，它的左的属性。按照语义规则对每个产生式来说，它的左部部部部E E、T T和和和和F F的属性值的计算来自它的右部的非终结符，这的属性值的计算来自它的右部的非终结符，这的属性值的计算来自它的右部的非终结符，这的属性值的计算来自它的右部的非终结符，这种属性称作种属性称作种属性称作种属性称作综合属性综合属性综合属性综合属性。单词。单词。单词。单词digitdigit仅有综合属性仅有综合属性仅有综合属性仅有综合属性，它的值是，它的值是，它的值是，它的值是由由由由词法分析程序提供词法分析程序提供词法分析程序提供词法分析程序提供的。和产生式的。和产
24、生式的。和产生式的。和产生式L-EL-E相联的语义规则是相联的语义规则是相联的语义规则是相联的语义规则是一个过程，打印一个过程，打印一个过程，打印一个过程，打印E E产生的表达式的值，可以理解为产生的表达式的值，可以理解为产生的表达式的值，可以理解为产生的表达式的值，可以理解为L L的属性的属性的属性的属性是空的或是虚的。是空的或是虚的。是空的或是虚的。是空的或是虚的。9例例例例2 2：描述说明语句中各种变量的类型信息的语义规则。：描述说明语句中各种变量的类型信息的语义规则。：描述说明语句中各种变量的类型信息的语义规则。：描述说明语句中各种变量的类型信息的语义规则。产生式产生式产生式产生式语义
25、规则语义规则语义规则语义规则0)D-TLL.in:=T.type0)D-TLL.in:=T.type1)T-1)T-intintT.type:=integerT.type:=integer2)T-realT.type:=real2)T-realT.type:=real3)L-L3)L-L1 1,idL,idL1 1.in:=L.in.in:=L.inaddtype(id.entry,L.inaddtype(id.entry,L.in)4)L-id4)L-idaddtype(id.entry,L.inaddtype(id.entry,L.in)注：例中与注：例中与注：例中与注：例中与L L产生式
26、相联的语义规则中有一过程调用，过产生式相联的语义规则中有一过程调用，过产生式相联的语义规则中有一过程调用，过产生式相联的语义规则中有一过程调用，过程程程程addtypeaddtype的功能是把每个标识符的类型信息登录在符号表的功能是把每个标识符的类型信息登录在符号表的功能是把每个标识符的类型信息登录在符号表的功能是把每个标识符的类型信息登录在符号表的相关项中。的相关项中。的相关项中。的相关项中。属性文法属性文法该文法定义了一种说明语句，该说明语句的形式是由该文法定义了一种说明语句，该说明语句的形式是由该文法定义了一种说明语句，该说明语句的形式是由该文法定义了一种说明语句，该说明语句的形式是由关
27、键字关键字关键字关键字intint或或或或realreal开头，后跟一标识符表，每个标识符间开头，后跟一标识符表，每个标识符间开头，后跟一标识符表，每个标识符间开头，后跟一标识符表，每个标识符间由逗号隔开。非终结符由逗号隔开。非终结符由逗号隔开。非终结符由逗号隔开。非终结符T T有一综合属性有一综合属性有一综合属性有一综合属性typetype，它的值由它的值由它的值由它的值由关键字决定关键字决定关键字决定关键字决定(intint或或或或real)real)。与产生式与产生式与产生式与产生式D-TLD-TL相联的语义相联的语义相联的语义相联的语义规则规则规则规则L.in:=T.typeL.in:
28、=T.type将将将将L.inL.in的属性值置为该说明语句指定的属性值置为该说明语句指定的属性值置为该说明语句指定的属性值置为该说明语句指定的类型。属性的类型。属性的类型。属性的类型。属性L.inL.in是继承属性，将被沿着语法树传递到是继承属性，将被沿着语法树传递到是继承属性，将被沿着语法树传递到是继承属性，将被沿着语法树传递到下边的结点使用，与下边的结点使用，与下边的结点使用，与下边的结点使用，与L L产生式相联的规则里使用了它。产生式相联的规则里使用了它。产生式相联的规则里使用了它。产生式相联的规则里使用了它。下图是句子下图是句子下图是句子下图是句子intintid1,id2id1,i
29、d2的语法树的语法树的语法树的语法树，使用使用使用使用=表示属性的表示属性的表示属性的表示属性的传递情况。传递情况。传递情况。传递情况。10语法制导翻译概论语法制导翻译概论从概念上讲，从概念上讲，从概念上讲，从概念上讲，基于属性文法基于属性文法基于属性文法基于属性文法的处理过程即的处理过程即的处理过程即的处理过程即语法制导翻语法制导翻语法制导翻语法制导翻译译译译通常是这样的：对单词符号串进行通常是这样的：对单词符号串进行通常是这样的：对单词符号串进行通常是这样的：对单词符号串进行语法分析语法分析语法分析语法分析，构造语，构造语，构造语，构造语法法法法分析树分析树分析树分析树，然后根据需要构造，
30、然后根据需要构造，然后根据需要构造，然后根据需要构造属性依赖图属性依赖图属性依赖图属性依赖图，遍历遍历遍历遍历语法树语法树语法树语法树并在语法树的各个结点处并在语法树的各个结点处并在语法树的各个结点处并在语法树的各个结点处按语义规则进行计算按语义规则进行计算按语义规则进行计算按语义规则进行计算。11计算语义规则计算语义规则所谓所谓所谓所谓依赖图依赖图依赖图依赖图，是一个有向图，用于描述分析树中的属性，是一个有向图，用于描述分析树中的属性，是一个有向图，用于描述分析树中的属性，是一个有向图，用于描述分析树中的属性和属性间的相互依赖关系。和属性间的相互依赖关系。和属性间的相互依赖关系。和属性间的相
31、互依赖关系。依赖图的构造算法依赖图的构造算法依赖图的构造算法依赖图的构造算法如下。如下。如下。如下。例例例例2 2的的的的变量说明语句变量说明语句变量说明语句变量说明语句Realid1,id2,id3Realid1,id2,id3分析树的依赖图分析树的依赖图分析树的依赖图分析树的依赖图（图（图（图（图中结点用数字表示）如下图。中结点用数字表示）如下图。中结点用数字表示）如下图。中结点用数字表示）如下图。属性计算有树遍历的和一遍扫描的方法。属性计算有树遍历的和一遍扫描的方法。属性计算有树遍历的和一遍扫描的方法。属性计算有树遍历的和一遍扫描的方法。树遍历：设语法树已经建立好，并且树中已经带有树遍历
32、：设语法树已经建立好，并且树中已经带有树遍历：设语法树已经建立好，并且树中已经带有树遍历：设语法树已经建立好，并且树中已经带有开始符开始符开始符开始符号的继承属性号的继承属性号的继承属性号的继承属性和终结符的综合属性。然后以某种次序遍历和终结符的综合属性。然后以某种次序遍历和终结符的综合属性。然后以某种次序遍历和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。最常用的遍历方法是深度语法树，直至计算出所有属性。最常用的遍历方法是深度语法树，直至计算出所有属性。最常用的遍历方法是深度语法树，直至计算出所有属性。最常用的遍历方法是深度优先，从左到右的遍历方法。若需要可使用多次遍历。优
33、先，从左到右的遍历方法。若需要可使用多次遍历。优先，从左到右的遍历方法。若需要可使用多次遍历。优先，从左到右的遍历方法。若需要可使用多次遍历。一遍扫描：是在语法分析的同时计算属性值，而不是语法一遍扫描：是在语法分析的同时计算属性值，而不是语法一遍扫描：是在语法分析的同时计算属性值，而不是语法一遍扫描：是在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构造实际分析构造语法树之后进行属性的计算，而且无需构造实际分析构造语法树之后进行属性的计算，而且无需构造实际分析构造语法树之后进行属性的计算，而且无需构造实际的语法树。对于编译程序来说，在单遍扫描中完成语义翻的语法树
34、。对于编译程序来说，在单遍扫描中完成语义翻的语法树。对于编译程序来说，在单遍扫描中完成语义翻的语法树。对于编译程序来说，在单遍扫描中完成语义翻译工作很重要。译工作很重要。译工作很重要。译工作很重要。12S-属性文法和自下而上翻译属性文法和自下而上翻译一个一般的属性文法的翻译器可能很难建立，但一个一般的属性文法的翻译器可能很难建立，但一个一般的属性文法的翻译器可能很难建立，但一个一般的属性文法的翻译器可能很难建立，但L-L-属性属性属性属性文法的翻译器文法的翻译器文法的翻译器文法的翻译器是很是很是很是很容易建立容易建立容易建立容易建立的。的。的。的。S-S-属性文法属性文法属性文法属性文法是是是
35、是L-L-属性文法的特例，是指只含有综合属性属性文法的特例，是指只含有综合属性属性文法的特例，是指只含有综合属性属性文法的特例，是指只含有综合属性的属性文法。的属性文法。的属性文法。的属性文法。综合属性综合属性综合属性综合属性可以在分析输入符号串的同时可以在分析输入符号串的同时可以在分析输入符号串的同时可以在分析输入符号串的同时自下而上自下而上自下而上自下而上的来计的来计的来计的来计算。算。算。算。S-S-属性文法的属性文法的属性文法的属性文法的翻译器翻译器翻译器翻译器通常可借助于通常可借助于通常可借助于通常可借助于LRLR分析器分析器分析器分析器实现。分实现。分实现。分实现。分析器可以保存与
36、栈中文法符号有关的综合属性值，每当进析器可以保存与栈中文法符号有关的综合属性值，每当进析器可以保存与栈中文法符号有关的综合属性值，每当进析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符行归约时，新的属性值就由栈中正在归约的产生式右边符行归约时，新的属性值就由栈中正在归约的产生式右边符行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。号的属性值来计算。号的属性值来计算。号的属性值来计算。13S-属性文法和自下而上翻译属性文法和自下而上翻译例：输入串是例：输入串是例：输入串是例：输入串是2+3*52+3*5，其，其，其，其语法树
37、语法树语法树语法树如下图，在第一步归约用如下图，在第一步归约用如下图，在第一步归约用如下图，在第一步归约用产生式产生式产生式产生式6 6），执行语义动作是置），执行语义动作是置），执行语义动作是置），执行语义动作是置F.valF.val的值为单词的值为单词的值为单词的值为单词digitdigit值，值，值，值，把语法树中每个结点的语义值括在该结点处。那么把语法树中每个结点的语义值括在该结点处。那么把语法树中每个结点的语义值括在该结点处。那么把语法树中每个结点的语义值括在该结点处。那么第一次第一次第一次第一次归约并完成语义动作后的情形归约并完成语义动作后的情形归约并完成语义动作后的情形归约并完成
38、语义动作后的情形如下图。继续进行分析，如下图。继续进行分析，如下图。继续进行分析，如下图。继续进行分析，第第第第七次归约后的情形七次归约后的情形七次归约后的情形七次归约后的情形如下图，归约至如下图，归约至如下图，归约至如下图，归约至E E，它的值它的值它的值它的值1717就计算出就计算出就计算出就计算出来了。来了。来了。来了。14S-属性文法和自下而上翻译属性文法和自下而上翻译语法制导翻译的具体实现途径不难。假定有一个语法制导翻译的具体实现途径不难。假定有一个语法制导翻译的具体实现途径不难。假定有一个语法制导翻译的具体实现途径不难。假定有一个LRLR语法语法语法语法分析器，现在把它的分析器，现
39、在把它的分析器，现在把它的分析器，现在把它的分析栈扩充分析栈扩充分析栈扩充分析栈扩充，使得每个文法符号都跟，使得每个文法符号都跟，使得每个文法符号都跟，使得每个文法符号都跟有有有有语义值语义值语义值语义值，即把，即把，即把，即把栈的结构看成如下图所示栈的结构看成如下图所示栈的结构看成如下图所示栈的结构看成如下图所示。同时把同时把同时把同时把LRLR分析器的功能扩大分析器的功能扩大分析器的功能扩大分析器的功能扩大，使它不仅执行语法分析任，使它不仅执行语法分析任，使它不仅执行语法分析任，使它不仅执行语法分析任务，且能在用某个产生式进行务，且能在用某个产生式进行务，且能在用某个产生式进行务，且能在用
40、某个产生式进行归约的同时调用相应的语义归约的同时调用相应的语义归约的同时调用相应的语义归约的同时调用相应的语义子程序子程序子程序子程序，完成在，完成在，完成在，完成在前面介绍的表达式的属性文法前面介绍的表达式的属性文法前面介绍的表达式的属性文法前面介绍的表达式的属性文法中描述的语中描述的语中描述的语中描述的语义动作。每步工作后的语义值保存在扩充的分析栈里义动作。每步工作后的语义值保存在扩充的分析栈里义动作。每步工作后的语义值保存在扩充的分析栈里义动作。每步工作后的语义值保存在扩充的分析栈里“语语语语义值栈义值栈义值栈义值栈”栏中。采用的栏中。采用的栏中。采用的栏中。采用的LRLR分析表分析表分
41、析表分析表如下图，其中如下图，其中如下图，其中如下图，其中d d代替代替代替代替digitdigit。分析和计算分析和计算分析和计算分析和计算2+3*52+3*5的过程的过程的过程的过程如下图所示。如下图所示。如下图所示。如下图所示。按照上述实现办法，若把语义子程序改为产生某种中间代按照上述实现办法，若把语义子程序改为产生某种中间代按照上述实现办法，若把语义子程序改为产生某种中间代按照上述实现办法，若把语义子程序改为产生某种中间代码的动作，那么则可在语法分析的制导下，随着分析的进码的动作，那么则可在语法分析的制导下，随着分析的进码的动作，那么则可在语法分析的制导下，随着分析的进码的动作，那么则
42、可在语法分析的制导下，随着分析的进展逐步生成中间代码。展逐步生成中间代码。展逐步生成中间代码。展逐步生成中间代码。15L-属性文法在自上而下分析中的实现属性文法在自上而下分析中的实现一个属性文法称为一个属性文法称为一个属性文法称为一个属性文法称为L-L-属性文法属性文法属性文法属性文法，如果对于每个产生式，如果对于每个产生式，如果对于每个产生式，如果对于每个产生式A-A-XX1 1X X2 2X Xn n，其每个语义规则中的每个属性其每个语义规则中的每个属性其每个语义规则中的每个属性其每个语义规则中的每个属性或者或者或者或者是是是是综合属综合属综合属综合属性性性性，或者或者或者或者是是是是X
43、Xj j(1=j=n)(1=jE-EaddopTEaddopTprint(addop.Lexemeprint(addop.Lexeme)E-TE-TT-numT-numprint(num.valprint(num.val)如果采用如果采用如果采用如果采用LRLR分析方法分析方法分析方法分析方法，用例，用例，用例，用例3 3的属性计算很容易实现，的属性计算很容易实现，的属性计算很容易实现，的属性计算很容易实现，比如在对串比如在对串比如在对串比如在对串2+3-52+3-5的分析同时执行语义动作，打印出的分析同时执行语义动作，打印出的分析同时执行语义动作，打印出的分析同时执行语义动作，打印出23+5
44、-23+5-。语法分析树中加上虚线连结的语义结点，形成一个可语法分析树中加上虚线连结的语义结点，形成一个可语法分析树中加上虚线连结的语义结点，形成一个可语法分析树中加上虚线连结的语义结点，形成一个可说明说明说明说明语义动作的树语义动作的树语义动作的树语义动作的树，如下图。，如下图。，如下图。，如下图。17L-属性文法在自上而下分析中的实现属性文法在自上而下分析中的实现 LLLL（1 1）这种自上而下分析方法的分析过程，从概念上这种自上而下分析方法的分析过程，从概念上这种自上而下分析方法的分析过程，从概念上这种自上而下分析方法的分析过程，从概念上说可以看成是深度优先建立语法树的过程，因此可以说可
45、以看成是深度优先建立语法树的过程，因此可以说可以看成是深度优先建立语法树的过程，因此可以说可以看成是深度优先建立语法树的过程，因此可以在自在自在自在自上而下语法分析上而下语法分析上而下语法分析上而下语法分析的同时的同时的同时的同时实现实现实现实现L-L-属性文法的计算属性文法的计算属性文法的计算属性文法的计算。注意，例注意，例注意，例注意，例3 3是一个含左递归规则的文法，采用是一个含左递归规则的文法，采用是一个含左递归规则的文法，采用是一个含左递归规则的文法，采用LLLL（1 1）分分分分析析析析必须改写文法如下：必须改写文法如下：必须改写文法如下：必须改写文法如下：E-TRR-E-TRR-
46、addopaddopTR|TR|T-numT-num 这时这时这时这时2+3-52+3-5的语法树的语法树的语法树的语法树如下图，将如下图，将如下图，将如下图，将后缀式后缀式后缀式后缀式23+5-23+5-输出的动作输出的动作输出的动作输出的动作在语法树中应出现的位置在语法树中应出现的位置在语法树中应出现的位置在语法树中应出现的位置如下图。如下图。如下图。如下图。18L-属性文法在自上而下分析中的实现属性文法在自上而下分析中的实现例例例例4.4.（中缀表达式翻译成相应的后缀表达式）（中缀表达式翻译成相应的后缀表达式）（中缀表达式翻译成相应的后缀表达式）（中缀表达式翻译成相应的后缀表达式）E-T
47、RE-TRR-R-addopaddopT Tprint(addop.Lexemeprint(addop.Lexeme)R)R|T-numT-numprint(num.valprint(num.val)例例例例4 4给出了可使用给出了可使用给出了可使用给出了可使用LLLL（1 1）分析方法分析方法分析方法分析方法的语义描述，不同的的语义描述，不同的的语义描述，不同的的语义描述，不同的是，语义动作不是附在产生式右部的末尾，而是嵌在了右是，语义动作不是附在产生式右部的末尾，而是嵌在了右是，语义动作不是附在产生式右部的末尾，而是嵌在了右是，语义动作不是附在产生式右部的末尾，而是嵌在了右部文法符号部文法
48、符号部文法符号部文法符号T T和和和和R R之间。把这种语义处理的描述形式称为之间。把这种语义处理的描述形式称为之间。把这种语义处理的描述形式称为之间。把这种语义处理的描述形式称为翻翻翻翻译模式译模式译模式译模式。19L-属性文法在自上而下分析中的实现属性文法在自上而下分析中的实现 翻译模式翻译模式翻译模式翻译模式是适合语法制导翻译的另一种描述形式。翻译是适合语法制导翻译的另一种描述形式。翻译是适合语法制导翻译的另一种描述形式。翻译是适合语法制导翻译的另一种描述形式。翻译模式给出了使用语义规则进行模式给出了使用语义规则进行模式给出了使用语义规则进行模式给出了使用语义规则进行计算的次序计算的次序
49、计算的次序计算的次序，可把某些实现，可把某些实现，可把某些实现，可把某些实现细节表示出来。在翻译模式中，和文法符号相关的细节表示出来。在翻译模式中，和文法符号相关的细节表示出来。在翻译模式中，和文法符号相关的细节表示出来。在翻译模式中，和文法符号相关的属性属性属性属性和和和和语义规则语义规则语义规则语义规则，用花括号括起来，用花括号括起来，用花括号括起来，用花括号括起来，插入到产生式右部的合适位插入到产生式右部的合适位插入到产生式右部的合适位插入到产生式右部的合适位置上置上置上置上。20L-属性文法在自下而上分析中的实现属性文法在自下而上分析中的实现 计算继承属性计算继承属性计算继承属性计算继
50、承属性的的的的办法办法办法办法有有有有两种两种两种两种：1 1）从翻译模式中去掉嵌入从翻译模式中去掉嵌入从翻译模式中去掉嵌入从翻译模式中去掉嵌入在产生式中间的动作；在产生式中间的动作；在产生式中间的动作；在产生式中间的动作；2 2）用综合属性代替继承属性。用综合属性代替继承属性。用综合属性代替继承属性。用综合属性代替继承属性。为了使所有嵌入的动作都出现在产生式的为了使所有嵌入的动作都出现在产生式的为了使所有嵌入的动作都出现在产生式的为了使所有嵌入的动作都出现在产生式的末尾末尾末尾末尾，可以，可以，可以，可以自自自自下而上下而上下而上下而上处理继承属性，从翻译模式中处理继承属性，从翻译模式中处理