Chapt6_第6章语法制导翻译技术

1、第第6 6章章 语法制导翻译技术语法制导翻译技术 No cross, no crown. 不经历风雨，怎么见彩虹不经历风雨，怎么见彩虹.n6.1 翻译文法翻译文法n6.2 语法制导翻译语法制导翻译n6.3 自顶向下语法制导翻译自顶向下语法制导翻译n6.4 属性翻译文法属性翻译文法n6.5 属性文法的自顶向下翻译属性文法的自顶向下翻译n6.6 自底向上语法制导翻译自底向上语法制导翻译第第6 6章章 语法制导翻译技术语法制导翻译技术n语法制导翻译语法制导翻译n翻译文法、属性翻译文法及其应用翻译文法、属性翻译文法及其应用 学习重点学习重点第第6 6章章 语法制导翻译技术语法制导翻译技术n语义语义：是

2、程序设计语言中按语法规则所构成的各：是程序设计语言中按语法规则所构成的各个语法成分的含义。个语法成分的含义。例如下列例如下列Test语言代码语言代码： int a; b= a+1; write b;n一个源程序经历了词法分析与语法分析，表明它一个源程序经历了词法分析与语法分析，表明它在书写上和语法上是正确的在书写上和语法上是正确的，但不能保证其在语义，但不能保证其在语义上是正确。上是正确。语义分析的任务语义分析的任务：分析程序的含义，分析程序的含义，并作相应的语义处并作相应的语义处理。理。第第6 6章章 语法制导翻译技术语法制导翻译技术n语义分析的功能语义分析的功能 类型和运算合法性检查类型和

3、运算合法性检查：检查运算的合法性与运：检查运算的合法性与运算分量类型的一致性（或相容性），必要时作相应的算分量类型的一致性（或相容性），必要时作相应的类型转换。例如，类型转换。例如，a+b,要求要求a和和b都是算术型（整型或都是算术型（整型或实型），当实型），当a和和b不是同一种类型时，需进行类型转换。不是同一种类型时，需进行类型转换。 确定类型确定类型：确定标识符所关联数据对象的数据类：确定标识符所关联数据对象的数据类型（有时由词法分析完成）。型（有时由词法分析完成）。识别含义识别含义：确定程序中各构造成分组合到一起的：确定程序中各构造成分组合到一起的含义，并作相应的语义处理。这时对可执行语

4、句生成含义，并作相应的语义处理。这时对可执行语句生成中间代码或目标代码。中间代码或目标代码。 第第6 6章章 语法制导翻译技术语法制导翻译技术n语义分析的功能语义分析的功能 一致性检查一致性检查：在很多程序设计语言中要求对象只：在很多程序设计语言中要求对象只能被说明一次。能被说明一次。 控制流检查控制流检查：控制流语句必须转移到合法的地方。：控制流语句必须转移到合法的地方。例如，在例如，在C语言中，语言中，break语句使得控制跳离包括该语语句使得控制跳离包括该语句的句的while、for或或switch语句，如果不存在包括它的这语句，如果不存在包括它的这样的语句，则报告错误。样的语句，则报告

5、错误。其它语义检查其它语义检查：如对象的作用域等。：如对象的作用域等。第第6 6章章 语法制导翻译技术语法制导翻译技术n语义分析的实现语义分析的实现 语义分析是以语法分析的输出（语法分析树或其它语义分析是以语法分析的输出（语法分析树或其它等价的内部中间表示）作为输入，输出则是中间代码，等价的内部中间表示）作为输入，输出则是中间代码，甚至是目标代码。一般情况下，语义分析仅产生中间代甚至是目标代码。一般情况下，语义分析仅产生中间代码，即码，即语义分析与目标代码生成分成两遍来进行。语义分析与目标代码生成分成两遍来进行。第第6 6章章 语法制导翻译技术语法制导翻译技术n语义往往是上下文有关的，只宜于用

6、口语描述，语义往往是上下文有关的，只宜于用口语描述，语语义形式化很困难义形式化很困难。目前，比较流行的语义描述和语义。目前，比较流行的语义描述和语义处理方法是处理方法是语法制导翻译技术语法制导翻译技术。n语法制导翻译技术语法制导翻译技术l基础：基础：形式描述的属性翻译文法形式描述的属性翻译文法l特点：把语法与语义分开，但又特点：把语法与语义分开，但又在语法分析的同在语法分析的同时进行相应的语义工作时进行相应的语义工作l提高了实用性提高了实用性6.1 6.1 翻译文法翻译文法 n例例: 设计一个翻译器，它能将中缀表达式翻译成波兰后设计一个翻译器，它能将中缀表达式翻译成波兰后缀表达式。缀表达式。

7、假设输入串是假设输入串是a+b*c，则，则问题问题: 如何实现这个翻译过程呢？如何实现这个翻译过程呢？a+b*c翻译器翻译器abc*+输入串输入串输出串输出串先看输入串先看输入串a+b*c的推导过程的推导过程:中缀表达式文法：中缀表达式文法： EE+T F(E) ET Fa TT*F Fb TF FcEE+TE+T*FE+T*c E+F*c E+b*c T+b*c F+b*c a+b*c由推导过程由推导过程 EE+TE+T*FE+T*c E+F*c E+b*c T+b*c F+b*c a+b*c得到输入串的语法树：得到输入串的语法树： 记住翻译目标是：记住翻译目标是：abc*+EE+TTT*F

8、FEcba添加叶子结点，用添加叶子结点，用表示输出操作（输出表示输出操作（输出其后的字符）。其后的字符）。EE+TTT*FFEcbabac*+将将符号的叶子结点从左到右连起来，得到符号的叶子结点从左到右连起来，得到abc*+（注意注意:这种带有这种带有的符号串称为的符号串称为动作序列动作序列。 ）执行这个符号序列，得到执行这个符号序列，得到abc*+这就是翻译这就是翻译结果结果!EE+TTT*FFEcbaEE+TTT*FFEcbabac*+问题：问题：如何得到这棵带动作符号的语法树呢？如何得到这棵带动作符号的语法树呢？ 在中缀表达式文法（输入文法）的基础上加入在中缀表达式文法（输入文法）的基础

9、上加入动作符号动作符号，得到翻译文法。得到翻译文法。 EE+T F(E) ET Fa TT*F Fb TF Fc EE+T+ F(E) ET Faa TT*F* Fbb TF Fcc输入文法输入文法翻译文法翻译文法n例例 用输入文法推导用输入文法推导a+b*c的过程如下的过程如下:EE+TE+T*FE+T*c E+F*c E+b*c T+b*c F+b*c a+b*c 用翻译文法进行相同的推导用翻译文法进行相同的推导:EE+T+E+T*F*+E+T*cc *+ E+F*cc *+ E+bb*cc *+ T+bb*cc *+ F+bb*cc *+ aa+bb*cc *+ EE+T F(E) ET

10、 Fa TT*F Fb TF Fc EE+T+ F(E) ET Faa TT*F* Fbb TF Fcc输入文法输入文法翻译文法翻译文法输入序列输入序列活动序列活动序列将活动序列中的输入序将活动序列中的输入序列去掉，得到动作序列：列去掉，得到动作序列： abc*+6.1 6.1 翻译文法翻译文法 n翻译文法翻译文法是上下文无关文法的推广，是上下文无关文法的推广，是在描述语言文法是在描述语言文法规则的右部适当位置加入规则的右部适当位置加入语义动作语义动作得到的。得到的。为了区分文法为了区分文法符号与语义动作，在文法的表示中，将代表语义动作的符符号与语义动作，在文法的表示中，将代表语义动作的符号前

11、面加号前面加动作符号标记动作符号标记来表示。来表示。n输入序列输入序列：用输入：用输入文法通过推导可以得文法通过推导可以得到的终结符号串。到的终结符号串。n活动序列活动序列：用翻译：用翻译文法通过推导得到的文法通过推导得到的符号串。符号串。n动作序列动作序列：从某活：从某活动序列中去掉所有输动序列中去掉所有输入序列，即由所有动入序列，即由所有动作符号组成的符号串。作符号组成的符号串。 输入文法输入序列（终结符号串）推导翻译文法活动序列（终结符号串）推导添加语义动作输入动作序列（终结符号串）输出包括包括6.1 6.1 翻译文法翻译文法 6.1 6.1 翻译文法翻译文法n上例的翻译文法可表示成：上

12、例的翻译文法可表示成： G(E)=Vn,Vt,P,E，其中其中Vn=E, T, FVt=a, b, c, +, *, +, *, a, b, c P= EE+T+， ET， TF， Faa， TT*F*, Fbb，Fcc n在高级程序设计语言的翻译中有各种各样的翻译文法，在高级程序设计语言的翻译中有各种各样的翻译文法，其中的动作符号代表不同的语义动作。其中的动作符号代表不同的语义动作。n在翻译文法中在翻译文法中,如果如果的动作就是输出其后的符号的动作就是输出其后的符号,可可称该文法为称该文法为符号串翻译文法符号串翻译文法。符号串翻译文法是翻译符号串翻译文法是翻译文法中的一种特定类型。文法中的一

13、种特定类型。 6.2 6.2 语法制导翻译语法制导翻译n例：例：根据前面的算术表达式翻译文法，对于输入符号串根据前面的算术表达式翻译文法，对于输入符号串a+b*c， 推导出的活动序列为：推导出的活动序列为：aa+bb*cc*+其中：其中： a+b*c 为输入为输入序列序列 abc*+ 为动作为动作序列序列 如果执行该动作序列如果执行该动作序列中中的动作，则产生输出序列的动作，则产生输出序列abc*+，这就是输入序列，这就是输入序列a+b*c的翻译结果。的翻译结果。 由于这种翻译结果是通过翻译文法获得的，所以就称由于这种翻译结果是通过翻译文法获得的，所以就称为为语法制导翻译语法制导翻译。 n语法

14、制导翻译语法制导翻译：就是给定一输入：就是给定一输入序列序列，根据，根据翻译文法翻译文法获获得翻译该符号得翻译该符号串的活动序列，从活动序列中分离出动作符串的活动序列，从活动序列中分离出动作符号串，然后执行该动作符号串所规定的动作，从而得到翻号串，然后执行该动作符号串所规定的动作，从而得到翻译结果。译结果。6.2 6.2 语法制导翻译语法制导翻译按按 语法制导翻译语法制导翻译的方法来实现语言的翻译的方法来实现语言的翻译1. 首先要根据输入语言的文法，分析各条产生式的语义，首先要根据输入语言的文法，分析各条产生式的语义，即分析他们即分析他们要求计算机所完成的操作要求计算机所完成的操作。2. 分别

15、编出完成这些操作的子程序或程序段分别编出完成这些操作的子程序或程序段(称为称为语义子语义子程序程序或或语义动作语义动作)3. 把这些子程序或程序段的名字把这些子程序或程序段的名字作为动作符号作为动作符号插入到输插入到输入文法各产生式右部的适当位置上，从而实现翻译文入文法各产生式右部的适当位置上，从而实现翻译文法。法。 6.3 6.3 自顶向下语法制导翻译自顶向下语法制导翻译n自顶向下的语法制导翻译有自顶向下的语法制导翻译有递归下降翻译递归下降翻译和和LL(1)翻译。翻译。递归下降翻译递归下降翻译：递归下降翻译器的实现思路与：递归下降翻译器的实现思路与递归下降分析基本相同，要求也一样，即不能有递

16、归下降分析基本相同，要求也一样，即不能有左递归，头符号集不能相交，左递归，头符号集不能相交，只需在适当的位置只需在适当的位置插入实现动作符号的子程序插入实现动作符号的子程序。 6.3 6.3 自顶向下语法制导翻译自顶向下语法制导翻译n例例 算术表达式算术表达式翻译文法如下：翻译文法如下： EE+T+ ET TT*F* TF F(E) Fii注：注：为输出为输出其后的符号串。其后的符号串。解：去掉文法解：去掉文法中的左递归，中的左递归，修改后文法为：修改后文法为： ET+T+ TF*F* F(E)|ii处理处理E的递归下降翻译程序流程图的递归下降翻译程序流程图 处理处理T的递归下降翻译程序流程图

17、的递归下降翻译程序流程图 TF*F*处理处理F的递归下降翻译程序流程图的递归下降翻译程序流程图 F(E)|iiFINPUTSYM=(INPUTSYM=下 一 个 符 号INPUTSYM=iINPUTSYM=)EINPUTSYM=下 一 个 符 号出 口errorOUT(i)INPUTSYM=下 一 个 符 号NYYNYerrorN6.3 6.3 自顶向下语法制导翻译自顶向下语法制导翻译n自顶向下的语法制导翻译有递归下降翻译和自顶向下的语法制导翻译有递归下降翻译和LL(1)翻译。翻译。LL(1)翻译翻译：LL(1)翻译器的实现思路与翻译器的实现思路与LL(1)分分析法基本相同，要求也一样，即不能

18、有左递归，析法基本相同，要求也一样，即不能有左递归，头符号集不能相交，只需在文法适当的位置插入头符号集不能相交，只需在文法适当的位置插入实现动作符号的子程序，并在实现动作符号的子程序，并在LL(1)分析表中加分析表中加入相应的动作符号。入相应的动作符号。 6.3 6.3 自顶向下语法制导翻译自顶向下语法制导翻译n例例(P126) 考考虑下面的输入虑下面的输入文法：文法： AaBcD Ab Bc BaA DcD Db 输入文法的输入文法的LL(1)分析表分析表 设其翻译文法为：设其翻译文法为： AvawBxcyDz Ab Bcr BamA DcDn Dsb6.3 6.3 自顶向下语法制导翻译自顶

19、向下语法制导翻译翻译文法的翻译文法的LL(1)LL(1)分析表分析表 注意：注意：对于翻译文法，动作符号像其它符号一样入栈。但对于翻译文法，动作符号像其它符号一样入栈。但当当动作符号处于栈顶动作符号处于栈顶时，时，无论当前的输入符号是什么，都无论当前的输入符号是什么，都要要执行由该动作符号所规定的操作执行由该动作符号所规定的操作，并将该动作符号从栈，并将该动作符号从栈顶弹出，且不移动读符号指针。顶弹出，且不移动读符号指针。 6.3 6.3 自顶向下语法制导翻译自顶向下语法制导翻译 假如翻译器的分析栈的栈顶符号为假如翻译器的分析栈的栈顶符号为A，且当前输入符号为，且当前输入符号为a，那么将发生的

20、动作是弹出，那么将发生的动作是弹出A，zDycxBwav入栈。入栈。由于此时栈顶为动作符号由于此时栈顶为动作符号v，因此，因此v出栈，并执行由该动作出栈，并执行由该动作符号所规定的操作，对于该符号串翻译文法就是要输出符号所规定的操作，对于该符号串翻译文法就是要输出v，即，即out(v)。紧接着，。紧接着，a出栈，读下一个符号出栈，读下一个符号c。然后，动作符号。然后，动作符号w为栈顶，因此为栈顶，因此w出栈，并执行由该动作符号所规定的操作，出栈，并执行由该动作符号所规定的操作，对于该符号串翻译文法就是要输出对于该符号串翻译文法就是要输出w，即，即out(w)。ac#A.#vv a a ww B

21、.#B.#vv出栈并执行，出栈并执行，a a出栈，读入出栈，读入c,wc,w出栈并执出栈并执行行ac#6.3 6.3 自顶向下语法制导翻译自顶向下语法制导翻译n翻译文法的翻译文法的LL(1)翻译的总控程序总结翻译的总控程序总结：1) 当翻译器的控制执行程序根据当翻译器的控制执行程序根据栈顶符号栈顶符号和和当前输当前输入符号入符号查该表得到元素为空时，则转错误处理程序。查该表得到元素为空时，则转错误处理程序。2)若控制执行程序识别若控制执行程序识别栈顶符号为动作符号栈顶符号为动作符号时，不时，不管当前输入符号是什么，将该动作符号从栈中弹出并管当前输入符号是什么，将该动作符号从栈中弹出并转相应的子

22、程序以完成所需的翻译（转相应的子程序以完成所需的翻译（执行动作执行动作）。对）。对于符号串翻译文法，其语义动作为输出动作符号中的于符号串翻译文法，其语义动作为输出动作符号中的符号串。符号串。 6.4 6.4 属性翻译文法属性翻译文法n引例引例声明语句文法：声明语句文法： TYPE ID ; ，ID 其中其中TYPE代表类型，其值可为代表类型，其值可为int或或 real或或bool。 问题：问题：将输入符号串将输入符号串“int a,b;”翻译为翻译为: int a int b思考：思考：能否通过在文法产生式右部添加动作符号能否通过在文法产生式右部添加动作符号实现该翻译？实现该翻译？6.4 6

23、.4 属性翻译文法属性翻译文法n引例引例声明语句文法：声明语句文法： TYPE ID ; ，ID 其中其中TYPE代表类型，其值可为代表类型，其值可为int或或 real或或bool。 输入：输入：int a,b;输出：输出：int a int b输入串输入串int a,b;”的推导过程：的推导过程： TYPE ID ; TYPE ID，ID ; TYPE ID, ID 问题：问题：无法将文法符号无法将文法符号TYPE、ID与输入符号与输入符号int、a、b关联起来！关联起来！6.4 6.4 属性翻译文法属性翻译文法6.4 6.4 属性翻译文法属性翻译文法 n属性：属性：对文法符号引进一些属性

24、，这些属性代表与对文法符号引进一些属性，这些属性代表与文法符号相关的信息，如类型、值、代码序列、符号文法符号相关的信息，如类型、值、代码序列、符号表内容等。表内容等。n属性值可以在语法分析过程中计算和传递。属性值可以在语法分析过程中计算和传递。n属性一般用标识符表示，通常写在相应文法符号的属性一般用标识符表示，通常写在相应文法符号的下边，它的意义局限于它所在的产生式。下边，它的意义局限于它所在的产生式。属性加工的属性加工的过程就是语义的处理过程。过程就是语义的处理过程。n属性的分类属性的分类综合属性综合属性继承属性继承属性 通常规定，每个文法符号的综合属性和继承属性通常规定，每个文法符号的综合

25、属性和继承属性的交集为空。的交集为空。6.4 6.4 属性翻译文法属性翻译文法 n综合属性综合属性：综合属性的计算规则是按：综合属性的计算规则是按“自下而上自下而上”方式进行，即文法产生式左部符号的某些属性方式进行，即文法产生式左部符号的某些属性根据其根据其右部符号的属性和右部符号的属性和/ /或自己的其它属性计算而得或自己的其它属性计算而得。n在语法树中，如果一个结点的某一属性，其值由子在语法树中，如果一个结点的某一属性，其值由子结点的属性值来计算，则该属性为综合属性。结点的属性值来计算，则该属性为综合属性。n综合属性可用综合属性可用“”来表示。来表示。对终结符号其综合属对终结符号其综合属性

26、具有指定的初始值性具有指定的初始值, ,该初始值由词法分析程序提供。该初始值由词法分析程序提供。n例例 ApXq,rYs,t p=q+s,r=p+t 其中，其中，p是综合属性，是综合属性，r不是综合属性，不是综合属性，q,s,t不能不能确定，需参考其它产生式的属性计算规则才能确定。确定，需参考其它产生式的属性计算规则才能确定。6.4 6.4 属性翻译文法属性翻译文法 n继承属性继承属性：继承属性的计算规则是按：继承属性的计算规则是按“自上而下自上而下”方式进行，即方式进行，即文法产生式右部符号的某些属性根据其文法产生式右部符号的某些属性根据其左部符号的属性和左部符号的属性和/ /或右部的其它符

27、号的某些属性计算或右部的其它符号的某些属性计算而得。而得。n在语法中，如果一个结点的某一属性，其值由该结在语法中，如果一个结点的某一属性，其值由该结点的父结点和点的父结点和/ /或兄弟结点的属性值来计算，则该属性或兄弟结点的属性值来计算，则该属性为继承属性。为继承属性。n继承属性可用继承属性可用“”来表示。开始符号的继承属性来表示。开始符号的继承属性具有初始值。具有初始值。n例例 ApXq,rYs,t p=q+s,r=p+t 显然，显然，r是继承属性。是继承属性。6.4 6.4 属性翻译文法属性翻译文法n例例 算术表达式的属性翻译文法算术表达式的属性翻译文法: SEqANSWERr r=q E

28、p Eq+ Tr p=q+r Ep Tq p=q Tp Tq* Fr p=q*r Tp Fq p=q Fp (Eq) p=q Fp NUMq p=q 6.4 6.4 属性翻译文法属性翻译文法n语义规则语义规则 (语义动作语义动作或或翻译子程序翻译子程序)：为输入文：为输入文法配备计算属性的计算规则，称为语义规则。法配备计算属性的计算规则，称为语义规则。 如上例中，如上例中， p=q+r就是语义规则。就是语义规则。n产生式只能产生符号串，它并未指明所产生的产生式只能产生符号串，它并未指明所产生的符号串的含义是什么。符号串的含义是什么。语义规则给出了一个产生语义规则给出了一个产生式所产生的符号串的

29、含义，而且还根据这种含义式所产生的符号串的含义，而且还根据这种含义规定了对应的加工动作。规定了对应的加工动作。n这些加工动作包括查填各类表格、改变编译程这些加工动作包括查填各类表格、改变编译程序的某些变量的值、打印各种错误信息以及生成序的某些变量的值、打印各种错误信息以及生成中间形式代码等。中间形式代码等。6.4 6.4 属性翻译文法属性翻译文法n属性翻译文法属性翻译文法（或（或属性文属性文法法）：）： 对于某个压缩的上下文对于某个压缩的上下文无关文法，当无关文法，当为文法符号为文法符号引进一组属性引进一组属性，且让该文，且让该文法中的产生式法中的产生式附加上语义附加上语义规则时规则时，称该上

30、下文无关，称该上下文无关文法为属性翻译文法。文法为属性翻译文法。输 入 文 法属 性 翻 译 文 法添 加 属 性 和语 义 动 作翻 译 文 法添 加 语义 动 作添 加 属 性 及其 计 算 规 则6.4 6.4 属性翻译文法属性翻译文法n语义分析的翻译过程：语义分析的翻译过程：步骤步骤1 1 分析输入符号串，建立语法树；分析输入符号串，建立语法树；步骤步骤2 2 从语法树得到描述结点属性间依赖关系的依赖从语法树得到描述结点属性间依赖关系的依赖图，由此依赖图得到语义规则的计算次序；图，由此依赖图得到语义规则的计算次序；步骤步骤3 3 进行语义规则计算，得到翻译结果。进行语义规则计算，得到翻

31、译结果。 n语义分析翻译过程的分类：语义分析翻译过程的分类：自顶向下的翻译自顶向下的翻译自底向上的翻译自底向上的翻译6.4 6.4 属性翻译文法属性翻译文法n自顶向下的语义分析翻译过程的示例自顶向下的语义分析翻译过程的示例声明语句文法：声明语句文法： TYPE ID ; ，ID 其中其中TYPE代表类型，其值可为代表类型，其值可为int或或 real或或bool。 属性翻译文法：属性翻译文法： 1) TYPEtIDnSET_TYPEn1,t1 ； t2=t，t1=t ，n1=n 2) ，IDnSET_TYPEn1,t1 t2=t，t1=t ，n1=n 3 ) 其中，过程其中，过程SET_TYP

32、E输出变量名及其类型。输出变量名及其类型。给出输入符号串给出输入符号串“int a,b;”的语义分析翻译过程。的语义分析翻译过程。输入：输入：int a,b;输出：输出： a int b int6.4 6.4 属性翻译文法属性翻译文法声明语句 ；IDa TYPEint 变量表IDb变量表， int a ,b ；的语法树；的语法树 解：输入符号串解：输入符号串“int a,b;”的语义分析翻译过程：的语义分析翻译过程：声明语句 ；SET_TYPEn1,t2 IDn TYPEt 变量表t2 SET_TYPEn1, t1 IDn变量表t2 ， int a ,b ；的语法树的语法树加入动作符号和属性加

33、入动作符号和属性t2=t，t1=t ，n1=nt2=t，t1=t ，n1=n6.4 6.4 属性翻译文法属性翻译文法声明语句 ；SET_TYPEa, int IDa TYPEint 变量表int SET_TYPEb, int IDb变量表int ， int a ,b ；的翻译树的翻译树解：输入符号串解：输入符号串“int a,b;”的语义分析翻译过程：的语义分析翻译过程：声明语句 ；SET_TYPEn1,t2 IDn TYPEt 变量表t2 SET_TYPEn1, t1 IDn变量表t2 ， int a ,b ；的语法树的语法树加入动作符号和属性加入动作符号和属性t2=t，t1=t ，n1=n

34、t2=t，t1=t ，n1=n6.4 6.4 属性翻译文法属性翻译文法n自底向上的语义分析翻译过程的示例自底向上的语义分析翻译过程的示例 输入算术表达式输入算术表达式3+2*3，应输出，应输出9，给出输入符号串，给出输入符号串3+2*3的语义分析翻译过程。的语义分析翻译过程。 SEANSWER EE+T ET TT*F TF F(E) FNUM SEqANSWERr r=q Ep Eq+ Tr p=q+r Ep Tq p=q Tp Tq* Fr p=q*r Tp Fq p=q Fp (Eq) p=q Fp NUMq p=q 翻译文法翻译文法属性翻译文法属性翻译文法SET+EF*TTFNUM3

35、FNUM2 NUM3 3+ 2* 3的语法树的语法树 NUM3 SE9 T6 +E3 ANSWER9 F3 *T2 T3 F3 F2 NUM2 NUM3 3+ 2* 3的翻译树的翻译树 解：输入符号串解：输入符号串3+2*3的语义分析翻译过程：的语义分析翻译过程：6.4 6.4 属性翻译文法属性翻译文法6.4 6.4 属性翻译文法属性翻译文法n 例例 设计一个属性翻译文法，要求对于输入的中缀表设计一个属性翻译文法，要求对于输入的中缀表达式，经过翻译将输出具有下面性质的四元组代码达式，经过翻译将输出具有下面性质的四元组代码序列序列 1) 输出符号串中的每个双目运算都用一个四元式表示。输出符号串中

36、的每个双目运算都用一个四元式表示。2) 四元组中的四元式的顺序与执行时要完成的运算顺四元组中的四元式的顺序与执行时要完成的运算顺序相同。序相同。3) 每个四元式有四个参数，自左向右的顺序为每个四元式有四个参数，自左向右的顺序为 运算符，左操作数，右操作数，运算结果运算符，左操作数，右操作数，运算结果 例如，翻译器处理表达式例如，翻译器处理表达式a+b将生成如下的四元式将生成如下的四元式 ADD , a , b , t1 其中其中t1是临时变量，保存表达式的结果。是临时变量，保存表达式的结果。翻译器处理表达式翻译器处理表达式a+a*b将生成将生成 MULT , a , b , t1 ADD ,

37、a , t1 , t2 6.4 6.4 属性翻译文法属性翻译文法解：第一步先设计满足上述要求的翻译文法。解：第一步先设计满足上述要求的翻译文法。翻译文法：翻译文法：EE+TADDETTT*FMULTTFF(E)FID 输入文法：输入文法：EE+TETTT*FTFF(E)FID 6.4 6.4 属性翻译文法属性翻译文法属性翻译文法：属性翻译文法：Ex Eq +Tr ADDy,z,t y=q, z=r, t=NEWT，x=tEx Tp x=pTx Tq *Fr MULTy,z,t y=q, z=r, t=NEWT，x=tTx Fp x=pFx (Ep) x=pFx IDp x=p其中，其中，NEW

38、T是一个函数，每次调用它时返回一个新的临是一个函数，每次调用它时返回一个新的临时变量名，临时变量名按产生顺序分别为时变量名，临时变量名按产生顺序分别为t1、t2、等。等。动作符号动作符号ADDy,z,t 输出输出“ADD,y,z,t”，动作符号动作符号MULTy,z,t 输出输出 “MULT,y,z,t”第二步，构造属性和求值规则，把翻译文法构造成属性翻第二步，构造属性和求值规则，把翻译文法构造成属性翻译文法。译文法。6.4 6.4 属性翻译文法属性翻译文法IDa ET+EF*TTFFIDa IDb 表达式表达式a+a*b的语法树的语法树 IDa Et2 Tt1 +Ea Fb *Ta Ta F

39、a Fa IDa IDb 表达式表达式a+a*b的翻译树的翻译树 MULTa,b,t1 ADDa,t1,t2 6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译n自顶向下的语义分析翻译过程示例自顶向下的语义分析翻译过程示例-回顾回顾属性翻译文法：属性翻译文法： 1) TYPEtIDnSET_TYPEn1,t1 ； t2=t，t1=t ，n1=n 2) ，IDnSET_TYPEn1,t1 t2=t，t1=t ，n1=n 3 ) 输入符号串输入符号串“int a,b;”的翻译树如下。的翻译树如下。声明语句声明语句 ；SET_TYPEa,int IDa TYPEint变量表变量表int SET_

40、TYPEb, int IDb变量表变量表int ， 属性值依赖于属性值依赖于上一级的上一级的属性值依赖于左属性值依赖于左边的边的a和和int6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译n分析分析l 按照自顶向下的有序方式对某个属性求值时，应按照自顶向下的有序方式对某个属性求值时，应当确保所需要的当确保所需要的基本值已知基本值已知。n我们需要我们需要对属性计算规则设定约束条件对属性计算规则设定约束条件！l 要求文法必须是要求文法必须是L-属性文法。属性文法。6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译nL- -属性翻译文法属性翻译文法满足下面三个条件：满足下面三个条件：（1

41、1）给定一产生式，其）给定一产生式，其右部符号的继承属性值右部符号的继承属性值是以左是以左部符号的继承属性或出现在给定符号左边的产生式右部部符号的继承属性或出现在给定符号左边的产生式右部符号的任意属性为变元的函数。符号的任意属性为变元的函数。（2 2）给定一产生式，其）给定一产生式，其左部符号的综合属性值左部符号的综合属性值是以左是以左部符号的继承属性或某个右部符号的任意属性为变元的部符号的继承属性或某个右部符号的任意属性为变元的函数。函数。（3 3）给定）给定一动作符号，其综合属性值一动作符号，其综合属性值是以该动作符号是以该动作符号的继承属性为变元的函数。的继承属性为变元的函数。 6. 5

42、 属性文法的自顶向下翻译属性文法的自顶向下翻译n例例 假设文法中有产生式为：假设文法中有产生式为： AI1S2,S3BI4CS5DS6I7,I8EI9 根据根据L-属性的限制条件，属性的限制条件，I4=F(I1)、 I4=123、 I7=G(I1)合法，而合法，而I4=H(S2)、 I4=K(S6,I4)则不合则不合法。法。 n 例例(P134) 假设文法中有产生式为：假设文法中有产生式为： Aa1a2Bb1b2Cc1c2A、B和和C的属性可以按下面的顺序进行求值的属性可以按下面的顺序进行求值 1)A的继承属性的继承属性a1 ； 2) B的继承属性的继承属性b1 ； 3) B的综合属性的综合属

43、性b2； 4) C的继承属性的继承属性c1 ； 5) C的综合属性的综合属性c2 ； 6) A的综合属性的综合属性a2 。 6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译n为了进行属性翻译的程序设计，我们采用下述为了进行属性翻译的程序设计，我们采用下述约定约定：1) 产生式中的产生式中的属性名字属性名字用作用作变量和参数的名字。变量和参数的名字。n例：例： Lab Ei Rj 写成子程序（函数）时，表示为：写成子程序（函数）时，表示为：int L(int a, int b) int i, j; 6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译n为了进行属性翻译的程序设计，我们采用

44、下述为了进行属性翻译的程序设计，我们采用下述约定约定：2) 所有出现在左部的同名非终结符，应具有相同的所有出现在左部的同名非终结符，应具有相同的属性名表。属性名表。在左部同名非终结符属性名表的同一化过在左部同名非终结符属性名表的同一化过程中，程中，属性名称的改动范围仅局限于产生式左部。属性名称的改动范围仅局限于产生式左部。属属性重新命名以后，应修改性重新命名以后，应修改某些属性求值规则。某些属性求值规则。n例例 产生式产生式 Lab EiRj i,j=b，a=i+2 L xyHzw w=y，z=2，x=z+y 按约定按约定2，应改成，应改成 LabEiiRj i,j=b，a=i+2 LabHz

45、w w=b，z=2，a=z+b6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译n为了进行属性翻译的程序设计，我们采用下述为了进行属性翻译的程序设计，我们采用下述约定约定：3) 如果两个属性有相同的值，那么可给它们相同的如果两个属性有相同的值，那么可给它们相同的名字，但对于左部符号的属性值相等时，不能改变成名字，但对于左部符号的属性值相等时，不能改变成相同的名字。相同的名字。 n例例 对规则对规则LabaBcCd ,当当c,d=a时，可写成时，可写成: LabaBaCa但当但当b=a时，上式时，上式不能写成不能写成LaaaBaCa这是因为过程这是因为过程L(int a,int b)不可写成

46、不可写成L(int a,int a)。 6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译n采用采用C语言编写语言编写L-属性文法递归下降翻译程序时采用属性文法递归下降翻译程序时采用的方法：的方法：1)1)形式参数：形式参数：产生式左部非终结符的产生式左部非终结符的属性名表属性名表设计设计成相应过程的成相应过程的形式参数表形式参数表。 继承属性继承属性值形参值形参( (即简单变量即简单变量) ) 综合属性综合属性指针变量。指针变量。2)2)局部变量：局部变量：在产生式中，与左部属性名不同的属在产生式中，与左部属性名不同的属性名变成相应过程的性名变成相应过程的局部变量局部变量。3)3)非终结

47、符的代码：非终结符的代码：产生式右部的每个非终结符的产生式右部的每个非终结符的过程调用，过程调用，该非终结符的属性作为实参该非终结符的属性作为实参。要注意：。要注意：如如果实参是简单变量，形参是指针变量，调用时实参应果实参是简单变量，形参是指针变量，调用时实参应为简单变量的地址。为简单变量的地址。6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译n采用采用C语言编写语言编写L-属性文法递归下降翻译程序时采属性文法递归下降翻译程序时采用的方法：用的方法：4)输入符号的代码：输入符号的代码：对文法中出现的每个输入符号对文法中出现的每个输入符号(即终结符号即终结符号)，将赋值语句插入到过程中它所

48、对应的，将赋值语句插入到过程中它所对应的NEXTSYM之前，把保存在读符号程序之前，把保存在读符号程序NEXTSYM中的中的终结符号属性终结符号属性(某个全局变量中某个全局变量中)赋给输入符号属性中的赋给输入符号属性中的每个属性变量。每个属性变量。5)动作符号的代码：动作符号的代码：对出现在文法中的每个动作符号，对出现在文法中的每个动作符号，插入代码便于对动作符号的综合属性进行计算，并且把插入代码便于对动作符号的综合属性进行计算，并且把结果赋给对应于该综合属性的变量，然后输出相应的符结果赋给对应于该综合属性的变量，然后输出相应的符号。号。6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译n

49、采用采用C语言编写语言编写L-属性文法递归下降翻译程序时采用属性文法递归下降翻译程序时采用的方法：的方法：4)输入符号的代码：输入符号的代码：对文法中出现的每个输入符号对文法中出现的每个输入符号(即即终结符号终结符号)，将赋值语句插入到过程中它所对应的，将赋值语句插入到过程中它所对应的NEXTSYM之前，把保存在读符号程序之前，把保存在读符号程序NEXTSYM中的中的终结符号属性终结符号属性(某个全局变量中某个全局变量中)赋给输入符号属性中的赋给输入符号属性中的每个属性变量。每个属性变量。5)动作符号的代码：动作符号的代码：对出现在文法中的每个动作符号，对出现在文法中的每个动作符号，插入代码便

50、于对动作符号的综合属性进行计算，并且把插入代码便于对动作符号的综合属性进行计算，并且把结果赋给对应于该综合属性的变量，然后输出相应的符结果赋给对应于该综合属性的变量，然后输出相应的符号。号。6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译n采用采用C语言编写语言编写L-属性文法递归下降翻译程序时采属性文法递归下降翻译程序时采用的方法：用的方法：6)属性规则的代码：属性规则的代码：与每个产生式有关的属性求值规与每个产生式有关的属性求值规则，插入其代码以便对属性求值规则的右部求值，并把则，插入其代码以便对属性求值规则的右部求值，并把结果赋给该规则左部的每个变量。可以把这些代码放在结果赋给该规

51、则左部的每个变量。可以把这些代码放在属性计算规则的所有自变量已知之后，且函数值被使用属性计算规则的所有自变量已知之后，且函数值被使用之前的任何地方。之前的任何地方。7)主程序：主程序：C语言都是从语言都是从MAIN函数开始运行。在函数开始运行。在MAIN函数中，对文法的开始符号，其相应的每一个综函数中，对文法的开始符号，其相应的每一个综合属性的名字变成主程序的局部变量，然后调用开始符合属性的名字变成主程序的局部变量，然后调用开始符号对应的过程。在调用时，如果实参对应开始符号的继号对应的过程。在调用时，如果实参对应开始符号的继承属性，则对每个继承属性以该属性的初始值作为值参承属性，则对每个继承属

52、性以该属性的初始值作为值参传入，对每个综合属性取该属性的局部变量的地址传入。传入，对每个综合属性取该属性的局部变量的地址传入。6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译n例例 算术表达式属性翻译文法如下算术表达式属性翻译文法如下,用用C语言实现其语言实现其递归下降翻译器递归下降翻译器。EtTpEptEpt+Tr ADDp,r,t0 E t0t t0=NEWT Ept t=pTtFpTptTpt*Fr MULTp,r,t0 Tt0t t0=NEWT Tpt t=pFp -(Ep) | IDp 6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译main() /主程序主程序int e

53、s=0,t; printf(请输入算术表达式请输入算术表达式(操作数只能是单个操作数只能是单个字母字母)：);ch=getchar();printf(输出四元式为：输出四元式为：n);es=E(&t); /调分析表达式调分析表达式E的翻译程序，的翻译程序， EtTpEptif (es=0) printf(n翻译成功翻译成功!n);else printf(n表达式有语法错误表达式有语法错误!n);6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译/产生式产生式EtTpEpt的翻译子程序，的翻译子程序，t为综为综合属性合属性,形参用指针变量形参用指针变量int E(int *t) in

54、t es=0; int p; es=T(&p); /调分析调分析T子程序子程序 es=E1(p,t); /调分析调分析E子程序子程序 ，t是指针是指针 return(es);E(int *t)int pT(&p)E(p,t)return/产生式产生式Ept+Tr ADDp,r,t0 Et0t|的的翻译子程序，其翻译子程序，其中，中，p为继承属性，形参用整型变量，为继承属性，形参用整型变量，t为综合属性，形参为综合属性，形参用指针变量用指针变量int E1(int p,int *t) int r,es=0,t0; if (ch=+) ch=getchar(); es=T(&

55、;r); t0=NEWT(); /产生一个临时变量产生一个临时变量 printf(ADD,%c,%c,%cn,p,r,t0); es=E1(t0,t); return(es); else *t=p;return(0);E(int p,int *t)int r,t0;+?nextsymT(&r)t0=NEWT()E(t0,t)return*t=pnyn n/返回一个临时变量返回一个临时变量,顺序产生顺序产生A、B、.、Z，最，最多产生多产生26个临时变量个临时变量int NEWT() static int i=64;/设置设置i为静态变量确保下次调用为静态变量确保下次调用 时时i为上次调

56、用的结果为上次调用的结果 i=i+1; return(i);6. 5 6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译/产生式产生式TtFpTpt的翻译子程序，的翻译子程序，t为为综合属性综合属性,形参用指针变量形参用指针变量int T(int *t) int es=0,p; es=F(&p); /调分析调分析F子程序子程序 es=T1(p,t); /调分析调分析T子程序子程序 return(es);T(int *t)int pF(&p)T(p,t)return/产生式产生式Tpt*Fr MULTp,r,t0 Tt0t

57、 |的翻译子程序的翻译子程序int T1(int p,int *t) int r,es=0,t0;if (ch=*) ch=getchar(); es=F(&r); t0=NEWT(); /产生一个临时变量产生一个临时变量 printf(MULT,%c,%c,%cn,p,r,t0); es=T1(t0,t); return(es); else *t=p; return(0); T(int p,int *t)int r,t0;*?nextsymF(&r)t0=NEWT()T(t0,t)return*t=p ny/产生式产生式Fp (Ep) | IDp 的翻译子程序的翻译子程序in

58、t F(int *p) /分析分析F子程序子程序 int es=0; if (ch=( ) ch=getchar(); es=E(p); /调分析调分析E子程序子程序 if (ch!=) return(3); else ch=getchar();return(es); else if (isalpha(ch) /判断是否为字母判断是否为字母 *p=ch; ch=getchar(); return(es); else return(4); F(int *p)(?nextsymE(p)nextsymreturn*p=ch ny)?nextsym字母?yy6. 5 属性文法的自顶向下翻译属性文法的自

59、顶向下翻译运行这段程序，若输入：运行这段程序，若输入： a*(b+c)+b*dADD,b,c,AMULT,a,A,BMULT,b,d,CADD,B,C,D输出四元式序列为：输出四元式序列为： 其中其中A、B、C、D都都是临时变量。是临时变量。 6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译n要要实现属性翻译文法的实现属性翻译文法的LL(1)翻译器翻译器，是对翻译文法的是对翻译文法的LL(1)翻译器进行扩充翻译器进行扩充,方法是方法是(P139)：对于所有符号，不仅对于所有符号，不仅符号进分析栈，其属性也同时进栈。符号进分析栈，其属性也同时进栈。即将栈符号设计为两部分，符号名和即将栈符号

60、设计为两部分，符号名和属性域。任何栈符号的域都是在栈内属性域。任何栈符号的域都是在栈内的一些存贮单元。的一些存贮单元。A属性属性 A1属性属性 A2B属性属性B1C#n例例(P139) 对符号串对符号串ABC，假定，假定A有有两个属性，两个属性，B有一个属性而有一个属性而C没有任何没有任何属性。若符号名也占用一个存贮单元，属性。若符号名也占用一个存贮单元，则相应则相应A的栈符号用三个存贮单元，的栈符号用三个存贮单元，B用二个，用二个，C用一个。用一个。6. 5 属性文法的自顶向下翻译属性文法的自顶向下翻译n例例(P139) 已知文法：已知文法： SEpANSWERr r=p Ep+EqErADDA1,A2R A1=q,A2=r,R=A1+A2,p=R Ep*