当前位置：文档之家 › 第四章语法制导的翻译

第四章语法制导的翻译

  • 格式：doc
  • 大小：281.50 KB
  • 文档页数：26

1 第四章 语法制导的翻译

在3.7节用Yacc写的例子中，我们看到一种有用的描述形式：语言结构的属性附加在代表语言结构的文法符号上，这些属性值由附加在文法产生式的语义动作来计算，这些语义动作在归约对应的产生式时进行计算，由此得到结果。这种描述形式可用来描述编译器的语义分析，因此本章系统地研究这种称之为“语法制导下的语言翻译”的描述方法及其实现。它的语义动作（有时称为语义规则）的计算可以产生代码、把信息存入符号表、显示出错信息、或完成其它工作。语义规则的计算结果就是我们所要的记号流的翻译。

本章讨论语义规则和产生式相联系的两种方式：语法制导的定义和翻译方案。语法制导定义是较抽象的翻译说明，它隐蔽了一些实现细节；而翻译方案陈述了一些实现细节，主要是指明了语义规则的计算次序。在第五章说明语义检查和第七章描述中间代码生成时，大量使用这两种方法。

本章还讨论语法制导定义和翻译方案的实现方法。概念上的方法是，首先分析输入的记号串，建立分析树，然后从分析树得到描述结点属性间依赖关系的有向图，从这个依赖图得到语义规则的计算次序，然后进行计算，最终得到翻译的结果。实际的实现并不需要按上面步骤逐步进行，本章将讨论几种不同限制下的实现方法。

4.1 语法制导的定义

语法制导的定义是上下文无关文法的推广，其中每个文法符号都有一个属性集合，它分成两个子集，分别叫做该文法符号的综合属性集合和继承属性集合。如果我们把分析树上的结点看成是保存对应文法符号的属性的记录，那么属性对应记录的域。属性可以表示任何东西：串、数、类型、内存单元，或其它想表示的东西。分析树结点的属性值由该结点所用产生式的语义规则定义。在语法制导定义中，我们把其中的文法称为基础文法。

本节介绍语法制导定义的形式及其概念上的实现模型。

4.1.1 语法制导定义的形式

在语法制导定义中，每个文法符号有一组属性，每个文法产生式A  有一组形式为b := f (c1, c2, …, ck )的语义规则，其中f 是函数，b和c1, c2, …, ck 是该产生式的文法符号的属性，并且：

（1） 如果b是A的属性，c1 , c2 , …, ck 是产生式右部文法符号的属性或A的其它属性，那么b叫做文法符号A的综合属性。

（2） 如果b是产生式右部某个文法符号X的属性，c1 , c2 , …, ck 是A的属性或右部文法符号的属性，那么b叫做文法符号X的继承属性。

在这两种情况下，我们都说属性b依赖于属性c1 , c2 , …, ck。每个文法符号的综合属性集和继承属性集的交集应为空。一般来说，结点的综合属性的值是通过分析树中它子结点的属性值来计算；继承属性的值由结点的兄弟结点和父结点的属性值来计算。

语义规则函数通常是表达式。有时，语法制导定义中某些规则的目的是要产生副作用，如打印值或修改全程量，这样的语义规则写成过程调用或程序段。可以把它们想象成定义了产生式左部非终结符的一个虚拟综合属性，这个虚拟属性和符号:=在该规则中没有显式表示出来。

属性文法是指语义规则函数无副作用的语法制导定义。

例4.1 图4.1的语法制导定义表示一个台式计算器程序。这个定义分别给非终结符E、 2 T和F一个存放整数值的综合属性val。对每个E、T和F产生式，语义规则从产生式右部非终结符的属性值val（或digit的lexval）计算产生式左部非终结符的属性值val。

表4.1简单台式计算器的语法制导定义

产 生 式 语 义 规 则

L  E n print (E.val)

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 := digit.lexval

记号digit有综合属性lexval，它的值由词法分析器提供。产生式L E n的语义动作是打印由E产生的算术表达式的值，我们把它看成定义了L的一个虚拟属性。这个台式计算器的Yacc说明在图3.25已给出，那儿的目的是用来说明LR分析时的翻译。 

在语法制导定义中，终结符看成只有综合属性，因而定义中没有提供计算终结符属性的语义规则，终结符的属性值通常由词法分析器提供。开始符号没有任何继承属性。

4.1.2 综合属性

综合属性在实践中有广泛应用。仅仅使用综合属性的语法制导定义叫做S属性定义。对于S属性定义，分析树各结点属性的计算可以自下而上地完成：从叶结点到根，通过计算语义规则而得到结点的属性。4.2节将描述LR分析器的生成器怎样实现以LR文法为基础的S属性定义。

每个结点的属性值都标注出来的分析树叫做注释分析树（annotated parse tree），计算各结点属性值的过程叫做分析树的注释或修饰。

例4.2 例4.1的S属性定义说明一台式计算器。例如，若输入是表达式8+5*2，并跟随一个换行符，那么该计算器打印值18。图4.1是8+5*2 n的注释分析树，在树的根结点打印18。

为了明白属性值是怎么计算的，考虑最左边最底层的内部结点，它使用的产生式是F 

digit，对应的语义规则是F.val := digit.lexval。从该规则得到该结点的属性F.val为8，因为它的子结点digit的lexval是8。同样地，该结点的父结点的属性T.val也为8。

我们再以产生式EE + T的结点为例，这个结点的属性E.val由产生式EE1 + T和语 L

E.val = 18 n

T.val = 10 E.val = 8

T.val = 8

F.val = 8

digit.lexval = 8 T.val = 5 +

*

F.val = 5 F.val = 2

digit.lexval = 2

digit.lexval = 5

图4.1 8+5*2 n的注释分析树 3 义规则E.val := E1 .val + T.val定义。当我们在这个结点运用该语义规则时，子结点E1的val为8，子结点T的val为10，故在此结点求得E.val的值为18。 

4.1.3 继承属性

在分析树中，一结点的继承属性是由该结点的父结点和/或兄弟结点的属性来定义的。程序设计语言的一些语法结构的属性依赖于它们所在的上下文，此时使用继承属性是方便的。在下面的例子中，继承属性传递类型信息给一张声明标中的各个标识符。

例4.3 在表4.2的语法制导定义中，非终结符D产生的声明由保留字int或real及一张标识符表组成。非终结符T有综合属性type，它的值由声明中的保留字决定。产生式D  TL

的语义规则置L的继承属性为声明中的类型。产生式L L1 , id的语义规则L1.in := L.in把继承属性in沿分析树向下传递类型。L产生式的规则调用过程addtype，把类型信息加到符号表中各个标识符的条目（属性entry给出条目的入口）中。

表4.2 有继承属性的语法制导定义

产 生 式 语 义 规 则

D  TL L.in := T.type

T int T. type := integer

T real

T. type := real

L L1, id L1.in := L.in;

addtype (id.entry, L.in )

L id addtype (id.entry, L.in )

图4.2给出句子int id1, id2, id3的注释分析树。这些属性值的确定首先是计算根的左子结点属性T.type，然后在根的右子树自上而下地计算三个L结点的L.in。在每个L 结点，我们还调用过程addtype，在符号表中将右子结点上的标识符的类型记为整型。 

使用继承属性的地方很多，例如，我们可以用继承属性来记住标识符是出现在赋值号的左边呢还是右边，以便决定是需要它的地址还是需要它的值。

重写语法制导定义使之仅使用综合属性总是可能的，但有时会使得重写后的文法失去了简洁和直观，反而不如使用带继承属性的语法制导定义自然。

4.1.4 属性依赖图

如果分析树一结点的属性b依赖某个结点的属性c，那么属性b的语义规则的计算必须在属性c的语义规则的计算之后。分析树结点的属性间的互相依赖可以用一种叫做依赖图的有向图来描绘。 D

int T.type = integer

, id3 L.in = integer

图4.2 int id1, id2, id3的注释分析树 L.in = integer

L.in = integer id2

id1 , 4 在构造分析树的依赖图之前，我们先为由过程调用组成的语义规则引入虚拟综合属性b，使得每条语义规则都能写成b := f (c1, c2, …,ck) 的形式。依赖图的组成是这样的，分析树上每个结点的所有属性在依赖图上各有一个结点，如果属性b依赖于属性c，那么从c的结点到b的结点有一条有向边。

例如，若S.s := f (A.a, B.b, C.c)是产生式S  ABC的语义规则，它定义了依赖于属性A.a，B.b和C.c的综合属性S.s。如果把这个产生式用于分析树，那么在依赖图上有4个结点S.s，A.a，B.b和C.c，并且结点A.a，B.b和C.c分别有边到结点S.s。

如果产生式S  ABC有语义规则A.a := f (S.s, B.b, C.c)，那么在依赖图上，结点S.s，B.b和C.c分别有边到结点A.a，因为A.a依赖于S.s，B.b和C.c。

例4.4 图4.3给出了图4.2分析树的依赖图。在图4.3中，虚线表示的是分析树；依赖图的结点用数表示，边用实线表示。从结点4的T.type到结点5的L.in有一条边，因为根据产生式D TL的语义规则L.in := T.type， L.in依赖于T.type。因为产生式LL1, id的语义规则L1.in := L.in导致L1.in依赖于L.in，因此依赖图上有分别到达结点7和9的两条向下的边。L产生式的语义规则addtype(id.entry, L.in)导致虚拟属性的建立，结点6，8，10是这样的虚拟属性结点。 

4.1.5 属性计算次序

拓扑排序是无环有向图的结点的一种排序m1, m2, …, mk，它使得边只会从这个次序中先出现的结点到后出现的结点，也就是若mi mj是从mi到mj的边，那么在此排序中mi先于mj。

显然，依赖图的任何拓扑排序都是分析树中结点属性计算的一个正确次序，即按拓扑排序进行计算的话，用语义规则b := f (c1, c2, …, ck )计算b时，属性c1, c2, …, ck 已经计算过了。

合集下载

语法制导翻译

语法制导翻译

for循环语句翻译 递归下降法 输出三地址码 /////////////

#define MAX 100

#include

#include

#include

char str[MAX];

char ch;

int turn;

char strToken[MAX];

int kind;

int n=0;//存放strtoken[]元素的个数

struct Word//结构体 存放单词

{

int sort;

char word[MAX];//存放strtoken[]的内容

};

//record[x]=new Word;

Word *record[12];//放所有识别出来的单词，分别存放他们的编号以及字符串，x是其下标

////////////////////词法分析///////////////////////

int buffer()//载入

{

int i=0;

cout<<"输入程序，以“#”作为结束标志。"<

for(int n=0;n<=MAX;n++)

{

for(;i<=MAX;i++)

{

scanf("%c",&str[i]);

/////////////cin>>str[i]不可用，用C语言读入字符。

if(str[i]=='#')

break;///////如果尾数为识别码#,则表示程序读完,跳出循环.

}

break;

}

return(i); }

bool IsLetter(char ch)///////////判断是否是字母

{

if(ch>=65&&ch<=90||ch>=97&&ch<=122)

return(true);

else

return(false);

}

bool IsDigit(char ch)//////////判断是否是数字

{

if(ch>=48&&ch<=57)

语法制导翻译与生成中间代码(附代码)

语法制导翻译与生成中间代码(附代码)

《编译系统设计实践》

实验项目三：语法制导翻译与生成中间代码

学号：

姓名：

年级：

学院： 数计学院

专业： 计算机

本组其它成员：学号 姓名

学号 姓名

实验时间：2016－2017学年第一学期

任课教师：

一、实验目的

通过语法制导或翻译模式生成中间代码。

二、实验内容

在自底向上语法分析基础上设计语义规则（语法制导翻译），将源程序翻译为四元式输出，若有错误将错误信息输出。

三、设计思路

1. 分析过程

主函数，读取文件，存入字符串数组，调用语义分析，判断关键字，调用相应的语义规则（这里只有if和while和赋值语句），赋值语句调用表达式处理，if语句调用条件表达式处理，while也是调用表达式处理，然后是一个递归过程，不断的递归调用，按序输出三地址语句。在本例程序中选用expr及num作为运算数。

2. 主要函数

string link() //字符串和数字的连接

string element() //获取表达式中的元素对象

string expression() //处理表达式

string expression_1() //处理表达式

string biaodashi() //处理表达式，转为三地址输出

string biaodashi_1() //递归---处理表达式，转为三地址输出

string getOperator() //判断并获取运算符

void condition(int L1,int L2) //输出if语句的条件的三地址代码

第四章语法制导的翻译

第四章语法制导的翻译

1 第四章 语法制导的翻译

在3.7节用Yacc写的例子中，我们看到一种有用的描述形式：语言结构的属性附加在代表语言结构的文法符号上，这些属性值由附加在文法产生式的语义动作来计算，这些语义动作在归约对应的产生式时进行计算，由此得到结果。这种描述形式可用来描述编译器的语义分析，因此本章系统地研究这种称之为“语法制导下的语言翻译”的描述方法及其实现。它的语义动作（有时称为语义规则）的计算可以产生代码、把信息存入符号表、显示出错信息、或完成其它工作。语义规则的计算结果就是我们所要的记号流的翻译。

本章讨论语义规则和产生式相联系的两种方式：语法制导的定义和翻译方案。语法制导定义是较抽象的翻译说明，它隐蔽了一些实现细节；而翻译方案陈述了一些实现细节，主要是指明了语义规则的计算次序。在第五章说明语义检查和第七章描述中间代码生成时，大量使用这两种方法。

本章还讨论语法制导定义和翻译方案的实现方法。概念上的方法是，首先分析输入的记号串，建立分析树，然后从分析树得到描述结点属性间依赖关系的有向图，从这个依赖图得到语义规则的计算次序，然后进行计算，最终得到翻译的结果。实际的实现并不需要按上面步骤逐步进行，本章将讨论几种不同限制下的实现方法。

4.1 语法制导的定义

语法制导的定义是上下文无关文法的推广，其中每个文法符号都有一个属性集合，它分成两个子集，分别叫做该文法符号的综合属性集合和继承属性集合。如果我们把分析树上的结点看成是保存对应文法符号的属性的记录，那么属性对应记录的域。属性可以表示任何东西：串、数、类型、内存单元，或其它想表示的东西。分析树结点的属性值由该结点所用产生式的语义规则定义。在语法制导定义中，我们把其中的文法称为基础文法。

本节介绍语法制导定义的形式及其概念上的实现模型。

4.1.1 语法制导定义的形式

在语法制导定义中，每个文法符号有一组属性，每个文法产生式A  有一组形式为b := f (c1, c2, …, ck )的语义规则，其中f 是函数，b和c1, c2, …, ck 是该产生式的文法符号的属性，并且：

编译原理(龙书)课后习题解答(详细)

编译原理(龙书)课后习题解答(详细)

编译原理(龙书)课后习题解答(详细)

编译原理(龙书)课后题解答

第一章

1.1.1 ：翻译和编译的区别？

答：翻译通常指自然语言的翻译，将一种自然语言的表述翻译成另一种自然语言的表述，而编译指的是将一种高级语言翻译为机器语言（或汇编语言）的过程。

1.1.2 ：简述编译器的工作过程？

答：编译器的工作过程包括以下三个阶段：

(1) 词法分析：将输入的字符流分解成一个个的单词符号，构成一个单词符号序列；

(2) 语法分析：根据语法规则分析单词符号序列中各个单词之间的关系，确定它们的语法结构，并生成抽象语法树；

(3) 代码生成：根据抽象语法树生成目标程序（机器语言或汇编语言），并输出执行文件。

1.2.1 ：解释器和编译器的区别？

答：解释器和编译器的主要区别在于执行方式。编译器将源程序编译成机器语言或汇编语言等，在运行时无需重新编译，程序会一次性运行完毕；而解释器则是边翻译边执行，每次执行都需要进行一次翻译，一次只执行一部分。

1.2.2 ：Java语言采用的是解释执行还是编译执行？

答：Java一般是编译成字节码的形式，然后由Java虚拟机（JVM）进行解释执行。但是，Java也有JIT（即时编译器）的存在，当某一段代码被多次执行时，JIT会将其编译成机器语言，提升代码的执行效率。

第二章

2.1.1 ：使用BNF范式定义简单的加法表达式和乘法表达式

答：

::= "+" |

::= "*" |

::= | "(" ")"

2.2.3 ：什么是自下而上分析？

答：自下而上分析是指从输入字符串出发，自底向上构造推导过程，直到推导出起始符号。自下而上分析的方法分为两类：一种是移进-归约分析（shift-reduce parsing），另一种是带有回溯的移进-归约分析（backtracking shift-reduce parsing）。

2.2.4 ：什么是语法制导翻译？