Как избежать сдвига уменьшить конфликт в грамматике 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)))))

Терминалы: комментарий, новая строка, текстовый чанк и пробел. Нетерминалы: ввод, список узлов, узел и текст.

Биглоо жалуется на правило сокращения текста для фрагмента текста:

*** 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 уровень? Это решило бы проблему.