我正在尝试简化一个规则，该规则将递归保留为：形式
A → Aα | β
----------
A → βA'
A' → αA' | ε
我的规则是：
selectStmt: selectStmt (setOp selectStmt) | simpleSelectStmt
根据我对公式的理解，以下是我的变量：
A = selectStmt
α = setOp selectStmt
β = simpleSelectStmt
A'= selectStmt' // for readability
然后，从规则的应用中我们得到：
1. A → βA'
selectStmt → simpleSelectStmt selectStmt'
2. A' → αA' | ε
selectStmt' -> setOp selectStmt selectStmt' | ε
但是，我该如何进一步简化它以获得最终产品呢？在我之前的一个问题中的一条评论中，删除了定义SELECT语句的这种左递归方式，它说：
在我们的直接应用程序中，它将把我们从最初的
selectStmt: selectStmt (setOp selectStmt) | simpleSelectStmt
带到selectStmt: simpleSelectStmt selectStmt'
和selectStmt': (setOp selectStmt) | empty
，这简化为selectStmt: simpleSelectStmt (setOp selectStmt)?
我不明白这种简化是如何工作的。具体而言：
selectStmt' -> setOp selectStmt selectStmt' | ε如何简化为selectStmt': (setOp selectStmt) | empty？这里的ε是如何移除的？我假设(setOp selectStmt) | empty简化为(setOp selectStmt)?，因为如果它可以是空的，那么它只意味着可选的?。
您的起点：
# I removed the parentheses from the following
selectStmt: selectStmt setOp selectStmt | simpleSelectStmt
不明确。左递归消除不能解决歧义；相反，它保留了模糊性。因此，首先解决歧义并不是一个坏主意。
现实世界中的解析器生成器可以通过使用运算符优先级规则来解决这种歧义。一些解析器生成器要求您写出优先级规则，但Antlr更喜欢使用一组默认的优先级规则(使用语法中乘积的顺序，并假设每个运算符都是关联的，除非另有声明)。(我提到Antlr是因为您似乎将其用作参考实现，尽管它的生产语义有点古怪；隐式优先级规则只是其中一个怪癖。)
将运算符优先级转换为精确的BNF是一项不平凡的工作。解析器生成器倾向于通过在语法编译时(yacc/bison)或使用运行时谓词(Antlr4和大多数基于调车场算法的生成器)消除某些生成来实现运算符优先级。然而，由于运算符优先级不影响上下文无关属性，我们知道是一种上下文无关语法，其中歧义已经得到解决。在某些情况下，比如这个，它很容易找到。
这本质上与算术表达式中的歧义相同；如果没有某种优先级解析，1+2+3+4在语法上是模糊的，有五个不同的解析树。((1+(2+(3+4)))、(1+((2+3)+4))、((1+2)+(3+4))、((1+(2+3))+4)、(((1+2)+3)+4))。碰巧的是，它们在语义上是相同的，因为加法是关联的(在数学意义上)。但对于其他运算符，如-或/，不同的解析会导致不同的语义。(如果使用浮点运算，语义也会有所不同，因为浮点运算不是关联的。)
所以，就像你的语法一样，开始的代数语法是：
expr: expr '+' expr
expr: expr '*' expr
模棱两可；这恰恰导致了上述歧义。解决方案是说CCD_ 19和大多数其他代数算子是左结合的。这导致了语法的调整：
expr: expr '+' term | term
term: term '*' factor | factor
...
这是不含糊的(但仍然是递归的)。
请注意，如果我们选择使这些运算符正确关联，从而生成解析(1+(2+(3+4)))，那么明确的语法将是正确递归的：
expr: term '+' expr | term
term: factor '*' term | factor
...
由于这些特定的运算符是关联的，所以我们选择哪种语法绑定并不重要(只要*比+绑定得更紧密)，我们可以完全绕过左递归消除，只要它们是我们唯一关心的运算符。但是，如上所述，有很多操作符的语义并不那么方便。
值得停下来了解一下为什么毫不含糊的语法是毫不含糊的。它应该不难理解，而且它是上下文无关语法的一个重要方面。
以生产expr: expr '+' term为例。注意，term并不导出2 + 3；term只允许乘法运算符。因此，只有将1 + 2还原为expr，将3还原为term，才能产生1 + 2 + 3，留下与expr的产量相匹配的expr '+' term。因此，((1+2)+3)是唯一可能的解析。CCD_ 35只能用显式括号书写。
现在，很容易对expr: expr '+' term或selectStmt: selectStmt setOp simpleSelectStmt | simpleSelectStmt执行左递归消除，以返回手头的问题。除了α是setOp simpleSelectStmt之外，我们完全按照您的指示进行。然后我们得到：
selectStmt: simpleSelectStmt selectStmt'
selectStmt': setOp simpleSelectStmt selectStmt'
| ε
通过将selectStmt反代入selectStmt'的第一次生产中，我们得到了
selectStmt: simpleSelectStmt selectStmt'
selectStmt': setOp selectStmt
| ε
这很酷；它不是模棱两可的，不是左递归的，并且没有LL(1)冲突。但它并没有生成与原始解析树相同的解析树。事实上，解析树非常特殊：S1 UNION S2 UNION S3被解析为(S1 (UNION S2 (UNION S3 ())))。
有趣的是，如果我们使用正确的联想语法selectStmt: simpleSelectStmt setOp selectStmt | simpleSelectStmt，这正是我们应该到达的地方。该语法是明确的，不是递归的，但它不是LL(1)，因为这两个选项都以simpleSelectStmt开头。因此，我们需要左因子，将其转换为selectStmt: simpleSelectStmt (setop selectStmt | ε)，与我们从左递归起点得到的语法完全相同。
但左递归语法和右递归语法确实不同：它们中的一个解析为((S1 UNION S2) UNION S3)，另一个解析成(S1 UNION (S2 UNION S3))。有了UNION，我们可以不在乎，但例如，SET DIFFERENCE运算符就不是这样了。
因此：左递归消除消除消除了左和右关联运算符之间的差异，并且必须使用一些非语法特性(例如Antlr的运行时语义)来消除这种差异。另一方面，像Yacc/Bison这样的自下而上的解析器不需要左递归消除，可以在不需要任何额外机制的情况下实现任意一种解析。
不管怎样，让我们回到
selectStmt: simpleSelectStmt selectStmt'
selectStmt': setOp simpleSelectStmt selectStmt'
| ε
应当清楚的是，CCD_ 50表示CCD_。(试着用一张纸，依次推导出更长的句子，以说服自己这是真的。)
因此，如果我们有一个解析器生成器来实现Kleene*运算符(零次或多次重复)，我们可以将selectStmt'写成(setOp simpleSelectStmt)*，使最终的语法
selectStmt: simpleSelectStmt (setOp simpleSelectStmt)*
这不再是BNF——BNF没有分组、可选性或重复运算符——但从实际意义上讲，它更容易阅读，如果你使用Antlr或类似的解析器生成器，你将不可避免地编写它。(尽管如此，它仍然不能表明setOp是向左绑定还是向右绑定。因此，这种便利性确实是以很小的价格提供的。)