•把表达式翻译成后缀式的语义规则描述 产生式 语义动作 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