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

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

0 голосов
/ 30 мая 2010

Я использую 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

1 Ответ

4 голосов
/ 14 июня 2010

Ваша основная проблема заключается в том, что вам нужно два токена предвидения, чтобы сделать то, что вы хотите - когда вход, который вы видели до сих пор, равен course, а предвидение - OR_CONJ, вы не знаете, уменьшать ли * От 1003 * до 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

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

...