首先,遵循两个语法中的非终端

Question

给出以下语法

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

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

如果语法改为

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

什么是第一个并遵循？

Answer 1

当我在大学学习编译课程时,我根本不了解FIRST和FOLLOWS.我实现了龙书中描述的算法,但我不知道发生了什么.我想我现在这样做.

我假设你有一本书给出了这两套的正式定义,这本书完全不可理解.我将尝试对它们进行非正式的描述,希望这将有助于您理解书中的内容.

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)中唯一的东西是$输入结束符号.

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

看看这个简单的解释,现在忽略所有的东西?,因为你没有任何包含空字符串的产品.在"First Sets规则"下,规则#1,#3和#4.1应该是有意义的.在"遵循规则集"下,规则#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(或多或少)来实现.

我希望这有帮助,你可以自己找出第二个语法的第一和第二.

如果有帮助,则R表示Rvalue - 您无法分配的"事物",例如常量或文字.左值也可以作为右值(但不是相反).

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.