grammar - 两个文法中非终结符的 first 和 follow

Question

给出以下语法

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

非终结符的 first 和 follow 是什么？

如果语法改成

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

第一个和后续是什么？

Answer 1

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

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

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

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

将 FIRST(S) 视为可能开始一个语句的一组非终结符。直觉上，您知道您不会以 = 开头.所以你不会期望它出现在 FIRST(S) 中。

那么语句是如何开始的呢？有两个产生式规则定义了 S看起来像，它们都以 L 开头.因此，要弄清楚 FIRST(S) 中的内容，您真的必须查看 FIRST(L) 中的内容。有两个产生式规则定义了左值的样子:它要么以 * 开头。或使用 id .所以 FIRST(S) = FIRST(L) = { * , id }.

关注(S)很容易。没有后续 S因为它是开始符号。所以 FOLLOWS(S) 中唯一的就是 $ , 输入结束符号。

FOLLOWS(L) 有点棘手。您必须查看 L 处的每个产生式规则。出现，看看它后面会发生什么。在第一条规则中，您会看到 =可以关注 L .所以=在跟随(L)。但是您也注意到在该规则中还有另一个 L在生产规则的末尾。所以另一件事可以遵循L是任何可以跟随生产的东西。我们已经发现唯一可以跟随 S 的东西。生产是投入的终点。所以跟随(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)。所以关注(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.