【正文】 遞歸和回溯 ， 故其不是LL(1)文法 。 第三章 語法分析 void S′ ( ) { if ( lookahead==′ +′ ) { match (′ +′ )。 第三章 語法分析 ( L )SL , SS ( L )Sa圖 35 句型 (S,(a))的語法樹 第三章 語法分析 (2) 由圖 35可知： 短語： S、 a、 (a)、 S,(a)、 (S,(a))； 直接短語： a、 S； 句柄： S； 素短語：素短語可由圖 35中相鄰終結符之間的優(yōu)先關系求得 ， 即： ? (?， ? (?a?)?)? 因此 ， 素短語為 a。 第三章 語法分析 A a B b S c ABA caSB dbb S c ABA caSB d c( a ) ( b )c圖 34 習題 (a) aAaBcbbdcc。 【 解答 】 (1) 由 L={aibj|j＞ i≥ 0}知 ， 所求該語言對應的上下文無關文法首先應有 S→ aSb型產生式 ， 以保證 b的個數不少于 a的個數；其次 ， 還需有 S→ Sb或 S→ b型的產生式 ， 用以保證 b的個數多于 a的個數 。 (2) 最左推導： NNDNDDNDDDDDDD0DDD01DD012D0127 NNDDD3D34 NNDNDDDDD5DD56D568 最右推導： NNDN7ND7N27ND27N127D1270127 NNDN4D434 NNDN8ND8N68D68568 第三章 語法分析 已知文法 G[S]為 S→ aSb|Sb|b， 試證明文法G[S]為二義文法 。 a. 直接短語 b. 句柄 c. 最左素短語 d. 素短語 (6) 若 a為終結符 ， 則 A→ α a. 最左推導和最右推導對應的語法樹必定相同 b. 最左推導和最右推導對應的語法樹可能不同 c. 最左推導和最右推導必定相同 d. 可能存在兩個不同的最左推導 ， 但它們對應的語法樹相同 第三章 語法分析 (3) 采用自上而下分析 ， 必須 。 a. LALR文法 b. LR(0)文法 c. LR(1)文法 d. SLR(1)文法 第三章 語法分析 (8) 同心集合并有可能產生新的 沖突 。 第三章 語法分析 SS SaS Sa? ??SSS aSS a???( a ) ( b )圖 32 句子 aa對應的兩棵不同的語法樹 第三章 語法分析 由圖 32可知 ， 文法 G[S]為二義文法 。 此外 ， 為了保證遞歸地推出所要求的 ab串 ，應有 S→ aBS和 S→ bAS。 由此可知 ， 畫出對應句型的語法樹然后尋找最左直接短語是確定句柄的好方法 。 } 第三章 語法分析 void S ( ) { if ( lookahead==′ a′ ) match (′ a′ )。 S ( )。 第三章 語法分析 (2) 構造預測分析表的方法如下： ① 對文法 G[A′ ]的每個產生式 A→ α 執(zhí)行 ② 、 ③步 。 故文法 G[V′ ]為 LL(1)文法 。 由 ① 得： E→ … +T， 得 LASTVT(E)={+}； T→ … *P， 得 LASTVT(T)={*}； P→ i， 得 LASTVT(P)={i}。 第三章 語法分析 表 33 習題 + * i + ? ? ? * ? ? ? i ? ? 第三章 語法分析 用關系圖構造優(yōu)先函數的方法是：對所有終結符 a用有下腳標的 fa、 ga為結點名畫出全部終結符所對應的結點 。如果有一個函數值大于 2n(n為終結符個數 )，則不存在優(yōu)先函數。 第三章 語法分析 表 36 習題 a b ( ) d a ? ? ? b ? ? ? ( ? ? ? ? ) ? ? ? d ? ? ? ? ? ? ? ? 第三章 語法分析 由表 36可以看出 ， 任何兩個終結符之間至多只滿足 、?、 ?三種優(yōu)先關系之一 ， 故 G[S]為算符優(yōu)先文法 。 ( A )SS d ASba圖 310 (adb)的語法樹 第三章 語法分析 在算符優(yōu)先分析法中 ， 為什么要在找到最左素短語的尾時才返回來確定其對應的頭 ， 能否按掃描順序先找到頭后再找到對應的尾 ， 為什么 ？ 【 解答 】 設句型的一般形式為 N1a1N2a2… NnanNn+1。 (2) 設 n=k時結論成立 ， 則對任何 k+1步推導所產生的句型必為 Sα ∪ β ? α ∨ β 其中 ， α 、 β ∈ (VT∪ VN) *， U∈ VN， 而 U→ V是一條產生式 。 (2) 由文法 G[S]可以看出： S推出串的形式是 ai P bi(i≥ 0)， P推出串的形式是 bjQcj(j≥ 1)， Q推出串的形式是 ak(k≥ 1)。 規(guī)范歸約是關于 α 的一個最右推導的逆過程 ， 因此 ， 規(guī)范歸約也稱最左歸約 。 這既是算符優(yōu)先分析的優(yōu)點 ， 同時也是它的缺點 ， 因為忽略非終結符在歸約過程中的作用存在某種危險性 ， 可能導致把本來不成句子的輸入串誤認為是句子 ， 但這種缺陷容易從技術上加以彌補 。文法 G每一個產生式的右部添加一個圓點稱為 G的一個LR(0)項目 (簡稱項目 )，可以使用這些項目狀態(tài)構造一個NFA。B S→ A→ e S→ bA 文法 G[S′ ]的 DFA如圖 311所示 。 A S B S →b S → I8： S →bA S B 最后得到 SLR(1)分析表見表 39。 (4) LALR從本質上講與 LR(1)相同 ， 只不過它把那些棧頂符號串相同但現(xiàn)行輸入符號不同 (即認為這個相同的棧頂符號串為同心 )的判斷合一 (使狀態(tài)數又減少到與 LR(0)、 SLR(1)一樣 )， 只有輸入符號跟在棧頂符號串后面形成一規(guī)范句型前綴時 ， 才認為棧頂的這個符號串為句柄而進行歸約 。 第三章 語法分析 ( a ) ( b ) ( c )5 r14 r23 r22 s451 a cc0 s31 2狀態(tài)A C T I O N G O T Ob S B4 r1r1r13 r2r2r22 s2s30 s3s211 a cc g狀態(tài)A C T I O N G O T Oa b T4 r13 r22 a cc1 s1s30 s12s3狀態(tài)A C T I O N G O T Oi k P圖 312 LR分析表 第三章 語法分析 (2) 對 SLR(1)分析表來說 ， 若項目 A→ α ,b]屬于 Im(狀態(tài) )， 則同樣置 ACTION[m,b]欄目為 rj。F 2. S′ → S*Fi 4. S→ (i 6. S→ (Eti 8. S→ (EtSe(EtSeS) S→ (EtSF I1: S′ → S) I15: E→ +EFtSeS) I10: S→ ii S→ (Eti=E 文法 G[S′ ]的 DFA如圖 313所示 。 E t S ) E → t S e S ) S →( E i I1 7： F →* S e S ) S →( E t ( E t S e S ) S → 第三章 語法分析 表 310 習題 SLR(1)分析表 A CT IO N G O T O 狀態(tài) t + e ( ) * = i S E F 0 s10 1 1 acc 2 s13 3 16 3 s4 4 s2 s10 5 5 s6 s9 6 s2 s10 7 7 s8 8 r1 r1 r1 9 r2 r2 r2 10 s11 11 s13 12 16 12 r3 r3 r3 13 s13 14 16 14 s17 15 15 r4 r4 r4 r4 r4 16 r5 r5 r5 r5 r5 17 s17 s20 18 18 s19 19 r6 r6 r6 r6 r6 20 r7 r7 r7 r7 r7 第三章 語法分析 為二義文法 G[T]構造一個 LR分析表 (詳細說明構造方法 )。 6 ． T→ TATAT 8 ． T→ b T A T T → A T A → a I8： T →T A T ； I9： T →bT e 下面 。 逐一檢查各狀態(tài) ， 得知 I8存在 “ 移進 ” /“歸約 ” 沖突 (因為T→ TAT A T A → ； I5： A→ ， a I2： T →b 16． A→ 。 14． A→ ， G[T]: T→ TAT | bTe | a A→ , | 。 i ＝ E I7： S →( E t S e S ( E t S e S ) S → * F i F → I1 3： E → ＋ F I10： S →i I0： S ′ →F I19: F→ *Fi*Fi S→ (E+EF I8: S→ (EtSeS)(EtS) F→ +EF S→ 24. E→ +EFS) 22. E→ +EtS) 20. S→ i=E 18. S→ i 第三章 語法分析 因此 ， 圖 312(a)的分析表為 LR(1)分析表 (在不同行有相同的 r2存在 )；圖 312(b)為 LR(0)分析表 (有 rj的行是每行都填滿了 rj且同一行 rj的 j相同 ， 不同行 rj的 j不同 )；而圖 312(c)為 LR(0)分析表 (存在并不全部填滿 rj的行 ，且不同行 rj的 j不同 )。表現(xiàn)在 ACTION子表中 ， 則存在某個歸約狀態(tài)所在的行并不全部填滿 rj， 并且不同行的 “ rj”其下標 j不同 。 此外 ， LALR這種同心集的合并有可能帶來新的 “ 歸約 ” /“歸約 ” 沖突 。 它們的本質區(qū)別是尋找句柄的方法不同 。 a I10： A →dS a bA I9： B →c dS a A → B B → S→ Aa A→ cAa 第三章 語法分析 I1: S′ → S構成識別一個文法活前綴的 DFA項目集 (狀態(tài) )的全體稱為這個文法的 LR(0)項目集歸范族。 第三章 語法分析 什么是規(guī)范句型的活前綴 ？ 引進它的意義何在 ？ 【 解答 】 在討論 LR分