解析中使用的FIRST和FOLLOW集合是什么？

Question

什么是第一和跟随集？它们用于解析的目的是什么？它们用于自上而下还是自下而上的解析器？

谁能为我解释以下语法规则的第一和后续内容：

E := E+T | T
T := T*V | T
V := <id>

Answer 1

它们通常在LL（自上而下）解析器中使用，以检查正在运行的解析器是否会遇到任何一种以上的方式继续解析的情况。

如果您有替代项A | B并同时具有FIRST(A) = {"a"}和FIRST(B) = {"b", "a"}，那么您将发生FIRST / FIRST冲突，因为当输入中的下一个“ a”出现时，您将不知道要扩展A还是B 。（假设超前为1）。

[另一方面，如果您有一个非终结符，例如AOpt: ("a")?，则可以为空，那么您必须确保FOLLOW(AOpt)不包含“ a”，因为否则您将不知道是否要扩展AOpt，就像这里：S: AOpt "a" S或AOpt都可能消耗“ a”，这给我们带来了第一/后续冲突。

FIRST集也可以出于性能原因在解析过程中使用。如果您具有可为空的非终结符NullableNt，则可以对其进行扩展以查看它是否可以消耗任何东西，或者检查FIRST(NullableNt)是否包含下一个标记，并且如果不简单地忽略它，则可能会更快（回溯与预测性解析）。另一个性能改进将是为词法扫描程序另外提供当前的FIRST集，因此该扫描程序不会尝试所有可能的终端，而只会尝试上下文当前允许的那些终端。这与保留的终端冲突，但并非总是需要这些。

自下而上的解析器具有不同类型的冲突，即减少/减少和移位/减少。他们还使用项目集来检测冲突，而不是FIRST，FOLLOW。

您的语法不适用于LL分析器，因为它包含左递归。但是E，T和V的第一组将是{id}（假设您的T := T*V | T应该是T := T*V | V）。

Answer 2

答案：

E-> E + T | T

左递归

E-> TE'

E'-> + TE'| eipsilon

T-> T * V | T

左递归

T-> VT'

T'-> * VT'| epsilon

无左递归

V->（id）

因此语法是：

E-> TE'

E'-> + TE'| epsilon

T-> VT'

T'-> * VT'| epsilon

V->（id）

FIRST（E）= {（}

FIRST（E'）= {+，epsilon}

FIRST（T）= {（}

FIRST（T'）= {*，epsilon}

FIRST（V）=​​ {（}

起始符号= FOLLOW（E）= {$}

E-> TE'，E'-> TE'| epsilon：FOLLOW（E'）= FOLLOW（E）= {$}

E-> TE'，E'-> + TE'| epsilon：FOLLOW（T）= FIRST（E'）= {+，$}

T-> VT'，T'-> * VT'|ε：FOLLOW（T'）= FOLLOW（T）= {+，$}

T-> VT'，T-> * VT'| epsilon：FOLLOW（V）= FIRST（T）= {*，epsilon}

第一套规则

If X is a terminal then First(X) is just X!
If there is a Production X → ε then add ε to first(X)
If there is a Production X → Y1Y2..Yk then add first(Y1Y2..Yk) to first(X)
First(Y1Y2..Yk) is either
    First(Y1) (if First(Y1) doesn't contain ε)
    OR (if First(Y1) does contain ε) then First (Y1Y2..Yk) is everything in First(Y1) except for ε  as well as everything in First(Y2..Yk)
    If First(Y1) First(Y2)..First(Yk) all contain ε then add ε to First(Y1Y2..Yk) as well.

套子规则

First put $ (the end of input marker) in Follow(S) (S is the start symbol)
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).
If there is a production A → aB, then everything in FOLLOW(A) is in FOLLOW(B)
If there is a production A → aBb, where FIRST(b) contains ε, then everything in FOLLOW(A) is in FOLLOW(B)

Answer 3

维基百科是您的朋友。请参阅discussion of LL parsers和第一套/跟随套。

根本上，它们用作解析器构造的基础，例如，作为解析器生成器的一部分。您也可以使用它们来推理语法的属性，但是大多数人并不需要这样做。