【编译原理系列】语义分析与中间代码、符号表

Bertha 。 2023-01-10 11:53 153阅读 0赞

# 静态语义分析 #

**语法制导翻译**是**处理语义**的基本方法

*  **以语法分析为基础**，在语法分析得到语言结构的结果时，处理附着于此结构上的语义，如计算表达式的值、生成中间代码等

## 语法与语义 ##

*  语法是指**语言结构**，即语言的“样子”；
 *  语义是*附着于语言结构上的**实际含义***，即语言的“意义”

**语义分析的作用：**

*  **检查**是否结构正确的句子所表示的意思也**合法**
 *  执行规定的语义动作
 *  例如如：
    
     *  表达式求值
     *  符号表填写
     *  中间代码生成等

方法：

*  **语法制导翻译**

## 语法制导翻译 ##

基本思想：

*  将语言结构的语义以**属性**的形式赋予代表此结构的文法符号，而**属性的计算**以**语义规则**的形式赋予由文法符号组成的产生式。
 *  在语法分析推导或规约的每一步骤中，通过语义规则实现对属性的计算，以达到对语义的处理

**具体方法：**

*  将文法符号所代表的语言结构的意思，用附着于该文法符号的**属性**表示
 *  用**语义规则**规定产生式所代表的语言结构之间的关系（即属性之间的关系），即用语义规则实现属性计算

### 语义规则 ###

**两种形式：**

*  语法制导定义 *（算法）*
    
     *  用**抽象的属性**和**运算**表示的语义规则 (公式，做什么)
 *  翻译方案 *（程序实现，方法不唯一）*
    
     *  用**具体的属性**和**运算**表示的语义规则 (程序段，如何做)

**语义规则**也被习惯上称为**语义动作**

*  忽略实现细节，二者作用等价（设计与实现）

### 属性 ###

对于产生式A→α，其中α是由文法符号X1X2…Xn组成的序列，它的**语义规则**可以表示为关于属性的函数：`b := f(c1, c2, …, ck)`

语义规则中的属性存在下述性质与关系:

*  (1) 若b是A的属性，c1, c2, …, ck是α中文法符号的属性，或者A的其它属性，则称b是A的综合属性。
 *  (2) 若b是α中某文法符号Xi的属性，c1, c2, …, ck是A的属性，或者是α中其它文法符号的属性，则称b是Xi的继承属性。
 *  (3) 称(4.1)中属性b依赖于属性c1, c2, …, ck。
 *  (4) 若语义规则的形式如 f(c1, c2, …, ck)，则可将其想像为产生式左部文法符号A的一个虚拟属性。属性之间的依赖关系，在虚拟属性上依然存在。

**属性**之间的**计算**构成了**语义规则**，**计算的先后次序**被称为**属性的依赖关系**

*  例如：`E→E1+E2 E.val:=E1.val+E2.val`，则表明：E的属性.val由E1和E2的相应属性计算而来，E的属性依赖于E1和E2的属性

#### 注释分析树 ####

*  将**属性**附着在**分析树**对应**文法符号**上，形成**注释分析树**；
 *  类似的，将**属性**附着在**语法树**对应**文法符号**上，形成**语法分析树**

注释分析树直观地反映属性的性质和属性之间的关系，所以画树还要标属性

*  对于S标nc，对于M标stat，对于E标tc和fc \*

**继承属性：**

*  自上而下计算的，从前辈和**兄弟**的属性计算得到，即“自上而下，包括兄弟”

**综合属性：**

*  自下而上计算的，从子孙和**自身**的其他属性计算得到，即“自下而上，包括自身”

## LR分析翻译方案的设计 ##

*  LR分析中的语法制导翻译实质上是对LR语法分析的扩充：

**扩充LR分析器的功能：**

*  当执行归约产生式的动作时，也执行产生式对应的语义动作。
 *  由于是**归约**时执行语义动作，因此\*限制语义动作仅能放在产生式右部的**最右边**

**扩充分析栈：**

*  增加一个**与分析栈并列的语义栈，用于存放分析栈中文法符号所对应的属性值**

#### 递归下降分析翻译方案的设计 ####

*  在产生式右部**任何位置**都可以嵌入语义动作；（与LR分析只能在最右边进行比较）
    
     *  由于是根据 LR 分析拓展，所以对于继承属性采用回填的办法
     *  即：产生式右边要用到继承属性的符号，在其相邻的右边多出一个 M（M -> ε），就是通过这个 M 的语义进行回填
 *  在函数返回值、参数、变量等设计存储空间

# 后缀式 #

也被称为逆波兰表示，*操作数在前，操作符紧随其后，无需用括号限制运算的优先级和结合性*

表示并不惟一

x := first_token;
    while  not end_of_exp 
    loop    if   x in operands
            then push x;          -- 操作数进栈
            else pop(operands);  -- 算符，弹出操作数
                 push(evaluate);  -- 计算，并将结果进栈
            end  if;
         	next(x);
    end loop;

后缀式并不局限于二元运算的表达式，可以推广到**任何语句**，*只要遵守操作数在前，操作符紧跟其后的原则即可*

# 三地址码 #

形式接近机器指令，且具有便于优化的特征

*  顾名思义，是由**不超过三个地址**组成的一个运算

题目中的三地址码序列需要像这样：

(1) if a < b goto (3)
    (2) goto (8)
    (3) if c < d goto(5)
    (4) goto (8)
    (5) t1:= a + c
    (6) x:=t1
    (7) goto -

语法：

*  `result := arg1 op arg2`结果存放在result中的二元运算`arg1 op arg2`
 *  或`result := op arg1`结果存放在result中一元运算op arg1
 *  或 `op arg1`一元运算op arg1
 *  或`result := arg1`直接拷贝

## 三元式 ##

`(i)(op, arg1, arg2)`

*  序号(i)是它们在三元式表中的位置
 *  序号的双重含义：既代表**此三元式**，又代表**三元式存放的结果**
 *  存放方式：**数组结构**，三元式在数组中的位置由下标决定
 *  弱点：给代码的**优化**带来困难  
    因为代码优化常使用的方法是删除某些代码或移动某些代码位置，而一旦进行了代码的删除或移动，则表示某三元式的序号会发生变化，从而使得其他三元式中对原序号的引用无效

### 语法制导翻译 ###

1.  属性 .code：三元式代码，指示标识符的**存储单元**或三元式表中的**序号**
2.  属性 .name：**标识符的名字**
3.  函数trip( op，arg1，arg2 )：**生成一个三元式**，**返回**三元式的**序号**
4.  函数 entry(id.name)：**返回**标识符在**符号表中的位置**或**存储位置**

产生式：					语义规则：
    (1) A→id:=E		{A.code:=trip(:=,entry(id.name),E.code)}
    (2) E→E1+E2		{E.code:=trip(+,E1.code，E2.code)}
    (3) E→E1*E2 	{E.code:=trip(*,E1.code，E2.code)}
    (4) E→(E1) 	 	{E.code:=E1.code}
    (5) E→-E1		{E.code:=trip(@，E1.code, )}
    (6) E→id		{E.code:=entry(id.name)}

## 四元式 ##

1.  四元式与三元式的唯一区别是将**由序号所表示的运算结果**改为了由**临时变量**来表示
2.  此改变使得**四元式具有了运算结果**与**四元式在四元式序列中的位置无关的特点**，它为代码的优化提供了极大方便，因为这样可以**删除或移动四元式而不会影响运算结果**【避免了三元式的值与三元式在三元式组中的位置相关的弱点】
3.  三地址码与四元式形式的一致性
    
    四元式 (op，arg1，arg2，result) ==> 三地址码 result := arg1 op arg2
    
    result的表示方法通常是给出一个临时名字，用它来存放运算的结果，被称为**临时变量**（语法制导翻译时可以随意引入临时变量，若干临时变量可以共用同一个存储空间）

### 语法制导翻译 ###

1.  属性.code： 表示存放**运算结果的变量**
2.  函数newtemp：返回一个**新的临时变量**，如T1，T2，…等
3.  过程emit( op，arg1，arg2, result)：**生成一个四元式**，若为一元运算，则**arg2可空**

产生式：					语义规则：
    1)A→id:=E	{A.code:=newtemp; emit(:=, entry(id.name), E.code, A.code)}
    (2)E→E1+E2	{E.code:=newtemp; emit(+，E1.code,E2.code,E.code)}
    (3)E→E1*E2	{E.code:=newtemp; emit(*，E1.code,E2.code,E.code)}
    (4)E→(E1)	{E.code:=E1.code}
    (5)E→-E1	{E.code:=newtemp; emit(@,E1.code, , E.code)}
    (6)E→id		{E.code:=entry(id.name)}

## 图形表示 ##

树作为中间代码，语法树真实反映句子结构，对语法树稍加修改（加入语义信息），即可以作为中间代码的一种形式(注释语法树)

### 树语法制导翻译 ###

1.  属性.nptr：指向树节点的指针
2.  函数mknode(op，nptr1，nptr2)： 生成一个根或内部节点，节点数据是op， nptr1和nptr2分别指向的左右孩子的子树。若仅有一个孩子，则nptr2为空
3.  函数mkleaf(node)： 生成一个叶子节点

产生式：					语义规则：
    (1) A → id := E 	{A.nptr:= mknode(:=,mkleaf(entry(id.name)),E.nptr)}
    (2) E → E1 + E2		{E.nptr:=mknode(+,E1.nptr,E2.nptr)}
    (3) E → E1 * E2 	{E.nptr:=mknode(*,E1.nptr,E2.nptr)}
    (4) E → ( E1 )  	{E.nptr:=E1.nptr}
    (5) E → - E1		{E.nptr:=mknode(@,E1.nptr, )}
    (6) E → id			{E.nptr:=mkleaf(entry((id.name))}

### 树的优化表示DAG ###

如果树上若干个节点有完全相同的孩子，则这些节点可以指向同一个孩子，形成一个**有向无环图(Directed Acyclic Graph, DAG)**

*  DAG与树的唯一区别是**多个父亲可以共享同一个孩子**，从而达到**资源（运算、代码等）共享**的目的
 *  仅需要在mknode和mkleaf中增加相应的**查询功能**
 *  首先查看所要构造的节点是否已经存在，若存在则无需构造新的节点，直接返回指向已存在节点的指针即可

## 树与其他中间代码的关系 ##

1.  树表示的中间代码与后缀式和三地址码之间有内在联系
2.  对树进行**深度优先后序遍历**，得到的**线性序列**就是**后缀式**，或者说后缀式是树的一个线性化序列
3.  树的**每个内部节点和它的孩子**对应一个**三元式或四元式**

# 符号表 #

**符号表的作用：连接声明**与**引用**的桥梁，记住每个符号的相关信息，如作用域和绑定等，帮助编译的各个阶段正确有效地工作

符号表的空间存储应该是可以动态扩充的

符号表设计的**基本要求**：目标是**合理存放信息**和**快速准确查找**

*  **正确存储**各类信息
 *  **适应不同阶段的需求**
 *  便于**有效**地进行**查找、插入、删除和修改**等操作；
 *  **空间**可以**动态扩充**

逻辑上讲：

*  每个声明的名字在符号表中占据一栏，称为一个**条目**，用于存放名字的相关信息

符号表中的内容：

*  **保留字、标识符、特殊符号（包括算符、分隔符等）** 等等
 *  **多个子表**：不同类别的符号可以存放在不同的子表中，如变量名表、过程名表、保留字表等
 *  存放方式：**关键字＋属性**

*组合关键字至少应该包括三项：名字＋作用域＋类型*

**构成名字的字符串的存储：**

*  定长数据/直接存放
    
     *  名字：直接存储名字
 *  变长数据（名字长度变化范围很大）/间接存放
    
     *  名字，起始地址；名字间可以用特殊符号隔开，也可以在名字中添加长度

## 名字的作用域 ##

<1> **静态作用域规则**（static-scope rule）：

*  **编译时**就可以确定名字的作用域，也可以说，仅从静态读程序就可确定名字的作用域。

<2> **最近嵌套规则**（most closely nested）：

*  以程序块为例，也适用于过程

1.  程序块B中声明的作用域包括B；
2.  如果名字x不在B中声明，那么B中x的出现是在外围程序块B’的x声明的作用域中，使得
    
     *  B’有x的声明，并且
     *  B’比其它任何含x声明的程序块更接近被嵌套的B

## 线性表 ##

线性表应是一个**栈**（后进先出），以正确反映名字的作用域，即**符号的加入和删除，均在线性表的一端**进行

**查找：** 从表头(栈顶)开始，遇到的第一个名字；

**插入：** 先查找，再插入在表头；

**删除：**

*  (a) 暂时：将在同一作用域的名字同时摘走，适当保存
 *  (b) 永久：将在同一作用域的名字同时摘走，不再保存

**修改：** 与查找类似，修改第一个遇到的名字的信息；修改可以用删除＋插入代替

**效率（n个条目）：**

*  一个名字的查找
    
     *  成功查找(平均)：(n+1)/2
     *  不成功查找：n+1
 *  **建立**n个条目的符号表(最坏)： ∑ i = 1 n i \\displaystyle\\sum^n\_\{i=1\}i i=1∑ni = (n+1)(n+2)/2

## 散列表 ##

将线性表分成m个小表，构造**hash函数**，使名字**均匀散布**在m个子表中；若散列均匀，则时间复杂度会降到原线性表的1/m

名字挂在两个链上(便于删除操作)：

*  **散列链(hash link)：** 链接所有具有**相同hash值**的元素，表头在表头数组中
 *  **作用域链(scope link)：链接所有在同一作用域**中的元素，表头在作用域链中

**操作：**

*  查找
    
     *  首先计算**散列函数**，然后从散列函数所指示的入口进入某个线性表，在线性表中**沿hash link**，像查找单链表中的名字一样查找
 *  插入
    
     *  首先**查找**，以确定要插入的名字是否已在表中，若不在，则要**分别沿hash link和scope link**插入到两个链中，**方法均是插在表头**，即两个表均可看作是**栈**
 *  删除
    
     *  把**以作用域链连在一起的所有元素**从当前符号表中删除，保**留作用域链所链的子表**，为后继工作使用（如果是临时删除，则下次使用时直接沿作用域链加入到散列链中即可）

**散列函数的设计：**

1.  减少冲突，分布均匀
2.  充分考虑程序设计语言的特点  
    如：若有变量V001,V002,…,V300，且首字母的值作为hash值