编译原理第5章 语义分析及中间代码产生.ppt

第五章语法制导翻译和中间代码产生 * * 算术表达式a+b*c翻译到三地址语句的过程： 03 0 $ $a 01 $E 014 $E+ 0143 $E+b －a －a－ －a－－ 状态栈 符号栈 语义栈 输入串 a+b*c$ +b*c$ +b*c$ b*c$ *c$ － － － 第五章语法制导翻译和中间代码产生 * * *c$ c$ $ $ $ $ t1=b*c t2=a+t1 状态栈 符号栈 语义栈 输入串 01475 0147 $E+E $E+E* 014753 $E+E*c 014758 $E+E*E 0147 $E+E 01 $E －a－b－ － －a－b－c －a－t1 －a－b－ －a－b －t2 acc 第五章语法制导翻译和中间代码产生 * * 二、布尔表达式的翻译 1、E→E ∨ E 2、E→E ∧ E 3、E→ ? E 4、E→(E) 5、E→id rop id 6、E→id 第五章语法制导翻译和中间代码产生 * * 1、类似算术表达式的翻译方法 （求每个因子，再求表达式的值） 例如： 布尔表达式 ： a ∨ b ∧ ? c 三地址序列： T1:= ? c T2:=b ∧ T1 T3:=a ∨ T2 第五章语法制导翻译和中间代码产生 * * 1. E→ E (1)∨ E (2) { E.place ＝ newtemp( )； emit ( E.place’＝’E(1).place’∨’E(2).place ) } 2. E→ E (1) ∧ E (2) { E.place ＝ newtemp( )； emit ( E.place’＝’E(1).place’∧’E(2).place ) } 3. E→ ? E (1) { E.place ＝ newtemp( )； emit ( E.place’＝’’?’ E(1).place} 4. E→ ( E (1) ) { E.place ＝ E(1).place；} 5. E→ i (1) rop i (2) { E.place ＝ newtemp( )； emit (‘if ’ i (1).place rop.op i (2).place ‘goto’ next+3); emit ( E.place’＝’ ‘0’ ); emit ( goto next+2); emit ( E.place’＝’ ‘1’ ); } 6. E→ i { E.place ＝ i . place；} 第五章语法制导翻译和中间代码产生 * * E E ∨ E a b E ∧ E cd ef 第五章语法制导翻译和中间代码产生 * * 2、根据布尔表达式的特殊性采取某种优化措施 A ∨ B if A then trun else B A ∧ B if A then B else false ? A if A then false else true ①对非终结符E赋予两个出口 真出口：布尔表达式为真时，需转移的四元式地址。 假出口：布尔表达式为假时，需转移的四元式地址。 第五章语法制导翻译和中间代码产生 * * ②设置两个语义变量： E.ture : 用来记录表达式E对应的四元式需回填真出口的四元式的地址所构成的链。 E.false:用来记录表达式E对应的四元式需回填假出口的四元式的地址所构成的链。 ③定义三个函数： 第五章语法制导翻译和中间代码产生 * * 链接函数merge(P1 , P2)：把以P1和P2为链首的两条链合并为一，返回合并后的链首（当P2=0时，返回P1 ; 当P2≠0时，返回P2）。 int merge(int P1 , int P2 ) { int P; if (! P2) return P1; else { P=P2 ; while (P.result 0) P=P.result; P.result=P1; return P2 ; } 第五章语法制导翻译和中间代码产生 * * 回填函数backpatch( p , t )：把p所链接的每个四元式的第四分量都回填为t。 void BP( int p , int t ) { int q=p ; while (q) { int q1