第八章语法制导翻译和中间代码生成1、教学目的及要求：
本章介绍编译程序的第三个阶段语义分析及中间代码生成的设计原理和实现方法，要求理解语法制导翻译、语义动作的基本概念；掌握算数表达式和赋值语句到中间代码的翻译、布尔表达式的目标代码结构分析和到四元式的语法制导翻译。
◇明确语义分析在编译过程所处的阶段和作用。
◇掌握属性文法的基本概念。
◇使用属性文法和语法制导翻译方法描述具体的语义分析和产生中间代码。
2、教学内容：
语法制导翻译的基本概念、中间代码的形式，可执行语句的语法制导翻译方法。
3、教学重点：
语法制导翻译基本思想，语法制导翻译概述，基于属性文法的处理方法，自下而上分析制导翻译概述。
4、教学难点：
属性文法的处理方法,语法制导翻译实现的方法。
5、课前思考
◇ 回顾第一章介绍的编译过程，理解语义分析在编译过程中的位置和作用。
◇什么是中间表示（中间代码），为什么要中间表示？
◇"语法制导翻译"是什么含义？
◇ 高级语言语句的结构和低级语言结构的不同。
6、章节内容
第一节语法制导翻译概述
第二节中间代码的形式
第三节简单算术表达式和赋值语句的翻译
第四节布尔表达式的翻译
8.1语法制导翻译概述
编译程序的第三个阶段是语义分析。语义分析的任务是：在词法分析和语法分析的基础上，分析所写源程序的含义，在理解含义的基础上生成中间代码或直接生成目标代码。语义分析包括语义检查和语义处理。
语义检查，例：类型、运算、维数、越界。
语义处理，例：变量的存储分配、表达式的求值、语句的翻译（中间代码的生成）。
中间代码或称中间语言，是复杂性介于源程序语言和机器语言之间的一种表示形式，在中间代码一级可进行代码优化工作。
一、属性文法
目前许多编译程序的语义分析均采用语法制导翻译方法，它比较接近形式化。语法制导翻译法采用属性文法为工具来说明程序设计语言的含义。
属性是文法符号的语义性质的表示。对于文法中的某个终结符或非终结符，其属性可以有“类型”、“值”或“存储位置”等。
一个属性文法包含一个上下文无关文法和一系列语义规则，这些语义规则附在文法的每一个产生式上。形式上讲，一个属性文法是一个三元组 A=(G,V,F)
G：一个上下文无关文法
V：一个属性的有穷集
F：关于属性的断言或谓词的有穷集
其中：每个属性与文法的某个非终结符或终结符相联，每个断言与文法的某个产生式相联，如果对G中的某一输入串而言(句子)，A中的所有断言对该输入串的语法树结点的属性全为真，则该串也是A语言中的句子。
例1、有文法G为E→T1+T2|T1 or T2 T→num|true|false
若属性文法中用N.t表示与非终结符N相联的属性，则对上述表达式的类型检查的属性文法可表示如下：
E→T1+T2 {T1.t=int AND T2.t=int}
E→T1 or T2 {T1.t=bool AND T2.t=bool}
T→num {T.t=int }
T→true {T.t=bool }
T→ false {T.t=bool }
即与每个非终结符T相联的有属性t（即“类型”），t要么是int，要么是bool。与非终结符E的产生式相联的断言是：两个T的属性必须相同。
例2、简单算术表达式求值的语义描述
产生式语义规则
(0)L→E print(E.val)
(1)E→E1+T E.val:=E1.val+T.val
(2)E→T E.val:=T.val
(3)T→T1*F T.val:=T1.val*F.val
(4)T→F T.val:=F.val
(5)F→(E) F.val:=E.val
(6)F→digit F.val:=digit.lexval（lexval指综合属性）
每个非终结符都有一个属性val（即“数值”）。
单词digit的值是由词法分析程序提供的。
与产生式L→E相联的语义规则是一个过程，该过程实现的功能是打印由E产生的表达式的值。我们可以理解为L的属性是空的或是虚的。
例3.说明语句中变量的类型信息的语义规则
产生式语义规则
(1)D→TL L.in:=T.type
(2)T→int T.type:=integer
(3)T→real T.type :=real
(4)L→L1,id L1.in:=L.in addtype(id.entry,L.in)
(5)L→id addtype(id.entry,L.in)
该语义规则中的addtype为一过程调用，其功能是把每个标识符的类型信息登录在符号表的相关项中。type表示类型，综合属性；in起到类型传递的作用，继承属性；entry是单词 id 的属性。
属性文法最早出自克努特笔下，它将属性分为两类：综合属性和继承属性。
综合属性：从语法分析树的角度来看，如果一个节点的某一属性，其值由子节点的属性值来计算则称该属性为综合属性。有时把内在属性也看作是综合属性。
继承属性：在语法树分析中，若一个节点的某个属性值由该节点的兄弟结点或父节点的属性值来计算，则此节点的该属性称为继承属性。
二、语法制导翻译（产生中间代码）
产生中间代码的一种简单办法是让每个产生式对应一个语义子程序。在自上而下语法分析中，若一个产生式匹配输入串成功，或者在自下而上分析中，当一个产生式被用于归约时，此产生式相应的语义子程序就进入工作。
一个语义子程序描述了一个产生式所对应的翻译工作，这些翻译工作在很大程度上取决于要产生什么形式的中间代码。包括：改变编译程序某些变量的值，查填各种符号表，诊察与报告源程序错误，产生中间代码等。
在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（语义动作）进行翻译（产生中间代码）的方法叫做语法制导翻译法。语法制导翻译方法既可用来产生各种中间代码，也可用来产生目标指令，甚至可用来对输入串进行解释执行。
三、语法制导翻译的具体实现途径
假定有一个自底向上分析器LR(1)，可将LR(1)分析器的能力加以扩大，使之能在用某个产生式进行归约的同时调用相应的语义子程序进行有关的翻译工作，每个产生式的语义子程序执行之后，某些结果（语义信息）必须作为此产生式的左部符号的语义值暂时保存下来，以便以后语义子程序引用这些信息。
假定有一个LR语法分析器，现在把它的分析栈
扩充，使得每个文法符号都跟有语义值，如左图。
状态栈语义值符号栈
假定我们现在要分析的语法成分是简单算术表达式，所完成的语义处理不是将它翻译成中间代码或目标代码，而是计算表达式的值。假设语法分析方法是自下而上的。在用某一产生式进行归约的同时就执行相应的语义动作，在分析出一个句子时，这个句子的“值”也就同时产生了。以上是对输入串2+3*5的分析处理过程。
按照上述实现方法，若把语义子程序改为产生某种中间代码的动作，那么则可在语法分析的制导下，随着分析的进展逐步生成中间代码。
8.2中间代码的形式
不同的编译程序使用了不同的中间代码，有些快速编译程序甚至几乎没有中间代码阶段，但为编译程序的结构在逻辑上更为简单、明确，尤其为使目标代码的优化比较容易实现，许多编译程序都采用了复杂性介于源程序语言和机器语言之间的中间语言，并将源程序翻译成这种中间语言程序（中间代码）。
常见的中间语言有逆波兰记号、三元式、四元式和树形表示等。
源程序的中间代码是在编译程序将高级语言程序翻译成汇编语言或机器代码的过程中产生的，使用中间代码形式的优点：
可以不考虑机器特性；
可移植性；
便于优化处理。
一、逆波兰表示法
1、定义
逆波兰表示，也称后缀式，即运算量在前，算符写在后面，该方法可在不使用括号的情况下，无二义性地说明算术表达式。逆波兰表示不仅能用来作为算术表达式的中间代码形式，而且也能作为其它语言结构的中间代码形式。
一般而言，若θ是一个K(K>=1)目运算符，对后缀式e1,e2,..ek作用的结果将被表示为e1e2..ek θ，不必使用括号，如：
?abc+* a*(b+c)
?ab+cd+* (a+b)*(c+d)
?abc*bd*+:= a:=b*c+b*d
根据运算量和运算符出现的先后位置，就完全决定了一个表达式的分解。
2、后缀式的计算
逆波兰表示法表示表达式，其最大的优点是最易于计算机处理表达式，可用一个栈计算表达式的值。
计算过程为：自左至右扫描后缀式，每碰到运算量就将其推入栈，每碰到一个k目算符时，就将其作用于栈顶的k个项，并用运算结果来代替这k个项。
例：考虑后缀式ab+c@*的计值过程 (@表示一目减)
3、后缀式的推广
遵守运算量在前，算符在后的规则，可将后缀表示法扩大到比通常表达式更大的范围，如条件语句if E then S1 else S2 可表示为E S1 S2 ￥又如：数组元素A[<下标表达式1>, <下标表达式2>,…, <下标表达式n>]可表示为<下标表达式1><下标表达式2>…<下标表达式n>A subs
4、语法制导生成后缀式
①E→E1 OP E2 {E.CODE:=E1.CODE‖E2.CODE‖OP}
②E→(E1) {E.CODE:= E1.CODE}
③E→i {E.CODE:=i}
E.CODE表示构成后缀式的符号串。‖表示两串的“连接”。
第①个产生式语义动作的意思是：E的后缀式等于E1和E2两个后缀式的连接，而后再接上算符OP。
第②个产生式的语义动作指出，把括号无条件地去掉。
第③个产生式的语义动作告诉我们，标识符的语义值是那个标识符本身。
二、三元式和树形表示
1、三元式
表达式及各种语句都可表示成一组三元式：（算符OP 运算对象1 运算对象2）。例：a:=b*c+b*d的三元式表示为
(1) ( * b c)
(2) ( * b d)
(3) ( + (1) (2))
(4) ( := a (3))
三元式中含有对中间计算结果的显示引用，如三元式(1)表示的是b*c的结果。
对于一目算符op，通常用一个运算对象，如规定arg1，而多目运算符，可用若干个连续的三元式表示。
2、间接三元式
为便于代码优化处理，作为中间代码，常不使用三元式，而另设一张指示器表（间接码表），按运算的先后顺序列出有关三元式在三元式表中的位置，即利用一张间接码表辅以三元式表的方法来表示中间代码，这种方法即为间接三元式。
+ * a b d c 如x:=(a+b)*c; y:=d ↑(a+b)的间接三元式为：
三元式表
间接码表 (1) + a b
(1) (2) * (1) c
(2) (3) := x (2)
(3) (4) ↑ d (1)
(1) (5) := y (4)
(4) (5)
当在代码优化过程中需要调整运算顺序时，只需重新安排间接码表，无须改动三元式表。另外由于另设了间接码表，相同的三元式就无须重复填进三元式表中，这样可以节省三元式表的存储空间。
3、树形表示
如a*b+c*d 用树形结构表示为：
树形表示是三元式表示的翻版。
每个三元式（OP,ARG1,ARG2）对应一棵二叉子树，OP 为子树的根，ARG1和ARG2为子树的两个分支，它们或为终结符，或为下代子树的根。
二目运算对应二叉子树，多目运算对应多叉子树。但为方便于安排存储空间，一棵多叉子树可以通过引进新结点而表示成一棵二叉子树。
三、四元式
四元式是一种比较普遍采用的中间代码形式。其一般形式为：
(算符op 运算量arg1 运算量arg2 运算结果result)
运算量和运算结果有时指用户自定义的变量，有时指编译程序引进的临时变量。如果OP 是一个算术或逻辑算符，则result 总是一个新引进的临时变量，用以存放运算结果。
例、A:=-B*(C+D)
(1) @ B - T1
(2) + C D T2
(3) * T1 T2 T3
(4) := T3 - A
注意，四元式之间的联系是通过临时变量实现的，这一点和三元式不同。要更动一张三元式表是很困难的，它意味着必须改变其中一系列指示器的值，但要更动四元式表是很容易的，因为调整四元式之间的相对位置并不意味着必须改变其中一系列指示器的值。因此，当需要对中间代码进行优化处理时，四元式比三元式方便得多。
为更直观，将四元式的形式写成简单赋值形式或更易理解的形式如：
（* b c t1）t1：=b*c
（:= t2 - a ）a：=t2
（jump - - L）goto L
（jrop B C L） if B rop C goto L
其中rop是关系符，表示＜，≤，＞，≥，＝，≠等。
8.3 简单算术表达式和赋值语句的翻译
一、赋值语句的四元式翻译
四元式中的arg1,arg2,result在实际应用中或者是指针，指向符号表的某一登录项，或者是某一临时变量的整数码，在对赋值语句翻译为四元式的描述中，我们将表明怎样查找这样的符号表登记项。
赋值语句的文法描述：S→id:=E E→E+E|E*E|-E|(E)|id 为实现从表达式到四元式，需一系列的语义变量和语义过程：
lookup(https://www.doczj.com/doc/185346508.html,)表示审查https://www.doczj.com/doc/185346508.html,是否出现在符号表中，如在，返回指向该登录项的指针，否则返回nil；
emit表示输出四元式到输出文件上；
newtemp表示生成一临时变量，每调用一次，生成一新的临时变量；
E.place表示存放E值的变量名在符号表中的登录项或一整数码(该变量为一临时变量)。
(1)S→id:=E { p:=lookup(https://www.doczj.com/doc/185346508.html,);
if p<>nil then emit(p,‘:=’,E.place) else error} (2)E→E1+E2 { E.place:= newtemp;
emit( E.place,‘:=’,E1.place,‘+’,E2 .place)}
(3)E→ E1*E2 { E.place:= newtemp;
emit( E.place,‘:=’,E1.place,‘*’, E2 .place)}
(4)E→ - E1 { E.place:= newtemp;
emit( E.place,‘:=’,‘uminus’, E1 .place)}
(5)E→ (E1) { E.place:= E1.place}
(6)E→id { p:= lookup(https://www.doczj.com/doc/185346508.html,);
if p<>nil then emit(p,‘:=’,E.place) else error}
二、类型转换的语义处理
实际上，表达式中可能会出现不同类型的变量或常数，故编译程序除对变量进行“先定义后使用”的语义检查外，还必须做到或拒绝接受某种混合运算，或产生有关类型转换的指令。
为进行类型转换的语义处理，增加语义变量，用E.type表示E的类型信息，值为int或real；
为区别整数乘(加)和实型乘(加)，用*i表示整数乘，*r表示实型乘；
itr表示将整型运算对象转换成实型。（itr为一目算符）
则上述第三条产生式及有关语义描述如下：
E→E1*E2
{ E.place:= newtemp;
if E1.type=int AND E2.type=int then
BEGIN emit( E.place, ‘:=’,E1.place,‘*i’ ,E2 .place);
E.type:=int END
else if E1.type=real AND E2.type=real then
BEGIN emit( E.place, ‘:=’,E1.place,‘*r’,E2 .place);
E.type:=real END
else if E1.type=int AND E2.type=real then
BEGIN t:=newtemp;
emit(t,‘:=’,‘itr’, E1.place);
emit( E.place, ‘:=’,t,‘*r’ ,E2 .place);
E.type:=real END
else BEGIN t:=newtemp;
emit(t,‘:=’,‘itr’, E2.place);
emit( E.place, ‘:=’,E1.place,‘*r’ ,t);
E.type:=real END}
8.4 布尔表达式的翻译
一、概述
布尔表达式在程序中有两个基本作用：用于逻辑演算、计算逻辑值；更多情况，用作控制语句（if-then或while语句）中的条件表达式。
布尔表达式是由布尔运算符（and,or,not）作用于布尔变量（常数）或关系表达式而形成，布尔表达式的形式为E1 rop E2 ，其中rop是关系符，E1和E2是算术表达式。
布尔表达式的文法表示：
E E and E| E or E| not E|(E)|id rop id|true|false
习惯地，布尔运算符的优先顺序：not，and，or 并假定and和or都服从作结合规则。所有关系符的优先级都是相同的，而且高于任何布尔算符，低于任何算术算符。关系符不允许结合。
二、布尔表达式的翻译方法
1、计算布尔表达式的两种方法：
（1）如同算术表达式，一步步计算出表达式各部分的真假值，最后计算出整个表达式的值；例如：
1 or ( not 0 and 0 ) or 0
= 1 or ( 1 and 0 ) or 0
= 1 or 0 or 0
= 1 or 0
= 1
（2）采取优化措施，只计算部分表达式。例如：要计算A or B，若计算出A的值为1，那么B的值就不需要计算了，因为不管B的值为何值，A or B的值都为1。
2、布尔表达式的翻译
例1、布尔表达式 not A or B and C翻译成四元式序列为：
(1) t1:= not A
(2) t2:= B and C
(3) t3:= t1 or t2
例2、对于a rop b的表达式，看成if a rop b then 1 else 0
(1) if a rop b goto (4)
(2) t:=0
(3) goto (5)
(4) t:=1
(5)…
其中（5）为后续的四元式序号。临时变量t存放布尔表达式a rop b的值。
3、将布尔表达式翻译成四元式的描述
nextstat——给出在输出序列中下一四元式序号。emit 过程每调用一次，nextstat 增加1。
(1)E →E1 or E2
{ E.place:=newtemp;
emit(E.place,‘:=’, E1.place,‘or’, E2.place)}
(2)E →E1 and E2
{ E.place:=newtemp;
emit(E.place, ‘:=’, E1.place,‘and’, E2.place)}
(3) E → not E1
{ E.place:=newtemp;
emit(E.place, ‘:=’,‘not’, E1.place)}
(4) E →(E1)
{E.place:= E1.place}
(5) E → id1 relop id2
{ E.place:=newtemp;
emit(‘if ’ , id1.place,relop,id2.place,‘goto’,nextstat+3);
emit(E.place, ‘:=’,‘0’);
emit(‘goto’,nextstat+2);
emit(E.place, ‘:=’,‘1’)}
(6) E → true
{ E.place:=newtemp;
emit(E.place, ‘:=’,‘1’);
}
(7) E → false
{ E.place:=newtemp;
emit(E.place, ‘:=’,‘0’);
}
作业：
P198 8.5
for循环语句翻译递归下降法输出三地址码///////////// #define MAX 100 #include
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) return(true); else return(false); } char GetChar(int i)///////读取字符 { char ch; ch=str[i]; return(ch); } char GetBC(char ch)////判断是不是空格或者换行，如果是，直接读取下一个字符直道不再空白为止{ if(ch==32||ch==10) { turn++; ch=GetChar(turn); ch=GetBC(ch);/////////递归实现 return(ch); } else return(ch); } void Concat()/////////////连接，即为strtoken[]赋值 { strToken[n]=ch; n++;
《编译系统设计实践》 实验项目三:语法制导翻译与生成中间代码 学号: 姓名: 年级: 学院: 数计学院 专业: 计算机 本组其它成员:学号姓名 学号姓名 实验时间: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语句的条件的三地址代码 void yuyifenxi_list() //生成并输出条件返回地址 void yuyifenxi_list_1() //递归---生成并输出条件返回地址 void yuyifenxi(int next,int &flag) //判断关键字,调用相应的产生式分析 void readfile() //文件读入 四、测试报告 1.第一组测试: 图1-1 输入待翻译代码
《编译系统设计实践》 实验项目三：语法制导翻译与生成中间代码 学号： 姓名： 年级： 学院：数计学院 专业：计算机 本组其它成员：学号姓名 学号姓名 实验时间：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语句的条件的三地址代码 void yuyifenxi_list() //生成并输出条件返回地址 void yuyifenxi_list_1() //递归---生成并输出条件返回地址 void yuyifenxi(int next,int &flag) //判断关键字，调用相应的产生式分析 void readfile()//文件读入 四、测试报告