如何推导语法产生式中非终结符的追随者？

Question

这是一组语法制作：

S -> SA | T
A -> +S | S | *
T -> (S) | a

当消除左递归时，我得到了这些：

S -> TB
B -> AB | ε
A -> +S | TB | *
T -> (S) | a

然后我尝试按照龙书描述的步骤获取其中非终端的Firsts和Follows。我已经正确获得第一：

first(T) = [(, a]
first(A) = [+, *, (, a]
first(B) = [ε, +, *, (, a]
first(S) = [(, a]

但我不知道如何获得关注。那么任何人都可以具体展示如何做到这一点吗？

Answer 1

要计算 FOLLOW(Non-Terminal)，请应用以下规则，直到无法将任何内容添加到 FOLLOW 集中：- / / 取自龙书

将$放在FOLLOW(Start_Symbol)中，其中$为输入右结束符
如果有产生式A->XBY，那么 FIRST(Y) 中除 ε 之外的所有内容都在 FOLLOW(B) 中。
如果有产生式A->XB，或产生式A->XBY，其中FIRST(Y)包含ε，则FOLLOW(A)中的所有内容都在FOLLOW(B)中。

所以，现在按照规则，我们在这里导出所有非终结符的 FOLLOW() 。

FOLLOW(S) = {),$} 由于S是起始符号，FOLLOW(S)必须包含$.生产编号第4体(S) 解释为什么右括号在 FOLLOW(S).

FOLLOW(B) = {),$} 因为 B 只出现在 S-productions 的主体的末尾（而不是 A-productions，稍后在讨论部分讨论）。

FOLLOW(A) = {+,*,(,a,),$} 因为 A 只出现在物体中，后面跟着 B，因此，除了 ε 之外的所有东西都在 FIRST( B) 必须在 FOLLOW(A) 中。但是，由于 FIRST(B) 包含 ε，而 B 在初始产生式中是从 S 派生的，因此，FOLLOW(S) 中的所有内容也必须在 FOLLOW(A) 中。这解释了符号 $ 和 ).

FOLLOW(T) = {+,*,(,a,),$} 由于 T 出现在物体中仅后跟 B，因此，除了 ε 之外的所有东西都在 FIRST( B) 必须在 FOLLOW(T) 中。但是，由于 FIRST(B) 包含 ε，并且 B 是 S 产生式主体中 T 之后的整个字符串，因此 FOLLOW(S) 中的所有内容也必须在 FOLLOW(T) 中。这解释了符号 $ 和 )。

讨论：-

现在，谈到由于第 3 次生产而引起的某种冲突，A -> +S | TB | *，您可以轻松地用 S 代替 TB，因此你可能会感到困惑。

按照我的说法，您应该将作品保留为：-

S -> TB
B -> AB | ε
A -> +S | S | *  //substitute S for understanding FOLLOW(B) without any confusion
T -> (S) | a

如何推导语法产生式中非终结符的追随者？

How to deduce the Followers of non-terminals in syntax productions?

compiler-construction

syntax

grammar

production

parsing