确定文法是否满足 LL(1) 要求

Determining if grammar meets LL(1) requirements

我有一个用于递归下降解析器的 BNF。解决这个问题的步骤之一是验证语法是否为 LL(1),但我一直想验证它不是。

有问题的 BNF,或者更具体地说,我遇到问题的确切区域:

<S>           ->      start <vars> <block>
<block>       ->      begin <vars> <stats> end
<vars>        ->      e | id = number <vars>
<stats>       ->      <if> | <block> | <loop> | <assign> 

还有更多内容,但我相信这些是与这个问题相关的唯一作品。

我解决这个问题的方法是计算那些有选择的作品右侧的第一个。如果别无选择,我会跳过,因为我知道它们已经是 k=0.

FIRST(e | id = number <vars>) = {e, id} // Since it produces the empty set, I must also compute follow.

FOLLOW( e | id = number <vars> ) = FOLLOW(<vars>)

非终结符 'vars' 出现在 2 个作品中: and , 后面跟着两个非终结符:'block' 和 'stats'

FIRST(<block>) = {begin}
FIRST(<stats>) = { ... begin ... } // contains all terminals

现在,我的问题。在计算 FOLLOW() 时,我发现了两个开始标记,这让我说这个语法不是 LL(1)。但是,我不认为这个练习的答案是不可能创建递归下降解析器,所以我相信我在某处犯了错误或者我错误地执行了算法。

谁能指出我正确的方向?

所以你正确地发现 FOLLOW(var) = FIRST(block) ∪ FIRST(stats )。这些都是集合,因此当您计算前两个集合(每个集合包含 begin)的并集时,您最终只会得到一个 begin。只要这些集合都不包含 id,一切都很好,你的语法仍然是 LL(1).