【精品】【考研计算机专业课】天津大学 编译原理讲义 概述5.1精品ppt课件.ppt
【考研计算机专业课】天津大学 编译原理讲义 概述5.1例例，设计一个处理器，其输入为中缀表达式，输出为后缀表，设计一个处理器，其输入为中缀表达式，输出为后缀表达式。达式。例，中缀式例，中缀式a+b*c，后缀式，后缀式abc*+。输入序列是输入序列是:a+b*c 处理器的输入输出活动是处理器的输入输出活动是:RD(a)PT(a)RD(+)RD(b)PT(b)RD(*)RD(c)PT(c)PT(*)PT(+)用输入符号本身代表输入操作，用用输入符号本身代表输入操作，用开始的符号串代表开始的符号串代表输出操作输出操作:a a+b b*c c*+输出结果是输出结果是:a b c*+称为动作符号标记，由称为动作符号标记，由开始的符号串称为一个动作符号。开始的符号串称为一个动作符号。由文法构造翻译文法由文法构造翻译文法: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 结论结论:通过输入文法推导产生出某个输入序列通过输入文法推导产生出某个输入序列 通过翻译文法的推导，便可得到相应的活动序列通过翻译文法的推导，便可得到相应的活动序列 例例，句型句型(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*定义定义:翻译文法翻译文法是一个上下文无关文法。在该文法中终是一个上下文无关文法。在该文法中终结符号集由输入符号结符号集由输入符号(即原来终结符即原来终结符)和动作符号组成。和动作符号组成。例例，上述文法，上述文法:GT=(VN,VT,P,E)VN=E,T,F VT=a,b,c,+,*,(,),a,b,c,+,*P=产生式产生式 在此文法中，在此文法中，(语义动作语义动作)仅仅是输出该动作符号的动作标记仅仅是输出该动作符号的动作标记符符后面的符号串。这里后面的符号串。这里,该翻译文法是符号串翻译文法。该翻译文法是符号串翻译文法。语法树为语法树为 例例，输入序列：输入序列：(C3+C9)*(C2+C41)“数字串数字串”表示该符号表示该符号的值部分的值部分 接受接受:输出输出:显然显然,语法树中的非终结符语法树中的非终结符E,T,F的每次出现都是表示该输的每次出现都是表示该输入表达式的一个子表达式，其值部分应是其子表达式的计入表达式的一个子表达式，其值部分应是其子表达式的计算结果。算结果。例例，产生式产生式:F c T F 则则F的值部分等于的值部分等于c的值部分，的值部分，T的值部分等于的值部分等于F的值部分。的值部分。计算表达式的实际过程是计算表达式的实际过程是:先分别计算各子表达式的值，先分别计算各子表达式的值，再计算父表达式的值，直到求得整个表达值。再计算父表达式的值，直到求得整个表达值。表示属性计算的语法树表示属性计算的语法树(2)为了形式地表示上述表达式的求值过程，可以将产为了形式地表示上述表达式的求值过程，可以将产生式改写，对出现在每一个产生式中的每一个值赋以一生式改写，对出现在每一个产生式中的每一个值赋以一个不同的名字，而后使用这些名字说明各产生式中各符个不同的名字，而后使用这些名字说明各产生式中各符号的值部分之间的关系号的值部分之间的关系(求值规则求值规则)。例例，计算表达式值的符号串翻译文法可改写为：，计算表达式值的符号串翻译文法可改写为：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 产生式左部符号的属性值是通过计算右部符号的属性产生式左部符号的属性值是通过计算右部符号的属性值得来的。值得来的。在语法树中，每个非终结符的属性值都是由它下面的在语法树中，每个非终结符的属性值都是由它下面的那些符号那些符号(子结点子结点)来确定。来确定。这种可通过自底向上进行求值的属性，称这种可通过自底向上进行求值的属性，称综合属性综合属性。2.继承属性继承属性例例，(说明句说明句)文法文法: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调用过程调用过程SET-TYPE，把，把TYPE的值的值(类型类型)填到各个变量在符号表中的项的类型域中。填到各个变量在符号表中的项的类型域中。动作符号动作符号SET-TYPE的值部分有两个属性的值部分有两个属性:SET-TYPE变量变量,类型类型 变量表的类型值，这可采用自上向下传递方法求得来自产生变量表的类型值，这可采用自上向下传递方法求得来自产生式左部变量表属性值。式左部变量表属性值。翻译文法变成翻译文法变成:1.1.说明说明 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.变量表变量表 产生式右部的符号的属性值，是由其左部符号或同一右部的产生式右部的符号的属性值，是由其左部符号或同一右部的其左部的符号的属性值求得的其左部的符号的属性值求得的.这种求值规则求得的属性称这种求值规则求得的属性称继继承属性承属性。符号串符号串TYPEREAL V1,V2,V3的语法树的语法树 说明说明TYPEREALV1SET-TYPE1,REAL 变量表变量表REAL 变量表变量表REAL SET-TYPE2,REAL V2,变量表变量表REAL SET-TYPE3,REAL V3,3.属性翻译文法属性翻译文法定义定义:属性翻译文法是带有下列说明的翻译文法属性翻译文法是带有下列说明的翻译文法1.每个终结符，非终结符和动作符号都有一个与其相关的属性每个终结符，非终结符和动作符号都有一个与其相关的属性的有穷集，且每个属性都有一个值域。的有穷集，且每个属性都有一个值域。2.每一个非终结符号和动作符号的属性可分为两类：继承的或每一个非终结符号和动作符号的属性可分为两类：继承的或综合的。综合的。3.继承属性求值规则继承属性求值规则:(1)开始符号开始符号的每个继承属性具有指定的初始值。的每个继承属性具有指定的初始值。(2)给定一产生式，该产生式右边符号的继承属性用该产生式给定一产生式，该产生式右边符号的继承属性用该产生式左部或同一右部其左边其他符号的属性值计算。左部或同一右部其左边其他符号的属性值计算。4.4.综合属性求值规则综合属性求值规则:(1)每一个每一个输入符号输入符号的综合属性具有指定的初始值。的综合属性具有指定的初始值。(2)给定一产生式给定一产生式,其左部非终结符的综合属性值用该产生式右其左部非终结符的综合属性值用该产生式右部的某些符号的属性值计算。部的某些符号的属性值计算。在构造属性翻译文法的产生式时，每个符号的属性都用标识在构造属性翻译文法的产生式时，每个符号的属性都用标识符表示，称为符表示，称为属性变量名属性变量名。继承属性继承属性属性变量名属性变量名 综合属性综合属性属性变量名属性变量名 例例，X bY 写成写成:Xpq bs Yyu 5.1.3 语法制导翻译语法制导翻译语法制导翻译语法制导翻译:在语法分析过程中，随着分析的进展，根据在语法分析过程中，随着分析的进展，根据每个产生式所对应的语义子程序每个产生式所对应的语义子程序(语义动作语义动作)进行翻译进行翻译(产生产生中间代码中间代码)的一种办法。的一种办法。当一个产生式获得匹配当一个产生式获得匹配(自上而下分析自上而下分析)和用于归约和用于归约(自下而自下而上分析上分析)时，此产生式对应的语义子程序进入工作。时，此产生式对应的语义子程序进入工作。一个一个语义子程序描述了一个产生式所对应的翻译工作语义子程序描述了一个产生式所对应的翻译工作:改变改变编译程序某些变量的值；查填各种符号表；诊察与报告源程编译程序某些变量的值；查填各种符号表；诊察与报告源程序错误；产生中间代码等等。序错误；产生中间代码等等。语义动作的描述约定语义动作的描述约定:1.对每个文法符号对每个文法符号X的各方面的值的各方面的值(属性属性)进行描述，如用进行描述，如用X.TYPE，X.CAT，X.VAL表示表示“类型类型”，“种属种属”，“值值”。2.对于同一产生式中同一符号的多次出现，用上角标区别。对于同一产生式中同一符号的多次出现，用上角标区别。如如EE（1）+E（2）3.每个产生式对应的语义动作写在该产生式的花括号内，每个产生式对应的语义动作写在该产生式的花括号内，如如。例例，定义算术表达式，定义算术表达式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)产生式的语义动作规定了产生式的语义动作规定了:E的语义值的语义值E.VAL等于等于E(1)和和E(2)的语义值的语义值E(1).VAL和和E(2).VAL之之“和和”；E的语义值的语义值E.TYPE等于等于E(1).TYPE和和E(2).TYPE。第第(2)和第和第(3)产生式的语义动作直接规定了产生式的语义动作直接规定了E的语义值的语义值为为6或或9。按照其语义动作按照其语义动作，就可以，就可以一步步计算出表达式一步步计算出表达式E的值。的值。如果语义动作不是简单的计值程序，而是某种中间代码的产如果语义动作不是简单的计值程序，而是某种中间代码的产生程序生程序,那么随着语法分析的进展，这种代码也逐步生成那么随着语法分析的进展，这种代码也逐步生成。实际上实际上,语法制导翻译既可以用来产生中间代码语法制导翻译既可以用来产生中间代码,也可以用也可以用来产生目标指令，甚至可用来对输入串进行解释执行。来产生目标指令，甚至可用来对输入串进行解释执行。下面就通过介绍几种常见的中间代码形式，帮助大家初步下面就通过介绍几种常见的中间代码形式，帮助大家初步了解如何通过语法制导来产生中间代码。了解如何通过语法制导来产生中间代码。
