如何在分析嵌套列表的LALR语法中避免shift reduce冲突？

Question

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

我有一个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)))))

终端是:注释、换行、文本块和空格。非终端是: input、node-list、node和text。

Bigloo抱怨文本到文本块的reduce规则：

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

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

Answer 1

语法实际上是模棱两可的，因为可以在list2级别上累积一系列type2实例，但也可以将其视为一系列type1实例。

例如，此输入

 X X

可以被解析为

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

但也可以作为

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

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