关于FOLLOW函数的解释-语法

Question

我在理解FOLLOW函数时遇到了一些问题。我不会计算语法中的函数，这很不好。我试着练习来理解这个函数，特别是这个练习，我有这个语法:

S -> E

E -> T '

E' -> + T E' | - T E' |

T -> F T'

T' -> * F T' |

F -> id | (F'

)

F' -> E) | n)

下面是下面函数的计算结果:

新元

， $

$

T +， -，)， $

T' +， -，)， $

F *， +， -，)， $

F' *， +， -，)， $

我真的不明白为什么FOLLOW(T)=FOLLOW(T') = {+， minus，)， $}在我给出的语法中，"+"one_answers"-"这两个结尾符号从来不会出现在"T"或"T"的右边，所以如果有人能给我解释一下，那就太好了

Answer 1

从概念上讲，FOLLOW(X)是可以出现在语法中合法句子中的X之后的一组标记。因此，要计算它，您可以查看X出现在规则(任何规则)右侧的位置，并查看它后面的内容。对于T'，有

T -> F T'
T' -> * F T'

由于T'在两种情况下都是rhs上的最后一项，因此最终得到FOLLOW(T') = FOLLOW(T) ∪FOLLOW(T')，相当于FOLLOW(T') = FOLLOW(T)。

对于T，您有:

E -> T E'
E' -> + T E'

得到FOLLOW(T) = FIRST(E') ∪遵循(E)盆;FOLLOW(E')——包含下列，因为E'展开为ε。取决于你使用的是谁的FIRST和FOLLOW公式，这可能意味着& ε;型号;FIRST(E')(在这种情况下，您从FOLLOW(T)中删除它)或NULLABLE(E') = true，但对FOLLOW(T)的总体效果是相同的-它从FIRST(E')获得+和minus，从FOLLOW(E)获得)和$