LGYBY语法制导翻译和中间代码生成.ppt

《LGYBY语法制导翻译和中间代码生成.ppt》由会员分享，可在线阅读，更多相关《LGYBY语法制导翻译和中间代码生成.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第8章章语法制导翻译和中间语法制导翻译和中间代码生成代码生成赖国勇赖国勇攀枝花学院计算机学院攀枝花学院计算机学院1赖国勇本章内容重点难点教学要求本章内容重点难点教学要求n n教学内容：教学内容：教学内容：教学内容：n n语义分析概述；属性文法；中间代码生成。语义分析概述；属性文法；中间代码生成。语义分析概述；属性文法；中间代码生成。语义分析概述；属性文法；中间代码生成。n n重点：重点：重点：重点：三种中间语言：四元式、三元式、逆波兰三种中间语言：四元式、三元式、逆波兰三种中间语言：四元式、三元式、逆波兰三种中间语言：四元式、三元式、逆波兰式。式。式。式。n n难点：难点：难点：难点：三种中

2、间语言：四元式、三元式、逆波兰三种中间语言：四元式、三元式、逆波兰三种中间语言：四元式、三元式、逆波兰三种中间语言：四元式、三元式、逆波兰式。式。式。式。n n教学要求教学要求教学要求教学要求n n1 1、了解：、了解：、了解：、了解：属性文法。属性文法。属性文法。属性文法。n n2 2、理解：、理解：、理解：、理解：语义分析的功能。语义分析的功能。语义分析的功能。语义分析的功能。n n3 3、掌握：、掌握：、掌握：、掌握：逆波兰式、三元式和树形表示、四元式。逆波兰式、三元式和树形表示、四元式。逆波兰式、三元式和树形表示、四元式。逆波兰式、三元式和树形表示、四元式。2赖国勇第第8章章_目录目录

3、n n8.1语义处理概述语义处理概述n n8.2属性文法，语法制导翻译属性文法，语法制导翻译n n8.3中间代码中间代码3赖国勇语义分析的基础语义分析的基础n n1、语义分析的内容？、语义分析的内容？n n2、静态语义分析的主要任务？、静态语义分析的主要任务？n n3、动态语义分析的主要任务？、动态语义分析的主要任务？n n4、语义的形式化描述？、语义的形式化描述？4赖国勇源语言程序源语言程序中间代码中间代码汇编代码汇编代码词法分析词法分析语义分析语义分析语法分析语法分析中间代码生成中间代码生成代码生成代码生成在编译中的逻辑阶段在编译中的逻辑阶段前前端端处处理理后后端端处处理理语语义义处处理理

4、语义处理（语义分析和中间代码生成）语义处理（语义分析和中间代码生成）5赖国勇语言的语义和编译的语义处理工作语言的语义和编译的语义处理工作n n静态语义：语法规则的良形式条件。静态语义：语法规则的良形式条件。n n静态语义检查：审查静态语义。静态语义检查：审查静态语义。n n动态语义：程序单元执行的操作。动态语义：程序单元执行的操作。n n动态语义处理：生成中间动态语义处理：生成中间(目标目标)代码。代码。6赖国勇8.1语义处理概述语义处理概述7赖国勇编译阶段编译阶段-语义处理语义处理编译阶段编译阶段语义处理语义处理语法分析后的源程序语法分析后的源程序n n程序设计语言的语义程序设计语言的语义程

5、序设计语言的语义程序设计语言的语义n n静态语义静态语义静态语义静态语义是对程序约束的描述，这些约束无法通过抽象语法是对程序约束的描述，这些约束无法通过抽象语法是对程序约束的描述，这些约束无法通过抽象语法是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它规则来妥善地描述，实质上就是语法规则的良形式条件，它规则来妥善地描述，实质上就是语法规则的良形式条件，它规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分为可以分为可以分为可以分为类型规则和作用域类型规则和作用域类型规则和作用域类型规则和作用域/可见性规则可见性规则可见性规则可见性规则两大类

6、。例如：两大类。例如：两大类。例如：两大类。例如：n n类型相容性，变量先声明后引用，名称相关要求。类型相容性，变量先声明后引用，名称相关要求。类型相容性，变量先声明后引用，名称相关要求。类型相容性，变量先声明后引用，名称相关要求。n n动态语义动态语义动态语义动态语义程序单位描述的计算。程序单位描述的计算。程序单位描述的计算。程序单位描述的计算。n n编译程序的语义处理工作编译程序的语义处理工作编译程序的语义处理工作编译程序的语义处理工作n n静态语义审查。静态语义审查。静态语义审查。静态语义审查。n n解释执行动态语义。解释执行动态语义。解释执行动态语义。解释执行动态语义。8.18赖国勇静

7、态语义审查静态语义审查n n1、类型检查。、类型检查。n n2、控制流检查。控制流语句必须使控制、控制流检查。控制流语句必须使控制转移到合法的地方。转移到合法的地方。n n3、一致性检查。、一致性检查。n n4、上下文相关性检查。、上下文相关性检查。n n5、名字的作用域分析。、名字的作用域分析。8.19赖国勇解释执行动态语义解释执行动态语义n n（计算）生成代码（中间代码或目标代码）（计算）生成代码（中间代码或目标代码）（计算）生成代码（中间代码或目标代码）（计算）生成代码（中间代码或目标代码）8.110赖国勇例例8.18.111赖国勇语义处理的描述语义处理的描述n n属性文法：描述语义规则

8、。属性文法：描述语义规则。n n语法制导翻译：在语法分析的同时，执语法制导翻译：在语法分析的同时，执行语义子程序：行语义子程序：n n检查静态语义。检查静态语义。检查静态语义。检查静态语义。n n翻译翻译翻译翻译(生成生成生成生成)中间中间中间中间(目标目标目标目标)代码。代码。代码。代码。8.112赖国勇语义处理的描述语义处理的描述-例例8.2n nP PDD；E En nDDDD；D|id:TD|id:Tn nT Tchar|integer|arraynumofT|char|integer|arraynumofT|T Tn nE Eliteral|num|id|EmodE|EE|Elite

9、ral|num|id|EmodE|EE|En nP P代表程序；代表程序；代表程序；代表程序；D D代表说明；代表说明；代表说明；代表说明；E E代表表达式。如程序语句：代表表达式。如程序语句：代表表达式。如程序语句：代表表达式。如程序语句：n nkey:integer;key:integer;n nString:char;String:char;n nkeymod1999keymod1999n n语言本身提供两种基本类型：语言本身提供两种基本类型：语言本身提供两种基本类型：语言本身提供两种基本类型：charchar和和和和integerinteger。n n除此之外还有缺省的基本类型除此之外

10、还有缺省的基本类型除此之外还有缺省的基本类型除此之外还有缺省的基本类型type_errortype_error和和和和voidvoid。假定所。假定所。假定所。假定所有数组都从下标有数组都从下标有数组都从下标有数组都从下标1 1开始开始开始开始8.113赖国勇确定标识符类型的语义描述确定标识符类型的语义描述n n（1 1）P PD D；E En n（2 2）D DD D；D Dn n（3 3）D Did:Taddtype(id.Entryid:Taddtype(id.Entry，T.type)T.type)n n（4 4）T TcharT.Type:=charcharT.Type:=charn

11、 n（5 5）T TintegerT.Type:=integerintegerT.Type:=integern n（6 6）T TT T1 1T.Type:=pointer(TT.Type:=pointer(T1 1.type).type)n n（7 7）T TarraynumofTarraynumofT1 1 n nT.Type:=array(num.ValT.Type:=array(num.Val，TT1 1.type).type)8.114赖国勇类型检查的语义描述类型检查的语义描述-例例8.2n nS Sid:=Eid:=Eifid.Type=E.Typeifid.Type=E.Type

12、ThenS.Type:=voidThenS.Type:=voidelseS.Type:=type_errorelseS.Type:=type_errorn nS SifEthenSifEthenS1 1ifE.type=BooleanifE.type=BooleanthenS.Type:=SthenS.Type:=S1 1.type.typeelseS.type:=type_elseS.type:=type_errorerrorn nS SwhileEdoSwhileEdoS1 1ifE.type=BooleanifE.type=BooleanthenS.type:=SthenS.type:=

13、S1 1.Type.TypeelseS.type:=type_errorelseS.type:=type_error8.115赖国勇静态语义分析的环境静态语义分析的环境n n符号表符号表（将在第（将在第9章详细讲述）：章详细讲述）：n n为语义分析提供类型、作用域等信息。为语义分析提供类型、作用域等信息。为语义分析提供类型、作用域等信息。为语义分析提供类型、作用域等信息。n n为代码生成提供类型、作用域、存储类别、为代码生成提供类型、作用域、存储类别、为代码生成提供类型、作用域、存储类别、为代码生成提供类型、作用域、存储类别、存储（相对）位置等信息。存储（相对）位置等信息。存储（相对）位置等信

14、息。存储（相对）位置等信息。8.116赖国勇8.2属性文法，语法制导翻译属性文法，语法制导翻译属性文法属性文法8.2.2两种属性两种属性8.2.3属性计算方法属性计算方法8.2.4语法制导翻译语法制导翻译17赖国勇属性文法属性文法n n属性文法属性文法A(attributegrammar)是一个三是一个三元组：元组：A=(G，V，F)，其中：，其中：n nG G：是一个上下文无关文法。：是一个上下文无关文法。：是一个上下文无关文法。：是一个上下文无关文法。n nV V：有穷的属性集，每个属性与文法的一终结符：有穷的属性集，每个属性与文法的一终结符：有穷的属性集，每个属性与文法的一终结符：有穷的

15、属性集，每个属性与文法的一终结符或非终结符相联。或非终结符相联。或非终结符相联。或非终结符相联。n nF F：关于属性的属性断言或谓词集。每个断言与：关于属性的属性断言或谓词集。每个断言与：关于属性的属性断言或谓词集。每个断言与：关于属性的属性断言或谓词集。每个断言与一个产生式相联。而此断言只引用该产生式左端一个产生式相联。而此断言只引用该产生式左端一个产生式相联。而此断言只引用该产生式左端一个产生式相联。而此断言只引用该产生式左端或右端的终结符或非终结符相联的属性。或右端的终结符或非终结符相联的属性。或右端的终结符或非终结符相联的属性。或右端的终结符或非终结符相联的属性。18赖国勇属性文法属

16、性文法n n属性文法是允许为每个终结符和非终结符配备属性文法是允许为每个终结符和非终结符配备属性文法是允许为每个终结符和非终结符配备属性文法是允许为每个终结符和非终结符配备一些属性的文法。一些属性的文法。一些属性的文法。一些属性的文法。n n它既能描述程序设计语言的语法，又为其语它既能描述程序设计语言的语法，又为其语它既能描述程序设计语言的语法，又为其语它既能描述程序设计语言的语法，又为其语义描述提供了手段。义描述提供了手段。义描述提供了手段。义描述提供了手段。n n属性文法由于属性文法由于属性文法由于属性文法由于19681968年引进年引进年引进年引进.n n后来才被用于编译程序的设计。后来

17、才被用于编译程序的设计。后来才被用于编译程序的设计。后来才被用于编译程序的设计。8.219赖国勇例例8.4属性文法属性文法n n表达式文法表达式文法表达式文法表达式文法ET+T|TorTET+T|TorTTn|bTn|bn nE ET T11+T+T22n nTT1 1.type=int.type=intn nT T2 2.type=T.type=T1 1.type.typen nE.type:=intE.type:=intn nEE T T11orTorT22n nTT1 1.type=bool.type=booln nT T2 2.type=T.type=T1 1.type.typen n

18、E.type:=boolE.type:=booln nTTnnT.type:=intT.type:=intn nTTbbT.type:=boolT.type:=bool8.220赖国勇属性赋值属性赋值n n属性有不同的类型，可以象变量一样地被赋值。属性有不同的类型，可以象变量一样地被赋值。属性有不同的类型，可以象变量一样地被赋值。属性有不同的类型，可以象变量一样地被赋值。n n赋值规则附加于语法规则之上。赋值规则附加于语法规则之上。赋值规则附加于语法规则之上。赋值规则附加于语法规则之上。n n赋值与语法分析同时进行，赋值过程就是语义处理过赋值与语法分析同时进行，赋值过程就是语义处理过赋值与语法

19、分析同时进行，赋值过程就是语义处理过赋值与语法分析同时进行，赋值过程就是语义处理过程。程。程。程。n n在推导语法树的时候，诸属性的值被计算并通过赋值在推导语法树的时候，诸属性的值被计算并通过赋值在推导语法树的时候，诸属性的值被计算并通过赋值在推导语法树的时候，诸属性的值被计算并通过赋值规则层层传递。规则层层传递。规则层层传递。规则层层传递。n n有的从语法规则左边向右边传，有的从右边向左边传。有的从语法规则左边向右边传，有的从右边向左边传。有的从语法规则左边向右边传，有的从右边向左边传。有的从语法规则左边向右边传，有的从右边向左边传。n n语法推导树最后完成时，就得到开始符号的属性值，语法推

20、导树最后完成时，就得到开始符号的属性值，语法推导树最后完成时，就得到开始符号的属性值，语法推导树最后完成时，就得到开始符号的属性值，也就是整个程序的语义。也就是整个程序的语义。也就是整个程序的语义。也就是整个程序的语义。8.221赖国勇例例8.6n n例如：定义表例如：定义表例如：定义表例如：定义表达式的文法如达式的文法如达式的文法如达式的文法如下下下下(例例例例8.6)8.6)n nE EE+EE+En nE E(E)(E)n nE En nn n给出定义表达给出定义表达给出定义表达给出定义表达式值的属性文式值的属性文式值的属性文式值的属性文法。法。法。法。n n我们为文法符号我们为文法符号

21、我们为文法符号我们为文法符号E E引进属性符号引进属性符号引进属性符号引进属性符号valval，用，用，用，用E.valE.val表示表示表示表示E E的值，属性计算规则以赋值语句的形式给出，的值，属性计算规则以赋值语句的形式给出，的值，属性计算规则以赋值语句的形式给出，的值，属性计算规则以赋值语句的形式给出，附在每个产生式后，并用大括号括起来。为了明附在每个产生式后，并用大括号括起来。为了明附在每个产生式后，并用大括号括起来。为了明附在每个产生式后，并用大括号括起来。为了明确确确确E E的不同出现位置，用上角标区别。终结符的不同出现位置，用上角标区别。终结符的不同出现位置，用上角标区别。终结

22、符的不同出现位置，用上角标区别。终结符n n的的的的值是词法分析程序提供的，这里用值是词法分析程序提供的，这里用值是词法分析程序提供的，这里用值是词法分析程序提供的，这里用n.lexn.lex表示。下表示。下表示。下表示。下面给出属性文法：面给出属性文法：面给出属性文法：面给出属性文法：n nE EE E1 1+E+E2 2E.val:=EE.val:=E1 1.val+E.val+E2 2.val.valn nE E(E(E1 1)E.val:=EE.val:=E1 1.val.valn nE En nE.val:=n.lexE.val:=n.lexn n属性文法的主要思想有两点：属性文法的

23、主要思想有两点：属性文法的主要思想有两点：属性文法的主要思想有两点：n n首先对于每个文法符号引进相关的属性符号；首先对于每个文法符号引进相关的属性符号；首先对于每个文法符号引进相关的属性符号；首先对于每个文法符号引进相关的属性符号；n n其次对于每个产生式写出属性值计算的规则。其次对于每个产生式写出属性值计算的规则。其次对于每个产生式写出属性值计算的规则。其次对于每个产生式写出属性值计算的规则。8.222赖国勇8.2.2两种属性两种属性n n属性分为两种属性分为两种属性分为两种属性分为两种:继承继承继承继承属性和综合属性属性和综合属性属性和综合属性属性和综合属性（inheritedandin

24、heritedandsynthesized(derivsynthesized(derived)attributeed)attribute）。）。）。）。n n继承属性的计算规则继承属性的计算规则继承属性的计算规则继承属性的计算规则自顶向下，从其父结自顶向下，从其父结自顶向下，从其父结自顶向下，从其父结点的属性值计算出来点的属性值计算出来点的属性值计算出来点的属性值计算出来的。的。的。的。n n综合属性的计算规则综合属性的计算规则综合属性的计算规则综合属性的计算规则自底向上，从其兄弟自底向上，从其兄弟自底向上，从其兄弟自底向上，从其兄弟结点和子结点的属性结点和子结点的属性结点和子结点的属性结点和

25、子结点的属性值计算出来的。值计算出来的。值计算出来的。值计算出来的。n n出现在产生式左边的继承属性和出出现在产生式左边的继承属性和出出现在产生式左边的继承属性和出出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所现在产生式右边的综合属性不由所现在产生式右边的综合属性不由所现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行给定的产生式的属性计算规则进行给定的产生式的属性计算规则进行给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规计算，它们由其它产生式的属性规计算，它们由其它产生式的属性规计算，它们由其它产生式的属性规则计算。则计算。则计算。则计算。n nA AX

26、1X2XnX1X2Xnn nA A的综合属性，计算的综合属性，计算的综合属性，计算的综合属性，计算n nT(A):=f(I(X1)T(A):=f(I(X1)，I(Xn)I(Xn)n nXjXj的继承属性，计算的继承属性，计算的继承属性，计算的继承属性，计算n nT(Xj):=f(I(A)T(Xj):=f(I(A)，.I(Xn).I(Xn)n n1)1)非终结符既可有综合属性也可非终结符既可有综合属性也可非终结符既可有综合属性也可非终结符既可有综合属性也可有继承属性，但文法开始符号没有有继承属性，但文法开始符号没有有继承属性，但文法开始符号没有有继承属性，但文法开始符号没有继承属性继承属性继承属

27、性继承属性.n n2)2)终结符只有综合属性终结符只有综合属性终结符只有综合属性终结符只有综合属性.23赖国勇语义规则语义规则n n在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A A都有一套都有一套都有一套都有一套与之相关联的语义规则，每条规则的形式为与之相关联的语义规则，每条规则的形式为与之相关联的语义规则，每条规则的形式为与之相关联的语义规则，每条规则的形式为n nb:=f(cb:=f(c1 1，c c2 2cck k)n n这里，这里，这里，这里，f f是一个函数，而且或者是一个函数，而且或者是一

28、个函数，而且或者是一个函数，而且或者n n（1 1）b b是是是是A A的一个综合属性并且的一个综合属性并且的一个综合属性并且的一个综合属性并且c c1 1，c c2 2cck k是产生是产生是产生是产生式右边文法符号的属性式右边文法符号的属性式右边文法符号的属性式右边文法符号的属性;或者或者或者或者n n（2 2）b b是产生式右边某个文法符号的一个继承属性是产生式右边某个文法符号的一个继承属性是产生式右边某个文法符号的一个继承属性是产生式右边某个文法符号的一个继承属性并且并且并且并且c c1 1，c c2 2cck k是是是是A A或产生式右边任何文法符号的或产生式右边任何文法符号的或产生

29、式右边任何文法符号的或产生式右边任何文法符号的属性。属性。属性。属性。n n在两种情况下，我们都说属性在两种情况下，我们都说属性在两种情况下，我们都说属性在两种情况下，我们都说属性b b依赖于属性依赖于属性依赖于属性依赖于属性c c1 1，c c2 2cck k。8.224赖国勇例例8.7n n例如定义表达式值的属性文法，例如定义表达式值的属性文法，例如定义表达式值的属性文法，例如定义表达式值的属性文法，E.valE.val是一个综合属性的例子：是一个综合属性的例子：是一个综合属性的例子：是一个综合属性的例子：n nE EE E1 1+E+E2 2E.val:=EE.val:=E1 1.val

30、+E.val+E2 2.val.valn nE E(E(E1 1)E.val:=EE.val:=E1 1.val.valn nE En nE.val:=n.lexE.val:=n.lexn n考虑句子考虑句子考虑句子考虑句子2 2（3 31 1）的求值顺序，将）的求值顺序，将）的求值顺序，将）的求值顺序，将2 2（3 31 1）的语法）的语法）的语法）的语法树结点改为有附加属性的结点（这样的树称为带注释的语法树结点改为有附加属性的结点（这样的树称为带注释的语法树结点改为有附加属性的结点（这样的树称为带注释的语法树结点改为有附加属性的结点（这样的树称为带注释的语法树）：树）：树）：树）：E.va

31、l=6E.val=2E.val=4E.val=3E.val=1+n.lex=2n.lex=3n.lex=1()E.val=48.225赖国勇例例8.8一个简单台式计算器的定义一个简单台式计算器的定义n n非终结符非终结符非终结符非终结符E E、T T及及及及F F都有一个综合属性都有一个综合属性都有一个综合属性都有一个综合属性valval，符号，符号，符号，符号digitdigit有一个综合有一个综合有一个综合有一个综合属性，它的值由词法分析器提供。与产生式属性，它的值由词法分析器提供。与产生式属性，它的值由词法分析器提供。与产生式属性，它的值由词法分析器提供。与产生式L LEnEn对应的语义

32、规对应的语义规对应的语义规对应的语义规则仅仅是打印由则仅仅是打印由则仅仅是打印由则仅仅是打印由E E产生的算术表达式的值的一个过程，我们可认产生的算术表达式的值的一个过程，我们可认产生的算术表达式的值的一个过程，我们可认产生的算术表达式的值的一个过程，我们可认为这条规则定义了为这条规则定义了为这条规则定义了为这条规则定义了L L的一个虚属性。某些非终结符加下标是为了的一个虚属性。某些非终结符加下标是为了的一个虚属性。某些非终结符加下标是为了的一个虚属性。某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现。区分一个产生式中同一非终结符多次出现。区分一个产生式中同一非终结符多次出现。区分

33、一个产生式中同一非终结符多次出现。8.226赖国勇例例8.9:3*5+4的带注释的分析树的带注释的分析树n n只使用综合属性只使用综合属性只使用综合属性只使用综合属性.LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*8.227赖国勇例例8.10继承属性继承属性n n一个结点的继承属性值是由此结点的父结点一个结点的继承属性值是由此结点的父结点一个结点的继承属性值是由此结点的父结点一个结点的继承属性值是由此结点的父结点*（或）兄（或）兄（或

34、）兄（或）兄弟结点的某些属性来决定的。例，添加标识符类型的弟结点的某些属性来决定的。例，添加标识符类型的弟结点的某些属性来决定的。例，添加标识符类型的弟结点的某些属性来决定的。例，添加标识符类型的语义描述：语义描述：语义描述：语义描述：继承属性继承属性type产生式产生式语语 义义 规规 则则D TL T int T real L L1，idL idL.type:=T.typeT.type=integerT.type:=real L1.type:=L.type addtype(id.entry，L.type)addtype(id.entry，L.type)8.228赖国勇例例8.10继承属性（

35、续）继承属性（续）Realid1，id2，id3带注释的语法树带注释的语法树DL.type=realL.type=realL.type=realT.type=realrealid2id1id3.,8.229赖国勇例例8.11PDSPDSDvarV;D|DvarV;D|SV:=E;S|SV:=E;S|Vx|y|zVx|y|zn n现在使用两个属性，现在使用两个属性，现在使用两个属性，现在使用两个属性，namename和和和和dldl，每当一个新的变量声明时，就把它的，每当一个新的变量声明时，就把它的，每当一个新的变量声明时，就把它的，每当一个新的变量声明时，就把它的namename属性附给它，属

36、性附给它，属性附给它，属性附给它，namename属性是综合属性。属性是综合属性。属性是综合属性。属性是综合属性。n n将所声明的变量都放到一个变量名字清单中（用语义函数将所声明的变量都放到一个变量名字清单中（用语义函数将所声明的变量都放到一个变量名字清单中（用语义函数将所声明的变量都放到一个变量名字清单中（用语义函数addlistaddlist实现），实现），实现），实现），用属性用属性用属性用属性dldl综合声明块中声明的所有变量。然后这个综合声明块中声明的所有变量。然后这个综合声明块中声明的所有变量。然后这个综合声明块中声明的所有变量。然后这个dldl属性又作为继承属性属性又作为继承属性

37、属性又作为继承属性属性又作为继承属性传到后面的语句部分，每个语句用到的变量都要进行审查，看它是否在变传到后面的语句部分，每个语句用到的变量都要进行审查，看它是否在变传到后面的语句部分，每个语句用到的变量都要进行审查，看它是否在变传到后面的语句部分，每个语句用到的变量都要进行审查，看它是否在变量名字清单中量名字清单中量名字清单中量名字清单中。n nPDSS.dl=D.dlPDSS.dl=D.dln nD1varV;D2|D1varV;D2|D1.dl=addlist(V.nameD1.dl=addlist(V.name，D2.dl)|D2.dl)|D1.dl=NULLD1.dl=NULLn nS

38、1V:=E;S2|S1V:=E;S2|check(V.namecheck(V.name，S1.dl);S2.dl=S1.dlS1.dl);S2.dl=S1.dln nVx|y|zV.name=x|V.name=y|V.name=Vx|y|zV.name=x|V.name=y|V.name=zz8.230赖国勇varx；vary；x:=e；PDdl=x，ySdl=x，yvarV；Ddl=yV:=e；SxvarV；Ddl=y y 8.231赖国勇8.2.3属性计算方法属性计算方法n n树遍历的属性计算方法树遍历的属性计算方法n n设语法树已经建立起了，并且树中已带有开设语法树已经建立起了，并且树中

39、已带有开设语法树已经建立起了，并且树中已带有开设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。始符号的继承属性和终结符的综合属性。始符号的继承属性和终结符的综合属性。始符号的继承属性和终结符的综合属性。n n然后以某种次序遍历语法树，直至计算出所然后以某种次序遍历语法树，直至计算出所然后以某种次序遍历语法树，直至计算出所然后以某种次序遍历语法树，直至计算出所有属性。有属性。有属性。有属性。n n最常用的遍历方法是深度优先，从左到右的最常用的遍历方法是深度优先，从左到右的最常用的遍历方法是深度优先，从左到右的最常用的遍历方法是深度优先，从左到右的遍历方法。遍历方法。遍历

40、方法。遍历方法。n n如果需要的话，可使用多次遍历（或称遍）。如果需要的话，可使用多次遍历（或称遍）。如果需要的话，可使用多次遍历（或称遍）。如果需要的话，可使用多次遍历（或称遍）。32赖国勇一遍扫描的处理方法一遍扫描的处理方法n n与树遍历的属性计算方法不同，一遍扫描在语与树遍历的属性计算方法不同，一遍扫描在语与树遍历的属性计算方法不同，一遍扫描在语与树遍历的属性计算方法不同，一遍扫描在语法分析的同时计算属性值，而不是在语法分析法分析的同时计算属性值，而不是在语法分析法分析的同时计算属性值，而不是在语法分析法分析的同时计算属性值，而不是在语法分析构造语法树之后进行属性的计算，而且无需构构造语

41、法树之后进行属性的计算，而且无需构构造语法树之后进行属性的计算，而且无需构构造语法树之后进行属性的计算，而且无需构造实际的语法树。造实际的语法树。造实际的语法树。造实际的语法树。n n因为一遍扫描的处理方法与语法分析器的相互因为一遍扫描的处理方法与语法分析器的相互因为一遍扫描的处理方法与语法分析器的相互因为一遍扫描的处理方法与语法分析器的相互作用，它与下面两个因素密切相关：作用，它与下面两个因素密切相关：作用，它与下面两个因素密切相关：作用，它与下面两个因素密切相关：n n（1 1）所采用的语法分析方法）所采用的语法分析方法）所采用的语法分析方法）所采用的语法分析方法n n（2 2）属性的计算

42、次序。）属性的计算次序。）属性的计算次序。）属性的计算次序。8.233赖国勇8.2.4语法制导翻译语法制导翻译n n一个一个一个一个翻译翻译翻译翻译是符号串对的一个集合。是符号串对的一个集合。是符号串对的一个集合。是符号串对的一个集合。n n在一个编译程序定义的翻译中，符号串对是源程序和目标程序。在一个编译程序定义的翻译中，符号串对是源程序和目标程序。在一个编译程序定义的翻译中，符号串对是源程序和目标程序。在一个编译程序定义的翻译中，符号串对是源程序和目标程序。n n各个编译阶段定义一个翻译，各个编译阶段定义一个翻译，各个编译阶段定义一个翻译，各个编译阶段定义一个翻译，n n词法分析：（字符串

43、，单词串）词法分析：（字符串，单词串）词法分析：（字符串，单词串）词法分析：（字符串，单词串）n n语法分析：（单词串，语法树）语法分析：（单词串，语法树）语法分析：（单词串，语法树）语法分析：（单词串，语法树）n n代码生成（语法树，汇编语言）代码生成（语法树，汇编语言）代码生成（语法树，汇编语言）代码生成（语法树，汇编语言）n n设设设设 是输入字母表且是输入字母表且是输入字母表且是输入字母表且 是输出字母表。定义由语言是输出字母表。定义由语言是输出字母表。定义由语言是输出字母表。定义由语言L1L1 *到语到语到语到语言言言言L2L2 *的一个翻译是由的一个翻译是由的一个翻译是由的一个翻译

44、是由 *到到到到 *的一个关系的一个关系的一个关系的一个关系T T，使得，使得，使得，使得T T的定义的定义的定义的定义域为域为域为域为L1L1且且且且T T的值域为的值域为的值域为的值域为L2L2。n n使使使使(x(x，y)y)T T的句子的句子的句子的句子y y叫做叫做叫做叫做x x的一个输出的一个输出的一个输出的一个输出.n n直观地说，一个语法制导翻译的基础是一个文法，其中翻译成直观地说，一个语法制导翻译的基础是一个文法，其中翻译成直观地说，一个语法制导翻译的基础是一个文法，其中翻译成直观地说，一个语法制导翻译的基础是一个文法，其中翻译成分依附在每一产生式上。分依附在每一产生式上。分

45、依附在每一产生式上。分依附在每一产生式上。34赖国勇在语法分析的同时进行语义处理在语法分析的同时进行语义处理n n从概念上讲，语法制导翻译即基于属性文法的从概念上讲，语法制导翻译即基于属性文法的从概念上讲，语法制导翻译即基于属性文法的从概念上讲，语法制导翻译即基于属性文法的处理过程通常是这样的：对单词符号串进行语处理过程通常是这样的：对单词符号串进行语处理过程通常是这样的：对单词符号串进行语处理过程通常是这样的：对单词符号串进行语法分析构造语法分析树，然后根据需要遍历语法分析构造语法分析树，然后根据需要遍历语法分析构造语法分析树，然后根据需要遍历语法分析构造语法分析树，然后根据需要遍历语法树，

46、并在语法树的各结点处按语义规则进行法树，并在语法树的各结点处按语义规则进行法树，并在语法树的各结点处按语义规则进行法树，并在语法树的各结点处按语义规则进行计算。计算。计算。计算。n n实现：实现：实现：实现：n n输入符号串输入符号串输入符号串输入符号串分析树分析树分析树分析树 属性依赖图属性依赖图属性依赖图属性依赖图语义规则的计算顺序语义规则的计算顺序语义规则的计算顺序语义规则的计算顺序8.235赖国勇例例8.12：类形检查：类形检查n n例例例例8.128.12：类形检查：类形检查：类形检查：类形检查n nE ET T11+T+T22n nifTifT1 1.type=intandT.ty

47、pe=intandT2 2.type=int.type=intn nThenThen E.type:=intelseerrorE.type:=intelseerrorn nE E T T11oToT22n nifTifT1 1.type=boolandT.type=boolandT2 2.type=bool.type=booln nthenE.type:=boolelseerrorthenE.type:=boolelseerrornn T TnT.type:=intnT.type:=intn nTTbT.type:=boolbT.type:=booln n 编译实现编译实现编译实现编译实现:n

48、 n(LR)(LR)增加语义栈，增加语义栈，增加语义栈，增加语义栈，归约时进行语义动作归约时进行语义动作归约时进行语义动作归约时进行语义动作.n nLL(1)LL(1)匹配时进行语义动作匹配时进行语义动作匹配时进行语义动作匹配时进行语义动作.8.236赖国勇LR(0)分析表分析表(1)ET+T(2)EToT(3)Tn(4)Tb8.237赖国勇分析分析步骤步骤(1)ET+T(2)EToT(3)Tn(4)Tb8.238赖国勇对串对串n+b分析过程分析过程(1)ET+T(2)EToT(3)Tn(4)Tb8.239赖国勇8.3中间代码中间代码40赖国勇概述概述n n中间代码中间代码中间代码中间代码(I

49、ntermediatecode)(Intermediate(Intermediatecode)(Intermediaterepresentation)(Intermediatelanguage)representation)(Intermediatelanguage)n n是源程序的一种内部表示是源程序的一种内部表示是源程序的一种内部表示是源程序的一种内部表示n n复杂性介于源语言和目标机语言之间复杂性介于源语言和目标机语言之间复杂性介于源语言和目标机语言之间复杂性介于源语言和目标机语言之间n n中间代码的作用：中间代码的作用：中间代码的作用：中间代码的作用：n n使编译程序的逻辑结构更加简单

50、明确，使编译程序的逻辑结构更加简单明确，使编译程序的逻辑结构更加简单明确，使编译程序的逻辑结构更加简单明确，n n利于进行与目标机无关的优化，利于进行与目标机无关的优化，利于进行与目标机无关的优化，利于进行与目标机无关的优化，n n利于在不同目标机上实现同一种语言。利于在不同目标机上实现同一种语言。利于在不同目标机上实现同一种语言。利于在不同目标机上实现同一种语言。n n中间代码的形式：中间代码的形式：中间代码的形式：中间代码的形式：n n逆波兰式、四元式、三元式、间接三元式、树。逆波兰式、四元式、三元式、间接三元式、树。逆波兰式、四元式、三元式、间接三元式、树。逆波兰式、四元式、三元式、间接