Конфликт сдвига / уменьшения в yacc-Flex

У меня следующая грамматика в yacc, но я получаю 1 конфликт сдвига / уменьшения:

   %union {
   char* integer;
    char* string;
    char* boolean;
    char* date;
};



%token <integer> INTEGER
%token <string> STRING
%token <boolean> BOOLEAN
%token <date> DATE
%token WORKBOOK_START WORKBOOK_END STYLES_START STYLES_END STYLE_START STYLE_END WORKSHEET_START
%token WORKSHEET_END CLOSE_TAG EQUAL QUOTES COL_END_TAG
%token TABLE_START TABLE_END COLUMN_START ROW_START ROW_END CELL_START CELL_END DATA_START DATA_END
%token ID NAME PROTECTED EXPCOLCOUNT EXPROWCOUNT STYLEID HIDDEN WIDTH HEIGHT MERGEACR MERGEDOWN TYPE
%token MY_NUMBER MY_STRING MY_BOOL MY_DATETIME

%%
WORKBOOK: WORKBOOK_START INWORKBOOK WORKBOOK_END ;

INWORKBOOK: WORKSHEET MORE_WORKSHEETS 
      | NUM_STYLES WORKSHEET MORE_WORKSHEETS
      ;

MORE_WORKSHEETS: WORKSHEET MORE_WORKSHEETS
           |
           ;

NUM_STYLES: STYLES NUM_STYLES
      |
      ;

STYLES: STYLES_START INSTYLES STYLES_END ;

INSTYLES: STYLE INSTYLES
    |
    ;

STYLE: STYLE_START INSTYLE STYLE_END ;

INSTYLE: id CLOSE_TAG ; 

id: ID EQUAL QUOTES STRING QUOTES {checkID($4);};

WORKSHEET: WORKSHEET_START INWORKSHEET WORKSHEET_END  ;

INWORKSHEET: name protected CLOSE_TAG MORE_TABLES
       | protected name CLOSE_TAG MORE_TABLES
       | name CLOSE_TAG MORE_TABLES
       ;

name: NAME EQUAL QUOTES STRING QUOTES ;

%%

Я использовал параметр -v для получения сгенерированных конфликтов, и кажется, что у меня проблема в WORKBOOK: WORKBOOK_START INWORKBOOK WORKBOOK_END ;

State 1
1 WORKBOOK: WORKBOOK_START . INWORKBOOK WORKBOOK_END
STYLES_START     shift, and go to state 3
WORKSHEET_START  shift, and go to state 4
WORKSHEET_START  [reduce using rule 7 (NUM_STYLES)]
INWORKBOOK  go to state 5
NUM_STYLES  go to state 6
STYLES      go to state 7
WORKSHEET   go to state 8

Как я могу исправить эту проблему? Какие-либо предложения?


c lexer flex-lexer yacc
person Community    schedule 17.09.2018    source источник
comment
Замените правила для INWORKBOOK на INWORKBOOK: NUM_STYLES WORKSHEET MORE_WORKSHEETS. Это должно проанализировать ту же грамматику, но устранить конфликт.   -  person Ctx    schedule 18.09.2018
comment
Ваше правило MORE_WORKSHEETS: WORKSHEET MORE_WORKSHEETS | /* Nothing */ ; является рекурсивным справа; вам следует использовать правило левой рекурсии MORE_WORKSHEETS: MORE_WORKSHEETS WORKSHEET | /* Nothing */ ; - оно сокращает объем памяти, необходимый для обработки грамматики. Однако это не имеет ничего общего с конфликтом сдвига / уменьшения AFAIK.   -  person Jonathan Leffler    schedule 18.09.2018

Ответы (1)


arrow_upward
1
arrow_downward

NUM_STYLES может быть пустым. Итак, учитывая две альтернативы:

INWORKBOOK: WORKSHEET MORE_WORKSHEETS 
          | NUM_STYLES WORKSHEET MORE_WORKSHEETS

если входные данные помечаются токеном, который может быть началом WORKSHEET, синтаксический анализатор не может определить, следует ли использовать первую продукцию или уменьшить пустой NUM_STYLES и использовать вторую продукцию.

Вам следует еще раз взглянуть на таблицу состояний и попытаться понять, как она сообщает вам об этой проблеме.

person rici    schedule 17.09.2018