如何避免 LALR 语法中用于解析嵌套列表的移位归约冲突？

Question

我想创建一个 LALR 语法来解析嵌套列表，但我总是遇到移位/归约冲突。

我有 list1，它是 type1 项目的列表和 list2：

<list1> ::= <type1> | <type1> <list1> ;
<type1> ::= A | B | <list2> ;

我有一个 list2，它是 type2 项目的列表：

<list2> ::= <type2> | <type2> <list2> ;
<type2> ::= X | Y ;

此语法会产生移位/归约错误。我怎样才能避免它？

这是具体的 Bigloo 来源：

(lalr-grammar 
  (comment
   new-line 
   text-chunk
   white-space)
  (input
   (()                '())
   ((node-list)       node-list))
  (node-list
   ((node)            (cons node '()))
   ((node node-list)  (cons node node-list)))
  (node
   ((comment)         (cons 'comment comment))
   ((new-line)        (cons 'new-line new-line))
   ((text)            (cons 'text text))
   ((white-space)     (cons 'white-space white-space)))
  (text
   ((text-chunk)      (cons 'text text-chunk))
   ((text-chunk text) (cons 'text (string-append text-chunk text)))))

终端有：注释、换行、文本块和空白。 非终结符是：输入、节点列表、节点和文本。

Bigloo 抱怨文本到文本块的缩减规则：

*** WARNING:bigloo:lalr-grammar
** Shift/Reduce conflict: 
 - shift to state 2
 - reduce rule (text --> text-chunk)
on token `text-chunk'

但我不认为这是 Bigloo 的问题。看起来像是语法问题。

Answer 1

该语法实际上是不明确的，因为 type2 实例的序列可以在 list2 级别上累积，但它也可以被视为 type1 的序列代码>实例。

例如，此输入

 X X

可以解析为

 list1(
   type1(
     list2(
       type2(
         X)
       list2(
         type2(
           X)))))

，也可以解析为

 list1(
   type1(
     list2(
       type2(
         X)))
   list1(
     type1(
       list2(
         type2(
           X)))))

在 list1 级别引入分隔符怎么样？这样就可以解决问题了。