7

给定以下语法 

S -> L=L  
s -> L  
L -> *L  
L -> id

非终端的第一个和后续是什么？

如果语法改成

S -> L=R  
S -> R  
L -> *R  
L -> id  
R -> L

什么将是第一个和后续？

4

1 回答 1

23

当我在大学上编译器课程时，我根本不了解 FIRST 和 FOLLOWS。我实现了 Dragon 书中描述的算法，但我不知道发生了什么。我想我现在知道了。

我假设你有一本书给出了这两个集合的正式定义，而这本书是完全无法理解的。我将尝试对它们进行非正式的描述，希望这能帮助您理解书中的内容。

FIRST 集是您可能将其视为非终端扩展的第一部分的终端集。FOLLOWS 集是您在非终端扩展后可能看到的终端集。

在您的第一个语法中，只有三种终结符：=、*和id. （您也可以将$输入结束符号 视为终结符。）唯一的非终结符是S（语句）和L（左值 - 您可以分配给的“事物”）。

将 FIRST(S) 视为可能启动语句的非终结符集。直观地说，您知道您不会以 . 开头的语句=。所以你不会期望它会出现在 FIRST(S) 中。

那么声明是如何开始的呢？有两条生产规则定义了 an 的S样子，它们都以L. 因此，要弄清楚 FIRST(S) 中的内容，您必须查看 FIRST(L) 中的内容。有两个产生式规则定义了左值的样子：它要么以 a 开头，要么*以id. 所以 FIRST(S) = FIRST(L) = { *, id}。

FOLLOWS(S) 很容易。后面什么都没有S，因为它是开始符号。所以 FOLLOWS(S) 中唯一的东西是$，输入结束符号。

FOLLOWS(L) 有点棘手。您必须查看L出现的每个生产规则，并查看其后的内容。在第一条规则中，您会看到=可能会遵循L. FOLLOWS(L) 也是如此=。L但是您还注意到，在该规则中，产生式规则的末尾还有另一个。因此，可以遵循的另一件事是L可以遵循该生产的任何事物。我们已经发现，唯一可以跟随S生产的是输入结束。所以 FOLLOWS(L) = { =, $}。（如果你查看其他产生式规则，L总是出现在它们的末尾，所以你只是从中得到$。）

看看这个Easy Explanation，现在忽略所有关于 的东西ϵ，因为你没有任何包含空字符串的产品。在“第一组规则”下，规则#1、#3 和#4.1 应该是有意义的。在“Follows Sets 规则”下，规则 #1、#2 和 #3 应该是有意义的。

ϵ当您有生产规则时，事情会变得更加复杂。假设你有这样的东西：

D -> S C T id = V  // Declaration is [Static] [Const] Type id = Value
S -> static | ϵ    // The 'static' keyword is optional
C -> const | ϵ     // The 'const' keyword is optional
T -> int | float   // The Type is mandatory and is either 'int' or 'float'
V -> ...           // The Value gets complicated, not important here.

现在，如果你想计算 FIRST(D)，你不能只看 FIRST(S)，因为 S 可能是“空的”。您直观地知道 FIRST(D) 是 { static, const, int, float}。这种直觉被编入规则#4.2。将此SCT示例视为Y1Y2Y3“简单说明”规则。

如果要计算 FOLLOWS(S)，不能只看 FIRST(C)，因为那可能是空的，所以还得看 FIRST(T)。所以 FOLLOWS(S) = { const, int, float}。您可以通过应用“跟随集的规则”#2 和 #4（或多或少）来实现这一点。

我希望这会有所帮助，并且您可以自己弄清楚第二个语法的 FIRST 和 FOLLOWS。

如果有帮助，则R表示一个右值——一个你不能分配给它的“事物”，例如一个常量或一个文字。左值也可以充当右值（但不能反过来）。

a = 2;  // a is an lvalue, 2 is an rvalue
a = b;  // a is an lvalue, b is an lvalue, but in this context it's an rvalue
2 = a;  // invalid because 2 cannot be an lvalue
2 = 3;  // invalid, same reason.
*4 = b; // Valid!  You would almost never write code like this, but it is
        // grammatically correct: dereferencing an Rvalue gives you an Lvalue.
于 2010-02-18T07:52:53.387 回答