parsing - 手动计算 FIRST 组

Question

我有一个小问题一直困扰着我很长一段时间，我一直无法在网上找到合适的答案。

给定一个语法:
S = Sc | Eab | Db | bD = EDcD | ca | ɛE = dE | DYY = Ed | Dad | ɛ
要找到第一组说 Y，所以 FIRST(Y)，我是否正确假设它是这样的:
FIRST(Y)= FIRST(Ed) ∪ FIRST(Dad) ∪ FIRST(ɛ)= FIRST(E) ∪ (FIRST(D)\{ɛ}) ∪ FIRST(ad) ∪ {ɛ}= FIRST(E) ∪ (FIRST(D)\{ɛ}) ∪ {a, ɛ}
现在的问题是如何找到 FIRST(E) 和 FIRST(D)？

Answer 1

因此，FIRST(E) 和 FIRST(D) 的问题在于 E 和 D 相互引用。当您想要一种“最小固定点”时，解决方案是通常的解决方案——从所有内容开始，并不断迭代直到它们稳定。

即:首先，将所有 FIRST 集初始化为空集。现在，反复考虑每个产品，并假设您当前对非终端的 FIRST 集的估计是真实的。 (实际上，它们通常会“低估”。)计算出产品告诉您的有关其 LHS 的 FIRST 集的内容，并相应地更新您对该非终端的 FIRST 集的估计。继续这样做，依次处理所有产品，直到您完成所有产品并且您的估计没有改变。到那时，你就完成了。

在这种情况下，事情是这样的(当然，假设我没有犯错)。第一遍依次产生 S: {b}, D: {c,ɛ}, E: {c,d}, Y: {c,d,ɛ}。第二个依次产生 S: {b,c,d}, D: {c,d,ɛ}, E: {c,d,ɛ}, Y: {c,d,ɛ}。第三个不会改变任何一个，所以这些是最终的答案。