《编译原理 第八章语法制导翻译与中间代码生成汇总》由会员分享，可在线阅读，更多相关《编译原理 第八章语法制导翻译与中间代码生成汇总（48页珍藏版）》请在金锄头文库上搜索。
1、第八章 语法制导翻译与中间代码生成,语言的结构可形式的用一组产生式(BNF)描述，这使得语言的词法分析器和语法分析器的自动生成成为可能。 本章：语义的形式化困难，语义处理复杂，难以形式化 语义处理主要包括静态语义（包括类型规则和作用域/可见性规则）检查和翻译成中间代码； 对属性和属性文法作一介绍； 语法制导翻译：一种接近形式化的系统； 典型的中间代码； 语义子程序设计； 各种基本语言成分的自下而上分析的语法制导翻译。,8.1 属性和属性文法,8.1.1属性文法,属性(attribute)是编程语言结构的任意特性，是一个语法概念的特征描述。 属性是想表示的任何东西，典型的属性有：变量的数据类型、
2、表达式的值、存储器中变量的位置、程序的目标代码、数的有效位数等。 属性文法(attribute grammar)：将属性关系等式附加在相应文法规则上的文法 属性的表示：若a是文法符号X的一个属性，则记作X.a。a称为属性变量。 属性关系等式与采用何种语法分析方式无关，但是属性的计算次序受分析方法所限定的分析树结点的建立次序的约束。,例8.1 考虑下面简单的无符号数文法：,numbernumber digit | digit digit0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9,属性文法： 文法规则 语义规则 number(1)number(2) digit nu
3、mber(1).val=number(2).val*10 + digit.val numberdigit number.val=digit.val digit0 digit.val=0 digit9 digit.val=9,属性计算依赖于分析树或语法树明确或不明确的遍历：,例8.2 考虑下列类似C语言中变量声明的简单文法： decltype var-list typeint | float var-listid, var-list | id,属性文法： 文法规则 语义规则 decltype var-list var-list.dtype=type.dtype typeint type.dtyp
4、e=integer typefloat type.dtype=real var-list(1)id ,var-list(2) id.dtype=var-list(1).dtype var-list(2).dtype=var-list(1).dtype var-listid id.dtype=var-list.dtype,字符串float x,y的语法树，显示属性文法指定的dtype属性：,辅助函数mkOpNode和mkNumNode： mkOpNode构成一个新的树结点； mkNumNode构成一个叶子结点。,例8.3 考虑下列简单的整数算术表达式文法： expexp+term | exp-t
5、erm | term termterm*factor | factor factor(exp)| number exp(或term或factor)的基本属性是它的数字值，写作val。 属性文法 ,简单整型算术表达式的抽象语法树的属性文法： 文法规则 语义规则 exp(1)exp(2)+term exp(1).tree=mkOpNode(+,exp(2).tree,term.tree) exp(1)exp(2)-term exp(1).tree=mkOpNode(-,exp(2).tree,term.tree) expterm exp.tree=term.tree term(1)term(2)*
6、factor term(1).tree=mkOpNode(*,term(2).tree,factor.tree) termfactor term.tree=factor.tree factor(exp) factor.tree=exp.tree factornumber factor.tree=mkNumNode(number.lexval),8.1.2 综合和继承属性,综合属性(synthesized attribute) ：若产生式左部符号A的属性值是通过右部符号的属性值或A的其它属性值得来的 S属性文法：所有的属性都是综合的任一右部符号的属性计算与它所在的产生式无关（从语法树看，任一结点
7、的属性仅依赖它的下层或它自己的其它属性，换句话说不依赖上层和同层其它结点的属性） S属性文法的属性值可以通过对树进行简单后序遍历来计算：,void PostEval(treenode T) for each child C of T do PostEval(C); compute all synthesized attributes of T; ,并不是所有的属性都是综合的。所有的非综合属性称为继承(inherited)属性。,例8.4 对例8.1中的文法进行修改，数可以是八进制或十进制的 based-numnum basechar basecharo | d numnum digit | d
8、igit digit0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 此时，num和digit均需要一个新的属性base用来计算属性val。,文法规则 语义规则 based-numnum basechar based-num.val=num.val num.base=basechar.base basecharo basechar.base=8 basechard basechar.base=10 num(1)num(2) digit num(1).val= if digit.val=error or num(2).val=error then error else
9、num(2).val*num(1).base+digit.val num(2).base=num(1).base digit.base=num(1).base numdigit num.val=digit.val digit.base=num.base digit0 digit.val=0 digit7 digit.val=7 digit8 digit.val=if digit.base=8 then error else 8 digit9 digit.val=if digit.base=8 then error else 9,345o的语法树：,与综合属性不同，子孙继承属性计算的顺序是重要的
10、，因为在子孙的属性中继承属性可能有依赖关系。 此文法有两个属性，综合属性val、继承属性base； 先计算base，再用后序遍历计算val。,综上所述，属性文法是带有下列说明的翻译文法： 1每个终结符、非终结符都有一个与其相关的属性的有穷集。 2每一个非终结符号的属性可分为两类：继承的或综合的。 3在分析树中，一个结点的综合属性值是从其子结点和它本身的属性值计算出来的；而一个结点的继承属性值是由该结点兄第结点和父结点和它本身的属性值计算出来的。,属性计算方法,树遍历的属性计算方法 若语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有
11、属性。有时可能需要进行多遍遍历。 一遍扫描的处理方法 在很多情况下，翻译可以在扫描分析过程中完成，不需要构造出明确的语法分析树。L属性翻译的语法制导翻译方案包含了所有可以在语法分析过程中完成的翻译方案。 一遍扫描的处理方法与下面两个因素密切相关： （1）所采用的语法分析方法（不同方法对属性计算的方便性不同） （2）属性的计算次序。,8.1.3 属性的变换,属性计算主要在语义分析阶段进行，但语义分析的部分工作可以放到词法/语法分析阶段进行。如，当一个名字填入符号表时，就可以检查这个名字是否只定义了一次。 如果语义分析可以推迟到所有的语法分析完成之后进行，那么实现语义分析的任务就相当容易，其本质上
12、是对语法树的一序列的遍历过程，同时在遍历中每次遇到结点时进行计算，但也这就意味着编译程序必须是多遍的。 另一方面，如果要求编译程序在一遍中完成所有的操作(包括代码生成)，那么语义分析的实现就会变成寻找计算语义信息的正确顺序和方法的特别的过程。,可能会有这样的情况，不改变语言合法的字符串而修改文法会使属性的计算更简单或更复杂。 定理：(Knuth 1968)给定一个属性文法，通过适当地修改文法，而无须改变文法的语言，所有的继承属性可以改变成综合属性。 虽然重写文法使之仅使用综合属性总是可能的，但通常是使用带继承属性的属性文法更自然些。,属性等式与使用什么样的语法分析方法以及分析算法的具体实现无关
13、。在下面的语法制导翻译中，我们将会看到属性文法的作用在于它能指导我们写出更加清晰、简练、不易出错的的语义分析子程序，同时子程序也更加易懂。,例8.5 再次考虑变量声明的简单文法： decltype var-list typeint | float var-listid, var-list | id 可将这个文法改写为： declvar-list id var-listvar-list id, | type typeint | float,8.2 属性文法和语法制导翻译,语义分析包括构造符号表、记录声明中建立的名字的含义、在表达式和语句中进行类型检查等。 类型检查应验证一种结构的类型是否匹配其上
14、下文的要求。 如何把源程序改造成某种形式的中间语言程序？ 在语法分析中，有相当成熟的理论和算法：使用 BNF中的上下文无关文法描述语言的语法结构，并用自顶向下或自底向上的分析算法实现语法分析。 语义分析目前还没有给出一种公认的形式化描述系统，只能说有一些成功的系统和方法，其中比较接近形式化的一种方法是语法制导翻译法。,所谓语法制导翻译，直观上说就是为每个产生式配上一个翻译子程序（语义子程序），并且在语法分析的同时执行它。 语义子程序的功能包括改变编译程序某些变量的值、查填各种符号表、诊察与报告源程序错误、产生中间代码等。 语义子程序是给产生式赋予具体意义的手段，一方面规定了产生式产生的符号串的
15、意义，另一方面又按照这种意义规定了生成代码应做的基本动作。,例如，定义二进制算术表达式E的”值”的语义： 1. EE(1)+E(2) E.VAL:=E(1).VAL+E(2).VAL 2. E0 E.VAL:=0 3. E1 E.VAL:=1,对输入串1+1+0+1，一旦分析器认出它是一个句子时，它的值“11”也就被语义子程序计算出来了。,语法制导翻译既可以用来产生中间代码，也可以用来产生目标指令，甚至可用来对输入串进行解释执行。 总之，按语法制导翻译的方法来实现语言的翻译，就是要根据语言的文法，按照各产生式的语义，分别编写出完成这些操作的语义子程序，并把它们插入到各产生式右部的适当位置上，从
16、而形成翻译文法。这样，在语法分析过程中，就能在分析符号串的同时，执行由翻译文法所确定的、与该符号串相对应的动作序列，即按动作符号的顺序调用相应的子程序完成翻译任务。 语义子程序的设计：以属性文法为基础，将属性等式转化为计算规则（属性等式本身指示了属性计算时的顺序约束）。,对产生式 X0X1 X2 . . . Xn 的属性等式 Xi.aj=fij(X0.a1，X0.ak，X1.a1，X1.ak，Xn.a1，Xn.ak) 等式右边出现的所有属性值必须已经存在。但在属性文法的说明中，这个要求可能被忽略，可以将等式写成任意顺序而不会影响正确性。 实现属性文法的关键在于为属性的计算寻找一个顺序，以确保当每次进行计算时使用的所有属性值都是有效的。,文法规则 语义规则 declvar-list id id.dtype=
