Как решить этот конфликт Shift / Reduce в YACC - PullRequest
Новая
       24

Как решить этот конфликт Shift / Reduce в YACC

2 голосов
/ 19 ноября 2009

У меня есть такая грамматика:

«Сопоставить одно или несколько правил1, где правило1 - это одно или несколько правил2, где правило2 - это одно или несколько правил3 и т. Д. И т. Д., Каждый из которых разделен символами новой строки». Посмотрите на следующий пример. 

start:   rule1_list
      ;

rule1_list:   rule1
           |  rule1_list NEWLINE rule1
            ;

rule1:   rule2
     |   rule2 NEWLINE rule3_list
      ;

rule2:   TERMINAL2
      ;

rule3_list:   rule3
          |   rule3_list NEWLINE rule3
          ;

rule3 :  TERMINAL3
      ;

Я получаю сдвиг / уменьшение конфликтов при этом, как я могу изменить грамматику, чтобы остановить? По сути, он должен перейти после новой строки и посмотреть, является ли следующая вещь TERMINAL2 или TERMINAL3.

Ответы [ 3 ]

5 голосов
/ 19 ноября 2009

Неоднозначная грамматика, не LALR (1), по умолчанию не разбирается в режиме yacc

Короче говоря, вы можете "исправить" это с помощью объявления %glr-parser следующим образом: 

%glr-parser
%%
start: rule1_list
. . .
. . .

Чтобы сделать длинную историю средней длины ...

Конфликты сдвиг-уменьшение обычно не являются ошибками. Конфликт разрешается, всегда делая сдвиг, который, как правило, то, что вы хотите. Большинство или все грамматики реального мира имеют конфликты сдвига-уменьшения. И если вы хотели сокращения, вы можете договориться об этом с объявлениями предшествования.

Однако в действительно неоднозначной грамматике выполнение сдвига отправит синтаксический анализатор по одному из двух путей, только один из которых в конечном итоге найдет строку в грамматике. В этом случае конфликт S / R является фатальной ошибкой.

Анализируя первый, когда анализатор видит новую строку в случае | rule2 NEWLINE rule3_list, он может либо перейти в новое состояние, где ожидается ожидаемый список правил3, либо уменьшить правило1, используя rule1: rule2. Он всегда будет искать список rule3_list из-за выбора по умолчанию shift.

Второй конфликт возникает, когда он видит новую строку в rule3_list: rule3_list . NEWLINE rule3. Теперь он может либо сдвинуться и начать искать правило 3, либо уменьшить правило 1, используя | rule2 NEWLINE rule3_list.

В результате, как написано, и принимая «2» и «3» для терминалов, вы можете анализировать только 2 строки, а затем 3 строки. Если вы возитесь с приоритетом, вы можете анализировать только строки «2», но не строки «3».

Наконец, я должен добавить, что использование сгенерированного yacc синтаксического анализатора GLR является чем-то вроде клуджа. Я предполагаю, что это будет работать просто отлично, но это чистый BFI, парсер разбивает, хранит два стека, продолжается по обоим путям, пока один не найдет строку в грамматике. К сожалению, другие исправления также являются клуджами: 1. переформулируйте грамматику как LALR (1), 2. добавьте дополнительный взгляд в сканер и верните составной токен, 3. Поэкспериментируйте с правилами для вашей грамматики, возможно, yacc может обработать вариант.

Вот почему я на самом деле не люблю yacc и предпочитаю рукописный рекурсивный спуск или что-то более современное, такое как PEG. (см. Верхушку дерева)

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

%%
start:   stmtList
      ;

stmtList: /* nothing */ 
      | stmtList '2' threeList;
      ;

threeList: /* nothing */
      | threeList '3'
      ;
%%
int yylex() { int c; do {  c = getchar (); } while (c == '\n'); return c; }
1 голос
/ 22 ноября 2009

не двусмысленно, просто не LALR (1)

Проблема в том, что для нескольких мест в грамматике требуется двухголовая рука-стрелка, чтобы увидеть, какой ТЕРМИНАЛ идет после NEWLINE, чтобы решить, что делать. Есть несколько вещей, которые вы можете сделать, чтобы это исправить.

  1. пропустить новые строки в scaaner - тогда они больше не будут токенами и не будут мешать взгляду

  2. Использовать% glr-parser. Это может быть опасно, если вы когда-нибудь введете противоречия в вашей грамматике, так как они потребуют функций слияния, чтобы заставить вещи работать. Нет хорошего способа определить, является ли какой-либо конкретный конфликт следствием неоднозначности или просто требует большего внимания - вам нужно тщательно проанализировать каждый отчет о бизонах конфликта, чтобы узнать.

  3. реорганизовать грамматику, чтобы отложить принятие решений, поэтому не требуется много внимания. Одним из простых вариантов является включение новых строк в правила в качестве разделителей вместо разделителей: 

    start:   rule1_list ;

rule1_list:   rule1
          |  rule1_list rule1
          ;

rule1:   rule2
     |   rule2 rule3_list
     ;

rule2:   TERMINAL2 NEWLINE ;

rule3_list:   rule3
          |   rule3_list rule3
          ;

rule3 :  TERMINAL3 NEWLINE ;

конечно, это меняет грамматику, так как теперь требуется новая строка после последнего правила перед EOF

0 голосов
/ 19 ноября 2009

Я думаю, что вы должны преобразовать левые рекурсии в правые рекурсии. Пример для rule3_list: 

rule3_list: TERMINAL3 | TERMINAL3 NEWLINE rule3_list;
...