寻找有关使此 BNF 语法适合 LL(1) 解析(左因式分解)的建议
Looking for advice on making this BNF grammar suitable for LL(1) parsing (left factoring)
我正在从事一个解析项目,该项目使用此语法对 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>
符号,如果我们颠倒顺序,我们仍然会得到它。我是不是漏掉了什么,或者在这种情况下简单地颠倒顺序就能达到与左分解相同的目标?
您要解决的问题是
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
我正在从事一个解析项目,该项目使用此语法对 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>
符号,如果我们颠倒顺序,我们仍然会得到它。我是不是漏掉了什么,或者在这种情况下简单地颠倒顺序就能达到与左分解相同的目标?
您要解决的问题是
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