手動計算FIRST集

我遇到了一個小問題，這個問題現在已經困擾我很長一段時間了，我一直沒能在網上找到合適的答案。手動計算FIRST集

給定一個語法：

S = Sc | Eab | Db | b
D = EDcD | ca | ɛ
E = dE | DY
Y = 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）？

來源

2012-07-19 Andrej Žukov-Gregorič

因此，FIRST（E）和FIRST（D）的問題在於E和D互相引用。當你需要某種「最不固定點」時，解決方案就是通常的解決方案 - 從一切開始，一直保持迭代直到穩定。

即：首先，將所有FIRST集初始化爲空集。現在，反覆地考慮每個生產並假裝您目前對非終端的FIRST套裝的估計是事實。（實際上，它們通常會被「低估」）。制定出產品告訴你的關於第一組LHS的信息，並相應地更新對非終端的FIRST集的估算。繼續這樣做，依次處理所有的作品，直到你完成了所有的作品，並且你的估計沒有改變。那時，你已經完成了。

在這種情況下，它是如何發展的（當然假設我沒有愚蠢）。第一遍依次產生S：{b}，D：{c，ɛ}，E：{c，d}，Y：{c，d，ɛ}。第二個依次產生S：{b，c，d}，D：{c，d，ɛ}，E：{c，d，}，Y：{c，d，ɛ}。第三個並沒有改變任何這些，所以這些是最終的答案。

來源

2012-07-19 01:37:14

這種計算FIRST的方法是否總會給我們每個非終結符的正確FIRST集？或者我們應該只在這樣的情況下使用這種方法，當兩個非終端互相引用時？ – Zohaib 2012-10-28 04:42:13

如果沒有兩個非終結者互相引用（直接或間接），那麼相同的過程起作用，並且它更加明顯：它工作:-)。想象一下，從每個符號（終端或不是）繪製箭頭到依賴於它的每個其他事物。如果你沒有依賴的「循環」，那麼會發生什麼是正確的FIRST集合沿着箭頭傳播出去，並且在一段有限的時間之後，你已經遵循了每個箭頭，並且一切都停止了變化，並且你完成了。 – 2012-10-29 14:44:24

手動計算FIRST集

回答

相關問題