Фиксация лимонного анализа confilcts

Question

Я пишу небольшой парсер, который разбирает ограничения, используя Flex и Lemon. Лимон сообщает о нескольких конфликтах разбора, от которых мне не удалось избавиться. Существуют ли какие-либо особые приемы для избавления от разбора конфликтов в контексте свободной грамматики?

Грамматика заключается в следующем.

// Reprint of input file "Constraint_grammar.y". 
// Symbols: 
// 0 $   5 NE  10 PLUS  15 NOT   20 error 
// 1 IFF  6 GT  11 MINUS  16 LPAREN  21 constraint 
// 2 AND  7 GTE  12 TIMES  17 RPAREN  22 bool_expr 
// 3 OR   8 LT  13 DIVIDE  18 VARIABLE 23 int_expr 
// 4 EQ   9 LTE  14 POWER  19 INTEGER 
constraint ::= bool_expr. 
bool_expr ::= LPAREN bool_expr RPAREN. 
int_expr ::= LPAREN int_expr RPAREN. 
bool_expr ::= int_expr LT int_expr. 
bool_expr ::= int_expr GT int_expr. 
bool_expr ::= int_expr EQ int_expr. 
bool_expr ::= int_expr NE int_expr. 
bool_expr ::= int_expr GTE int_expr. 
bool_expr ::= int_expr LTE int_expr. 
bool_expr ::= bool_expr AND bool_expr. 
bool_expr ::= bool_expr OR bool_expr. 
bool_expr ::= bool_expr IFF bool_expr. 
int_expr ::= int_expr PLUS int_expr. 
int_expr ::= int_expr MINUS int_expr. 
int_expr ::= int_expr TIMES int_expr. 
int_expr ::= int_expr DIVIDE int_expr. 
int_expr ::= int_expr POWER int_expr. 
bool_expr ::= NOT bool_expr. 
int_expr ::= MINUS int_expr. 
int_expr ::= VARIABLE. 
bool_expr ::= VARIABLE. 
int_expr ::= INTEGER.

%nonassoc IFF. 
%left AND. 
%left OR. 
%nonassoc EQ NE GT GTE LT LTE. 
%left PLUS MINUS. 
%left TIMES DIVIDE. 
%right POWER NOT. 
%nonassoc LPAREN RPAREN.

ошибки следующим образом.

State 28: 
    (19) int_expr ::= VARIABLE * 
    (20) bool_expr ::= VARIABLE * 

          $ reduce 20 
          IFF reduce 20 
          AND reduce 20 
          OR reduce 20 
          EQ reduce 19 
          NE reduce 19 
          GT reduce 19 
          GTE reduce 19 
          LT reduce 19 
          LTE reduce 19 
          PLUS reduce 19 
         MINUS reduce 19 
         TIMES reduce 19 
         DIVIDE reduce 19 
         POWER reduce 19 
         RPAREN reduce 19 
         RPAREN reduce 20 ** Parsing conflict **

State 40: 
      bool_expr ::= bool_expr * AND bool_expr 
      bool_expr ::= bool_expr * OR bool_expr 
      bool_expr ::= bool_expr * IFF bool_expr 
    (11) bool_expr ::= bool_expr IFF bool_expr * 

          $ reduce 11 
          IFF shift 4 
          IFF reduce 11 ** Parsing conflict ** 
          AND shift 1 
          OR shift 3 
         RPAREN reduce 11

Весь отчет парсер генератор здесь. http://pastebin.com/TRsV3WvK

Кто-нибудь знает, что я делаю неправильно здесь? Могу ли я игнорировать эти конфликты?

Answer 1

Я бы ожидал исправить конфликт «Состояние 28», разделив логическую переменную и целочисленную переменную, используя таблицу символов, чтобы помочь определить, какой тип маркера возвращается. Возможно, у вас бы были BOOL_VARIABLE и INT_VARIABLE. Тестирование показывает, что это изменение избавляется от конфликта «State 28».

Конфликт государства 40 легко удаляется путем изменения ассоциативности IFF от nonassoc до left. Есть ли веская причина не делать его ассоциативным?

Answer 2

У вас возникли конфликты парсера, что означает, что указанная вами грамматика не является однозначной, т. Е. Для некоторого заданного ввода символов терминала существует более одного дерева синтаксического анализа. Это довольно часто, но если нам нужна недвусмысленная грамматика, нам нужно указать правила неоднозначности, такие как ассоциативность и приоритет, так что мы всегда можем выбрать только один из деревьев разбора.

Я не уверен, какие ограничения вы анализируете грамматику, но я уверен, что вы хотите, чтобы здесь была umabigous грамматика, языки программирования (почти) всегда однозначны. (Однако, если ограничения связаны с каким-то источником естественного языка, вам, вероятно, придется использовать более подходящий синтаксический анализатор). Я не уверен, что сделает листок-парсер, если вы дадите ему двусмысленную грамматику, возможно, просто предпочтете один из переходов в своем автомате, что очень хорошо может привести к дереву, которого вы не хотите.