计算语法的第一组和第二组

Question

我必须计算以下语法的第一套和第二套：

A -> B C
B -> A x | x
C -> y C | y

根据我的理解，我得到以下计算：

首先我们删除左递归

A -> B C
B -> x B'
B' -> C x B' | ε
C -> y C | y

跟随（A）= {$}

但是在书中，跟随（A）的答案= {x，$}

为什么？他们没有删除左递归吗？

Answer 1

据我所知，您对这两个语法的FOLLOW（A）的内容是正确的，从表面上看，消除左递归时您没有更改语法的语言。

您为什么感到需要消除左递归？自上而下的解析可能不适用于左递归语法，但是FIRST和FOLLOW仍然定义良好。因此，您<只是为了计算这些集合而消除左递归，我想它们在您的文本中并未这样做。您可能已经意识到这一点，但是为了完整起见，我要补充一点，消除左递归肯定会更改语法分析树和语句形式，并且重要的是，此处的语法的第一套和第二套不更改L（G）。实际上，这就是进行消除的目的。

所以最重要的是：我想他们可能只是没有消除您书中的左递归，即使我不能从这里肯定地说出来。