编译原理(3)语义分析

正文索引 [隐藏]

编译原理:语义分析

woc 学校避重就轻跳过属性文法直接讲语义分析搞得我欲仙欲死,没办法自学一下

WOC期末考试要考一堆没讲的、不在课程大纲里的、连 PPT 都没有的玩意,紧急自学

​ 经过词法分析和语法分析之后,就要进行语义分析了,实现语义分析的基础就是属性文法,这里主要学习一下如何在自上而下和自下而上的分析中实现属性的计算。实际上,属性加工的过程就是语义分析。

一、属性文法

属性文法这个东西是在上下文无关文法的基础上,为每个文法符号(终结符或非终结符)配备若干值(属性)的文法。而对每个产生式都有一套语义规则,用于计算属性

1. 基本概念

  • 属性:在上下文无关文法的基础上,为每个文法符号配备若干代表 类型、值、代码序列、符号表内容 的相关值

    • 可以进行计算与传递
    • 属性的加工过程即为语义处理过程
  • 翻译模式:又称翻译方案,相比属性文法,属性文法将说明翻译顺序这些细节隐去了,而翻译模式则给出了使用语义规则进行计算的次序,如下例:
    $$
    A \rightarrow A_1Y \ \ \ \ \ {A.a:=g(A_1.a,Y.y)}
    $$

    $$
    A\rightarrow X \ \ \ \ \ {A.a:=f(X.x)}
    $$

  • 属性方程:描述属性的求值规则常常用作语义规则,并可以推广为包含一些函数和过程来描述常规意义下的语义动作。如:建立符号表、产生中间代码等

    • 一个属性方程只隶属于一个产生式,其中的文法符号仅限于该产生式中的文法符号
    • 如果一个文法符号在某一产生式中出现多次,那它的同名属性则作为不同的属性看待
  • 属性分类

    • 综合属性:用于“自下而上”(归约)传递信息

    • 语法树中,一个结点的综合属性是由此结点的子节点的属性值确定的

    • 终结符只有综合属性,由词法分析器提供
      因为终结符已经是“最下面了”,自下而上传递信息的信息源泉

    • 必须为产生式左边的综合属性提供计算操作

    • 仅使用综合属性的文法称为 S-属性文法

    • 继承属性:用于“自上而下”(推导)传递信息

    • 语法树中,一个结点的继承属性由此结点的父结点和兄弟结点的属性值确定

    • 文法开始符号的所有继承属性作为属性计算前的初始值
      因为文法开始符号是“最上面”,自上而下传递信息的信息源泉

    • 必须为产生式右边的继承属性提供计算操作

    • 方便表示上下文依赖关系,比如使用继承属性跟踪标识符,看其出现在赋值号左边还是右边

    • 举例:计算句子中嵌套括号最大深度

    img

    • S[0].level 就是一个综合属性,表示的是 S[0] 的 level 属性
    • 那些花括号里面的就是属性方程
    • 从第一个式子可以看出 S[0].level 依赖于 S[1].level 和 S[2].level

例题:文法及相应翻译方案如下:

$P\rightarrow bQb$ {print "1"}
$Q\rightarrow cR$ {print "2"}
$Q\rightarrow a$ {print "3"}
$R\rightarrow Qad$ {print "4"}

输入符号串 bcccaadadadb,该输入符号串的输出是什么?

解:先列归约树(或者最右推导),根据归约顺序打印,答案为 34242421

2. 处理方法

  1. 树遍历的属性计算方法

    先通过语法分析建立语法树,且树中带有开始符号的继承属性和终结符的综合属性,然后遍历语法树,计算剩余属性,但是要进行多次扫描,后面不做研究(主要是不考[捂脸])

  2. 一遍扫描的处理方法

    在语法分析的同时进行属性计算,不用构造语法树,效率提升。具体来说就是为每一个产生式都配上一组语义规则,在语法分析的同时进行属性计算:

    • S 属性文法:仅含有综合属性,进行自下而上分析的属性文法,常用于 LR 文法中

    • L 属性文法:自上而下单次遍历计算属性值,常用于 LL(1) 文法中

      img

      可以看到这个仅仅限制了继承属性,那么仅有综合属性的 S-属性文法就一定是 L-属性文法了

二、中间语言

一般来说,一个编译程序可以看成:源程序 --> 词法分析 --> 语法分析 + 语义分析 --> 机器指令,但是这样不利于代码优化,中间语言诞生了.

中间语言中的四元式其实也很像汇编指令,编译过程变为:源程序 --> 词法分析 --> 语法分析 + 语义分析 --> 中间语言 --> 优化 --> 机器指令,这样,语义分析的语义动作的目的变成了构建中间语言语句了。

下面介绍几种中间语言,不过重点在三地址代码,后缀式和抽象语法树就简要提一下,同时提供深入学习的链接。

1. 后缀式

  • 表示:又称逆波兰表示法,就是将算符放到操作数的右边,比如:a + b 用后缀式表达就是 ab+; 选择语句表示起来稍微麻烦一点,是三元运算,用 ?表达,if a then b else 表示为 abc?
  • 求值:从左到右扫描后缀式,每碰到运算量就把它推进栈,每碰到 k 目运算符就把它作用于栈顶的k个项,并用运算结果来代替这 k 个项

扩展学习:前缀、中缀、后缀表达式

2. 抽象语法树

这东西可以理解为归约树的化简版,简单变量或者常数的树就是该变量或者常数自身。一般叶子表示运算量,内结点表示OP,非常便于理解,如下图:

抽象语法树

那么语义分析的任务就是构建一棵树咯,用数据结构的知识就搞定了。

3. 三地址代码

三地址代码实质是抽象语法树的一种线性表示,其实还是一个抽象的东西,方便理解而不方便存储,一般会将三地址代码转化为三元式或者四元式(重要)进行代码存储。

三地址代码

  • 赋值:x := y
  • 索引取值:x := y[i]
  • 地址取值:x := &y
  • 指针取值:x := *y
  • 二元算术:x := y op z
  • 无条件转移:goto L
  • 条件转移:if x relop y goto L ( if x goto L)
  • 参数传递:param x
  • 过程调用:call p, n
  • 过程返回:return y

三元式

构成:OP ARG1 ARG2

  • OP:操作符,一般用整数编码存储
  • ARG:一般是指针(地址),指向符号表

举例:X := A + B * C

操作序号 OP ARG1 ARG2
(1) * B C
(2) + A (1)
(3) := X (2)

(3)

间接三元式:用一张间接码表辅助三元式表,出现相同的三元式时无需重复填入

间接三元式

计算动作的执行:先查间接码表,根据间接码表查三元式表,这样在中间代码优化时只用调整间接码表的次序即可,大大提升算法效率

四元式

构成:OP ARG1 ARG2 RESULT

  • OP:操作符,一般用整数编码存储
  • ARG:一般是指针(地址),指向符号表
  • RESULT:计算所得临时变量,填入符号表

举例:A:=-B(C+D) ps:负号用 @ 表示*

操作序号 OP ARG1 ARG2 RESULT
(1) @ B _ T1
(2) + C D T2
(3) * T1 T2 T3
(4) := T3 _ A

三元式和四元式的差异是表示式中有多少间接表示的问题。

三元式对于结果用指示器指向式子表示。

四元式使用临时变量,计算和使用的联系不那么直接了,允许重排顺序,利于优化。

三、语法制导的语义分析

这部分主要讲通过给定的语法、翻译模式,经过语法分析之后直接得到相应四元式的过程。

1. 简单赋值语句

翻译模式:
翻译模式

  • NEWTEMP:返回一个代表临时变量的整数码
  • ENTRY(i):返回终结符 i 在符号表中的位置
  • E.PLACE:存放 E 的变量名在符号表的入口 or 整数码(当 E 为临时变量时)
  • GEN(OP, ARG1, ARG2, RESULT):把四元式填入四元式表

使用过程:
间接三元式

上面这种简单的方法默认了所有终结符都是整型变量,如果要支撑类型转换,就需要加上类似的语义规则:
$$
{IF\ E^{(1)}.MODE = int\ \ AND\ \ E^{(2)}.MODE= int\ THEN\ E.MODE:=int\ ELSE\ E.MODE := r}
$$
加上这种语义规则之后,四元式的 OP 就要运算的类型(MODE),必要时还要能够产生类型转化:
$$
(+^i,Y,T_2,T_3)\
(itr,A1,\,T)
$$

2. 布尔表达式

布尔表达式能干两件事:求值、条件控制。求值没什么,方法和简单赋值语句一样不赘述,但是应用在条件控制的时候比较复杂。

首先先明确下这里所述的布尔表达式的约束条件:
布尔表达式约定

那么这里计算布尔表达式 E 就是第一个要面对的问题,有两种方法:

  1. 一般算法:和算术表达式一样计算

  2. 短路算法:

    A ∨ B if A then true else B

    A ∧ B if A then B else false

    ┐ A if A then false else true

上述这两种办法仅在布尔函数调用的时候有差别,其他时候可以放心使用短路算法

举例(一般算法):将 A∨B∧C=D 翻译成四元式

  1. = C D T1
  2. ∧ B T1 T2
  3. ∨ A T2 T3

3. 条件控制语句

无嵌套 IF 语句

看最简单的条件语句 if E then S1 else S2,执行 S1 还是 S2 是由 E 的真假控制的,所以要有真出口假出口的概念:

  • 真出口:E 为真,下一条语句执行位置
  • 假出口:E 为假,下一条语句执行位置

举例:IF A∨B<D THEN S1 ELSE S2
IF语句翻译

直观挺好理解,但是对于一步一步翻译的计算机来说就非常蛋疼,因为在将 E 算出来之后还不知道真假出口的位置在哪(比如 1 语句是不知道向哪里走的,因为 5 语句还没有翻译出来呐),所以转向地址是没有办法填的。只有当翻译进行到出口语句的时候再回过头取将地址填入真假出口位置

拉链-反填法

假设 p, q, r 的真出口都是 t
拉链法1

拉链法构造过程
拉链法2

  • 0 代表链尾,链首是最新翻译出来的四元式地址(图一中为 r)
  • 翻译出 t 时开始回填,从链首 r 遍历链填 t

根据这个思想,可以构造出如下的翻译模式
拉链法3

  • nextquad:指向下一条将要产生的四元式地址
  • makelist(i):创建一个仅含 i 的新链表,其中 i 表示四元式组的一个标号,函数返回指向这个新链表的指针
  • merge(p1, p2):将以p1, p2为链首的两条链表合并为一条, 返回合成链表的链首
  • backpatch(p,t):将以 p 为链首的链表所有四元式第四区段全填成 t

举例:通过分析树看一遍拉链的过程
拉链法4

含嵌套 IF 语句

if E1 then { if E2 then S1 else S2 } else S3

翻译完 S1 需要跳过 S2,要命的是还要跳过 S3(当 E1,E2 为真时才执行 S2),进一步来说有几层嵌套就要多跳几层,又是让计算机懵逼的一个活。

解决办法使用 S.CHAN,它指出一条链,该链式所有期待翻译完 S 后回填目标的四元式构成的,回填目标可能是{S}得下一条四元式,也可能不是。真正的回填,要在处理完S的外层后进行,翻译模式修改如下(加粗的是新增规则):
IF语句翻译2

WHILE 语句

有 IF 语句的铺垫, WHILE 语句就非常好理解(毕竟这东西还没有 ELSE 那一堆幺蛾子事儿):

  • 真出口指向 while 循环内执行代码
  • 假出口指向 while 循环外代码
  • 循环内最后异一步跳转回 while 条件判断

翻译模式:
WHILE语句翻译

标号和转移语句

标号:

L: S
Goto L

语言中允许标号先定义后使用,也允许先使用后定义。

先使用后定义这种情况和 IF 语句不知道真假出口在哪有着异曲同工之妙,不过这个就不存在拉链的问题了,直接悬置等到定义了再回填

4. CASE 语句

CASE 语句

case E of 
C1:S1
C2:S2
...
otherwise:Sn
end

当分叉只有 10 个左右时,翻译成条件转移语句

T := E;
L1: IF T != C1 GOTO L2
S1;
GOTO NEXT;
L2: IF T != C2 GOTO L3
S2;
GOTO NEXT;
...
LN: Sn;
NEXT:...

当分叉比较多的时候,可以考虑整个开关表出来
CASE语句翻译

  • 产生时,将 E 值送到该表末项的指令组,以及一个对E值查找开关表的程序
  • 运行时,循环程序对 E 值查开关表,当E与某个Ci匹配就执行Si

分叉如果特别多,嗯,目标就是优化分叉表了,数据结构 Hash 表走起,不赘述了

还有一种情况,选择子 E 在基本连续的一个范围(可通过变换)内变化, 如从 0 到 127,只有少数几个值不为Ci,则可建立一个数组B[0:127],每个元素 B[Ci] 中存放着 Si 的地址

5. 数组元素的引用

数组引用取值、存数的四元式就可以写成这样:

变址取数 X:=T1[T]
(=[], T1[T], _, X)

变址存数 T1[T]:=X
([]=, X, _, T1[T])

数组元素的引用,最重要的就是要根据给出的 index 计算出元素的真实地址,首先给出数组存储的约定:假设数组元素按行存放,每维下限都为1,上限为dn,每个元素只占一个机器字,目标机器存储器是以字编址的。

那么数组元素 A[i1, i2, ..., in] 的地址 D 计算公式如下:
$$
D = CONS + VAR
$$

$$
CONS = firstadrress - C
$$

$$
C=d_2d_3...d_n+d_3d_4...d_n+...+d_n+1
$$

$$
VAR=i_1d_2d_3...d_n+i_2d_3d_4...dn+...+i{n-1}d_n+i_n
$$

ps:看着高级,如果换成编程常用的每维下限是 0 的话 C = 0,再组合起来看,是不是顺眼多了?现推都行,根本不用记。

这么将 CONS 和 VAR 分开是为了简化计算,CONS 仅取决于数组首地址、各维度的上下限,这些都是在数组定义的时候确定的,只需要在翻译的时候作为数组的一条属性录入即可,而数组元素的引用只用计算 VAR,然后 CONS + VAR 即为地址。

有了上面的概念,下面就来看看在符号表中数组数据到底啥样子:
数组引用翻译
简单变量可以在符号表中查到它的地址,而数组元素却不行,在符号表中只有它们的总代表——数组名的入口。

翻译模式
数组引用翻译2

  • elist.ARRAY:数组名的符号表入口

  • elist.DIM:数组维数计数器

  • elist.PLACE:已形成的 VAR 的中间结果名字在符号表中的位置,或者是一个临时变量的整数码

  • LIMIT(ARRAY,k):函数过程,数组 ARRAY 的第 k 维长度dk

  • V.PLACE

    简单变量:变量名的符号表入口

    下标变量:保存CONSPART的临时变量的整数

  • V.OFFSET

    简单变量:NULL(用于区分简单变量和下标变量)

    下标变量:保存VARPART的临时变量的整数码

举例:A是一个10*20的数组,A[I+2,J+1]:=M+N 的翻译
数组引用翻译3
ps:这个示例看起来并没有把 CONS 起来,而是直接算了一遍(-, A, 21, T4),嗯它存的是 C=1*20+1=21,上课时用的 SB PPT,算了理解万岁 oV_Vo

6. 过程调用

过程调用本质上就是是把控制权转移给子程序,一个转移语句即可搞定,最重要的问题是如何传递参数、返回参数。

一个简单方法:由指令携带参数地址,把实参地址统一放在CALL 指令前,如下

如 CALL S(A+B,Z) 翻译成
K-4: {T := A+B}
K-3: Par T
K-2: Par Z
K-1: Call S
K:   …

四元式:
(+, ENTRY(A), ENTRY(B), T)
(par, _, _, T)
(par, _, _, Z)
(Call, _, _, ENTRY(S))
注意这个 par 代表一个将第四元添加到参数队列中去

根据这个思想,可以得到如下翻译模式
过程调用翻译

另外提一下,数组引用和 CALL 如果都用 ''()'' 会产生歧义,有如下解决方案:

  1. 查符号表
  2. 词法分析器在发送A之前先查表确定其特性
  3. 规定数组用[],避免冲突
  4. 先说明后引用,则使用两边扫描

7. 类型声明语句

Integer L,M,N;
ARRAY A;

语义动作是把 L,M,N,A登记到符号表中,并在相应位置填入整型等数据类型、性质。

可以构造一个简单的翻译模式完成这个任务,如下:
类型声明翻译

如果声明的是一个数组,就要填一数组的一堆属性了:
类型声明翻译2

  • l:每维上限
  • u:每维下限
  • d:长度

总结

​ 如果说词法分析接地气、语法分析繁琐的话,语义分析已经快上升到玄学的地步了,这篇总结直接绕过了最为恶心的部分——构造属性文法,可以看到一种语句的翻译有非常多种思路,每一种思路根据构造者的思维方式不同有非常多种翻译模式,而实际上,不同的编程者又会用不同的编程语言、算法思路去实现这些翻译模式。而且,在没有了解符号表、程序运行的存储空间内部是如何运转的前提下,是不可能完全掌握的。但是没有语义分析的前置知识,看存储空间就是在自裁。

​ So,管它嘞,我只是个要苟过期末的菜鸡,理解原理就差不多了,手动造轮子撸编译器是不可能的,这辈子都......啊呸,滚去继续复习了。