【正文】 ? T ? NFA for Viable Prefixes in Detail (1) S’ ? . E NFA for Viable Prefixes in Detail (2) S’ ? . E S’ ? E. E E? . T ? E ? . T+E ? NFA for Viable Prefixes in Detail (3) S’ ? E. E ? . T+E S’ ? . E E? . T T ? .int * T ? ? E T ? . (E) ? T? .int ? ? E? T. T NFA for Viable Prefixes in Detail (4) T ? . (E) S’ ? E. E ? . T+E S’ ? . E E? . T E? T. T? .int T ? .int * T ? ? E E ? T.+E T ? ? ? ? ? ? T NFA for Viable Prefixes in Detail (5) T ? . (E) T ? (.E) ( S’ ? E. E ? . T+E S’ ? . E E? . T E? T. T? .int T ? .int * T ? ? E ? ? ? ? ? ? T E ? T.+E T NFA for Viable Prefixes in Detail (6) T ? . (E) T ? (.E) ( S’ ? E. E ? . T+E S’ ? . E E? . T E? T. T? .int T ? .int * T ? ? ? ? E ? ? ? ? ? ? T E ? T.+E T T ? (E.) E NFA for Viable Prefixes in Detail (7) T ? . (E) T ? (.E) ( S’ ? E. E ? . T+E S’ ? . E E? . T E? T. T? .int T ? .int * T ? ? ? ? E ? ? ? ? ? ? T E ? T.+E T T ? (E.) E T ? (E). ) NFA for Viable Prefixes in Detail (8) T ? . (E) T ? (.E) ( S’ ? E. E ? . T+E S’ ? . E E? . T E? T. T? .int T ? .int * T ? ? ? ? E ? ? ? ? ? ? T E ? T.+E T T ? (E.) E T ? (E). ) E ? T+.E + NFA for Viable Prefixes in Detail (9) T ? . (E) T ? (.E) ( S’ ? E. E ? . T+E S’ ? . E E? . T E? T. T? .int T ? .int * T ? ? ? ? E ? ? ? ? ? ? T E ? T.+E T T ? (E.) E T ? (E). ) E ? T+.E + ? ? E ? T+E. E NFA for Viable Prefixes in Detail (10) T ? . (E) T ? (.E) ( S’ ? E. E ? . T+E S’ ? . E E? . T E? T. T? .int T ? .int * T ? ? ? ? E ? ? ? ? ? ? T E ? T.+E T T ? (E.) E T ? (E). ) E ? T+.E + ? ? E ? T+E. E T? int. int NFA for Viable Prefixes in Detail (11) T ? . (E) T ? (.E) ( S’ ? E. E ? . T+E S’ ? . E E? . T E? T. T? .int T ? .int * T ? ? ? ? E ? ? ? ? ? ? T E ? T.+E T T ? (E.) E T ? (E). ) E ? T+.E + ? ? E ? T+E. E T? int. int T ? int.* T int NFA for Viable Prefixes in Detail (12) T ? . (E) T ? (.E) ( S’ ? E. E ? . T+E S’ ? . E E? . T E? T. T? .int T ? .int * T ? ? ? ? E ? ? ? ? ? ? T E ? T.+E T T ? (E.) E T ? (E). ) E ? T+.E + ? ? E ? T+E. E T? int. int T ? int.* T int T ? int *.T * NFA for Viable Prefixes in Detail (13) T ? . (E) T ? (.E) ( S’ ? E. E ? . T+E S’ ? . E E? . T E? T. T? .int T ? .int * T ? ? ? ? E ? ? ? ? ? ? T E ? T.+E T T ? (E.) E T ? (E). ) E ? T+.E + ? ? E ? T+E. E T? int. int T ? int.* T int T ? int *.T * T ? int * T. T ? ? ? 根據(jù)圓點(diǎn)所在的位置和圓點(diǎn)后是終結(jié)符還是非終結(jié)符把項(xiàng)目分為以下幾種： 移進(jìn)項(xiàng)目，形如 A → ? ? a? 待約項(xiàng)目，形如 A → ? ? B? 歸約項(xiàng)目，形如 A → ? ? 接受項(xiàng)目，形如 S’ → S ? Translation to the DFA S’ ? . E E ? . T E ? .T + E T ? .(E) T ? .int * T T ? .int S’ ? E . E ? T. E ? T. + E T ? int. * T T ? int. T ? (. E) E ? .T E ? .T + E T ? .(E) T ? .int * T T ? .int E ? T + E. E ? T + . E E ? .T E ? .T + E T ? .(E) T ? .int * T T ? .int T ? int * .T T ? .(E) T ? .int * T T ? .int T ? int * T. T ? (E.) T ? (E). E T ( int int * ) E E T int ( ( int T + ( T 項(xiàng)目集 構(gòu)成識(shí)別一個(gè)文法活前綴的 DFA項(xiàng)目集（狀態(tài)）的全體稱為這個(gè)文法的 LR(0)項(xiàng)目集規(guī)范族 NFA確定化為 DFA的工作量較大，我們考慮直接構(gòu)造出項(xiàng)目集作為 DFA的狀態(tài)，就可直接構(gòu)造 DFA 通過 閉包函數(shù) (CLOSURE)來求 DFA一個(gè)狀態(tài)的項(xiàng)目集 如果 I是文法 G’的一個(gè)項(xiàng)目集，定義和構(gòu)造 I的閉包CLOSURE(I)如下： a)I的項(xiàng)目都在 CLOSURE(I)中 b)若 A→ ? ? B?屬于 CLOSURE(I)，則每一形如 B→ ? ?的項(xiàng)目也屬于 CLOSURE(I) c)重復(fù) b)直到 CLOSURE(I)不再擴(kuò)大 定義轉(zhuǎn)換函數(shù)如下： GOTO（ I， X） = CLOSURE（ J） 其中： I為包含某一項(xiàng)目集的狀態(tài)， X為一文法符號(hào) J={任何形如 A→ ?X ? ?的項(xiàng)目 | A→ ? ? X ?屬于 I} 圓點(diǎn)不在產(chǎn)生式右部 最左邊 的項(xiàng)目稱為 核 ，唯一的例外是 S’ → ? S。 步驟 符號(hào)棧 輸入符號(hào)串 動(dòng)作 1） abbcde 移進(jìn) 0 S2 2） a bbcde 移進(jìn) 02 S4 4） aA bcde 移進(jìn) 023 S6 6） aA cde 移進(jìn) 023 S5 7） aAc de 移進(jìn) 0235 S8 9） aAcB e 移進(jìn) 02357 S9 11） S 接受 01 acc 對(duì)輸入串 abbcde的 LR分析過程 3） ab bcde 歸約 (A→ b) 024 r2 3 5） aAb cde 歸約 (A→ Ab) 0236 r3 3 8） aAcd e 歸約 (B→ d) 02358 r4 7 10） aAcBe 歸約 (S→ aAcBe) 023579 r1 1 狀態(tài)棧 ACTION GOTO 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 ? * 步驟 符號(hào)棧 輸入符號(hào)串 動(dòng)作 1） abbcde 移進(jìn) 0 S2 對(duì)輸入串 abbcde的 LR分析過程 狀態(tài)棧 ACTION GOTO 0 1 4 2 3 5 7 6 9 S a b A b c B e d 8 ? * 步驟 符號(hào)棧 輸入符號(hào)串 動(dòng)作 1） abbcde 移進(jìn) 0 S2 2） a bbcde 移進(jìn) 02 S4 對(duì)輸入串 abbcde的 LR分析過程 狀態(tài)棧 ACTION GOTO 0 1 4 2 3 5 7 6 9 S a b A b c