如何生成第一个上下文无关文法集

Question

我一直在寻找这个上下文无关文法的"first set"。我想出了 2 个答案，但我不确定它们是否正确。如果有人可以解释如何生成此语法的第一组，我将不胜感激。

两个答案都以不同的方式写成，因为我读过的资料是用不同的语法解释的。

有问题的语法：

E1 -> E2+E1|E2
E2 -> num*E2|num

我的第一个回答：

|   A -> α     |   FIRST(α)  | 
|:-----------  |------------:|
| E1 -> E2+E1  |  {num, num} |
| E1 -> E2     |  {num, num} |
| E2 -> num*E2 |    {num}    |
| E2 -> num    |    {num}    |

我的第二个回答：

FIRST(E1) = {num}
FIRST(E2) = {num}

Answer 1

FIRST集合最常用的定义是FIRST(S)是可以出现在从S开始的某个推导开始的终结符集合，如果也可以推导空字符串则加上ε .

这里，注意FIRST(S1) = FIRST(S2) 因为从S1 开始的任何推导都必然以从S2 推导的东西开始，而S2 不能推导空字符串。然后，FIRST(S2) = {num} 因为 S2 的每个产生式都以 {num} 开头。

所以是的，FIRST(S1) = FIRST(S2) = {num}。

您计算 FIRST(S1) 和 FIRST(S2) 的特定方法 - 即查看产生式并查看产生了什么 - 是一个很好的方法。