【正文】 OW(E) ={ ), } FIRST(E?)={ +, ? } FOLLOW(E?)={ ), } FIRST(T) ={ (, i } FOLLOW(T) ={ +, ), } FIRST(T?)={ *, ? } FOLLOW(T?)={ +, ), } FIRST(F) ={ (, i } FOLLOW(F) ={ *, +, ), } i + * ( ) E E → TE ? E → TE ? sy nch sy nch E ? E ?→ +T E ? E ?→ ? E ?→ ? T T → FT ? sy nch T → FT ? sy nch sy nch T ? T ?→ ? T ?→ * FT ? T ?→ ? T ?→ ? F F → i sy nch sy nch F → (E) sy nch sy nch 同步符號的選擇 ? 把 FOLLOW(A)中的所有符號作為 A的同步符號 ? 跳過輸入串中的一些符號直至遇到這些“同步符號”，把 A從棧中彈出，可使分析繼續(xù) ? 把 FIRST(A)中的符號加到 A的同步符號集 ? 當 FIRST(A)中的符號在輸入中出現(xiàn)時，可根據(jù) A恢復語法分析 ? 若不能匹配棧頂?shù)慕K結(jié)符號，一種簡單的想法是 ? 彈出棧頂?shù)倪@個終結(jié)符號，并發(fā)出一條信息，說明已經(jīng)插入這個終結(jié)符，繼續(xù)進行語法分析 步驟 符號棧 輸入串 所用產(chǎn)生式0 E ) i*+i 錯, 跳過)1 E i*+i i ∈F I R S T ( E )2 E39。T i*+i E →T E 39。3 E39。T39。F i*+i T →F T 39。4 E39。T39。i i*i+i F →i5 E39。T39。 *+i6 E39。T39。F* *+i T 39。 →* F T 39。7 E39。T39。F +i 錯, M [ F , + ] = s y n c h8 E39。T39。 +i F 已彈出棧9 E39。 +i T39?！?ε10 E39。 +i E 39。 →+ T E 39。11 E39。T+ +i12 E39。T i T →F T 39。13 E39。T39。F i F →i14 E39。T39。i i15 E39。T39。 T39?！?ε16 E39。 E39?！?ε17 練習一 ? 文法 G[V]： V→N | N[E] E→V | V+E N→i 是否為 LL(1)文法？若不是，如何改造成 LL(1)文法？ ? 解： ? LL(1)文法的基本條件是不含左遞歸和回溯（公共左因子）， 而 G[V]中含有回溯，所以先消除回溯得到文法 G’[V]： G’[V]： V→NV’ V’→ ε |[E]V’ E→VE’ E’→ ε |+EE’ N→i ? 由 LL(1)文法的充要條件可證 ? G’ [V]是 LL(1)文法 ? 文法 G[s]: S→BA A→BS|d B→aA|bS|c ? 證明文法 G是 LL(1)文法 ? 構(gòu)造 LL(1)分析表 ? 寫出句子 adccd的分析過程 ? 解： ? 一個 LL(1)文法的充要條件是 ?對每一個非終結(jié)符 A的任何兩個不同產(chǎn)生式 A→ α|β，有下面的條件成立 ?FIRST(α)∩FIRST(β)=Φ ? 若 β*?ε , 則有 FIRST(α)∩FOLLOW(A)=Φ 練習二（一） 練習二（二） ? 對于文法 G[s]: S→BA A→BS|d B→aA|bS|c ? FIRST集 ? FIRST(B)={a, b, c}。 FIRST(A)={a, b, c, d}。FIRST(S)={a, b, c}。 ? FOLLOW集 ? FOLLOW(S)={} ? 對 S→BA 有 ? FIRST(A)\{ε }加入 FOLLOW(B)，即 FOLLOW(B)={a, b, c, d } ? 對 A→BS 有 ? FIRST(S)\{ε }加入 FOLLOW(B)，即 FOLLOW(B)={a, b, c, d } ? 對 B→aA 有 ? FOLLOW(B)加入 FOLLOW(A)，即 FOLLOW(A)={a, b, c, d } ? 對 B→bS 有 ? FOLLOW(B)加入 FOLLOW(S)，即 FOLLOW(S)={, a, b, c, d } 練習二（三） ? 由 A→BS|d 得 ? FIRST(BS) ∩FIRST(d) = { a, b, c } ∩nhcuj7d3 = Φ ? 由 B→aA|bS|c 得 ? FIRST(aA)∩FIRST(bS)∩FIRST(c)={a}∩∩{c}= Φ ? 由于文法 G[s]不存在形如 β→ ε 的產(chǎn)生式，故無需求解形如FIRST(α )∩FOLLOW(A) 的值 ? 也即， 文法 G[S]是一個 LL(1)文法 練習二（四） ? 由 G[s]： S→BA A→BS|d B→aA|bS|c 的 FIRST(B)={a, b, c}。 FOLLOW(B)={a, b, c, d }。 FIRST(A)={a, b, c, d}。 FOLLOW(A)={a, b, c, d }。 FIRST(S)={a, b, c}。 FOLLOW(S)={, a, b, c, d } 可構(gòu)造 LL(1)預測分析表如下： a b c d S S→BA S→BA S→BA A A→BS A→BS A→BS A→d B B→aA B→bS B→c ? (3)在分析表的控制下，句子 adccd的分析過程如下： 棧 當前輸入符號 輸入串 說明S a dccd S →B AAB a dccd B →a AAAa a dccdAA d ccd A →dAd d ccdA c cd A →B SSB c cd B →cSc c cdS c d S →B AAB c d B →cAc c dA d A →dd d 分析成功a b c d S S→BA S→BA S→BA A A→BS A→BS A→BS A→d B B→aA B→bS B→c