寻找有关使此 BNF 语法适合 LL(1) 解析（左因式分解）的建议

Question

我正在从事一个解析项目，该项目使用此语法对 Perl 正则表达式的改编 http://www.cs.sfu.ca/~cameron/Teaching/384/99-3/regexp-plg.html。为了我自己的目的，我已经简化了这个语法，就像这样（注意，因为“|”是一个标记，所以我使用逗号“，”所以给定的非终结符的单独产生式）：

<RE>      := <union>, <simple>
<union>   := <RE> | <simple>
<simple>  := <concat>, <basic>
<concat>  := <simple><basic>
<basic>   := <zero>, <one>, <onezero>, <elem>
<zero>    := <elem>*
<one>     := <elem>+
<onezero> := <elem>?
<elem>    := <group>, <any>, <literal>, <class>
<group>   := (<RE>)
<class>   := [<items>]
<items>   := <item>, <item><items>
<item>    := <range>, <literal>

我想编写一个 LL(1) 解析器来处理此语法，对于 LL(1) 解析器，<items> 的产生式有些歧义。为了解决这个问题，我可以通过添加一个新的非终结符 <X> 来对它们进行左因式分解，如下所示：

<items>   :=  <item><X>
<X>       :=  <items>, epsilon

但我想知道的是，我能不能把 <items> 中第二部作品的顺序翻转过来，像这样：

<items>   := <item>, <items><item>

并避免添加新的非终结符？它看起来并没有破坏任何东西，毕竟这个产品的全部意义在于允许任意数量的连续 <item> 符号，如果我们颠倒顺序，我们仍然会得到它。我是不是漏掉了什么，或者在这种情况下简单地颠倒顺序就能达到与左分解相同的目标？

Answer 1

您要解决的问题是

items → item
items → item items

不是左因式；两部作品都以 item.

开头

您提出的修复方案

items → item
items → items item

并没有真正帮助（无论什么开始 item 仍然可以开始生产 items），但更重要的是，它是左递归的，即 verboten 用于 LL 文法。

原则上，"new non-terminal" 是正确的解决方案，但在递归下降解析器中，您可能会这样做：

def items():
  list = [ item() ]
  while couldStart(item, lookahead):
    list.append(item())
  return list

寻找有关使此 BNF 语法适合 LL(1) 解析（左因式分解）的建议

Looking for advice on making this BNF grammar suitable for LL(1) parsing (left factoring)

parsing

compiler-construction

bnf