第八章 语法制导翻译和中间代码生成

第8章 语法制导翻译和中间代码生成

8.8 Yacc和语法制导翻译

Yacc作为语法分析程序的自动构造工具，在第7章中已经讨论过其原理。Yacc采用语法制导翻译的方法获取翻译和语义处理信息，成为编译程序的生成工具。

语法制导翻译指的是编译实现的方法--源语言翻译是要由语法分析程序（parser）驱动的。换言之，分析过程和分析树用于制导（direct）语义分析和源程序的翻译。常用的方法是扩充惯用的文法，加上控制语义分析和翻译的信息，这样的文法称作属性文法。 将每个文法符号加上相联的属性以描述它的性质。一个属性有一个名字和一个相联的属性值--这个属性值可以是一个类型，一个存储位置或者一个分配的寄存器等等，只要是需要的属性都可以定义其属性值。

例如变量可以有一个属性\类型\以便以后进行类型审查，整常数可以有一个属性\值\，以便以后生成代码需要。

对每个产生式，给一个语义规则或动作（actions），用以描述如何计算和每个符号相联的属性值。

在8.2节，我们已经讨论了两种类型的属性：综合和继承的。综合的属性是指沿着语法树向上的属性，即产生式左端的非终结符的属性是由产生式右端的非终结符的属性计算的，终结符的属性通常由词法分析程序提供，然后再作为综合属性由此向上走。也就是说，若产生式为 x→y1y2…yn，综合属性a的计算公式形式为x.a=f(y1.a,y2.a, …,yn.a)。 例如，下述属性文法说明了计算整数的过程： → 0 {digit.value=0} …

9 {digit.value=9}

→ {int1.value=digit.value}

| {int1.value=int2.value*10+digit.value} 图8.14 属性值自底向上传递

图8.14是句子42的标有属性值的语法树，属性值value的计算过程首先从最底层最左边的结点4开始，然后按照自底向上归约的顺序，一步步向上综合的。

继承属性是沿着语法树向下的，既右端的属性是从左端属性，或是其它的右端属性导出的。这些属性用于把有关的上下文信息传到语法树的下层结点。 若产生式为 x→y1y2…yn，继承属性yk.a=f(x.a,y1.a,y2.a,…,yk-1.a,yk+1.a,…)。

a的计算公式形式为

第8章 语法制导翻译和中间代码生成

也就是说，继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的。 考虑下面文法，文法定义的是类-Pascal文法的变量说明语句和简单赋值语句，程序分为声明块和语句块，语句块使用的变量必须在声明块中先声明过。 P → DS

D → var V；D|ε S → V:=e；S|ε

V → x|y|z

该文法定义的句子的例子： var x； var y； x:=e； y:=e；

现在使用两个属性，name和dl，每当一个新的变量声明时，就把它的name属性附给它，name属性是综合属性。

如声明的变量为x，使用的产生式为V → x，计算name属性的语义描述则表示为： V → x {V.name='x'}

将所声明的变量都放到一个变量名字清单中（用语义函数addlist实现），用属性dl综合声明块中声明的所有变量。

D1 → var V； D2{D1.dl=addlist(V.name，D2.dl)} D →ε {D.dl=null}

然后这个dl属性又作为继承属性传到后面的语句部分，每个语句用到的变量都要进行审查，看它是否在变量名字清单中（用语义函数check 实现）。下面给出语义描述，看看我们如何利用继承属性dl去保持变量清单以进行类型审查。 P → DS {S.dl=D.dl}

D1 → var V； D2 {D1.dl=addlist(V.name，D2.dl)} |ε {D1.dl=null} S1 → V:=e； S2 {check(V.name，S1.dl)； S2.dl=S1.dl} |ε

V → x {V.name='x'}

|y {V.name='y'} |z {V.name='z'} 例： var x；

1

1

var y； x:=e；

y:=e；是该文法定义的句子，图8.15和图8.16是这个句子的带有属性信息的语法树。其中图8.15只给出了左分支的属性信息。图8.16只给出了右分支的属性信息。从右分支很清楚地看到dl属性的传递情况

图8.15 带有属性信息的语法树（左分支） f8-8-1.swf

图8.16 带有属性信息的语法树（右分支）

第8章 语法制导翻译和中间代码生成

思考问题：如果不用属性dl，是否同样可以实现纪录变量和审查变量？答案是肯定的，比如利用符号表。请你据此再给出一种语义描述。

Yacc或bison作为编译程序的生成工具，利用的就是语法制导翻译方法。它使用符号$$表示产生式左端的属性，$n表示存取产生式右端第n个文法符号相联的属性，上述例子的Yacc描述如右页所示。

P → DS {$2.dl=$1.dl} 1

D → var V； D{$$.dl=addlist($2.name，$4.dl)} |ε {$$.dl=null}

S1 → V:=e； S{check($1.name，$$.dl)； $5.dl=$$.dl} |ε

V → x {$$.name='x'}

|y {$$.name='y'} |z {$$.name='z'}

如果采用下面的数据结构attribute定义属性name和dl，可以具体化为： type struct_attribute { char *name； struct_attribute *list； } attribute；

P → DS {$2.list=$1.list}

D1 → var V； D{$$.list=add_to_list($2.name，$4.list)} |ε {$$.list=null}

1

S → V:=e； S{check($1.name，$$.list)； $5.list=$$.list} |ε

V → x {$$.name='x'}

|y {$$.name='y'} |z {$$.name='z'}

我们这里只把Yacc的原理做了介绍，有关Yacc的使用方法详见讲义（教科书）附录C

第8章 语法制导翻译和中间代码生成

本章小结

【本章小结】 ◇ 中间代码是复杂性介于源程序语言和机器语言的一种表式形式。编译程序中所使用的中间代码有多种形式，常见的有逆波兰记号、三元式和四元式等等。 ◇ 源程序翻译成中间表示，要在保证源语言语句语义的条件下进行源语句到目标语句结构上的变换。学习了本章应能掌握一般语法成分，如条件语句，循环语句和简单说明语句等结构的翻译。

◇ 语法制导翻译指的是编译实现的方法，分析过程和分析树用于制导语义分析和源程序的翻译，常用的办法是扩充惯用的文法，加上控制语义分析和翻译的信息，这样的文法称为属性文法。Yacc这类工具接受这种方式提供的语义分析和翻译信息，因而成为编译程序的生成器。