例P142和16,4和7.18和1g是同心集 在LR(0)项目集规范族中，同心集在一个项目集中。但在LR(1) 中分成两个项目集合，所以体积增大，占用内存。此为LR(1)的缺 点，所以引入LALR(1) P145表7.12是LALR(1) 当3.6通过B到达的两个状态不再一个集合，即合并同心集出错。所 以不是LALR(1) 例如果到8,7 LR(1)可能是LALR(1)→同心集合并无冲突，是LALR(1) 同心集合并有冲突，不是LALR(I) LR (0)SLR (1)LR (1)LALR (1) 是 是 →是 不是 →不一定 不是 +不一定 是 +不一定 不一定一是 肯定不是←—肯定不是 二义性文法本身无法证明，但如果文法是LL(K)算符优先或LR(K) 文法，则就可以证明不是二义性文法。 LL(1)→判断串是否为句子，因为用推导 所以LL(I)精确判断，思想是最左推导相同，Select集相交为空 算符优先→归约，FIRSTUT,LASTUT,但可能产生错误的句子
例 P142 I3和 I6 ， I4和 I7， I8和 I9是同心集 在 LR（0）项目集规范族中，同心集在一个项目集中。但在 LR（1） 中分成两个项目集合，所以体积增大，占用内存。此为 LR（1）的缺 点，所以引入 LALR（1） P145 表 7.12 是 LALR（1） 当 3.6 通过 B 到达的两个状态不再一个集合，即合并同心集出错。所 以不是 LALR（1） 例如果到 8，7 LR（1）可能是 LALR（1） 同心集合并无冲突，是 LALR（1） 同心集合并有冲突，不是 LALR（1） LR（0） SLR（1） LR（1） LALR（1） 是 是 是 是 不是 不一定 不是 不一定 是 不一定 不一定 是 肯定不是 肯定不是 二义性文法本身无法证明，但如果文法是 LL（K）算符优先或 LR（K） 文法，则就可以证明不是二义性文法。 LL（1） 判断串是否为句子，因为用推导 所以 LL（1）精确判断，思想是最左推导相同，Select 集相交为空 算符优先 归约，FIRSTUT，LASTUT，但可能产生错误的句子
算符优先矩阵。 LR(1)→应用最广，但相对复杂 第七章制导翻译和中间代码生成 源程序 分词法分析 了语法分析 →与机器无关 析语支分析【中间代码生成】 综代码优化对中代优化 合了目标代码生成，系统结构，指令系统与机器有关 目标程序 自定向下：推导（匹配）成功后进行语义分析 自底向上：归约成功后进行语义分析 &7.1属性文法P155 1.属性：语言结构的特征 i.type 变量数据类型 {i.Val变量，值 i.Add变量，地址 文法符号属性：Xt 2.属性文法P155 3.语义规则：(}语义子程序：描述了一个产生式所对应的翻译工作。 例P156例1,2,3 &7.2语法制导翻译概论
算符优先矩阵。 LR（1） 应用最广，但相对复杂 第七章 制导翻译和中间代码生成 源程序 分 词法分析 语法分析 与机器无关 析 语义分析 【中间代码生成】 综 代码优化 对中代优化 合 目标代码生成，系统结构，指令系统 与机器有关 目标程序 自定向下：推导（匹配）成功后进行语义分析 自底向上：归约成功后进行语义分析 &7.1 属性文法 P155 1.属性：语言结构的特征 i. type 变量数据类型 i. Val 变量，值 i. Add 变量，地址 文法符号属性：X.t 2.属性文法 P155 3.语义规则：｛｝ 语义子程序：描述了一个产生式所对应的翻译工作。 例 P156 例 1，2，3 &7.2 语法制导翻译概论
1.语法制导翻译P157 自顶向下 「逆归子程序 (LL（1)-栈推导的同时执行语义分析 自底向上 〔算符优先 一栈找着最左表短语归约，同时执行 LR (K) 语义规则 例1：LR(K)P158 例2：G[A:A→aB {print“0”;}当输入串为aacbb时打印 A→C {print“1”:}的字符串 B→Ab(print“2”: 方法1：画语法树，句柄归约时 方法2：算符优先归约 方法3：LR(K) 1A←-C “1” 2B+Ab “12” 3A←-aB “120” 4B+Ab “1202 5A+aB “12020” 所以打印的字符串是“12020” 例3.G[S]S'→S{print(S.num} S(L){S.num:=L.num+1;) Sa (S.num:=0;) L-L,S (L.num:=L,num+S.num;) L一6{L.num=S.num}问(a,(a,a)的值为多少？
1.语法制导翻译 P157 自顶向下 逆归子程序 LL（1） - 栈 推导的同时执行语义分析 自底向上 算符优先 栈 找着最左表短语归约，同时执行 LR（K） 语义规则 例 1： LR（K） P158 例 2： G[A]：A aB ｛print “0”；｝ 当输入串为 aacbb 时打印 A C ｛print “1”；｝ 的字符串 B Ab ｛print “2”；｝ 方法 1：画语法树，句柄归约时 方法 2：算符优先 归约 方法 3：LR（K） 1 A C “1” 2 B Ab “12” 3 A aB “120” 4 B Ab “1202” 5 A aB “12020” 所以打印的字符串是“12020” 例 3.G[S'] S' S {print(S.num);} S (L) {S.num:=L.num+1;} S a {S.num:=0;} L L,S {L.num:=L,num+S.num;} L S {L.num:=S.num} 问(a,(a,a))的值为多少？
S'=>S=>(L)>(L,S)=>(S,S)=>(a,S=>(a,L)）=>(a,(L,S)=>(a,(S,S)=> (a,L,S)=>(a,(S,S)=>(a,(a,S)=>a,(a,a) 1.S1Rlc*de/-=>R2de/-=>R2 R3-=>R4 R:代表第i次运算结果 用栈实现：自古向右扫描，运算对象入栈，算符K目就对栈顶KJ元 来操作，结果代替入栈，最后后果保留至栈顶
S'=>S=>(L)=>(L,S)=>(S,S)=>(a,S)=>(a,(L))=>(a,(L,S))=>(a,(S,S))=> （a,(L,S)）=>(a,(S,S))=>(a,(a,S))=>(a,(a,a)) 1.S1 例：x*(y+z) xyz+* (a+b)*(c+d) ab+cd+* a+b*(c+d)*(e+f) abcd+*ef+*+ 1.计算值时：例：(a+b)*c-d/e ab+c*de/-=>R1 c*de/-=>R2 de/-=>R2 R3-=>R4 Ri:代表第 i 次运算结果 用栈实现：自古向右扫描，运算对象入栈，算符 K 目就对栈顶 KJ 元 来操作，结果代替入栈，最后后果保留至栈顶
例1.(a+b)*c ab+c* 例2.(a+b)*c-d小e ab+c*del- 2.推行 (I)赋值语句：:= = 例：x=a+b*(c-d) xabcd-*+:= (2)转向语句：gotoLJ(Jump) 例：goto100 100 LJ(Jump) (3)条件语句：ifthenelse FJRJb then max:=a else max:=b 或：￥：三目运算符if-then-else 或：1ab>411FJ6maxa:=914RJ11maxb= (4)循环语句： 例：fori=a to b do s转换为条件语句，在递表示i=a; l0:lfi递：ia=ib<=17 FJs'iil+-:=4RJ Begin s;i:=i+1;Goto 10;end; 例：fori=lto20dos=stii=l 20:if i<=20 then begin s:=s+i;i:=i+1;goto 20 end; While exp do s
例 1.（a+b）*c ab+c* 例 2.(a+b)*c-d\e ab+c*de\- 2.推行 (1)赋值语句：:= := 例：x:=a+b*(c-d) xabcd-*+:= (2)转向语句：goto LJ(Jump) 例：goto 100 100 LJ(Jump) (3)条件语句: if then else FJRJ 例：if a>b then max:=a else max:=b 或: ￥:三目运算符 if-then-else 或:1 ab> 4 11FJ 6 maxa:= 9 14RJ 11 maxb:= (4)循环语句: 例:for i:=a to b do s 转换为条件语句，在递表示 i:=a; 10 :If i递：ia:=ib<=17 FJ s' ii1+:=4 RJ Begin s; i:=i+1; Goto 10; end; 例:for i:=1 to 20 do s:=s+i i:=1 20: if i<=20 then begin s:=s+i;i:=i+1; goto 20 end; While exp do s
FJ1RJ 例：while i. Blockblockend 二、三元式(op,ARG1,ARG2) 例1.atb*c(*,b,c),.(什，a,lI) 例2：P160 (1)表达式，赋值语法 例：x=a+b*(c-d)(-,c,d*,b,1)+,a,2)=,3,x) (2)转向语句goto L(LJ,L,1) (3)条件：ifa>b then max::=a else max:=b 1.(,a,b) 2.(FJ,5,1)3=,a,max) 4.(RJ,6,1)5.(=,b,max)6() (4)循环：fori=1to20d0s=s+i; 1.(=,1,i) 2.(<=,i20)3FJ,9,2) 4.(+,s,i0 5.(=,4,s)6.(+,i,1)7=,6,) 8(RJ,2,1)9() While i<=100 do S:=S+i, 1.(<=,i,100) 2.(FJ,8,1)3.(+,s,i)4.(=,3,5) 5.(+,i1)6(=,5,i)7RJ,1,1)8(.)
FJ 1 RJ 例:while i. Block . blockend 二、三元式(op,ARG1,ARG2) 例 1. a+b*c (*,b,c),(+,a,1) 例 2: P160 (1)表达式，赋值语法 例：x:=a+b*(c-d) (-,c,d)(*,b,1)(+,a,2)(:=,3,x) (2)转向语句 goto L (LJ,L,1) (3)条件: if a>b then max:=a else max:=b 1.(>,a,b) 2.(FJ,5,1) 3(:=,a,max) 4.(RJ,6,1) 5.(:=,b,max) 6(.) (4)循环: for i:=1 to 20 do s:=s+i; 1.(:=,1,i) 2.(<=,i,20) 3(FJ,9,2) 4.(+,s,i) 5.(:=,4,s) 6.(+,i,1) 7(:=,6,i) 8(RJ,2,1) 9(.) While i<=100 do s:=s+i; 1.(<=,i,100) 2.(FJ,8,1) 3.(+,s,i) 4.(:=,3,5) 5.(+,i,1) 6(:=,5,i) 7(RJ,1,1) 8(.)
(⑤)复合语句1.(block,1,1) n.(blockend,1,1) 三、树形表示一由三元示而来 树叶-运算对象（常量/变量） 结点运算符 T1212T1 一个三元式对应一个二叉树 OP, ARGI ARG2) 子树根 子树的两棵子树（或终结符，或下代子树的根）》 例：a*b+c*d 1.(*,a,b) 2.(*,c,d) 3.(+,1,2) 四、四元式(OP,ARG1,ARG2,RESULT) 例1：a+b(+,a,b,T)-a(←.a.T1,T2)单目ARG2为空 例2：a+b*c(*,b,c,T1)(什，a,T1,T2)T1是临时变量，联系四元式 X:=a (=,a,1,x) (1)例3.y=(-b)*(c+d) (,b/,T1)(+,c,d,T2)(*,T1,T2,T3)(=,T3,/y) 写成赋值语句更直观：T1:=bT2:=c+dT3=T1*T2y=T3 (2)转向语句和条件语句 goto L, (LJ.L/.L) If「无条件转到序号A(RJ,A,) (B为假转到A(FJ,A,B,)
(5)复合语句 1.(block,1,1) n.(blockend,1,1) 三、树形表示-由三元示而来 树叶-运算对象（常量/变量） + * - 结点-运算符 T1 T2 T1 T2 T1 一个三元式对应一个二叉树 （ OP， ARG1 ，ARG2） 子树根 子树的两棵子树（或终结符，或下代子树的根） 例： a*b+c*d + 1.(*,a,b) * * 2.(*,c,d) a b c d 3.(+,1,2) 四、四元式 （OP ， ARG1， ARG2， RESULT） 例 1：a+b (+,a,b,T) -a (-.a.T1,T2) 单目 ARG2 为空 例 2：a+b*c (*,b,c,T1) (+,a,T1,T2) T1 是临时变量,联系四元式 x:=a (:=,a,1,x) (1)例 3. y:=(-b)*(c+d) (-,b,/,T1) (+,c,d,T2) (*,T1,T2,T3) (:=,T3,/,y) 写成赋值语句更直观: T1:=-b T2:=c+d T3=T1*T2 y:=T3 (2)转向语句和条件语句 goto L, (LJ,L,/,L) If 无条件转到序号 A (RJ,A,/,/) B 为假转到 A (FJ,A,B,/)
例：ifa>b then max:=a else max:=b 1.(U,a,b,T1) 2.(FJ,5,T1,0 3.(:=,a,max) 4.(RJ,60 5.(=,b,/,max)6.() (3)循环语句 for i:=1 to 20 do s:=s+i while iT4:=T1
例：if a>b then max:=a else max:=b 1.(/,a,b,T1) 2.(FJ,5,T1,/) 3.(:=,a,max) 4.(RJ,6,/,/) 5.(:=,b,/,max) 6.(.) (3)循环语句 for i:=1 to 20 do s:=s+i while iT4:=T1
2.代码外提：把循环中代码总数减少 例：fori=1 to 10 begin x:=x+i y:=a+b End 3强度消弱：运算强度大的转化成强度小的代码 4变换循环控制条件：减少变量 5.1)合并已知量2)复写传播 例：T=2*3=>T:=61=5x=+8=>x=13 例：TXxy=>Ty 6删除无用赋值 两次赋值之间没有对变量引用，删除前一个赋值 局部优化 基本块：定义11.2P15 例1. →l.read c 2.A=0 -3.B:=1 →4.A:=A+B 5.If B>=C goto 10 →6.B:=B+1 -7.Goto 4
2.代码外提：把循环中代码总数减少 例：for i:=1 to 10 begin x:=x+i y:=a+b End 3.强度消弱：运算强度大的转化成强度小的代码 4.变换循环控制条件：减少变量 5.1）合并已知量 2）复写传播 例：T=2*3=>T:=6 I:=5 x:=I+8=>x:=13 例：T:=x x:=y => T:=y 6.删除无用赋值 两次赋值之间没有对变量引用，删除前一个赋值 局部优化 基本块：定义 11.2 P115 例 1.1.read c 2.A:=0; 3.B:=1 4.A:=A+B 5.If B>=C goto 10 6.B:=B+1 7.Goto 4
8A:=B+C 多余无用语句（死代码） 义B:=A+2 →10.Write A 11.Halt 例2：a=20 a=20,(合并已知量) b:=a*(a+10) =>b:=600: c:=a*b => c=12000: 例3：(a*b+c)/a*b-c)t(c*b+a-d)/(a*b+c) 1.(*a,b,T1)2.(+,T1,c,T2)3.(*,ab,T3)4.(-,T1,c,T4) 5.(0,T2,T4,T5)6.(*,c,b,T6) 7.(+,T6,a,T78.(,T7,d,T8) 9(*,a,b,T9)10.(+,T1,c,T2)11.(,T8,T10,T11)12.(+,T5,T11,T12) 控制流分析和循环优化 +i=l; B1i=10: Read k: *1:X:=k*工， y:=j*i; Z:=x*y; B2 write j; i:=i+l; If ihalt:
8.A:=B+C 多余无用语句(死代码) 9.B:=A+2 10.Write A 11.Halt 例 2：a:=20 a:=20;(合并已知量) b:=a*(a+10) => b:=600; c:=a*b => c:=12000; 例 3：(a*b+c)/(a*b-c)+(c*b+a-d)/(a*b+c) 1.(*,a,b,T1) 2.(+,T1,c,T2) 3.(*,a,b,T3) 4.(-,T1,c,T4) 5.(/,T2,T4,T5) 6.(*,c,b,T6) 7.(+,T6,a,T7) 8.(-,T7,d,T8) 9(*,a,b,T9) 10.(+,T1,c,T2)11.(/,T8,T10,T11)12.(+,T5,T11,T12) 控制流分析和循环优化 i:=1; B1 j:=10; Read k; 1: x:=k*i; y:=j*i; z:=x*y; B2 write j; i:=i+1; If i halt;