1

好的，我已经了解了如何计算 Follow_k(N) 集（N 是非终结符）：对于 A -> aBc 形式的每个生产规则，您将 First_k(First_k(c)Follow_k(A)) 添加到 Follow_k(B ) (a, c 是任意一组终结符和非终结符，甚至是 lambda)。...然后您重复此操作，直到没有可添加的内容为止。

但是产生式规则会发生什么，例如：S -> ABCD（A、B、C、D 都是非终结符）？

我应该
将 First_k(First_k(BCD)Follow_k(S)) 添加到 Follow_k(A) 还是
将 First_k(First_k(CD)Follow_k(S)) 添加到 Follow_k(B) 或
添加 First_k(First_k(D)Follow_k(S))到 Follow_k(C) 或
将 First_k(First_k(lambda)Follow_k(S)) 添加到 Follow_k(D) 或
执行以上所有操作？

更新：
让我们以下面的语法为例：

S -> ABC
A -> a
B -> b
C -> c

直观地说，Follow_1(S) = {} 因为在 S 之后没有任何内容
Follow_1(A) = {b} 因为 b 在 A 之后，
Follow_1(B) = {c} 因为 c 在 B 之后，
Follow_1(C) = {} 因为在 C 之后没有任何内容。
为了使用该算法获得此结果，您必须考虑 S -> ABC 的所有情况。

但我的判断或例子可能不正确，所以问题仍然悬而未决......

4

1 回答 1

2

If you run into trouble on other grammar problems like this, give this online first, follow, & predict set finder a shot. It's automatic and you can compare answers to its output to get a feel for how to work through these.

But what happens for production rules like: S -> ABCD (A, B, C, D are all nonterminals)?

Here are the rules for finding follow sets.

  1. First put $ (the end of input marker) in Follow(S) (S is the start symbol)
  2. If there is a production A → aBb, (where a can be a whole string) then everything in FIRST(b) except for ε is placed in FOLLOW(B).
  3. If there is a production A → aB, then everything in FOLLOW(A) is in FOLLOW(B)
  4. If there is production A → aBb, where FIRST(b) contains ε, then everything in FOLLOW(A) is in FOLLOW(B)

Let's use your example grammar:

  • S -> ABC
  • A -> a
  • B -> b

  • C -> c

    1. Rule 1 says that follow(S) contains $.
    2. Rule 2 gives us: follow(A) contains first(B); also, follow(B) contains first(C).
    3. Rule 3 says that follow(C) contains follow (S).
    4. None of your productions are nullable, so we don't care about rule #4. A symbol is nullable if it derives ε or if it derives a nullable non-terminal symbol.

Nullability's transitivity can trip people up. Consider this grammar:

  • S -> A
  • A -> B
  • B -> ε

Since B derives ε, B's nullable. Since A derives B, which derives ε, A's nullable too. S derives A, which derives B, which derives ε, so S is nullable as well.

Granted, you didn't bring that up, but it's a common source of confusion in compiler courses, so I figured I'd lay it out.

Also, if you need some sample grammars to work through, http://faculty.stedwards.edu/laurab/cosc4342/g1answers.txt might be handy.

于 2012-05-09T23:51:24.357 回答