首先计算并遵循此语法的集合

Question

我正在为编译器做考试题。问题是找到以下语法的第一个和后面的集合：

S → uBDz
B → Bv | w
D → EF
E → y | e
F → x | e

这是我计算第一组时得到的：

First
S  u,v,w,y,x,z,e
B  v,w
D  y,x,e
E  y,e
F  x,e

我的讲师已经给出了解决方案，但我似乎无法理解他从哪里得到答案：

   First     Follow
S  u         $
B  w         y,x,z,y
D  y,x,e     z
E  y,e       x,z
F  x,e       z

PS。 e = epsilon

Answer 1

如果非终结符的扩展可以从该符号开始，则该符号位于非终结符的第一个集合中。这是 FIRST 集的定义，如果您的算法没有产生该结果，则该算法是错误的。

例如，在您的示例语法中 S 的唯一产生式是：

S → uBDz

这意味着 S 的每个扩展都必须以 u 开头。没有办法回避这个事实。跳过 u 并使用其他字符串继续生成是不可能的。所以很容易看出 FIRST(S) 恰好是 {u}.

同样，B有两个作品

B → Bv
B → w

这意味着B可以产生：

w
Bv → wv
Bv → Bvv → wvv
Bv → Bvvv → wvvv

等等。扩展可以包含任意数量的 v，但第一个符号始终是 w。所以 FIRST(B) 恰好是 {w}.

Calculating first and follow sets of this grammar