编译7语义和中间代码产生1讲述.ppt

* * (2)逆波兰表示的特点 a.标识符(运算对象)出现的顺序（从左到右）和原有顺序相同。 b. 运算符是按实际计算顺序（从左到右）出现的。 c. 运算符紧跟在运算对象的后面出现，并且没有括号。 * * (3) 好处：易于对表达式的计算处理 对于一般表达式的计算，系统需要用两个工作栈分别处理运算对象和运算符。 对于逆波兰表示的表达式计算处理只用一个工作栈。 一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。 * * 例：逆波兰式ab+c*的计算处理过程 遇运算对象a,b入栈 扫描ab+c* b a 栈 遇二目运 算符+c* 取出a,b，运算结果T入栈 T c T 取出c,T作运算，设结果T1 T1 遇运算符* c* 遇运算对象c入栈 * * 2. 形成逆波兰表示 怎样将一般表达式转换成逆波兰表示？ 基本思想:从左到右扫描表达式，每遇到： 1o 表达式中的运算对象则往左去。 2o 表达式中的运算符，则与运算符栈顶元素比较优先数： * * 逆波兰表示 表达式 运算对象 运算符 进栈 出栈 运算符栈 如果运算符栈顶元素的优先数大于或等于表达式中当前的运算符优先数，则栈顶元素退栈向左去。然后当前运算符继续与栈顶的新元素比较优先数。直到栈顶元素的优先数小于表达式中当前运算符为止。此时，才将表达式中当前运算符进栈。 * * 例：画出形成表达式a*(b+c/d)的逆波兰表示过程 a *(b+c/d)# # 步骤① a (b+c/d)# * # 步骤② a b+c/d)# ( * # 步骤③ ab +c/d)# ( * # 步骤④ ab c/d)# + ( * # 步骤⑤ abc /d)# + ( * # 步骤⑥ * * abc d)# / + ( * # 步骤⑦ abcd )# / + ( * # 步骤⑧ / + ( * # abcd/ )# 步骤⑨ + ( * # abcd/+ )# 步骤⑩ * # abcd/+* # 步骤 ⑾ * * 形成逆波兰表示的过程，实质上是表达式的翻译过程。（算法不难写出） 例：a/b/c+d = ab/c/d+ (a+b)*(c-d/e) = ab+cde/-* * * 数组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 抽象语法树 * * 7.1.2 图表示法 无循环有向图(Directed Acyclic Graph，简称DAG) 对表达式中的每个子表达式，DAG中都有一个结点 一个内部结点代表一个操作符，它的孩子代表操作数 在一个DAG中代表公共子表达式的结点具有多个父结点 * * a:=b*(-c)+b*(-c)的图表示法 assign a + * b uminus c DAG assign a + * b uminus c 抽象语法树 * b uminus c * * 抽象语法树对应的代码： T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5 assign a + * b uminus c 抽象语法树 * b uminus c * * DAG对应的代码： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5 assign a + * b uminus c DAG 抽象语法树对应的代码： T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5 * * 产生赋值语句抽象语法树的属性文法 产 生 式 语义规则 S→id:=E S.nptr:=mknode(‘assign’, mkleaf(id,id.place),E.nptr) E→E1+E2 E.nptr:=mknode(‘+’,E1.nptr,E2.nptr) E→E1*E2 E.nptr:=mknode(‘*’,E1.nptr,E2.nptr) E→-E1