国防科技大学：《编译原理》课程电子教案（PPT教学课件）第7章 语义分析和中间代码产生

第七章语义分析和中间代码产生 ■静态语义检查 口类型检查 口控制流检查 口一致性检查 口相关名字检查 口名字的作用域分析 语法分 静态检 中间代码 析器 查器 产生器 中间代码优化器 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 第七章 语义分析和中间代码产生 ◼ 静态语义检查 类型检查 控制流检查 一致性检查 相关名字检查 名字的作用域分析 语法分 析器 中间代码 产生器 静态检 查器 中间代码优化器

■ 中间语言（复杂性界于源语言和目标语言 之间)的好处： ▣便于进行与机器无关的代码优化工作 口易于移植 口使编译程序的结构在逻辑上更为简单明确 Compiler Compiler 源语言 Front End 中间语 Back End 目标语 程序 言程序 言程序 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 中间语言(复杂性界于源语言和目标语言 之间)的好处： 便于进行与机器无关的代码优化工作 易于移植 使编译程序的结构在逻辑上更为简单明确 源语言 程序 目标语 言程序 中间语 言程序 Compiler Front End Compiler Back End

7.1中间语言 ■常用的中间语言： 口后缀式，逆波兰表示 口图表示：DAG、抽象语法树 口三地址代码 ■三元式 ■四元式 ■间接三元式 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 常用的中间语言： 后缀式，逆波兰表示 图表示： DAG、抽象语法树 三地址代码 ◼三元式 ◼四元式 ◼间接三元式 7.1 中间语言

7.1.1 后缀式 ■ 后缀式表示法：Lukasiewicz发明的一种表示 表达式的方法，又称逆波兰表示法。 ■一个表达式E的后缀形式可以如下定义： 1.如果E是一个变量或常量，则E的后缀式是E 自身。 2.如果E是E1opE2形式的表达式，其中op是任 何二元操作符，则E的后缀式为E1'E2'op,其 中E1'和E2'分别为E1和E2的后缀式。 3.如果E是(E)形式的表达式，则E1的后缀式就 是E的后缀式。 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 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个项。 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 ◼ 逆波兰表示法不用括号。只要知道每个 算符的目数，对于后缀式，不论从哪一 端进行扫描，都能对它进行唯一分解。 ◼ 后缀式的计算 用一个栈实现。 一般的计算过程是：自左至右扫描后缀式， 每碰到运算量就把它推进栈。每碰到k目运 算符就把它作用于栈顶的k个项，并用运算 结果代替这k个项

•把表达式翻译成后缀式的语义规则描述 产生式 语义动作 E→E0opE2) E.code:=E().code E2).code llop E→(E) E.code:=EO.code E→id E.code:=id 。E.code表示E后缀形式 op表示任意二元操作符 “‖”表示后缀形式的连接。 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 •把表达式翻译成后缀式的语义规则描述 产生式 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表示任意二元操作符 • “||”表示后缀形式的连接

E→EopE2) E.code:=E).code E2).code llop E→E E.code:=E0).code E→id E.code:=id ■数组POST存放后缀式：k为下标，初值为1 上述语义动作可实现为： 产生式 程序段 E→E1opE2) {POST[k]:=op;k:=k+1} E→(E) Ei POST[k]:=i;k:=k+1} ■例：输入串a+b+c的分析和翻译 POST: 23 4 5 a b + + 国防科技大学计算机系602数研室

国防科技大学计算机系602教研室 ◼ 数组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 E→E(1)op E(2) E.code:= E(1).code || E(2).code ||op E→ (E(1)) E.code:= E(1).code E→id E.code:=id a b + c + …

7.1.2图表示法 ■图表示法 DAG 口抽象语法树 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 7.1.2 图表示法 ◼ 图表示法 DAG 抽象语法树

7.1.2图表示法 ■ 无循环有向图(Directed Acyclic Graph, 简称DAG) 口对表达式中的每个子表达式，DAG中都有一个 结点 口一个内部结点代表一个操作符，它的孩子代表 操作数 口在一个DAG中代表公共子表达式的结点具有多 个父结点 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 7.1.2 图表示法 ◼ 无循环有向图(Directed Acyclic Graph， 简称DAG) 对表达式中的每个子表达式，DAG中都有一个 结点 一个内部结点代表一个操作符，它的孩子代表 操作数 在一个DAG中代表公共子表达式的结点具有多 个父结点

a:=b*(c)+b*(-c)的图表示法 assign assign uminus b uminus uminus 抽象语法树 DAG 国防科技大学计算机系602教研室

国防科技大学计算机系602教研室 a:=b*(-c)+b*(-c)的图表示法 assign a + * b uminus c DAG assign a + * b uminus c 抽象语法树 * b uminus c