context-free-grammar - 如何生成此上下文无关文法的第一组

Question

我一直在尝试找到这种上下文无关语法的“第一组”。我想出了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) 的特定方法——即查看产品并查看产生了什么——是一种很好的方法。