如何避免移位，减少LALR语法中解析嵌套列表的冲突

Question

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

我有list1，它是类型1项的列表和list2:

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

我有一个list2，它是类型2项目的列表:

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

这个语法会产生一个shift/reduce错误。我怎样才能避免呢?

这是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'

但我不认为这是一个大问题。

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级别引入分隔符怎么样?