●逆波兰表示法不用括号。只要知道每个算符 的目数.对爱式,谂从哪一端进行扫 后缀式的计算 用一个栈实现。 般的让算过程是:自左至右扫描盾缓式 碰到 就把管推迸栈。每碰到自送算符 把它作用于栈顶的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 ＋