例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.S1<-aS1num=0 2.L <-S Li.num=S1.num=0 3.S2<-aS2.num=0 4.L2 <-S2 L2num=S1.num=0 5.S3<-aS3.num=0 6.L<-L,SL.num=0+0=0 7.S<-(L)S.num=L.num+1=0+1=1 8.L <-L,S L.num=L.num+S.num=0+1=1 9.S<-(L)S.num=L,num+1=l+1=2 10.S'<-S print(S.num)print 2: &7.3中间代码的形成 一、逆波兰表示：后缀表示法，最简单，对象去前，运算符去后 注意：算符的优先级，高到低：()，符号，乘方，*，+，=○ 例：x*y+z)Xyz+*(a+b)*(c+d)ab+cd+* a+b*(c+d)*(e+f)abcd+*ef+*+ l.计算值时：例：(a+b)*c-d/e ab+c*de/-=>Rlc*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 <- a S1.num=0 2.L1 <- S1 L1.num=S1.num=0 3.S2 <- a S2.num=0 4.L2 <- S2 L2.num = S1.num=0 5.S3 <- a S3.num=0 6.L <-L,S L.num=0+0=0 7.S <- (L) S.num=L.num+1=0+1=1 8.L <-L,S L.num=L.num+S.num=0+1=1 9.S <- (L) S.num=L,num+1=1+1=2 10.S' <- S print(S.num) print 2; &7.3 中间代码的形成 一、逆波兰表示：后缀表示法，最简单，对象去前，运算符去后 注意：算符的优先级，高到低：（），符号，乘方，*/，+-，=<> 例：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)赋值语句：<左P>:=<表达式> <左P><表达式的递波兰式>= 例：x=a+b*(c-d) xabcd-*+:= (2)转向语句：goto<标号><标号>LJ(Jump) 例：goto100 100 LJ(Jump) (3)条件语句：if<exp>then<sl>else<s2> <xp递波兰式><N>FJ<s1的递波兰式><N2>RJ<s2的递波兰式 例：ifa>b then max:=a else max:=b 或：<exp递波兰式><sl><s2>￥：三目运算符if-then-else 或：1ab>411FJ6maxa:=914RJ11maxb= (4)循环语句： 例：fori=a to b do s转换为条件语句，在递表示i=a; l0:lfi<=b then->递：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)赋值语句：<左 P>:=<表达式> <左 P><表达式的递波兰式>:= 例：x:=a+b*(c-d) xabcd-*+:= (2)转向语句：goto<标号> <标号>LJ(Jump) 例：goto 100 100 LJ(Jump) (3)条件语句: if<exp> then <s1> else <s2> <exp 递波兰式><N1>FJ<s1 的递波兰式><N2>RJ<s2 的递波兰式> 例：if a>b then max:=a else max:=b 或:<exp 递波兰式><s1><s2> ￥:三目运算符 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<=b then ->递：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