布尔表达式文法Follow集计算疑问：我的结果与参考答案为何不同？

原始文法 #

bexpr -> bexpr or bterm | bterm
bterm -> bterm and bfactor | bfactor
bfactor -> not bfactor | ( bexpr ) | true | false

消除左递归后的文法 #

bexpr -> bterm bexpr'
bexpr' -> or bterm bexpr' | ε
bterm -> bfactor bterm'
bterm' -> and bfactor bterm' | ε
bfactor -> not bfactor | (bexpr) | true | false

已计算的First集 #

first(bexpr) = first(bterm) = first(bfactor) = [not, (, true, false]
first(bexpr') = [or, ε]
first(bterm') = [and, ε]

你的计算结果 #

follow(bterm)=first(bexpr')\epsilon+follow(bexpr)=[or]+[$,)]=[or,$,)]
follow(bfactor)=first(bterm')\epsilon+follow(bterm)=[and]+[or,$,)]=[and, or, $, )]

参考答案结果 #

follow(bterm) = [or, $]
follow(bfactor) = [and, $]

结果分析 #

你的计算是正确的，参考答案存在错误。

Follow集的核心计算规则是：若产生式为A→αBβ，则First(β)中除ε外的元素加入Follow(B)；若β可推导出ε，则Follow(A)的元素也加入Follow(B)。

具体推导过程：

1. 计算follow(bexpr)：

   • 作为文法开始符号，$默认属于follow(bexpr)；
   • 从产生式bfactor -> (bexpr)可知，bexpr后紧跟终结符)，因此)也属于follow(bexpr)，最终follow(bexpr) = {$, )}。

2. 计算follow(bterm)：

   • 从产生式bexpr -> bterm bexpr'，first(bexpr')去掉ε的元素是[or]，需加入follow(bterm)；
   • 由于bexpr'可推导出ε，因此follow(bexpr)的元素[$, )]也需加入follow(bterm)；
   • 最终follow(bterm) = {or, $, )}。

3. 计算follow(bfactor)：

   • 从产生式bterm -> bfactor bterm'，first(bterm')去掉ε的元素是[and]，需加入follow(bfactor)；
   • 由于bterm'可推导出ε，因此follow(bterm)的元素[or, $, )]也需加入follow(bfactor)；
   • 最终follow(bfactor) = {and, or, $, )}。

这和你的计算结果完全一致，参考答案遗漏了)的存在，是错误的。

内容的提问来源于stack exchange，提问作者rd142857