5

什么是 FIRST 和 FOLLOW 集？它们在解析中用于什么？它们是用于自上而下还是自下而上的解析器？

谁能向我解释以下一组语法规则的 FIRST 和 FOLLOW SETS：

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

3 回答 3

3

它们通常在 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/FOLLOW 冲突。

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

自底向上解析器有不同类型的冲突，即 Reduce/Reduce 和 Shift/Reduce。他们还使用项目集来检测冲突，而不是 FIRST，FOLLOW。

您的语法不适用于 LL 解析器，因为它包含左递归。但是 E、T 和 V 的第一个集合是 {id} （假设你T := T*V | T的意思是T := T*V | V）。

于 2013-05-01T10:16:04.663 回答
1

回答 ：

E->E+T|T

左递归

E->TE'

E'->+TE'|epsilon

T->T*V|T

左递归

T->VT'

T'->*VT'|ε

没有左递归

V->(id)

因此语法是：

E->TE'

E'->+TE'|ε

T->VT'

T'->*VT'|ε

V-> (id)

第一（E）={（}

FIRST(E')={+,epsilon}

第一（T）={（}

FIRST(T')={*,epsilon}

第一（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'|epsilon: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)
于 2013-12-29T13:03:34.427 回答
0

维基百科是你的朋友。请参阅LL 解析器和 first/follow 集的讨论。

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

于 2010-09-30T10:43:27.417 回答