《编译原理》课程教学资源：语义分析和中间代码产生

27语义分析和中间代码产生 ●本节要点 中间表示(后缀式、三地址代码和DAG图) ●语言中常见结构的翻译 ●赋值语句 ●声明语句 ●数组引用 ●布尔表达式 ●控制语句

2.7 语义分析和中间代码产生 本节要点 ⚫ 中间表示（后缀式、三地址代码和DAG图） ⚫ 语言中常见结构的翻译 ⚫ 赋值语句 ⚫ 声明语句 ⚫ 数组引用 ⚫ 布尔表达式 ⚫ 控制语句

27语义分析和中间代码产生 ●静态语义检查 ●类型检查 控制流检查 致性检查 ●相关名字检查 名字的作用域分析 法分 静态检 析器 查器 中间代码中间代码优化器 产生器

2.7 语义分析和中间代码产生 静态语义检查 ⚫ 类型检查 ⚫ 控制流检查 ⚫ 一致性检查 ⚫ 相关名字检查 ⚫ 名字的作用域分析 语法分 析器 中间代码 产生器 静态检 查器 中间代码优化器

●中间语言(复杂性界于源语言和目标语 言之间)的好处: 便于进行与机器无关的代码优化工作 ●易于移植 使编译程序的结构在逻辑上更为简单明确 Compiler Compiler 源语言 Front End 中间语BakE叫d目标语 程序 言程序 言程序

中间语言(复杂性界于源语言和目标语 言之间)的好处： ⚫ 便于进行与机器无关的代码优化工作 ⚫ 易于移植 ⚫ 使编译程序的结构在逻辑上更为简单明确 源语言 程序 目标语 言程序 中间语 言程序 Compiler Front End Compiler Back End

271中间语言 常用的中间语 ●后缀式(逆波兰表示) 三地址代码 三元式 ●四元式 ●问接三元式 ●DAG图表示

常用的中间语言： ⚫ 后缀式(逆波兰表示) ⚫ 三地址代码 ⚫ 三元式 ⚫ 四元式 ⚫ 间接三元式 ⚫ DAG图表示 2.7.1 中间语言

后缀式 后缓式表示法: Lukasiewicz发明的一种表示 表达式的方法,又称逆兰表示法 个表达式E的后缀形式可以如下定义 1.如果E是一个变量或常量,则E的后缀式是E自身。 2.如果E是E1opE2形式的表达式,其中op是任何二 元操作符,则E的后缀式为EE2'op,其中E1和 E2′分别为E1和E2的后缀式。 3如果E是(E形式的表达式,则E1的后缀式就是E 的后缀式

2.7.1.1 后缀式 后缀式表示法：Lukasiewicz发明的一种表示 表达式的方法，又称逆波兰表示法。 一个表达式E的后缀形式可以如下定义： 1. 如果E是一个变量或常量，则E的后缀式是E自身。 2. 如果E是E1 op E2形式的表达式，其中op是任何二 元操作符，则E的后缀式为E1  E2  op，其中E1  和 E2  分别为E1 和E2的后缀式。 3. 如果E是(E1 )形式的表达式，则E1 的后缀式就是E 的后缀式

●逆波兰表示法不用括号。只要知道每个算符 的目数.对爱式,谂从哪一端进行扫 后缀式的计算 用一个栈实现。 般的让算过程是:自左至右扫描盾缓式 碰到 就把管推迸栈。每碰到自送算符 把它作用于栈顶的k个项,并用运算结果代替这 k个项。 ●是语法树的后序遍历线性化

逆波兰表示法不用括号。只要知道每个算符 的目数，对于后缀式，不论从哪一端进行扫 描，都能对它进行唯一分解。 后缀式的计算 ⚫ 用一个栈实现。 ⚫ 一般的计算过程是：自左至右扫描后缀式，每 碰到运算量就把它推进栈。每碰到k目运算符就 把它作用于栈顶的k个项，并用运算结果代替这 k个项。 ⚫ 是语法树的后序遍历线性化

把表达式翻译成后缀式的语义规则描 述 产生式 语义动作 E→E(opE2)E.code:=E(p, code‖E2. code llop E→(E①) E code: =E, code E→id E code =id E code表示E后缀形式 op表示任意二元操作符 1”表示后缀形式的连接

把表达式翻译成后缀式的语义规则描 述 产生式 E→E(1)op E(2) E→ (E(1)) E→id 语义动作 E.code:= E(1).code || E(2).code ||op E.code:= E(1).code E.code:=id • E.code表示E后缀形式 • op表示任意二元操作符 • “||”表示后缀形式的连接

数组POST存放后缀式:k为下标,初值为1 上述语义动作可实现为 产生式 程序段 EE(1op E(2) POsT[K]:≡op;k:=k+} E→(E() IPOST[k =i; k =k+11 ●例:输入串a+b+c的分析和翻译 POST 1234 ab+c 6x ●●●

数组POST存放后缀式：k为下标，初值为1 上述语义动作可实现为： 产生式 程序段 E→E(1)op E(2) {POST[k]:=op;k:=k+1} E→ (E(1)) { } E→i {POST[k]:=i;k:=k+1} 例：输入串a+b+c的分析和翻译 POST： 1 2 3 4 5 a b + c + …

2712图表示法 ●图表示法 DAG 抽象语法树 有向无环图( Directed Acyclic Graph,简称 DAG ●对表达式中的每个子表达式,DAG中都有一个结点 个内部结点代表一个操作符,它的孩子代表操作 数 在一个DAG中代表公共子表达式的结点具有多个父 结点(允许它使用多次) 没有父节点的节点称为根节点,dag可以有多个根 节点

2.7.1.2 图表示法 图表示法 ⚫ DAG ⚫ 抽象语法树 有向无环图(Directed Acyclic Graph，简称 DAG) ⚫ 对表达式中的每个子表达式，DAG中都有一个结点 ⚫ 一个内部结点代表一个操作符，它的孩子代表操作 数 ⚫ 在一个DAG中代表公共子表达式的结点具有多个父 结点（允许它使用多次） ⚫ 没有父节点的节点称为根节点，dag可以有多个根 节点

DAG举例 与(A+B)+(A+B对应的DAG

DAG举例 与（A+B)+(A+B)对应的DAG ＋ A B ＋