§53中间代码 逆波 主要用于表达式 1、表达式的逆波兰表示 后缀式e1e200是k目运算符(k>=1) 特点运算量在前运算符在后,无括号 例:a+b*c 逆波兰abc*+ a*(bc/d)逆波兰abcd/+* a *(b+c) 逆波兰abc+* (a+b)*(c+d)逆波兰ab+cd+*
1 §5.3 中间代码 一、逆波兰------主要用于表达式 1、表达式的逆波兰表示 后缀式: e1e2……ekθ θ是k目运算符(k>=1) 特点:运算量在前,运算符在后,无括号 例:a+b*c 逆波兰 a bc*+ a*(b+c/d) 逆波兰 ab cd/+* a*(b+c) 逆波兰 a bc+* (a+b)*(c+d) 逆波兰 ab+cd+*
2、后缀式的计算利用分析栈 计算步骤:自左向右扫描后缀式 遇到运算量进栈 遇到k目运算符则作用于栈顶的k项 用运算结果代替这k项. 例:计算ab+c*
2 2、后缀式的计算:利用分析栈 计算步骤:自左向右扫描后缀式 遇到运算量进栈 遇到k目运算符则作用于栈顶的k项 用运算结果代替这k项. 例:计算ab+c* a, b + c * b a t1 t2 c t1
3、后缀式的推广 (1)赋值语句的后缀式 a=e 逆波兰:ae 例:a:=3*(b+c)逆波兰a3bc+* (2)条件语句的后缀式 例: if e then x else y 将 if -then-else看成三目运算符Y 逆波兰:exy￥ 缺点ⅹy都被计值
3 3、后缀式的推广 (1)赋值语句的后缀式 a:=e 逆波兰: ae:= 例: a:=3*(b+c) 逆波兰 a3bc+*:= (2)条件语句的后缀式 例: if e then x else y 将if—then —else 看成三目运算符￥ 逆波兰:exy ￥ 缺点:x,y 都被计值
改进将后缀式放在 维数组POST]中 运算符 后缀式意义 无条件转移 ump p Jump转到POST[p 条件转移:小于转jt e,e, p jlt e<e, #tPOSTipI 零转jez ep jez e=0转POST[p] 例 f e then x else y表示成 e p ez Jump y 4
4 改进:将后缀式放在一个一维数组POST[n]中 运算符 后缀式 意义 无条件转移:jump p jump 转到POST[p] 条件转移:小于转jlt e1e2 p jlt e1<e2转POST[p] 零转jez e p jez e=0转POST[p] 例:if e then x else y表示成 e’ p1 jez x’ p2 jump y’ …
4、语法制导生成后缀式 E:code:构成后缀式的符号串 两串并置运算 Op:运算符 产生式 语义动作 E-E(op E(2)E code= E(). code lE(2)code llop) E→→(E() (E code= E()code j E→id E·code=id}
5 4、语法制导生成后缀式 E·code:构成后缀式的符号串 ‖：两串并置运算 Op:运算符 产生式 语义动作 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}