計算的FOLLOW集

Question

我的任務是計算FIRST和FOLLOW集以下語法：

P ::= S CS . 
S ::= (int , int) 
CS ::= C CS | epsilon 
C ::= left int | right int | low C 

我得到了以下第一組：

FIRST(S) = {'('} 
FIRST(C) = {left,right,low} 
FIRST(CS) = {left,right,low,epsilon} 
FIRST(P) = FIRST(S) = {'('} 

對於以下組I計算：

FOLLOW(P) = $ (or empty) 
FOLLOW(C) = {left,right,low,'.'} 
FOLLOW(CS) = {'.'} 
FOLLOW(S) = {left,right,low} 

我試着用我的解決方案，使用第一套和跟隨套發電機，我跟隨（S）得到的是：FOLLOW(S) = {'.', left, right, low}。發電機解決方案是否正確，爲什麼？我使用公式計算了我的解答：FOLLOW(S) = FIRST({left,right,low} concat FOLLOW(P)) = {left, right, low}。有人可以解釋我爲什麼我的/發電機的解決方案不正確，並檢查我是否有一切正確的？我也想知道爲什麼我沒有在第一個或隨後的集合中使用int，並且如果這對於稍後構建解析器來說可以。謝謝

Answer 1

當你計算FOLLOW集合時，你必須小心空製作。

在這種情況下，CS有一個空的生產，這意味着S可能隨後在P → S CS .一個.。同樣，在C CS的C可能是在生產結束，所以C也跟着一個.

int可以在left或right令牌之後纔會出現。它不會出現在名義終端的開始處，也不會立即出現在非終端之後。所以完全可以預料它不會出現在任何FIRST或FOLLOW集合中。