给定文法:A::=BCc|gDB B::=ε|bCDE C::=DaB|ca D::=ε|dD E::=gAf|c,求FIRST集和FOLLOW集
时间: 2024-06-18 09:04:18 浏览: 164
首先,我们需要先了解一下什么是FIRST集和FOLLOW集。
- FIRST集:对于文法中的非终结符号A,它的FIRST集合FIRST(A)表示A所能推导出的所有字符串的首符号集合。
- FOLLOW集:对于文法中的非终结符号A,它的FOLLOW集合FOLLOW(A)表示所有可以在文法中紧随在A后面的终结符的集合。
现在,我们来求解这个文法的FIRST集和FOLLOW集。
- FIRST集
首先,我们可以看到文法中出现了一些 ε,这意味着这些非终结符号可以推出空串。然后,我们逐一求解每个非终结符号的FIRST集。
- FIRST(A) = {g, c, d}
- FIRST(B) = {ε, b}
- FIRST(C) = {c, d, g, a}
- FIRST(D) = {ε, d}
- FIRST(E) = {g, c}
需要注意的是,在求解FIRST(A)时,我们需要将A所能推导出的所有候选式的首符号都加入到FIRST(A)中。例如,在A::=BCc|gDB这个产生式中,B和D都可以产生 ε,因此我们需要将c和g都加入到FIRST(A)中。
- FOLLOW集
接下来,我们来求解每个非终结符号的FOLLOW集。需要注意的是,在这个文法中,我们需要考虑到起始符号S和终止符号$。
- FOLLOW(A) = {$}
- FOLLOW(B) = {c, g}
- FOLLOW(C) = {c, g}
- FOLLOW(D) = {c, g}
- FOLLOW(E) = {c, g}
需要注意的是,在求解FOLLOW(B),FOLLOW(C),FOLLOW(D),FOLLOW(E)时,我们需要考虑到它们出现在A、C、B等其他产生式右侧时所能推导出的符号。例如,在B::=ε|bCDE这个产生式中,如果B后面还有符号,则这些符号一定是C、D、E等非终结符号,因此我们需要将C、D、E所能推导出的所有字符串的首符号都加入到FOLLOW(B)中。同样地,在A::=BCc|gDB这个产生式中,我们需要将C、B、D所能推导出的所有字符串的首符号都加入到FOLLOW(A)中。
阅读全文