Как избежать сдвига уменьшить конфликт в грамматике LALR для разбора вложенных списков? - PullRequest
Новая
       84

Как избежать сдвига уменьшить конфликт в грамматике LALR для разбора вложенных списков?

2 голосов
/ 28 сентября 2011

Я хотел бы создать грамматику 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)))))

Терминалы: комментарий, новая строка, текстовый чанк и белыйпространство.Нетерминалы: input, node-list, node и text.

Bigloo жалуется на правило сокращения текста в text-chunk: 

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

Но я не думаю, что этопроблема БиглооЭто похоже на проблему грамматики.

1 Ответ

2 голосов
/ 28 сентября 2011

Грамматика на самом деле неоднозначна, потому что последовательность type2 экземпляров может быть накоплена на уровне list2, но она также может рассматриваться как последовательность type1 экземпляров.

Например, этовходные данные 

 X X

могут быть проанализированы как 

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

, но также как 

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

А как насчет введения разделителя на уровне list1?Это решило бы проблему.

...