Как решить сдвиг / уменьшить конфликт? - PullRequest
Новая
       41

Как решить сдвиг / уменьшить конфликт?

8 голосов
/ 02 июля 2010

Я использую CUP для создания парсера, который мне нужен для моей диссертации.У меня есть конфликт сдвига / уменьшения в моей грамматике.У меня есть это производственное правило: 

command ::= IDENTIFIER | IDENTIFIER LPAREN parlist RPAREN;

, и у меня есть это предупреждение: 

Warning : *** Shift/Reduce conflict found in state #3
between command ::= IDENTIFIER (*) 
and     command ::= IDENTIFIER (*) LPAREN parlist RPAREN 
under symbol LPAREN

Теперь я на самом деле хотел, чтобы оно сместилось, поэтому я вполне согласен с этим, но мой профессорсказал мне, чтобы найти способ решить конфликт.Я слепой.Я всегда читал о конфликте if / else, но для меня это не так.Вы можете мне помочь?

PS: IDENTIFIER, LPAREN "(" и RPAREN ")" являются терминалами, parlist и команда не являются.

Ответы [ 3 ]

7 голосов
/ 22 июля 2010

Ваша проблема вообще не в этих правилах.Хотя ответ Михаила Мрозека является правильным подходом к решению «висящей проблемы», он не понимает проблему под рукой.

Если вы посмотрите на сообщение об ошибке, вы увидите, что при сдвиге LPAREN присутствует конфликт сдвига / уменьшения .Я почти уверен, что одни только правила не приведут к конфликту.

Я не вижу твоей грамматики, поэтому не могу помочь тебе.Но ваш конфликт, вероятно, возникает, когда за command следует другое правило, начинающееся с LPAREN.

. Посмотрите на любые другие правила, которые могут быть после command и начинаются с LPAREN.Затем вам нужно будет консолидировать правила.Очень велика вероятность того, что ваша грамматика ошибочна для определенного ввода.

5 голосов
/ 02 июля 2010

У вас есть два производства: 

command ::= IDENTIFIER
command ::= IDENTIFIER LPAREN parlist RPAREN;

Это конфликт сдвига / уменьшения, когда входные токены IDENTIFIER LPAREN, потому что:

  • LPAREN может быть началом нового производства, которое вы не перечислили, и в этом случае парсер должен уменьшить IDENTIFIER уже в стеке до command и иметь command LPAREN оставшихся
  • Они оба могут быть началом второго производства, поэтому он должен переместить LPAREN в стек рядом с IDENTIFIER и продолжить чтение, пытаясь найти parlist.

Вы можете исправить это, выполнив что-то вроде этого: 

command ::= IDENTIFIER command2
command2 ::= LPAREN parlist RPAREN |;
2 голосов
/ 15 ноября 2015

Попробуйте установить приоритет: 

precedence left     LPAREN, RPARENT;

Это вынуждает CUP решать конфликт, принимая левый матч.

...