為以下文法構建一個預測分析表，並檢查字串 id + id * id 是否被接受。

---

問題 - 考慮以下文法 -

E → TE′

E′ → +TE′|ε

T′ → FT′

T′ → FT′|ε

F → (E)|id

解答 -

步驟1 - 消除左遞歸併執行左因子化

由於文法中不存在左遞迴，因此我們將按原樣進行。同樣，也不需要進行左因子化。

步驟2 - 計算 FIRST 集

FIRST(E) = FIRST(T) = FIRST(F) = {(, id}

FIRST (E′) = {+, ε}

FIRST (T′) = {*, ε}

步驟3 - 計算 FOLLOW 集

FOLLOW (E) = FOLLOW(E′) = {), $}

FOLLOW (T) = FOLLOW(T′) = {+, ), $}

FOLLOW (F) = {+,*,),$}

步驟4 - 構建預測分析表

建立表格，即按行寫入所有非終結符，按列寫入所有終結符。

現在，透過應用預測分析表構建規則來填充表格。

• E → TE′

將 E → TE′ 與 A → α 進行比較

E →	TE′
A →	Α

∴ A = E, α = TE′

∴ FIRST(α) = FIRST(TE′) = FIRST(T) = {(, id}

應用預測分析表的規則 (1)

∴ 將 E → TE′ 新增到 M[E, ( ] 和 M[E, id]

∴ 在行 (E) 和列 {(, id} 前面寫入 E → TE′ (1)

• E′ → +TE′|𝛆

將其與 A → α 進行比較

E →	+TE′
A →	α

∴ A = E′ α = +TE′

∴ FIRST(α) = FIRST(+TE′) = {+}

∴ 將 E → +TE′ 新增到 M[E′, +]

∴ 在行 (E′) 和列 (+) 前面寫入產生式 E′ → +TE′ (2)

• E′ → ε

將其與 A → α 進行比較

E →	ε
A →	α

∴ α = ε

∴ FIRST(α) = {ε}

∴ 應用預測分析表的規則 (2)。

查詢 FOLLOW (E′) = { ), $}

∴ 將產生式 E′ → ε 新增到 M[E′, )] 和 M[E′, $]

∴ 在行 (E′) 和列 {$, )} 前面寫入 E′ → ε                                                         (3)

• T → FT′

將其與 A → α 進行比較

T →	FT′
A →	α

∴ A = T, α = FT′

∴ FIRST(α) = FIRST (FT′) = FIRST (F) = {(, id}

∴ 將產生式 T → FT′ 新增到 M[T, (] 和 M[T, id]

∴ 在行 (T) 和列 {(, id} 前面寫入 T → FT′                                                       (4)

• T′ →*FT′

將其與 A → α 進行比較

T →	*FT′
A →	α

∴ FIRST(α) = FIRST (* FT′) = {*}

∴ 將產生式 T → +FT′ 新增到 M[T′,*]

∴ 在行 (T′) 和列 {*} 前面寫入 T′ →∗ FT′ (5)

• T′ → ε

將其與 A → α 進行比較

T′ →	ε
A →	α

∴ A = T′

α = ε

∴ FIRST(α) = FIRST {𝜀} = {ε}

∴ 應用預測分析表的規則 (2)。

查詢 FOLLOW (A) = FOLLOW (T′) = {+, ), $}

∴ 將 T′ → ε 新增到 M[T′, +], M[T′, )] 和 M[T′, $]

∴ 在行 (T′) 和列 {+, ), $} 前面寫入 T′ → ε (6)

• F →(E)

將其與 A → α 進行比較

F →	(E)
A →	A

∴ A = F, α = E

∴ FIRST(α) = FIRST ((E)) = {(}

∴ 將 F → (E) 新增到 M[F, (]

∴ 在行 (F) 和列 (( ) 前面寫入 F → (E) (7)

• F → id

將其與 A → α 進行比較

F →	Id
A →	A

∴ FIRST(α) = FIRST (id) = {id}

∴ 將 F → id 新增到 M[F, id]

∴ 在行 (F) 和列 (id) 前面寫入 F → id (8)

將所有語句 (1) 到 (8) 組合起來將生成以下預測或 LL (1) 分析表 -

	Id	+	*	(	)	$
E	E → TE′			E → TE′
E′		E′ → +TE′			E′ → ε	T′ → ε
T	T → FT′			T → FT′
T′		T′ → ε	T′ →* FT′		T′ → ε	T′ → ε
F	F → id			F → (E)

步驟5 - 使用預測分析程式檢查字串 id + id * id 是否被接受

最初，棧將包含起始符號 E，並在棧底部包含 $。輸入緩衝區將包含一個字串，並在右側附加 $。

如果棧頂 = 當前輸入符號，則棧頂的符號將彈出，並且輸入指標也前進或讀取下一個符號。

預測分析器執行的步驟序列

棧	輸入	動作
$E	id + id * id $	E → TE′
$E′T	id + id * id $	T → FT′
$E′T′F	id + id * id $	F → id
$E′T′id	id + id * id $	移除 id
$E′T′	+id * id $	T′ → ε
$E′	+id * id $	E′ → +TE′
$E′T +	+id * id $	移除 +
$E′T	id * id $	T → FT′
$E′T′F	id * id $	F → id
$E′T′id	id * id $	移除 id
$E′T′	* id $	T′ →* FT′
$E′T′F *	* id $	移除 *
$E′T′F	id $	F → id
$E′T′id	id $	移除 id
$E′T′	$	T′ → ε
$E′	$	E′ → ε
$E	$	接受