Исправление разборов лимонов

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. Тестирование показывает, что это изменение избавляет от конфликта «Состояние 28».

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

Answer 2

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

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