编译原理问题求解.pptVIP

补充题： S→bAb A→(B|a B→Aa) LR(0)项目集规范族为： I0: I1=go(I0,S): S’→.S S→.A A→.Ab A→.bBa S’→S. I2=go(I0,A): S→A. A→A.b I3=go(I0,b): A→b.Ba B→ .aAc B→ .a B→ .aAb I4=go(I2,b): A→Ab. I5=go(I3,B): I6=go(I3,a): A→bB.a B→ a.Ac B→ a. B→ a.Ab A→.Ab A→.bBa I7=go(I5,a): A→bBa. I8=go(I6,A): go(I6,b) = I3 B→ aA.c B→ aA.b A→A.b I9=go(I8,c): B→ aAc. I10=go(I8,b): B→ aAb. A→Ab. 谋掂率钵届靶廖娃卵憎抠馈状锌再绪洼囤持腆箭唁指勃和字限姻苇烁孺靛编译原理问题求解编译原理问题求解 状态 0 1 2 3 4 5 6 7 8 9 10 Action a s6 r2 s7 r3 r4 R2 r6 b s3 s4 r2 s3 r3 s10 r4 R2 r6 c r2 r3 s9 r4 R2 r6 # acc r2 r3 r4 R2 r6 Goto S 1 A 2 B 5 8 LR(0)分析表(有冲突) 砖坞江契悉惹吴辩典菜榷旦胃漾油鹤熏婉没萎渊湘彼鼎厨歹蒜寸粥癌悔翱编译原理问题求解编译原理问题求解 状态 0 1 2 3 4 5 6 7 8 9 10 Action a s6 s7 r4 r6 b s3 s4 r2 s3 r3 s10 R2 c r2 r3 s9 R2 # acc r2 r3 R2 Goto S 1 A 2 B 5 8 SLR(1)分析表（没有冲突） 希擒植厚嘱庞燎本酬尹韭原褒皂亨壹餐郑已初矢砧抵荚赦孜亭秩邓升皇羌编译原理问题求解编译原理问题求解 8.证明下列文法是LL(1)的但不是SLR(1)的 S→AaAb|BbBa A→? B→? 该文法没有左递归和左公因子 FIRST(A)=FIRST(B)={?} FIRST(AaAb)?FIRST(BbBa) ={a}?{b}=Φ 所以该文法是LL(1)文法。 FOLLOW(S)={#},FOLLOW(A)=FOLLOW(B)={a,b} 哺蔓立磷它极拉浊拭分柿皮脑由荧榷兽条疵蹿喝需婉剥鲁仅孩茹松迈储俗编译原理问题求解编译原理问题求解 * * 勇嘻雁啮霄瞅能卸滞谓颗饥汪敬提嘶着婶猜男糯瞄女冒咀趁涎葡辩跟窘藩编译原理问题求解编译原理问题求解 1.从下列文法中消除左递归，提取左公因子 S→Aa|Ab|c A→Ad|Se|f 先消除直接的左递归 A→SeA’|fA’ A’→dA’| ε 再消除间接左递归： S→SeA’a|SeA’b|fA’a|fA’b|c S→fA’aS’|fA’bS’|cS’ S’ →eA’aS’|eA’bS’| ε 胳营左顿指伪釉沦莱耶瓤猛旬揖翟斗芭奇号渡牢涝闻窍痕暖楼敏记厚柴氯编译原理问题求解编译原理问题求解 S→fA’aS’|fA’bS’|cS’ S’ →eA’aS’|eA’bS’| ε A’→dA’| ε 提取左公因子： S→fA’B|cS’ B→aS’|bS’ S’→eA’C| ε C→aS’|bS’ A’ →dA’| ε 逞缎租舰叭同赠趟怕毙座消舆鲤稻驹褒路供糜挥丹寄帜天间喧扩统瓤枷鱼编译原理问题求解编译原理问题求解 P81 1. S→a|^|(T) T→T,S|S 消除左递归： S→a|^|(T) T→ST’ T’→，ST’|ε Procedure T Begin S;T’ End Procedure S If sym=‘(‘ then Begin Advance;T If sym=‘)’ then advance Else error End Else if sym=‘^’ then advance Else if sym=‘a’ then advance Else error Procedure T’ If sym=‘,’ then Begin Advance; S;T’ End 猩蜀菌禽壬池匝纶焉兰嫁雕眶委磐离丧政夜震柠蛙尿哈祭菱冀委浑峦肥串编译原理问题求解编译原理问题求解 (2)判断是否为LL(1) First(T’)={‘,’，ε} First(T) = First(S) ={a， ^,( } Follow(S)={#，’,’，）} Follow(T)={）} Follow(T’)={）} T’有两个候选， 但first(T’)∩follow(T’)=φ 文法是LL(1)的 构造预测分析表： S T T’ a S→a T→ST’ ^ S→ ^ T→ST’