编译原理备忘录-语法制导

内容

  • 语义计算
  • 静态语义分析
  • 中间代码生成
  • 代码优化

1. 语义处理(计算)

2. 前提

词法分析、语法分析只能保证程序在书写上是正确的、在语法上是正确的，不能保证含义（语义）上的正确性

  • 词法分析阶段把字符流翻译为单词流
  • 语法分析阶段把单词流翻译为语法树
  • 语义分析和代码生成阶段把语法树翻译为汇编代码或者机器代码等等

3. 目标

  • 审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义
  • 如果静态语义正确，语义处理则要执行真正的翻译，即，或者将源程序翻译成程序的一种中间表示形式（中间代码），或者将源程序翻译成目标代码。

4. 语义计算模型

  • 属性文法
  • 翻译模式

5. 属性文法

定义

  • 在上下文无关文法的基础上，
    • 为每个文法符号关联多个属性（Attribute）
    • 为文法的每个产生式关联一个语义规则集合或称为语义动作
  • $A=(G,V,F)$
    • $G$：上下文无关文法
    • $V$：每个文法符号有一组属性
    • $F$：每个文法产生式$A\rightarrow a$有一组形式为$b:=f(c_1,c_2…c_n)$的语义规则（属性规则），其中$f$是函数，$b$和$c_1,c_2…c_n$是该产生式文法符号的属性

类型

  • 综合属性（Synthesized Attributes）
    • 属性值是分析树中该结点的子结点的属性值的函数
    • 对于$A\rightarrow x_1,x_2…x_n$，$S(A):=f(I(x_1),I(x_2)…I(x_n))$
  • 继承属性（Inherited Attributes）
    • 属性值是分析树中该结点的父结点和/或兄弟结点的属性值的函数
    • 对于$A\rightarrow x_1,x_2…x_n$，$T(x_j):=f(I(x_1),I(x_2)…I(x_n))$

属性规则(语义规则)

  • 也有称之为属性方程
    • 将属性值a与文法符号X联系起来，记为X.a

用于描述如何计算当前产生式中文法符号的属性值或附加的语义动作

将语义以“属性”的形式附加到各文法符号上，再根据产生式所蕴含的语义，给出每个文法符号的属性的求值规则，从而形成一种带有语义属性的前后文无关文法，即属性文法。

  • $属性变量:=<属性表达式>$

    • $b:=f(c_1,c_2…c_n)$

  • 属性规则中的左部$b$只能为下述两种变量：

    • 产生式左部符号的综合属性变量

      • 对关联于产生式$A\rightarrow a$的语义规则$b:=f(c_1,c_2…c_n)$，如果$b$是$A$的某个属性, 则称$b$是$A$的一个综合属性，用于“自下而上”传递信息

    • 产生式右部符号的继承属性变量

      • 对关联于产生式$A\rightarrow a$的语义规则$b:=f(c_1,c_2…c_n)$，如果$b$是产生式右部某个文法符号$X$的某个属性，则称$b$是文法符号$X$的一个继承属性，用于“自上而下”传递信息

例：简单算术表达式求值的语义描述

1
2
3
4
5
6
7
8
产生式 　　　　　　    语义规则 
L → E              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
  • 按照语义规则对每个产生式来说，它的左部E，T，F的属性值的计算来自它右部的非终结符，这种属性称作综合属性
  • 单词digit仅有综合属性，它的值是由词法分析程序提供的
  • 和产生式L→E相联的语义规则是一个过程，打印由E产生的表达式的值。我们可以理解为L的属性是空的或是虚的

例：综合属性与继承属性

* 输入串$aabbcc$分析过程

  • 自下而上执行综合属性相应的语义动作

  • 自上而下执行继承属性相应的语义动作

属性传递

1
2
3
4
5
6
（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）}

  • 一种传递图解

6. 语法制导翻译

定义（非语法制导定义）

  • 在语法分析过程中，随着分析的步步进展，每当进行推导或归约时，同步的去执行每个产生式所附带的语义规则描述的语义动作，这样进行翻译的办法称作语法制导翻译

    另解：由语法分析程序的分析过程来主导的翻译过程

语法制导翻译的根本上是在一个上下文无关文法中通过向结果中添加动作（action）来工作的，从而形成语法制导定义（Syntax-Directed Definition）。动作是指，一个结果在推导过程中被使用的时候，将要被执行的步骤或过程

例：中缀算术表达式翻译为后缀表示形式

  • 语义描述（注意到属性文法(语义规则)是转换后缀表达式文法）

    1
    2
    3
    4
    5
    6
    E→T + E1   { E.code=T.code|| E1.code||+ }
    E→T            { E.code=T.code }
    T→F * T1   { T.code=F.code||T1.code|| * }
    T→F            { T.code =F.code }
    F→（E）    { F.code = E.code }
    F→a             { F.code = a }

  • 最左推导

    $E\Rightarrow T+E\Rightarrow F+E\Rightarrow a+T\Rightarrow …\Rightarrow a+b*c$

  • 语义规则计算带入推导过程

    1
    2
    3
    4
    5
    6
    7
    8
    (E , E.code) => (T+E, T.code||E.code||+ ) 
                 => (F+E, F.code||E.code||+ )
    　　　       =>  (a+E, a||E.code||+ )
    　　　　     => (a+T, a||T.code||+ )
    　　　       => (a+F＊T, a||F.code||T.code||＊||+ )
    　　　　     => (a+b＊T, a||b||T.code||＊||+ )
        　　　   => (a+b＊F, a||b||F.code||＊||+ )
    　　　　     => (a+b*c, a||b||c|| ＊||+ )

  • 去掉$a||b||c|| ＊ || +$中的连结符，得到中缀表达式$a+b＊c$的后缀式$a b c ＊ + $

7. 基于属性文法的语义计算

方法

  • 树遍历
    • 输入串→ 语法树→ 依赖图→ 计算语义规则顺序→ 语法分析树遍历→ 执行语义规则
  • 单遍

7.1. 树遍历

依赖图

  • 依赖图是一个有向图，用于描述分析树中的属性和属性之间的相互依赖关系

  • 构造算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    for 分析树中每一个结点n  do
            for 结点n所用产生式的每个语义规则中涉及的每一个属性a  do
                 为a在依赖图中建立一个结点；
            for 结点n所用产生式中每个形如f(c1,c2,…ck)的语义规则 do
                 为该规则在依赖图中也建立一个结点（称为虚结点）；
        for 分析树中每一个结点n    do
            for 结点n所用产生式对应的每个语义规则  b:=f(c1,c2,…ck) do
                 （可以只是f(c1,c2,…ck) ，此时b结点为一个虚结点）
                 for  i :=1 to k do
                     从ci结点到b结点构造一条有向边

  • int id1, id2, id3的分析树的依赖图👇（参照$D\rightarrow TL$例）

    * **若依赖图是无圈的**，则按造此无圈图的一种拓扑排序（Topological sort）对分析树进行遍历，则可以计算所有的属性

7.2. 单遍

定义

  • 语法分析遍的同时进行属性计算
    • 自下而上方法
    • 自上而下方法
  • 对特定文法
    • S-属性文法
    • L-属性文法

7.2.1. S-属性文法

定义

  • 仅仅使用综合属性的属性文法

    在语法树中，一个结点的综合属性的值由其子结点的属性值确定。而叶结点的（终结点）的综合属性值由词法分析得到。

基于LR分析的语义计算

  • 扩充分析栈

  • 分析过程(四则运算例)

    * 注意到语义计算过程中，仍然可能存在**类型匹配**的问题

    • 语法制导的类型检查

      1
      2
      3
      4
      5
      E→T1 + T2   
          { if  T1.type = int  and  T2.type= int
           then  E.type :=int 
           else  error
          }

7.2.2. L-属性文法

定义

  • 可以包含综合属性，也可以包含继承属性

  • S-属性文法是L-属性文法的一个特例

    L-属性文法是下列属性文法，如果对于每一个产生式A ->X1X2… Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj（1≤ j≤n）的一个继承属性(inherited attribute)，且这个继承属性仅依赖于：

    • 产生式Xj在左边符号X1X2… Xj-1的属性;
    • A的继承属性

基于LL1的语义计算

  • 深度优先后序遍历算法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    procedure dfvisit(n: node);
              begin
                  for n 的每一孩子m, 从左到右 do 
                        begin
                             计算 m 的继承属性值;
                             dfvisit(m)
                        end;
                        计算n的综合属性值
              end

8. 静态语义分析

定义

  • 编译阶段进行的语义分析叫静态语义分析

内容

  • 静态类型检查（type checks）
  • 控制流检查（flow-of-control checks）
    • 控制流语句必须使控制转移到合法的地方（如 break 语句必须有合法的语句包围它）
  • 唯一性检查（uniqueness checks）
    • 很多场合要求对象只能被定义一次（如枚举类型的元素不能重复出现）
  • 名字的上下文相关性检查（name-related checks）
  • …

9. 符号表

符号表的作用和地位

  • 语义检查的依据和目标代码生成阶段地址分配的依据

    属性信息：存放语言程序中出现的有关标识符的属性信息，在编译的不同阶段都要用到

    语义检查：在语义分析中，符号表所登记的内容将用于语义检查（如检查一个名字的使用和原先的说明是否一致）和产生中间代码

    存诸分配：在目标代码生成阶段，当对符号名进行地址分配时，符号表是地址分配的依据。

分类

1
2
3
4
5
6
PROCEDURE   INCWAP（M，N）
   BEGIN
  10：K＝M＋1
         M＝M＋4
         N＝K         
   END

经编译头三阶段后所产生的主要表格有：符号名表SNT、常数表CT、入口名表ENT、标号表LT和四元式表QT

**组织**

符号表项的组织传统上采用三种构造方法。即线性法，排序法及散列法

  • 线性组织：按符号在程序中被扫描到的先后顺序组织
  • 排序组织：按符号从大到小或从小到大的顺序排列
  • 散列组织：一个符号在散列表中的位置由对该符号进行某种函数（杂凑函数）操作所得到的函数值来决定。

10. 中间代码生成

定义

中间代码（语言）是一种特殊结构的语言，编译程序所使用的中间代码有多种形式。按其结构分常见的有逆波兰式（后缀式）、三地址代码（三元式、四元式）和树形表示（抽象语法树）、DAG表示

  • 逆波兰式是最简单的一种中间代码表示形式

引入

  • 用于源语言和目标语言之间的桥梁，避开二者之间较大的语义跨度，使编译程序的逻辑结构更加简单明确
  • 利于编译程序的重定向
  • 利于进行与目标机无关的优化

逆波兰式

  • 运算顺序不变
  • 运算符跟在运算分量之后无括号
  • 运算符出现的顺序就是运算的顺序

11. 后缀式

一般表示

  • op为k目运算符，则op作用于e1e2…ek的结果用 e1’e2’…ek’op 来表示

    1
    2
    3
    if a then if c-d then a+c else a*c else a+b 
    ⇒ a?c-d?a+c:a*c:a+b 
    ⇒ a cd- ac+ ac*? ab+?

12. 三地址代码

定义

  • 形如x:=y op z
  • x+y*z=>t1:=y*z t2:=x+t1

常用的三地址表示

1
2
3
4
5
6
7
赋值语句       x := y op z， x := op y， x := y
无条件转移     goto L
条件转移       if x relop y goto L
过程调用       param x 和call p , n
过程返回       return y
索引赋值       x := y[i]和 x[i] := y
地址和指针赋值 x := &y，x := *y　和　*x := y

具体实现方式

  • 四元式
    • (OP,ARG1,ARG2,RESULT)
  • 三元式
    • (编号)(OP,ARG1,ARG2)
  • 间接三元式
    • 间接码表：表示了执行三元式的顺序。

四元式举例

1
2
3
4
5
6
7
8
9
10
11
12
13
read x;
t1 = x > 0 if_false t1 goto L1 
fact = 1 
label L2 
t2 = fact * x 
fact = t2 
t3 = x – 1 
x = t3 
t4 = x == 0 
if_false t4 goto L2
write fact 
label L1 
halt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
(rd,x,_,_) 
(gt,x,0,t1)
(if_f,t1,L1,_) 
(asn,1,fact,_)
(lab,L2,_,_) 
(mul,fact,x,t2) 
(asn,t2,fact,_) 
(sub,x,1,t3) 
(asn,t3,x,_) 
(eq,x,0,t4)
(if_f,t4,L2,_)
(wri,fact,_,_) 
(lab,L1,_,_) 
(halt,_,_,_)
  • 没有左公因子

以文法符号的属性作为翻译时的枢纽

例一👇

1
2
算术表达式文法G(E):  E→E＋E | E*E | -E | (E) | id 
 要翻译 a+b*c => ( *, b, c, T1 ) ( +, a, T1, T2 )
* 定义语义变量 * 定义语义子程序 * `(e.g)Newtemp`：产生一个新的临时变量

例二👇

  • 布尔表达式的翻译方法

    1
    2
    3
    4
    5
    6
    7
    8
     E→E1 or E2     { E.place := newtemp ;
                      emit( E.place ‘:=‘ E1.place ‘or’ E2.place ) }

    E→E1 or E2     { 
        backpatch( E1.false,  E2.codebegin );
        E.codebegin := E1.codebegin ;
        E.true := merge( E1.true, E2.true ) ;
          E.false :=  E2.false    }

例三👇

  • while语句

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
     L1 ： if a＜b goto L2 
                goto Lnext 
     L2 ： if c＜d goto L3 
                goto L4 
     L3 ： t1 ：= y＋z 
                x：＝t1
                goto L1 (L5)
     L4 ： t2:=y－z 
                x：＝t2 
    (L5)     goto L1 
     Lnext：

13. 代码优化

定义

所谓优化是对代码进行等价变换，使得变换后的代码的效率更高

主要分类

  • 中间代码优化（不依赖具体计算机）
    • 删除多余运算（删除公共子表达式）
    • 合并已知量与复写传播
      • 如果运算量都是已知量，则在编译时就算出它的值，称为合并已知量
      • 若有A:=B，称为把B值复写到A
    • 删除无用赋值
      • 从未被引用的值
  • 目标代码优化（依赖于具体计算机）

14. 局部优化

定义

局部优化是指基本块内的优化

基本块

指程序中一顺序执行的语句序列，其中只有一个入口语句和一个出口语句

  • 只有一个入口，表示程序中不会有其它任何地方能通过jump跳转类指令进入到此基本块中
  • 只有一个出口，表示程序只有最后一条指令能导致进入到其它基本块去执行

所以，基本块的一个典型特点是：只要基本块中第一条指令被执行了，那么基本块内所有执行都会按照顺序仅执行一次

把中间代码形成划分成基本块的算法

  • 求基本块的入口语句

    入口语句对应的基本块方法是：该基本块由该入 口语句到下一入口语句（不含下一入口语句），或到一转移语句（包括该转移语句），或到一停语句（包括该停语句）之间的代码序列组成

  • 对每一入口语句，构造其所属的基本块

  • 凡未被纳入某一基本块的语句，是不会被执行到的语句，可以把它们删除

参考

DAG

  • (Directed Acyclic Graph)：无环路有向图的简称
  • 叶结点(无后继的结点)以一标识符或常数作标记，表示该结点代表该变量或常数的值
  • 内部结点(有后继的结点)以一运算符作标记
  • 各结点都可以附加上一个或多个标识符

15. 循环优化

16. 全局优化

17. 参考资料