第5章自頂向下語法分析方法-在線瀏覽
2024-11-04 09:09本頁面
【正文】 LECT(S→aAS) ∩ SELECT(S→b)={a}∩ =Φ SELECT(A→bA)∩SELECT(A→ ε)=∩{a,b,ε}≠Φ 所以該文法不是 LL(1)文法。 編譯原理 ε 的非終結(jié)符 S→AB S→bC A→ ε A→b B→ ε B→aD C→AD C→b D→aS D→c 非終結(jié)符 S A B C D 初值 未定 未定 未定 未定 未定 第一次掃描 是 是 否 第二次掃描 是 否 編譯原理 FIRST集 ? X?V?,則 FIRST(X)={X} ? X?VN,且有產(chǎn)生式 X?a…， 則 a∈FIRST(X) 。若 X ? Y1Y2…YK 是一個產(chǎn)生式 ,Y1,Y2,…,Y(i1)都是非終結(jié)符 ,而且 ,對于任何 j,1≤ j ≤i 1,FIRST(Yj)都含有?(即 Y1..Y(i1) ? ),則把 FIRST(Yj)中的所有非 ?元素都加到 FIRST(X)中 。 。 ? Ａ → αB是一個產(chǎn)生式 ,或 Ａ → αBβ是 ?? 一個產(chǎn)生式而 β ?(即 ??FIRST(β )）， 則把FOLLOW（ A）， 加至 FOLLOW（ B） 中． * ? 編譯原理 S→AB S→bC A→ ε A→b B→ ε B→aD C→AD C→b D→aS D→c FOLLOW(S)={}∪ FOLLOW(D) FOLLOW(A)={a}∪ {a,c}∪ FOLLOW(S) FOLLOW(B)=FOLLOW(S) FOLLOW(C)=FOLLOW(S) FOLLOW(D)=FOLLOW(B)∪ FOLLOW(C) FOLLOW(S)= {} FOLLOW(A)= {a,c,} FOLLOW(B)= {} FOLLOW(C)= {} FOLLOW(D)= {} 編譯原理 SELECT集 S→AB S→bC A→ ε A→b B→ ε B→aD C→AD C→b D→aS D→c FIRST(S)={a,b,ε} FIRST(A)={b, ε} FIRST(B)={a, ε} FIRST(C)={a,b,c} FIRST(D)={a,c} FIRST(AB)={a,b,ε} FIRST(AD)={a,b,c} SELECT(S→AB)={a, b,ε,} SELECT(S→bC)={ b} SELECT(A→ ε)={a,c,ε} SELECT(A→ b)= SELECT(B→ ε)={,ε} SELECT(B→aD)={a} SELECT(C→AD)={a, b,c} SELECT(C→b)={ b} SELECT(D→aS)={a} SELECT(D→c)={c} FOLLOW(S)= {} FOLLOW(A)= {a,c,} FOLLOW(B)= {} FOLLOW(C)= {} FOLLOW(D)= {} 該文法不是 LL(1)文法。 等價變換為 A→ α(β|γ)， 然后： A→ αA39。 → β|γ A→ αβ1|αβ2|…|αβ n 變換為 A→ α(β1|β2|…|β n) ，然后： A→ αA39。 → β1|β2|…|β n 編譯原理 ? 例：文法 G1[S] 為 : S→aSb S→aS S→ ε 化為： S→aS(b| ε) S→ ε 進(jìn)一步化為： S→aS A A→b A→ ε S→ ε 結(jié)果仍然不是 LL(1)文法。 w=aabb S=aSA =aaSAA =aaAA =aabA (aaA) 編譯原理 ? 例：文法 G2為 : A→ad A→Bc B→aA B→bB ： A→ad A→ aAc A→ bBc B→aA B→bB ： A→ a(d|Ac) A→ bBc B→aA B→bB ： A→ aA39?！?d A39。 編譯原理 ? 例：文法 G3[S] 為 : S→aSd S→Ac A→aS A→b ： S→aSd S→aSc S→bc A→aS A→b ： S→aS(d|c) S→bc A→aS A→b ： S→aS A39?！?d A39。 編譯原理 ? 例：文法 G4[S] 為 : S→Ap|Bq A→aAp|d B→aBq|e ：
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1