编译原理 第六章 语义分析与中间代码生成

编译原理 第六章 语义分析与中间代码生成

属性文法

在上下文无关文法的基础上,为每个文法符号(非终结符或终结符)配备若干相关的值(属性)。属性与变量一样,可以进行计算和传递。属性加工的过程,就是语义处理的过程。对于文法的每个产生式都配备了一组属性的计算规则,称为语义规则。

属性通常分为两类,综合属性和继承属性。综合属性用于自下而上传递信息;继承属性用于自上而下传递信息。

在一个属性文法中,对应于每个产生式 \(A\rightarrow \alpha\) 都有一套与之相关联的语义规则,每条规则的形式为: \[b:=f(c_1,c_2,...c_k)\]

在以下两种情况下,我们认为属性 b 依赖于属性 \(c_1,c_2,...c_k\)

  • b 是 A 的一个综合属性并且 \(c_1,c_2,...c_k\) 是产生式右边文法符号的属性;
  • 或者 b 是产生式右边某个文法符号的一个继承属性并且 \(c_1,c_2,...c_k\) 是 A 或产生式右边任何文法符号的属性。

终结符只有综合属性,由词法分析器提供;非终结符既有综合属性又有继承属性,文法开始符号的所有继承属性作为属性计算前的初始值。

语法树中,一个结点的综合属性的值由其子结点的属性值确定,通常采用自底向上的方法进行计算。仅仅使用综合属性的属性文法称 S-属性文法。

语法树中,一个结点的继承属性由此节点的父结点和/或兄弟结点的某些属性确定。

语法制导翻译方法

基于属性文法的处理过程通常是:对单词符号进行语法分析,构造语法分析树,根据需要遍历语法树并在语法树各结点处按语义规则进行计算。

这种由源程序的语法结构所驱动的处理方法就是语法制导翻译法。在某些情况下,并不一定按照上述的过程进行,可用一遍扫描实现属性文法的语义规则计算。即在语法分析的同时完成语义规则的计算,对于 L-属性文法,不用显式构造语法树就可以实现翻译。

依赖图

用依赖图来描述一棵语法树中结点的继承属性和综合属性之间的相互依赖关系。依赖图中为每一个属性设置一个结点,如果属性 b 依赖于属性 c,则从属性 c 的结点有一条有向边连到属性 b 的结点。

依赖图可按如下步骤构造;

一个有向非循环图的拓扑序是图中结点的任何顺序 \(m_1,m_2,...,m_k\),使得边必须是从序列中前面的结点指向后面的结点。一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。即,在拓扑排序中,在一个结点上,语义规则 \(b:=f(c_1,c_2,...c_k)\) 中的属性 \(c_1,c_2,...c_k\) 在计算 b 以前都是可用的。

如果一属性文法不存在属性之间的循环依赖关系,那么该文法是良定义的

树遍历的属性计算方法

在常用的深度优先,从左到右的遍历方法,在建立语法分析树的基础上。

1
2
3
4
5
6
7
8
9
10
11
12
while(语法树中还有未被计算的属性)  
VisitNode(S); // S 是文法的开始符号

void VisitNode(Node N){
if(N 是非终结符 )
// 假设 N 的产生式为 N→X1X2…Xm
for(i=1; i <= m; i ++)
if(Xi 是非终结符){
计算 Xi的所有能够计算的继承属性; VisitNode(Xi);
}
计算 N 的所有能够计算的综合属性;
}

一次扫描的处理方法

与树遍历的属性计算方法不同,一边扫描的处理方法是在语法分析的同时计算属性值,且无需构造实际的语法树(如有必要,也可构造)。

从一遍扫描的角度看,所谓语法制导翻译法,直观上说是为文法中每个产生式配上一组语义规则,并且在语法分析的同时执行这些语义规则。

自上而下的语义分析中, 若一个产生式匹配输入串成功,或者在自下而上分析中,当一个产生式被用于进行归约时,此产生式相应的语义规则就被计算,完成有关语义分析和代码生成的工作。

两类特殊的属性文法

S-属性文法

S-属性文法仅含有综合属性,而且综合属性可以在分析输入符号串的同时自下而上的分析器来计算。分析器可以保存与栈中文法符号有关的综合属性值,每当进行归约时,新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。

在自下而上的语法分析中,我们曾使用一个栈来存放已经分析过的子树的信息,现在我们可以在分析栈中附加一个域来存放综合属性值。

假设产生式 \(A\rightarrow XYZ\) 的语义规则是 \(A:=f(X.x,Y.y,Z.z)\),并且综合属性恰好是在每次归约前计算的。

L-属性文法

一个文法称为 L-属性文法,如果对于文法的每个产生式 \(A\rightarrow X_1X_2...X_n\),其每个语义规则中的每个属性或者是综合属性,或者是 \(X_j(1\leq j\leq n)\) 的一个继承属性,而且该继承属性仅依赖于:

  • 产生式 \(X_j\) 的左边符号 \(X_1X_2...X_{j-1}\) 的属性;
  • A 的继承属性

可以看出,S-属性文法是 L-属性文法的特例。

属性文法只是一种关于语言翻译的高级规范说明,并不含具体的实现细节。在进行语法制导翻译时,用的是属性文法的另一种描述形式——翻译模式。翻译模式给出了使用语义规则进行计算的次序(也称为语义动作),用花括号 “{” 和 “}” 括起来,插入到产生式右部的合适位置上。

例如:

其带语义动作的 9-5+2 的语法树为:

翻译模式的设计必须保证当某个动作引用一个属性时,该属性是有定义的,而 L-属性文法本身就能确保每个动作不会引用尚未计算出来的属性。

当文法中仅含综合属性时,其翻译模式可以这样来建立:为每一个语义规则建立一个包含赋值的动 ,并把该动作放在相应产生式右边的末尾;

当文法中既含有综合属性,又含有继承属性时,其翻译模式的建立需满足如下要求:

  • 产生式右边符号的继承属性必须在这个符号以前的动作中计算出来。
  • 一个动作不能引用该动作右边符号的综合属性。
  • 产生式左边非终结符的综合属性只有在它引用的所有属性都计算出来之后 才能计算,这种计算通常可以放在产生式右端的末尾。

中间代码的形式

编译程序所使用的中间代码形式很多,常见的有后缀式、图表示法和三地址代 码(包括三元式、四元式、间接三元式)等。其中,用得多的是三地址代码。

后缀式

即逆波兰表达式。把操作数写在前面,运算符写在后面。

一个表达式 E 的后缀式采用如下的递归方式定义:

  • 如果 E 是一个变量或常量,则 E 的后缀式是 E 自身;
  • 如果 E 是 E1 op E2 的形式(op 是二元运算符),则 E 的后缀式为 E1' || E2' || op, 其中,E1' 和 E2' 分别为 E1 和 E2 的后缀式,|| 是后缀式的连接;
  • 如果 E 是 (E1) 的形式,则 E1 的后缀式就是 E 的后缀式。

把表达式翻译成后缀式的属性文法:

图表示法

抽象语法树

算符优先级别低的,放在树的上部。操作符和关键字都不作为叶结点,而作为内部结点。

赋值语句 a:=b*(-c)+b*(-c) 的抽象语法树如下:

产生赋值语句抽象语法树的属性文法如下:

DAG

对于表达式中的每个子表达式,DAG 中相应的都有一个结点,一个内部结点代表一个操作符,其子结点代表操作数;DAG 中代表公共子表达式的结点具有多个父结点,而抽象语法树中的公共子表达式被表示为重复的子树。

赋值语句 a:=b*(-c)+b*(-c) 的 DAG 如下:

结点 ∗ 与其父结点 + 之间存在两条边,可以认为 ∗ 有两个父结点 +。

三地址代码

三地址代码最多包含三个地址,两个用来表示操作数,一个用来存放结果,通常形式为:\(x:=y\ op \ z\)

使赋值语句产生三地址代码的属性文法:

一般用三种方式来表示三地址语句分别是四元式、三元式以及间接三元式。

四元式

一个四元式是具有四个域的记录结构,形如:

\[(序号)\ (op,arg_1,arg_2,result)\]

三元式

为了避免临时变量带来的时空开销,可以通过计算临时变量值的代码的位置来引用该临时变量,从而使得表示三地址代码的记录只需 3 个域,形如:

\[(序号)\ (op,arg_1,arg_2)\]

说明语句的翻译

在 C、Pascal、FORTRAN 等语言的语法中,允许一个过程中的所有说明语句作为一个组来处理,安排在一所数据区中。用全程变量 offset 来跟踪下一个可用的相对地址的位置。

下图就是关于说明语句的翻译模式:

  • tblptr 用来保存各个外层过程的符号表指针;
  • S 表示各类可执行语句;
  • T 表示类型语句,含有两个综合属性 typewidth,分别表示名字的类型和域宽;
    • 上图假定整数域宽 4,实数域宽 8,指针域宽 4
  • mktable(previous) 创建一张新符号表,并返回一个指向新表的指针,previous` 指向一张先前创建的符号表;
  • addwidth(table, width) 在指针 table 所指的符号表表头中填入该表中所有名字所占用的总宽度;
  • enter(table, name, type, offset) 在指针 table 所指的符号表中为名字 name 建立一个新的表项,并将类型 type、相对地址 offset 填入该项中;
  • enterproc(table, name, newtable) 在指针 table 所指的符号表中为过程 name 建立一个新的表项,newtable 用来指向过程 name 的符号表。

一般情况下,对于说明语句的语义处理只是用来查填符号表,并不生成中间代码,但是过程说明和动态数组的说明例外。

赋值语句的翻译

这里首先讨论简单赋值语句的翻译,先不考虑对数组元素的寻址和引用。 下图是简单算术表达式的翻译模式:

  • lookup(id.name) 来检查符号表中是否存在该名字,若存在,则返回一个指向该表相的指针,否则返回 nil
    • lookup(id.name) 工作时,首先通过 tblptr 栈顶指针在当前符号表中查找 name,若未找到,则利用当前符号表表头的指针找到该符号表的外围符号表,然后在那里查找名字 name,直到找到 name 为止。如果所有外围过程的符号表 中均无 name,则 lookup 返回 nil,表明查找失败。
  • emit() 将生成的三地址语句发送的输出文件中

为了快速访问数组中的元素,一般放在连续的存储空间中。因此,具体访问某个具体的数组元组,需要计算该数组元素的地址。

若数组 A 的元素存放在一片连续单元里,则可以较容易地访问数组的每个元素。 假设数组 A 每个元素宽度为 w,则 A[i] 这个元素的起始地址为: \[base+(i-low)\times w\]

其中,low 为数组下标的下界,base 是分配给数组的相对地址。若将上式改写成 \(i\times w+(base-low\times w)\),则子表达式 \(base-low\times w\) 可在处理数组说明时提前计算出来。

对于二维数组,有者类似的处理,一个二维数组可以按行或按列处存放。

对于按行存放的二维数组 A 来说,可用如下公式计算 \(A[i_1,i_2]\) 的相对地址: \[base+((i_1-low_1)\times n_2+i_2-low_2)\times w\]

其中,\(low_1、low_2\) 分别为 \(i_1、i_2\) 的下界,\(n_2\)\(i_2\) 可取值的个数,若 \(i_2\) 的上界为 \(high_2\),则 \(n_2=high_2-low_2+1\)。上式可改写为 \[((i_2 \times n_2)+i_2)\times w+(base-((low_1\times n_2)+low_2)\times w)\]

则子表达式 \((base-((low_1\times n_2)+low_2)\times w)\) 可在编译时确定。

按行或按列存放方式可以推广到多维数组的情形。若多维数组 A 按行存放,则可推广如下公式计算元素 \(A[i_1,i_2,...i_k]\) 的相对地址: \[((...i_1n_2+i_2)n_3+i_3)...)n_k+i_k)\times w+C\]

其中,\(C=base-((...((low_1 n_2+low_2)n_3+low_3)...)n_k+low_k)\times w\),如果对于任何 j,\(n_j=high_j-low_j+1\) 都是确定的,那么 C 可以在编译时计算出来。

为对数组元素进行翻译。在简单赋值语句翻译模式中 id 出现的地方引入下列产生式:

\[\begin{align}&L\rightarrow id[Elist]|id \\ &Elist\rightarrow Elist,E|E \end{align}\]

为了便于语义处理,可将上述产生式改写为

\[\begin{align} &L\rightarrow Elist]| id \\ &Elist\rightarrow Elist,E|id[E \end{align}\]

非终结符 Elist 有综合属性 array,用来记录指向符号表中相应数组名字的指针;Elist.ndim 来记录 Elist 中的下表表达式的个数,即维数;调用函数 limit(array,j) 来返回 \(n_j\),即 array 所指示的数组的第 j 维长度;Elist.place 表示临时变量,用来存放由 Elist 中的下表表达式计算出来的值。

代表变量的非终结符 L 有两个属性 L.placeL.offset。前者表示指向符号表中相应名字表相的指针,后者表示数组元素相对于起始地址的偏移量。当 L 为一个简单名字时,L.offestnull

赋值语句加入数组元素之后的翻译模式如下:

(注,公式对应参考教材 p182)

布尔表达式的翻译

假定布尔表达式定义如下: \[E\rightarrow E\ or\ E\ |\ E\ and\ E\ |\ not\ E\ |\ (E)\ |\ id\ relop\ id\ |\ id\]

用语义变量 relop.op 来表示关系运算符,规定运算顺序是先括号内,后括号外,not 运算的优先级最高,其次是 and,其次是 or,且满足左结合原则。

在程序设计语言中,布尔表达式的作用有两个:一个是用作布尔赋值语句中的布尔运算,另一个是用作控制流语句中的条件表达式。同样,对于布尔表达式的计 算也有两种方法:一种是像计算算术表达式那样按部就班、一步一步地求解,另一 种是采取某种优化措施来进行。

下图给出了将布尔表达式翻译为三地址代码的翻译模式:

布尔运算有某些特殊性质可以采用优化措施进行运算。\(E_1\ or\ E_2\) 中,只要 \(E_1\) 为真,表达式结果一定为真,\(E_1\) 为假时,表达式结果由 \(E_2\) 决定。同理,\(E_1\ and\ E_2\) 中,只要 \(E_1\) 为假,表达式结果一定为假,\(E_1\) 为真时,表达式结果由 \(E_2\) 决定。

E.true 表示布尔表达式 E 的真出口,即 E 为真时应转向执行的中间代码位置,用 E.false 表示布尔表达式 E 的假出口,即 E 为假时应转向执行的中间代码位置。用以下四元式实现三地址代码:

  • \((jnz,E,\_,P)\) 表示当 E 为真时,跳转到四元式 P;
  • \((jrop,id_1,id_2,P)\) 表示当 \(id_1\ rop\ id_2\) 为真时跳转到四元式 P,其中 rop 代表六种关系运算之一;
  • \((j,\_,\_,P)\) 表示无条件跳转到四元式 P

通过一遍扫描来产生布尔表达式的中间代码时,对于生成的某些转移语句,可能还不知道该语句的具体转向位置,可以把这些转移方向相同的四元式链在一起,形式四元式链表,当目标确定之后再回填。 因此,对 E 的两个综合属性 truefalse 的意义进行拓展,规定 E.ture 不仅表示 E 的真出口,而且表示 E 中具有相同真出口的四元式链表的链首; 类似地,规定 E.false 不仅表示 E 的假出口,而且表示 E 中具有相同假出口的四元式链表的链首。

下图给出基于优化计算法的翻译模式:

  • nextquad 指向下一条将要产生的四元式的编号,初值为 1,每执行一次 emit,其值加一;
  • \(merge(p_1,p_2)\) 把两条链合二为一,返回合并后的链首
  • backpatch(p,t) 完成回填功能,把链首 p 所链接的每个四元式的第 4 分量都改写为地址 t。

控制语句的翻译

其实控制语句就是根据布尔表达式的值进行控制(跳转)的语句。其翻译模式为:

注意

第七章符号表与运行时存储空间组织 和 第八章优化 暂不做记录,待有时间补充。

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×