Почему LALR(1) в Lark ломается на директивных патчах и что делать

Разбираем в Lark, почему LALR(1) падает на директивных патчах: неоднозначности грамматики, конфликты лексера и рабочая альтернатива — линейный сканер/FSM.

Разбор аннотаций, похожих на патчи и встроенных в исходные файлы, кажется простым — пока производственная грамматика не сталкивается с ограничениями реальности. Типичный прием — обрамлять «find»-текст и его замену четко отделенными директивами, а затем проходить по файлу и применять правки. Но стоит отдать такой формат генератору парсеров, как всплывают тонкие неоднозначности и несовместимости лексера, приводящие к запутанным ошибкам — особенно при переходе с Earley на LALR(1). В этом материале на конкретном примере показывается, почему конфигурация LALR(1) падает, и предлагается прагматичная альтернатива, лучше подходящая для задачи.

Постановка задачи

Входной формат следует предсказуемой последовательности директив и содержимого. Инженеры фиксируют в репозитории текстовые блоки, ограниченные маркерами; вокруг них могут встречаться пробелы или «комментарий‑подобный» текст. Упрощенный пример:

//find_start asdf
a
//find_end

//replace_start
A
//replace_end

//find_start
b
//find_end
this should be ignored
//replace_start
B
//replace_end

//find_start
c
//find_end

//replace_start
C
C
//replace_end

Следующая грамматика Lark корректно разбирает эту структуру парсером Earley. Но с парсером LALR(1) она падает во время разбора с ошибкой «unexpected token».

Грамматика, демонстрирующая проблему

Вот грамматика с эквивалентной логикой и переименованными символами. Она сохраняет исходное поведение, но делает идентификаторы различимыми:

root: stanza+

stanza: skipzone? seek_chunk skipzone? swap_chunk skipzone?

seek_chunk: "//find_start" [note_text] payload "//find_end"
swap_chunk: "//replace_start" payload "//replace_end"

_EOL: /\n/+
ROW.-10: /. +/
ANNOT: /\s.+/
payload: (ROW _EOL)+
skipzone: (ROW _EOL)+
note_text: (ANNOT _EOL)

%import common.NEWLINE
%import common.WS
%ignore WS
%ignore NEWLINE

Попытка разобрать пример с LALR(1) приводит к такой ошибке (с именами, соответствующими исходному отчёту):

lark.exceptions.UnexpectedToken: Unexpected token Token('LINE', 'a') at line 3, column 1.
Expected one of: 
        * _NL
Previous tokens: [Token('LINE', 'asdf')]

Почему это ломается с LALR(1)

Здесь сходятся две разные проблемы. Во‑первых, грамматика неоднозначна: область пропуска может трактоваться как хвост одной секции или как начало следующей. Earley умеет жить с неоднозначностями, LALR(1) — нет. Обычно это проявилось бы как конфликт при построении парсера, но в данном случае сбой возникает уже на этапе разбора.

Непосредственная причина ошибки во время выполнения — обработка пробельных символов. Определения токенов конца строки и «псевдокомментариев» используют регулярные выражения, в которых участвуют перевод строки и пробелы, а в грамматике параллельно объявлены %ignore WS и %ignore NEWLINE. Если лексеру велено глобально игнорировать WS и NEWLINE, он не сможет одновременно распознавать токены, зависящие от этих символов — например, кастомные токены конца строки и комментариев. В итоге строки схлопываются в поток обобщённых текстовых токенов — ровно на это и намекает ошибка, когда сообщает о двух подряд токенах строки при отсутствии ожидаемого конца строки. Примечательно, что это противоречие формально должно задевать и Earley; почему тот же ввод проходит там без ошибки — неочевидно.

Более простой и надёжный подход

В этом сценарии полноценный парсер не нужен. Структура линейна и управляется директивами, поэтому прямой скан проще и меньше подвержен ошибкам. Ниже — логика одноразового прохода по файлу: строки выводятся или отбрасываются по маркерам, давая желаемый результат патча. Поведение повторяет описанный процесс, не привнося неоднозначностей грамматики и конфликтов по пробелам.

repeat_forever:
  read_and_forward until line_begins_with("//find_start")

  read_and_discard until line_begins_with("//find_end")

  take_one_line_and_drop_it
  ensure_next_line_begins_with("//replace_start")

  read_and_forward until line_begins_with("//replace_end")

end_repeat

Обрабатывайте конец файла и ошибки в рамках этого цикла.

Почему это важно

Патч‑форматы, основанные на директивах, разумнее трактовать как поток, а не как язык. Попытки втиснуть их в LALR(1)-грамматики проявляют две хрупкости: неоднозначности на границах блоков и конфликты токенов лексера из‑за глобального игнорирования пробелов. Решение в стиле сканера проще сопровождать, лучше соответствует рабочей модели патчера и не страдает от чувствительности парсера к политике токенизации. Если требуется дополнительная сложность — например, параметризация и опции после //find_start — её можно наслоить поверх простого конечного автомата (FSM): разбирать только эти короткие фрагменты отдельной грамматикой, а внешний обход файла оставить конечным автоматом.

Заключительные рекомендации

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