为以下文法构建一个预测分析表，并检查字符串 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	$	接受