最新【考研计算机专业课】天津大学 编译原理讲义 概述5.1(共23张PPT课件).pptx

5.1 概述概述(i sh)5.1.1 翻译翻译(fny)文法文法文法文法用于描述用于描述(mio sh)构成语言的全部句子的集合。构成语言的全部句子的集合。翻译文法翻译文法是在文法的基础上增加翻译功能，一边进行语法是在文法的基础上增加翻译功能，一边进行语法分析，一边进行翻译。分析，一边进行翻译。第一页，共二十三页。例例，设计一个处理器，其输入为中缀表达式，输出，设计一个处理器，其输入为中缀表达式，输出(shch)(shch)为后缀表达式。为后缀表达式。 例，中缀式例，中缀式a+b*c，后缀式，后缀式abc*+。输入输入(shr)(shr)序列是序列是: : a + b * c 处理器的输入输出活动是处理器的输入输出活动是: : RD(a) PT(a) RD(+) RD(b) PT(b) RD(*) RD(c) PT(c) PT(*) PT(+) 用输入符号本身用输入符号本身(bnshn)(bnshn)代表输入操作，用代表输入操作，用开始的符号串代表开始的符号串代表输出操作输出操作: : a a + b b * c c * + 输出结果是输出结果是: : a b c * + 称为动作符号标记，由称为动作符号标记，由开始的符号串称为一个动作符号。开始的符号串称为一个动作符号。 第二页，共二十三页。由文法由文法(wnf)构造翻译文法构造翻译文法(wnf):1. E E + T 2. E T 3. T T * F 4. T F 5. F ( E ) 6. F a 7. F b 8. F c 1. E E + T + 2. E T 3. T T * F * 4. T F 5. F ( E ) 6. F a a 7. F b b 8. F c c 第三页，共二十三页。结论结论(jiln):通过输入文法通过输入文法(wnf)(wnf)推导产生出某个输入序列推导产生出某个输入序列 通过翻译文法通过翻译文法(wnf)(wnf)的推导，便可得到相应的活动序的推导，便可得到相应的活动序列列 例例， 句型句型 (a+b)*c 输入文法的最左推导输入文法的最左推导: : E T T*F F*F (E)*F (E+T)*F (a+b)*c *翻译文法的最左推导翻译文法的最左推导: : E T T*F* F*F* (E)*F* (a a + b b +) * c c *ab+c*第四页，共二十三页。定义定义: : 翻译文法翻译文法是一个上下文无关是一个上下文无关(wgun)(wgun)文法。在该文法中终文法。在该文法中终结符号集由输入符号结符号集由输入符号 (即原来终结符即原来终结符)和动作符号组成。和动作符号组成。 例例，上述，上述(shngsh)文法文法: GT=(VN,VT, P, E) VN=E, T, F VT=a, b, c, +, *, (, ), a , b, c, +, * P=产生式产生式 在此文法中，在此文法中，(语义动作语义动作(dngzu)(dngzu)仅仅是输出该动作符号的动作仅仅是输出该动作符号的动作标记符标记符后面的符号串。这里后面的符号串。这里, 该翻译文法是符号串翻译文法。该翻译文法是符号串翻译文法。 第五页，共二十三页。5.1.2 属性翻译属性翻译(fny)文法文法翻译文法中的符号，包括翻译文法中的符号，包括(boku)非终结符，终结符和动作非终结符，终结符和动作符号都是有穷集合中的符号，都没有值的概念。符号都是有穷集合中的符号，都没有值的概念。 扩充翻译文法的概念扩充翻译文法的概念(ginin)，即让符号包含值部分。，即让符号包含值部分。 符号所具有的值部分称符号的属性。符号所具有的值部分称符号的属性。 第六页，共二十三页。(1) 将符号将符号(fho)的属性与语法树的节点联系起来，输入和输出值的属性与语法树的节点联系起来，输入和输出值之间的关系可以通过产生式来表示。之间的关系可以通过产生式来表示。 例例，设有一词法，设有一词法(cf)分析程序能够输出下列单词符号：分析程序能够输出下列单词符号：(, ), +, *, c 考虑考虑(kol)(kol)设计一个语法分析程序，它设计一个语法分析程序，它接受接受上述符号组成的算术表达上述符号组成的算术表达式，并式，并输出输出这个表达式的值。这个表达式的值。 翻译文法是翻译文法是: : 1. S E ANSWER 5. T F 2. E E + T 6. F ( E ) 3. E T 7. F c 4. T T * F 1. 综合属性综合属性第七页，共二十三页。语法树为语法树为 例例，输入序列：输入序列：(C3 + C9) * (C2 + C41) “数字串数字串”表示该符表示该符号的值部分号的值部分 接受接受(jishu):第八页，共二十三页。输出输出(shch):显然显然, 语法树中的非终结符语法树中的非终结符E, T, F的每次出现都是表示的每次出现都是表示(biosh)(biosh)该该输入表达式的一个子表达式，其值部分应是其子表达式的计算结输入表达式的一个子表达式，其值部分应是其子表达式的计算结果。果。例例，产生产生(chnshng)(chnshng)式式: F c T F 则则F的值部分等于的值部分等于c的值部分，的值部分，T的值部分等于的值部分等于F的值部分。的值部分。 计算表达式的实际过程是计算表达式的实际过程是: : 先分别计算各子表达式的值，再计先分别计算各子表达式的值，再计算父表达式的值，直到求得整个表达值。算父表达式的值，直到求得整个表达值。第九页，共二十三页。表示表示(biosh)(biosh)属性计算的语属性计算的语法树法树 第十页，共二十三页。(2) 为了形式地表示上述表达式的求值过程，可以将产生式改写，为了形式地表示上述表达式的求值过程，可以将产生式改写，对出现在每一个产生式中的每一个值赋以一个不同的名字，而后使对出现在每一个产生式中的每一个值赋以一个不同的名字，而后使用这些用这些(zhxi)(zhxi)名字说明各产生式中各符号的值部分之间的关系名字说明各产生式中各符号的值部分之间的关系 (求求值规则值规则) 。 例例，计算表达式值的符号串翻译文法可改写为：，计算表达式值的符号串翻译文法可改写为： 1.S Eq ANSWERr r = q2.Ep Eq + Tr p = q + r 3.Ep Tq p = q 4.Tp Tq * Fr p = q * r 5.Tp Fq p = q6.Fp (Eq) p = q7.Fp cq p = q 第十一页，共二十三页。产生式左部符号的属性值是通过产生式左部符号的属性值是通过(tnggu)(tnggu)计算右部符号的计算右部符号的属性值得来的。属性值得来的。 在语法树中，每个非终结符的属性值都是由它下面的那在语法树中，每个非终结符的属性值都是由它下面的那些些(nxi)(nxi)符号符号 (子结点子结点) 来确定。来确定。 这种可通过这种可通过(tnggu)(tnggu)自底向上进行求值的属性，称自底向上进行求值的属性，称综合属性综合属性。 第十二页，共二十三页。2.继承继承(jchng)属性属性例例，(说明句说明句)文法文法: : 1.1. 说明说明TYPE V变量表变量表2.2. 变量表变量表，V变量表变量表3.3. 变量表变量表integer a,b,c第十三页，共二十三页。翻译文法翻译文法: : 1.1. 说明说明TYPE V SET-TYPE 变量表变量表 2.2. 变量表变量表, V SET-TYPE 变量表变量表 3.3. 变量表变量表 动作符号动作符号SET-TYPE调用调用(dioyng)过程过程SET-TYPE，把，把TYPE的值的值(类型类型)填到各个变量在符号表中的项的类型域中。填到各个变量在符号表中的项的类型域中。动作符号动作符号SET-TYPE的值部分有两个属性的值部分有两个属性(shxng)(shxng): : SET-TYPE变量变量,类型类型 第十四页，共二十三页。变量表的类型变量表的类型(lixng)(lixng)值，这可采用自上向下传递方法求得来自值，这可采用自上向下传递方法求得来自产生式左部变量表属性值。产生式左部变量表属性值。 翻译翻译(fny)(fny)文法变成文法变成: : 1.1.说明说明(shumng)(shumng) TYPEt Vp SET-TYPEp1,t1 变量表变量表t2 t1 = t2 = t, p1 = p 2. 2. 变量表变量表t ，Vp SET-TYPEp1,t1 变量表变量表t2 t1 = t2 = t, p1 = p 3. 3. 变量表变量表 第十五页，共二十三页。产生式右部的符号的属性产生式右部的符号的属性(shxng)(shxng)值，是由其左部符号或同一右值，是由其左部符号或同一右部的其左部的符号的属性部的其左部的符号的属性(shxng)(shxng)值求得的值求得的. 这种求值规则求得的这种求值规则求得的属性称属性称继承属性继承属性。 符号串符号串TYPEREAL V1, V2, V3的语法的语法(yf)(yf)树树 说明说明TYPEREALV1SET-TYPE1,REAL 变量表变量表REAL 变量表变量表REAL SET-TYPE2,REAL V2,变量表变量表REAL SET-TYPE3,REAL V3,第十六页，共二十三页。3. 属性翻译属性翻译(fny)文法文法定义定义: : 属性翻译文法是带有下列属性翻译文法是带有下列(xili)(xili)说明的翻译文法说明的翻译文法1. 每个终结符，非终结符和动作符号都有一个每个终结符，非终结符和动作符号都有一个(y )(y )与其相关的属性的与其相关的属性的有穷集，且每个属性都有一个有穷集，且每个属性都有一个(y )(y )值域。值域。 2. 每一个非终结符号和动作符号的属性可分为两类：继承的或综合的。每一个非终结符号和动作符号的属性可分为两类：继承的或综合的。 3. 继承属性求值规则继承属性求值规则: :(1) 开始符号开始符号的每个继承属性具有指定的初始值。的每个继承属性具有指定的初始值。 (2) 给定一产生式，该产生式右边符号的继承属性用该产生式左部或同给定一产生式，该产生式右边符号的继承属性用该产生式左部或同一右部其左边其他符号的属性值计算。一右部其左边其他符号的属性值计算。 第十七页，共二十三页。4.4. 综合综合(zngh)(zngh)属性求值规则属性求值规则: : (1) 每一个每一个输入符号输入符号的综合的综合(zngh)(zngh)属性具有指定的初始值。属性具有指定的初始值。 (2) 给定给定(i dn)(i dn)一产生式一产生式, 其左部非终结符的综合属性值用该产生式其左部非终结符的综合属性值用该产生式右部的某些符号的属性值计算。右部的某些符号的属性值计算。 在构造属性翻译文法的产生式时，每个符号的属性都用标在构造属性翻译文法的产生式时，每个符号的属性都用标识符表示，称为识符表示，称为属性变量名属性变量名。 继承属性继承属性属性变量名属性变量名 综合属性综合属性属性变量名属性变量名 例例，X bY 写成写成: Xpq bs Yyu 第十八页，共二十三页。5.1.3 语法制导语法制导(zhdo)翻译翻译语法制导翻译语法制导翻译: 在语法分析过程中，随着分析的进展，根据在语法分析过程中，随着分析的进展，根据(gnj)(gnj)每个产生式所对应的语义子程序每个产生式所对应的语义子程序 (语义动作语义动作) 进行翻译进行翻译 (产生中间代产生中间代码码) 的一种办法。的一种办法。 当一个产生式获得匹配当一个产生式获得匹配 (自上而下分析自上而下分析(fnx)(fnx) 和用于归约和用于归约 (自下而上自下而上分析分析) 时，此产生式对应的语义子程序进入工作。时，此产生式对应的语义子程序进入工作。一个一个语义子程序描述了一个产生式所对应的翻译工作语义子程序描述了一个产生式所对应的翻译工作: : 改变编译程序某改变编译程序某些变量的值；查填各种符号表；诊察与报告源程序错误；产生中间代码些变量的值；查填各种符号表；诊察与报告源程序错误；产生中间代码等等。等等。 第十九页，共二十三页。语义动作的描述语义动作的描述(mio sh)(mio sh)约定约定:1. 对每个文法符号对每个文法符号X的各方面的值的各方面的值 (属性属性(shxng)(shxng) 进行描述，如用进行描述，如用X.TYPE，X.CAT，X.VAL表示表示“类型类型”，“种属种属”，“值值”。 2. 对于同一对于同一(tngy)(tngy)产生式中同一产生式中同一(tngy)(tngy)符号的多次出现，用上角符号的多次出现，用上角标区别。如标区别。如EE（1）+E（2） 3. 每个产生式对应的语义动作写在该产生式的花括号内，如每个产生式对应的语义动作写在该产生式的花括号内，如。 第二十页，共二十三页。例例，定义，定义(dngy)算术表达式算术表达式E的的“值值”的语义的语义:(1) E E(1)+E(2) E.VAL = E(1).VAL+E(2).VAL(2) E 6 E.VAL = 6(3) E 9 E.VAL = 9第第( (1) )产生式的语义动作产生式的语义动作(dngzu)(dngzu)规定了规定了: : E的语义值的语义值E.VAL等于等于E(1)和和E(2)的语义值的语义值E(1).VAL和和E(2).VAL之之“和和”；E的语义值的语义值E.TYPE等于等于E(1).TYPE和和E(2).TYPE。 第第( (2) )和第和第( (3) )产生式的语义动作产生式的语义动作(dngzu)(dngzu)直接规定了直接规定了E的语义的语义值为值为6或或9。 按照其语义动作按照其语义动作，就可以，就可以一步步计算出表达式一步步计算出表达式E的值。的值。 第二十一页，共二十三页。如果语义动作不是简单的计值程序，而是某种中间代码的产生如果语义动作不是简单的计值程序，而是某种中间代码的产生程序程序, 那么随着那么随着(su zhe)(su zhe)语法分析的进展，这种代码也逐步生成语法分析的进展，这种代码也逐步生成。实际上实际上, 语法制导翻译语法制导翻译(fny)(fny)既可以用来产生中间代码既可以用来产生中间代码, 也可以也可以用来产生目标指令，甚至可用来对输入串进行解释执行。用来产生目标指令，甚至可用来对输入串进行解释执行。 下面就通过介绍几种常见的中间代码形式，帮助大家下面就通过介绍几种常见的中间代码形式，帮助大家(dji)初步了解初步了解如何通过语法制导来产生中间代码。如何通过语法制导来产生中间代码。第二十二页，共二十三页。内容(nirng)总结5.1 概述。例，上述文法: GT=(VN,VT, P, E)。VN=E, T, F。例，设有一词法分析程序能够输出下列单词(dnc)符号：(, ), +, *, c。变量表, V SET-TYPE 变量表。动作符号SET-TYPE调用过程SET-TYPE，把TYPE的值(类型)填到各个变量在符号表中的项的类型域中。动作符号SET-TYPE的值部分有两个属性: SET-TYPE变量,类型第二十三页，共二十三页。