北京交通大学计算机与信息技术学院：《编译原理》课程教学资源（PPT课件讲稿）中间代码、自下而上分析法：简单语句的翻译、作为条件控制语句的布尔式的翻译

§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}

后缀式放入POST[k]中 产生式 语义动作 E-E(oP E(2)POST[k]: -op; k=k+1) E→(E() E→id ( POST[k]: =id; k=k+1

6 后缀式放入POST[k]中 产生式 语义动作 E→E(1) op E(2) {POST[k]:=op; k=k+1} E→(E(1)) { } E →id {POST[k]:=id; k=k+1}

三元式和树 三元式 (1)表示形式 op ARGI ARG2 其中:op:运算符 ARG1:第一运算量 ARG2第二运算量 表达式及各种语句都可以表示成三元式 三元式出现的顺序为表达式的计值顺序 目运算任选ARG1或ARG2

7 二、三元式和树 1、三元式 （1）表示形式 op ARG1 ARG2 其中：op：运算符 ARG1:第一运算量 ARG2:第二运算量 ▪ 表达式及各种语句都可以表示成三元式 ▪ 三元式出现的顺序为表达式的计值顺序 ▪ 一目运算任选ARG1或ARG2

例:A+B*C的三元式 op ARG1 ARG2 BA C (2)+ ARG1和ARG2 指示器,指向符号表的某一位置或三元式表自身的某 项 8

8 例：A+B*C的三元式 op ARG1 ARG2 (1) * B C (2) + A (1) ARG1和 ARG2： 指示器，指向符号表的某一位置或三元式表自身的某 一项

例:X:=a*b+c op ARGI ARG2 (2)+(1 (2) 例:(A∧B)∨(-CVD op ARGI ARG2 (1)∧ A B C (3) (1)(3)

9 例：X:=a*b+c op ARG1 ARG2 (1) * a b (2) + (1) c (3) := X (2) 例：(A ∧B) ∨ ( C ∨D) op ARG1 ARG2 (1) ∧ A B (2)  C _ (3) ∨ (2) D (4) ∨ (1) (3)

(2)语法制导生成三元式 EVAL:指示器,或指向符号表的某一项或三元式 自身的某一项 TRIP(op,ARG1,ARG2)语义过程,产生新的三元式 (op,ARG1,ARG2)并回送三元式在表中的位置 ENTRY(id)语义过程,查找标识符id在符号表中 的位置

10 (2)语法制导生成三元式 E·VAL: 指示器，或指向符号表的某一项或三元式 自身的某一项 TRIP(op,ARG1,ARG2):语义过程，产生新的三元式 （op,ARG1,ARG2)并回送三元式在表中的位置。 ENTRY(id):语义过程，查找标识符id在符号表中 的位置