文法

Question

Algorithmから発生する第1セット：

Given a grammar with the rules A1 → w1, ..., An → wn, we can compute the Fi(wi) and Fi(Ai) for every rule as follows: 

    initialize every Fi(Ai) with the empty set 
    set Fi(wi) to Fi(wi) for every rule Ai → wi, where Fi is defined as follows: 
     Fi(a w') = { a } for every terminal a 
     Fi(A w') = Fi(A) for every nonterminal A with ε not in Fi(A) 
     Fi(A w') = Fi(A) \ { ε } ∪ Fi(w') for every nonterminal A with ε in Fi(A) 
     Fi(ε) = { ε } 
    add Fi(wi) to Fi(Ai) for every rule Ai → wi 
    do steps 2 and 3 until all Fi sets stay the same. 

文法：

A -> B C c 
A -> g D B 
B -> EPSILON | b C D E 
C -> D a B | c a 
D -> EPSILON | d D 
E -> g A f | c 

次のようにこのwebsiteは、最初のセットを生成します。

Non-Terminal Symbol  First Set 

A      g, ε, b, a, c, d 
B      ε, b 
C      a, c, ε, d 
D      ε, d 
E      g, c 

しかしアルゴリズムはFi(A w') = Fi(A) for every nonterminal A with ε not in Fi(A)と言っているので、このアルゴリズムによる最初の（A）はεを含んではいけません。 First(A) = {g, b, a, c, d}。

Q：上記の文法の最初の（A）は、= First(B) - ε U First(C) U {g}ですか？

このvideoも上記のアルゴリズムに従い、εを選択しません。

Answer 1

First(B) = {ε, b} 
First(D) = {ε, d} 
First(E) = {g, c} 
First(C) = {c, d, a} 
First(A) = {b, g, c, d, a} 

例：

X -> Y a | b 
Y -> c | ε 

First(X) = {c, a, b} 
First(Y) = {c, ε} 

まず（X）は、εによってYを交換する場合は、最初の（Y A）が最初に等しいのでεを有していない（εA）= {A }

私のgithubで最初に設定された実装。

編集：更新リンク
https://github.com/amirbawab/EasyCC-CPP/blob/master/src/syntax/grammar/Grammar.cpp#L229
最初の計算とフォローセットが両方の上に新しいリンク上で利用可能です。