《[理学]第5章 语法制导翻译及中间代码》由会员分享，可在线阅读，更多相关《[理学]第5章 语法制导翻译及中间代码（69页珍藏版）》请在金锄头文库上搜索。
1、第5章 语法制导翻译及中间代码生成, 5.1 语法制导翻译 5.2 中间代码的形式 5.3 简单赋值语句的翻译 5.4 布尔表达式的翻译 5.5 控制语句的翻译,5.1 语法制导翻译,静态语义审查：审查每个语法结构的静态语义，即验证语法结构合法的程序，是否真正有意义。如类型检查。,语义处理是指两个功能：,动态语义处理：如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。,翻译的任务：首先是语义分析和正确性检查，若正确，则翻译成中间代码或目标代码。 使用的方法：语法制导翻译。 基本思想：根据翻译的需要设置文法符号的属
2、性，以描述语法结构的语义。即语法制导翻译法使用属性文法为工具来描述程序设计语言的语义。,1、属性文法(Syntax-directed definitions),(1) 属性,对文法的每一个符号， 引进一些属性，这些属性代表与文法符号相关的信息,，如类型、值、存储位置等。属性值，可以在语法分析过程中计算和传递。,属性分为两类:,属性加工的过程即是语义的处理过程。,综合属性和继承属性。,综合属性：其计算规则按“自下而上”方式进行， 即规则左部符号的某些属性根据其右部符号的属性和(或)自己的其他属性计算而得。在语法树中，一个结点的综合属性由该结点 的子结点的属性值确定。,继承属性：其计算规则按“自上
3、而下”方式进行， 即规则右部符号的某些属性根据其左部符号的属性和(或)右部其他符号的某些属性计算而得。继承属性值是由此结点的父结点和（或）兄弟结点的某些属性值来决定的。,(2) 属性文法,属性文法包含一个上下文无关文法和一系列语义规则。,语义规则：为文法的每一个规则配备的计算属性的计算规则， (描述语义处理的加工动作) 。,这些语义规则附在文法的每个产生式上，在语法分析过程中，执行语义规则描述的动作，从而实现语义处理。 即： 附在文法的每个产生式上的语义规则描述了语义处理的加工动作。,A（G，V，F）， G: 是一个上下文无关文法 V: 有穷的属性集,每个属性与文法的一终结符或非终结符 相连。
4、 F: 关于属性的属性断言或谓词集.每个断言与一个产生式 相联。一个断言即一个语义规则，描述各属性关系。,属性文法是一个三元组：,属性文法的主要思想有两点： 对于每个文法符号引进相关的属性符号； 对于每个产生式写出属性值计算的规则。,例如定义表达式的文法如下：,为文法符号E引进属性val表示E的值，记为E.val，语义规则以赋值语句的形式给出，附在每个产生式后。为了明确E的不同出现位置，用上角标区别。终结符n的值是词法分析程序提供的，这里用n.lex表示。下面给出属性文法： EE1+E2 E.val := E1.val +E2.val E(E1) E.val := E1.val En E.va
5、l := n.lex,EE+E E(E) En 给出定义表达式值的属性文法。,例1 表达式计算的语法制导定义,产生式 语义规则,LE print(Eval) E E1+T E val := E1 val+T val E T E val := T val T T1*F T val := T1 val+F val T F T val := F val F (E) F val := E val F digit F val := digitlexval,digitlexval:=3,Fval:=3,Tval:=3,digitlexval:=5,Fval:=5,Tval:=15,*,Eval:=2,+,
6、digitlexval:=2,Fval:=2,Tval:=2,Eval:=17,L,例2：输入23*5,只有综合属性,例2：变量说明的类型定义 int a,b,c,将L.in的属性值置为该说明语句T指定的类型,把每个标识符的类型信息登录在符号表相关项中（虚属性）,非终结符T有一综合属性type，它的值由关键字决定（int或real）。,与产生式DTL相联的语义规则L.in:=T.type，将L.in的属性值置为该说明语句指定的类型。,属性L.in被沿着语法树下传到下边结点，与L产生式相联的规则里使用了它。,T,L,L,id3,L,id2,D,id1,int,1 entry,2 entry,3
7、entry,4 type,5 in,6 in,7 in,例如：int a,b,c, 具有继承属性的属性文法,2、语法制导翻译,只含有综合属性的称为S属性文法 综合属性可以在分析输入符号串的同时采用自下而上的分析器来计算。分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。 S属性文法的翻译器很容易建立。通常可借助于LR分析器实现。,在语法分析过程中，依随分析的过程，根据每个产生式所对应的语义子程序(或语义规则描述的语义处理的加工动作)进行翻译的方法。,分析器模型,例如：*的分析和计值过程,步骤 动作 状态栈 语义栈(值栈) 符
8、号栈 余留输入串 ） 0 3* ） 05 2 3* ） r6 03 * ） r4 02 * ） r2 01 * ） 016 * ） 0165 * ） r6 0163 * ） r4 0169 * ） 01697 * ） 016975 - * ） r6 01697510 * # ） （15） ） （） ）接受,5.2 中间代码形式,“中间代码生成”程序的任务是：把经过语法分析和语义分析而获得的源程序中间表示翻译为中间代码表示。 方法：语法制导翻译。 采用独立于机器的中间代码的好处： 便于编译系统的建立和编译系统的移植； 便于进行独立于机器的代码优化工作。 中间代码表示形式有： 语法树 后缀式 三地
9、址代码表示（三元式、四元式）,1）后缀式,表示：将运算对象写在前面，运算符号写在后面。a+b写成ab+ 特点：运算符处于运算量之后； 运算符在表示式中出现的次序和计算的先后次序一致； 不用括号； 易于计算机处理表达式。利用栈自左至右扫描表达式后缀表示，碰到运算对象入栈；碰到运算符，则执行相应运算（出栈），结果入栈，最后结果留在栈顶。,语法制导生成后缀式举例：,”|”为捻接运算，在机器内实现是通过数组，利用post数组存放后缀式，k为下标，初值为1。 则：当用产生式EE1 + E2 归约句柄E1 + E2 时，分别与E1、E2相关的后缀式子串E1.nptr、E2.nptr均已在post 中，只需
10、将运算符“+”放入post即可。,Postp:=“op”,p:=p+1,Postp:=“id”,p:=p+1,例：EE+T Postp:=“+”,p:=p+1 ET TT*F Postp:=“*”,p:=p+1 TF F(E) Fi Postp:=“i”,p:=p+1,a+b*c生成后缀式,分析栈 当前符号 余留输入串 操作 后缀表示 # a b*c 移进 #a + b*c# 归约 a #F + b*c# 归约 #T + b*c# 归约 #E + b*c# 移进 #E+ b *c# 移进 #E+b * c# 归约 ab #E+F * c# 归约 #E+T * c# 移进 #E+T* c # 移
11、进 #E+T*c # 归约 abc #E+T*F # 归约 abc* #E+T # 归约 abc*+ #E,2）四元式,四元式：是一种更接近目标代码的中间代码形式，由于该形式的中间代码便于优化处理，因此得到广泛应用。 可用一种“三地址语句”等价表示，一般形式为： （op，arg1，arg2，result） Op为运算符； Arg1，arg2为两个运算对象：变量、常量、临时变量； Result中存放运算结果。,每个四元式只能有一个运算符，因此一个复杂表达式可由多个四元式构成的序列表示。 例：A+B*C写成： （*，B，C，T1） （+，A，T1，T2） 若op为一元、零元(无条件转移)时，arg
12、1、arg2可省略。 会引入一些临时变量。,注 意！,3）三元式,一般形式为：（i）（op，arg1，arg2）,其中：(i)为三元式编码，也代表了该式的运算结果。,例：a:=-b*(c+d) 其三元式表示写成： （1）(-，b， ) （2）(+，c，d) （3）(*，(1)，(2) （4）(:=，a，（3）) 特点：三元式比四元式空间少；三元式间的相互引用频繁，因此不便于优化。为此引入间接三元式。,1、辅助函数：,1）LOOKUP（name）：以name（变量名）查符号表，若在符号中，则将其表项位置（入口位置）作为LOOKUP的值，否则，取值为null。,2）ENTER（name）：在符号表
13、中以名字name新登记一项，并将此项的位置作为enter值。,5.3 简单赋值语句的翻译,3）ENTRY（name）：以name为名查、添符号表，描述为： function entry(name) entry:=lookup(name); if entry=null then entry:=enter(name),对于先说明后使用的语言，若在翻译表达式时，遇到的变量名不在表中，则程序出错。即 if entry=null then error,5）GEN（op，arg1，arg2，result）：产生一个四元式将它送入四元式表中，并以此四元式在四元式表中的位置作为返回值。,4) Newtemp函数，产生一个新的临时变量。返回值为标识此临时变量的整数码。,6) E.place属性：表示存放E值的变量名在符号表的入口或整数码（若E是临时变量）。,实例,2、赋值语句的属性文法,分析栈 当前符号 余留输入串 语义栈place 四元式 # A := B*(C+D) #A := B*(C+D) A #A:= B *(C+D) A_ #A:=B * (C+D) A_ B ，归约 #A:=E * (C+
