从语法生成第一集
从语法生成第一集
提问于 2016-06-17 16:27:17
寻找第一集的算法 ：
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 网站 生成第一组如下所示：
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}。
First(B) - ε U First(C) U {g} Q:首先(A)对上述语法是=
此视频也遵循上述算法，不选择ε。
回答 1
Stack Overflow用户
回答已采纳
发布于 2016-06-17 16:43:30
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)等于First(εa) = {a}
首先在我的github上设置实现。
编辑：更新链接
https://github.com/amirbawab/EasyCC-CPP/blob/master/src/syntax/grammar/Grammar.cpp#L229
在上面的新链接中，计算第一组和后续集都是可用的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/37886271
复制相关文章
相似问题
腾讯云开发者
