编译原理Ch7

第七章 语义分析和中间代码生成

一、后缀式

1.后缀式表示法

• 一种表示表达式的方法，又称逆波兰表示法

2.定义

• 一个表达式E的后缀形式可以如下定义
  • 如果E时一个变量或常量，则E的后缀式是E自身
  • 如果E是$E_1 op E_2$形式的表达式，其中op是任何二元操作符，则E的后缀式为$E’_1E’_2op$，其中$E’_1$和$E’_2$分别是$E_1、E_2$的后缀式
  • 如果E是$(E_1)$形式的表达式，则$E_1$的后缀式就是E的后缀式
• 后缀式表示法不用括号
  • 只需要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行无歧义地分解
• 后缀式的计算
  • 用一个栈实现
  • 自左向右扫描后缀式，每碰到运算量就把它推进栈，每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项

3.中缀表达式翻译成后缀式的属性文法

4.中缀表达式翻译成后缀式的翻译模式

二、图表示法

1.抽象语法树

• 赋值语句翻译成抽象语法树的属性文法
  

2.有向无环图（DAG）

(1)定义

• 对表达式中的每个子表达式，DAG中都有一个结点
• 一个内部结点代表一个操作符，它的孩子代表操作数
• 在一个DAG中代表公共子表达式的结点具有多个父节点
  

三、三地址代码

1.形式

• x:=y op z
• 可以看成是抽象语法树或有向无环图的一种线性表示
  
  

2.三地址语句的种类

(1)赋值

• 二元运算赋值
  • x:=y op z
• 一元运算赋值
  • x:=op y
• 零元运算赋值
  • x:=y

(2)跳转

• 无条件跳转
  • goto L
• 有条件跳转
  • if x relop y goto L或if a goto L

(3)传参、转子

• param x
• call p,n

(4)返回语句

• return y

(5)索引赋值

• x:=y[i]、x[i]:=y

(6)地址和指针赋值

• x:=&y、x:=*y、*x:=y

3.实现形式——四元式

• 一个带有四个域的记录结构，这四个域分别称为op，arg1，arg2及result
  

4.实现形式——三元式

• 用三个域表示：op、arg1、arg2
• 计算结果引用：引用计算该值的语句的位置
  

5.实现形式——简介三元式

• 三元式表+简介码表
• 简介码表
  • 一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置
• 优点
  • 方便优化，节省空间
    

四、类型表达式

1.基本类型

• intrger
• real
• char
• boolean
• type_error
• void

2.类型名

• 可以为表达式命名，类型名也是类型表达式

3.将类型构造符作用于类型表达式可以构造新的类型表达式

(1)数组构造符array

• 若T是类型表达式，则array(I,T)是类型表达式
  • int[3] -> array(3,int)
  • int[2][3] -> array(2,array(3,int))

(2)指针构造符pointer

• 若T是类型表达式，则pointer(T)是类型表达式，表示一个指针类型

(3)笛卡尔乘积构造符×

• 若T1和T2是类型表达式，则笛卡尔乘积T1×T2是类型表达式

(4)函数构造符→

• 若T1、T2、……、Tn和R是类型表达式，则T1×T2×……×Tn→R是类型表达式，其中T是参数的类型，R是返回值类型

(5)记录构造符record

• 若有标识符N1、N2、……、Nn与类型表达式T1、T2、……、Tn则record((N1×T1)×(N2×T2)×……×(Nn×Tn))是一个类型表达式
  

五、声明语句

1.局部变量的存储分配

• 对于声明语句，语义分析的主要内容就是收集标识符的类型等属性信息，并未每一个名字分配一个相对地址
  • 从类型表达式可以知道该类型在运行时刻所需的存储单元数量，称为类型的宽度
  • 在编译时刻，可以使用类型的宽度为每一个名字分配一个相对地址
• 名字的类型和相对地址信息保存在相应的符号表记录中

2.翻译过程

• 看一遍网课：点击跳转

六、简单赋值语句的翻译

1.赋值语句翻译的任务

• 基本文法
  • $S → id = E$
  • $S→E_1+E_2$
  • $E→E_1*E_2$
  • $E→-E_1$
  • $E→(E_1)$
  • $E→id$
• 主要任务
  • 生成对表达式求值的三地址码