Python/YACC: разрешение сдвига / уменьшение конфликта

Question

Я использую PLY. Вот одно из моих состояний из parser.out:

state 3

    (5) course_data -> course .
    (6) course_data -> course . course_list_tail
    (3) or_phrase -> course . OR_CONJ COURSE_NUMBER
    (7) course_list_tail -> . , COURSE_NUMBER
    (8) course_list_tail -> . , COURSE_NUMBER course_list_tail

  ! shift/reduce conflict for OR_CONJ resolved as shift
    $end            reduce using rule 5 (course_data -> course .)
    OR_CONJ         shift and go to state 7
    ,               shift and go to state 8

  ! OR_CONJ         [ reduce using rule 5 (course_data -> course .) ]

    course_list_tail               shift and go to state 9

Я хочу решить это как:

if OR_CONJ is followed by COURSE_NUMBER:
    shift and go to state 7
else:
    reduce using rule 5 (course_data -> course .)

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

В документации сказано:

Эти значения затем используются для добавления числового значения приоритета и направления ассоциативности к каждому правилу грамматики. Это всегда определяется путем рассмотрения приоритета самого правого терминального символа.

Что если в правиле нет терминалов?

ОБНОВЛЕНИЕ: полная грамматика:

Grammar

Rule 0     S' -> statement
Rule 1     statement -> course_data
Rule 2     or_phrase -> statement OR_CONJ statement
Rule 3     or_phrase -> course OR_CONJ COURSE_NUMBER
Rule 4     statement -> or_phrase
Rule 5     course_data -> course
Rule 6     course_data -> course course_list_tail
Rule 7     course_list_tail -> , COURSE_NUMBER
Rule 8     course_list_tail -> , COURSE_NUMBER course_list_tail
Rule 9     course -> DEPT_CODE COURSE_NUMBER

Answer 1

Ваша основная проблема в том, что вам нужно два токена упреждения, чтобы сделать то, что вы хотите - когда вход, который вы видели до сих пор, является course и предвкушение OR_CONJ Вы не знаете, следует ли уменьшить course к course_data или сдвинуться, не заглядывая вперед два токена к токену после OR_CONJ, Есть несколько способов справиться с этим

• используйте генератор синтаксических анализаторов LR(2), LR(k) или GLR - любой может справиться с этим.

• использовать взлом лексера, чтобы сделать упущение - в основном, лексер возвращает два разных OR_CONJ токены в зависимости от того, является ли следующий токен COURSE_NUMBER или нет.

• Факторинг грамматики, чтобы избавиться от конфликта, может привести к грамматике, которая анализирует что-то немного отличное от того, что вы хотите (требуются дополнительные проверки после анализа, чтобы отклонить некоторые недопустимые конструкции) и, как правило, делает грамматику намного труднее для понимания.

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

Rule 1    statement -> course
Rule 2    statement -> statement OR_CONJ course
Rule 3    course -> DEPT_CODE course_list
Rule 4    course -> DEPT CODE course_list OR_CONJ COURSE_NUMBER
Rule 5    course_list -> COURSE_NUMBER
Rule 6    course_list -> course_list , COURSE_NUMBER

Это также может быть переписано как праворекурсивное для генератора синтаксических анализаторов LL, но у него все еще есть проблема просмотра с 2 токенами. Один из способов рефакторинга это сделать, это сделать COURSE_NUMBER сам по себе действительный course и рекомбинировать его с предыдущим course в пост-проход (или дать ошибку, если его первым course в statement). Тогда правило 4 становится:

Rule 4    course -> COURSE_NUMBER

и у вас нет конфликтов.