【编译原理系列】变量与过程翻译

深藏阁楼爱情的钟 2023-01-10 11:53 108阅读 0赞

# 声明语句的翻译 #

声明语句的作用是**为可执行语句提供信息**，以便于其执行；对声明语句的处理，主要是将所需要的信息**正确地填写**进合理组织的**符号表**中

# 变量的声明 #

*  **类型定义：为编译器提供存储空间大小**的**信息**（预定义&自定义）
 *  **变量声明：为变量分配存储空间**

组合数据的类型定义和变量声明：

*  定义与声明在一起，定义与声明分离

决定变量**存储空间**的是变量的**数据类型**

1.  定义**确定**存储空间，声明**分配**存储空间
2.  *简单数据类型的存储空间是已经确定的*，如integer可以占4个字节，real可以占8个字节，char可以占1个字节等
3.  **组合数据**类型变量的存储空间，需要**编译器**根据程序员提供的信息**计算而定**

定义就好像`typedef struct node{};`，声明就好像`struct node Node;`，使用就好像`Node.val=1;`

## 语法制导翻译 ##

1.  全程量offset：记录**当前符号存储的偏移量**，初值设为0
2.  属性.type和.width：变量的**类型**和所**占据的存储空间**
3.  过程enter(name, type, offset)：为type类型的变量name**建立符号表条目**，并为其**分配存储空间(位置)offset**

产生式：					语义规则：
    (1)D→D;D	
    (2)D→id:T 	{enter(id.name, T.type, offset); offset:=offset+T.width;}
    (3)T→int	{T.type:=integer; T.width:=4;}
    (4)T→real	{T.type:=real; T.width:=8;}
    (5)T→array [num] of T1 {T.type:=array(num.val, T1.type); T.width:=num.val*T1.width;}
    (6)T→^T1	{T.type:=pointer(T1.type); T.width:=4;}

## 左值与右值 ##

形式上

*  出现在赋值号左边和右边的变量分别称为左值和右值；

实质上，

*  **左值必须具有存储空间**，**右值可以**仅是一个**值**，**而没有存储空间**；
 *  （变量【简单变量、组合变量】是左值，左值是地址，右值是值）形象地讲，**左值是容器，右值是内容**

# 过程的定义与声明 #

**过程（procedure）**：

*  **过程头/规格说明**(做什么)＋**过程体**(怎么做)；(有返回值的也称为**函数**，被操作系统调用的过程称为**主程序**)

**过程的三种形式：** 过程定义、过程声明和过程调用。

*  过程定义：过程头+过程体；
 *  过程声明：过程头

**先声明后引用的原则**，若在引用前已定义，则声明可省略，因为定义已包括了声明

## 参数的传递 ##

1、形参与实参

*  **定义时**的参数称为**形参(parameter或formal parameter)**，形式参数
 *  **引用时**的参数称为**实参(argument或actual parameter)**，实在参数

2、常见的**参数传递形式**：（不同的语言提供不同的形式）

*  值**调用**（call by value）
    
     *  过程内部对参数的修改，不影响作为实参的变量原来的值
     *  任何可以作为**右值**的对象均可作为**实参**
     *  **过程定义**时**形参被当作局部名**看待，并在过程内部为形参分配存储单元
     *  调用过程前，首先**计算**实参并将值（实参的**右值**）放入形参的存储单元
     *  **过程内部**对**形参单元中**的数据**直接访问**
 *  引用**调用**（call by reference）
    
     *  过程内部对形参的修改，等价于直接对实参的修改
     *  实参必须是**左值**
     *  定义时形参被当作**局部名**看待，并在过程内部为形参分配存储单元
     *  调用过程前，将作为实参的变量的**地址**（左值）放进形参的存储单元
     *  过程内把形参单元中的数据当作地址，**间接访问**
     *  存在副作用
        
            int a=2;
            void add_one(int &x){  a=x+1;  x=x+1; }
            void main ()
            {    cout<<"before: a="<<a<<endl;//2
                add_one(a);
                cout<<"after: a="<<a<<endl;//4
            }
 *  **复写－恢复（copy-in/copy-out）**
    
     *  实参与非本地量共用一个存储空间，使得在过程内改变参数值的同时，也改变了非本地量的值
     *  值调用和引用调用的结合
     *  **过程内**对参数的修改**不直接影响实参**，**避免了副作用**
     *  **返回时**将**形参内容**恢复给**实参**，实现了参数的返回
     *  实参必须是**左值**
     *  过程定义时形参被当作**局部名**看待，并在过程内部为形参分配单元(复写)
     *  调用过程前，首先**计算**实参并将值(实参的右值)放入形参的存储单元
     *  过程内部对形参单元中的数据**直接访问**
     *  **过程返回前**将形参的右值**放回实参的存储单元(恢复)**
 *  换名**调用**（call by name）
    
     *  **过程被认为**宏，每次对过程的调用，实质上是用**过程体替换过程调用**，替换中**用实参的文字替换体中的形参**;这样的替换方式被称为**宏替换或宏展开**
     *  当需要保持实参的完整性时， **可以为实参加括弧**
     *  在c++中的形式是宏定义`#define`【一种折中的方法，c++的内敛函数inline，避免了函数调用的同时，也消除了宏替换的副作用】
     *  运行速度快

3、参数传递方法的实质：

*  实参是代表左值、右值、还是实参本身的正文

## 过程的作用域 ##

同样遵守的是**静态作用域**和**最近嵌套原则**

*  设主程序（最外层过程）的嵌套深度dmain=1，
 *  <1> 若过程A直接嵌套定义过程B，则dB=dA+1；
 *  <2> **变量声明时**所在过程的嵌套深度，被认为是该变量的嵌套深度

嵌套过程

*  名字作用域信息的保存，可以用具有嵌套结构的符号表来实现，**每个过程**可以被认为是**一个子符号表**，或者是**符号表中的一个节点**
 *  **嵌套的节点之间**可以用**双向的链表连接**，**正向的链**指示过程的**嵌套关系**，而**逆向的链**可以用来实现**按作用域对名字的访问**  
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70][]
    
     *  动态链：指向本过程的调用过程的活动记录的起始地址，也称控制链。
     *  静态链：指向本过程的直接外层过程的活动记录的起始地址，也称存取链。
 *  和变量表的区别
    
     *  变量表是每个栈帧都有一个（即方法都有自己的数据，栈帧是用来装载方法里的局部数据的），不同方法的变量不可以直接使用
     *  因为数据的寻址方式是动态寻址（因为存在递归，所以方法的调用就不确定，所以变量定义就不确定，所以编译时无法确定），通过栈实现的这种动态寻址，然而栈帧是否会创建（即方法是否会被调用）与栈帧空间的分配都不确定，所以必须通过静态链，进行一次间址。

## 语法制导翻译 ##

P → D				(1)
    D → D ; D  			(2)
       | id : T			(3)
       | proc id ; D; S	(4) 
       
    修改文法，使得在定义D之前生成符号表，LR分析
    P → M D					(1)
    D → D ; D  				(2)
       | id : T				(3)
       | proc id ; N D; S	(4)
    M →ε					(5)
    N →ε					(6)

全程量：有序对栈（tblptr, offset）

*  其中， tblptr保存指向符号表节点的指针，
 *  offset保存当前节点所需宽度。

**栈上的操作：** push(t, o)、pop、top(stack)

1.  **函数mktable(previous)：建立**一个**新的节点**，并返回指向新节点的指针;参数**previous是逆向链**，指向该节点的前驱，或者说是外层
2.  **过程enter(table, name, type, offset)：在table指向的节点中为名字name建立新的条目**，包括名字的类型和存储位置等
3.  **过程addwidth(table, width)：计算table节点中所有条目**的**累加宽度**，并**记录**在**table的头部信息**中
4.  **过程enterproc(table, name, newtable)：为过程name在table指向的节点中建立一个新的条目**；参数**newtable是正向链**，指向name过程自身的符号表节点

产生式：					语义规则：
    (1) P → M D		{addwidth(top(tblptr),top(offset)); pop;} 
    (2) M → ε 		{t:=mktable(null);  push(t, 0,);} 
    (3) D → D ; D
    (4) D → id : T	{enter(top(tblptr),id.name,T.type,top(offset));
     top(offset):=top(offset)+T.width;} 
    (5) D → proc id ; N D1; S	{ t:=top(tblptr); 
      							  addwidth(t, top(offset));
      							  pop;
      							  enterproc(top(tblptr), id.name, t);
    							} 
    (6) N → ε 		{t:=mktable(top(tblptr));  push(t,0);}

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1][]

序号 产 生 式	   						语 义 处 理 结 果
    (1)  M1→ε   						t1 := mktable(null); push(t1, 0); 
    (2)  N1→ε	  						t2 := mktable(top(tblptr));  push(t2, 0);
    (3)  T1→int  						T1.type=integer,  T1.width=4
    (4)  T2→array [10]of T2 			T2.type=array(10,in…≥t),  T2.width=40
    (5)  D1→a:T2 						(a,arr,0)填进t2所指节点，top(offset):=40
    (6)  T3→int  						T3.type=integer,  T3.width=4
    (7)  D2→x:T3						(x,int,40)填进t2所指节点 top(offset):=44
    (8)  N2→ε	  						t3:=mktable(top(tblptr));  push(t3,0);
    (9)  T4→int  						T4.type=integer,  T4.width=4
    (10) D3→i:T4 						(i,int,0)填进t3所指节点，top(offset):=4
    (11) D4→proc readarray N2 D3 ; S	t:=top(tblptr); addwidth(t,top(offset)); pop; 											enterproc(top(tblptr),readarray,t);
    (12) D7→proc sort N1 D6 ; S			t:=top(tblptr); addwidth(t,top(offset)); pop;
    			   						enterproc(top(tblptr),sort,t);
    (13) P→M1 D7 						addwidth(top(tblptr),top(offset)); pop;

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70]: /images/20221119/26a4155802a4444ea722f3da9d9d61be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210124094558940.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNDYwNw==,size_16,color_FFFFFF,t_70