scheme - 如何避免 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)))))

终端是：comment、new-line、text-chunk 和 white-space。非终结符是：输入、节点列表、节点和文本。

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？这将解决问题。