下载文档原格式
中国科学技术大学陈意云编译原理全套参考资料chapter4中国科学技术大学陈意云编译原理全套参考资料chapter4 第四章语法制导的翻译在3.7节用Yacc写的例子中，我们看到一种有用的描述形式:语言结构的属性附加在代表语言结构的文法符号上，这些属性值由附加在文法产生式的语义动作来计算，这些语义动作在归约对应的产生式时进行计算，由此得到结果。
这种描述形式可用来描述编译器的语义分析，因此本章系统地研究这种称之为“语法制导下的语言翻译”的描述方法及其实现。
它的语义动作(有时称为语义规则)的计算可以产生代码、把信息存入符号表、显示出错信息、或完成其它工作。
语义规则的计算结果就是我们所要的记号流的翻译。
本章讨论语义规则和产生式相联系的两种方式:语法制导的定义和翻译方案。
语法制导定义是较抽象的翻译说明，它隐蔽了一些实现细节;而翻译方案陈述了一些实现细节，主要是指明了语义规则的计算次序。
在第五章说明语义检查和第七章描述中间代码生成时，大量使用这两种方法。
本章还讨论语法制导定义和翻译方案的实现方法。
概念上的方法是，首先分析输入的记号串，建立分析树，然后从分析树得到描述结点属性间依赖关系的有向图，从这个依赖图得到语义规则的计算次序，然后进行计算，最终得到翻译的结果。
实际的实现并不需要按上面步骤逐步进行，本章将讨论几种不同限制下的实现方法。
4.1 语法制导的定义语法制导的定义是上下文无关文法的推广，其中每个文法符号都有一个属性集合，它分成两个子集，分别叫做该文法符号的综合属性集合和继承属性集合。
如果我们把分析树上的结点看成是保存对应文法符号的属性的记录，那么属性对应记录的域。
属性可以表示任何东西:串、数、类型、内存单元，或其它想表示的东西。
分析树结点的属性值由该结点所用产生式的语义规则定义。
在语法制导定义中，我们把其中的文法称为基础文法。
本节介绍语法制导定义的形式及其概念上的实现模型。
4.1.1 语法制导定义的形式在语法制导定义中，每个文法符号有一组属性，每个文法产生式A , ,有一组形式为b := f (c, c, …, c )的语义规则，其中f 是函数，b和c, c, …, c 是该产生式的文法符号的12k12k属性，并且:(1) 如果b是A的属性，c , c , …, c 是产生式右部文法符号的属性或A的其它属12k性，那么b叫做文法符号A的综合属性。
＜表达式＞AVV ------ *第二早1、 L(G[S])={ abc }2、 L(G[N])={ n 位整数或空字符串| n>0}3、 G[E] : E —>E+D | E-D | DD —>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 94、 L(G[Z])={ a n b n | n>0 }5、(1)考虑不包括“ 0”的情况G[S]: S — >0S | ABC | 2 | 4| 6 | 8A —>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B —>AB | 0B | &C —>0 | 2 | 4 | 6 | 8考虑包括“ 0”的情况： G[S]: S — >AB | CB —>AB | CA —>0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 C —>0 | 2 | 4 | 6 | 8(2)方法1:G[S]: S — > ABC | 2 | 4 | 6 | 8A —>1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9B —>AB | 0B | &C —>0 | 2 | 4 | 6 | 8方法2:G[S]: S — >AB | CB —> AB | 0B |C | 0A —> 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 C —>2 | 4 | 6 | 8&设<表达式 >为E , <项>为T , <因子〉为F ,注：推导过程不能省略，以下均为最 左推导(1) E => T => F => i(4) E => E+T => T+T => T*F+T => F*F+T => i*F+T => i*i+T => i*i+F => i*i+i (6) E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*I8、 是有二义性的，因为句子abc 有两棵语法树(或称有两个最左推导或有两个最右 推导)ii＜表达式＞最左推导1: S => Ac => abc最左推导2：S => aB => abc9、⑴a a(2) 该文法描述了变量a和运算符+、*组成的逆波兰表达式10、(1)该文法描述了各种成对圆括号的语法结构(2)是有二义性的，因为该文法的句子()()存在两种不同的最左推导：最左推导1：S => S(S)S => (S)S => ()S => ()S(S)S => ()(S)S => ()()S => ()() 最左推导2：S => S(S)S => S(S)S(S)S => (S)S(S)S=> ()S(S)S => ()(S)S => ()()S => ()()11、⑴因为从文法的开始符E出发可推导出E+T*F，推导过程如下：E => E+T =>E+T*F，所以E+T*F 是句型。
第四章习题解答4.1词法分析的主要任务是对源程序进行扫描，从中识别出单词，它是编译过程的第一步，也是编译过程中不可缺少的部分。
4.2单词符号一般分为五类：关键字、标识符、常数、运算符和界限符。
分别用整数1、2、3、4、5表示。
对于这种非一符一个类别码的编码形式，一个单词符号除了给出它的单词类别码之外，还要给出它的自身值。
标识符的自身值被表示成按字节划分的内部码。
常数的自身值是其二进制值。
由于语言中的关键字、运算符和界限符的数量都是确定的，因此，对这些单词符号可采用一符一个单词类别码。
如果采取一符一个单词类别码，那么这些单词符号的自身值就不必给出了。
4.3设计词法分析程序有如下几种方法：①由正规文法设计词法分析程序——程序设计语言的单词一般都可以用正规文法描述，从正规文法可构造一个FA。
再对FA确定化和状态个数最少化，最后得到一个化简了的DFA。
这个DFA正是词法分析程序的设计框图，这样，由DFA编制词法分析程序就容易了。
②由正规表达式设计词法分析程序——正规表达式也是描述单词的一种方便工具。
由正规表达式转换成NDFA，然后再对它确定化和状态个数最少化，可得一个DFA。
再由DFA编制词法分析程序。
4.4符号表在编译程序中具有十分重要的意义，它是编译程序中不可缺少的部分。
在编译程序中，符号表用来存放在程序中出现的各种标识符及其语义属性。
一个标识符包含了它全部的语义属性和特征。
标识符的全部属性不可能在编译程序的某一个阶段获得，而需要在它的各个阶段中去获得。
在编译程序的各个阶段，不仅要用获取的标识符信息去更新符号表中的内容，添加新的标识符及其属性，而且需要去查找符号表，引用符号表中的信息。
因为，符号表是编译程序进行各种语义检查（即语义分析）的依据，是进行地址分配的依据。
标识符处理的基本思想是，当遇到定义性标识符时，先去查符号表（标识符表）。
如果此标识符已在符号表中登记过，那么表明该标识符被多次声明，将作为一个错误，因为一个标识符只能被声明一次；如果标识符在符号表中未登记过，那么将构造此标识符的机内符，并在符号表中进行登记。
