Проблема заключается в обработке NEWLINE токенов. Это создает конфликт сдвига / уменьшения, который разрешается в пользу действия сдвига. Следствием этого является то, что действие по сокращению конфликта никогда не может быть предпринято, что делает невозможным синтаксический анализ некоторых грамматических конструкций.
Вот один пример:
else_if_clause_seq: else_if_clause . [$end, NEWLINE, DEDENT]
| else_if_clause . NEWLINE else_if_clause_seq
Это взято из дампа конечного автомата Бизона для той же грамматики. Состояние синтаксического анализатора - это коллекция «элементов»; Каждый предмет - это производство с отмеченной позицией. (Отметка . в двух постановках.) Отметка в основном показывает, как далеко продвинулся синтаксический анализатор, когда он достигает этого состояния; если . находится в конце производства (как в первой строке), то возможно действие сокращения, потому что синтаксический анализатор достиг конца производства. Если . имеет некоторый следующий символ, то парсер может сдвинуть следующий токен, если следующий токен может быть (или быть первым токеном в некотором расширении) следующим символом. В случае второго производства, описанного выше, NEWLINE можно было бы сдвинуть, если бы это был следующий токен.
Производство в штате также аннотируется набором преднамеренного просмотра, хотя бизон показывает только набор предварительного просмотра для продукций, которые могут быть уменьшены. Аннотация [$end, NEWLINE, DEDENT] в конце первого производства - это набор для просмотра этого производства. Другими словами, это набор возможных следующих токенов в контексте, в котором производство может быть сокращено.
Это состояние является конфликтом сдвига / уменьшения, поскольку NEWLINE может либо вызвать уменьшение на else_if_clause_seq: else_if_clause, либо оно может быть смещено в предположении, что NEWLINE else_if_clause_seq будет проанализирован. Поскольку разрешением конфликта сдвига / уменьшения по умолчанию является предпочтение сдвига (в bison, ply, rply и большинстве других генераторов синтаксического анализатора LR), сокращение никогда не произойдет, что заставит анализатор всегда выбирать расширение else_if_clause_seq , Фактически это означает, что за else_if_clause, находящимся не в конце блока, всегда должен следовать другой else_if_clause, что делает невозможным синтаксический анализ else_if true 1 else 1, в котором за else_if_clause следует предложение else.
С этой грамматикой у парсера, который может просматривать два токена, проблем не возникнет. Второй следующий токен, следующий за NEWLINE, должен быть либо else, либо else_if; в первом случае требуется уменьшение, а во втором случае сдвиг является правильным действием. На самом деле, NEWLINE действительно не имеет смысла, так как и else, и else_if всегда должны предшествовать токены NEWLINE. Кроме того, поскольку else_if_clause может заканчиваться только block, а block может заканчиваться только DEDENT, мы можем заключить, что NEWLINE должен предшествовать DEDENT.
Похоже, что вы решили отправить NEWLINE после DEDENT, поскольку ваша грамматика, кажется, указывает на то, что вы отправили NEWLINE до и INDENT. Это, вероятно, работает в теории, но это определенно приводит к конфликтам сдвига / уменьшения, которые вы испытываете.
Более распространенная реализация лексического сканирования с учетом пробелов использует алгоритм , описанный в руководстве по Python : токен NEWLINE генерируется при обнаружении новой строки, если только окружающие строки не явным или неявным образом соединены и затем принимается решение о выдаче либо одного INDENT, одного или нескольких DEDENT s, либо ничего. Тщательное изучение грамматики Python показывает, как это сочетается. Вот упрощенная выписка в EBNF:
stmt: simple_stmt | compound_stmt
simple_stmt: small_stmt (';' small_stmt)* [';'] NEWLINE
small_stmt: expr_stmt …
compound_stmt: if_stmt …
if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]
suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT
suite более или менее соответствует вашему block, но допускает использование одинарных операторов в одной строке, но обратите внимание, что оно начинается с NEWLINE. Простые (не составные) операторы заканчиваются на NEWLINE; составные операторы рассматриваются как самоограниченные.
Альтернативный подход состоит в том, чтобы выдавать NEWLINE токенов только в случае, когда две последовательные строки имеют одинаковый отступ.Как отмечалось выше, NEWLINE токены в строках с отступом или с отступом строго избыточны, так как их присутствие может быть выведено;их полное исключение уменьшает количество токенов, которые должны обрабатываться парсером.Но если вы сделаете это, вы больше не сможете использовать простой принцип, согласно которому простые операторы всегда заканчиваются NEWLINE, поскольку за последним простым оператором в block непосредственно следует DEDENT.Это делает необходимым использование чуть более сложного (и праворекурсивного) определения expression_seq:
block : INDENT statement_sequence DEDENT
statement : simple_statement | compound_statement
statement_sequence : statement
| simple_statement NEWLINE statement_sequence
| compound_statement statement_sequence