генерирующая Первый сет из грамматики

Question

Algorithm для нахождения первого набора:

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), поэтому первый (А) в соответствии с этим алгоритмом не должен содержать ε. First(A) = {g, b, a, c, d}.

В: Первый (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, ε} 

Во-первых (Х) не имеет, потому что е, если заменить Y через е, то первый (Y а) равно First (ε а) = {а }

Первый набор реализации на моем github.

Редактировать: Обновлена ​​ссылка
https://github.com/amirbawab/EasyCC-CPP/blob/master/src/syntax/grammar/Grammar.cpp#L229
Вычисление первого и последующих наборов являются доступными по новой ссылке выше.