https://habr.com/ru/post/471988/

• Python
• Программирование
• Алгоритмы

Грамматика становится ещё лучше, если вы можете добавить (некоторую) семантику в соответствии с правилами. В частности, для анализатора Python, который я разрабатываю, мне нужно возвращать узел AST из каждой альтернативы, поскольку я хочу придерживаться текущей реализации AST в CPython.

Многие грамматики используют соглашение, позволяющее добавлять экшены к правилам — обычно это блок кода внутри {фигурных скобок}. Точнее, они привязаны к альтернативам. Код в этом блоке пишется на том же языке, что и остальной компилятор, например, на C, дополненный некоторой возможностью ссылки на элементы в альтернативе. В оригинальном pgen Python я не добавил этот функционал, но для нового проекта мне бы хотелось его реализовать.

Вот как мы это делаем для упрощённого генератора парсеров, который я разрабатываю в рамках этой серии постов.

Синтаксис для экшенов обычно такой:

rule: item item item { action 1 } | item item { action 2 }

Поскольку это делает грамматику более многословной, генераторы парсеров обычно допускают многострочные правила, например:

rule: item item item { action 1 }
    | item item { action 2}

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

Вечный вопрос — когда выполнять этот блок. В Yacc / Bison это делается сразу после того, как синтаксический анализатор распознает правило, поскольку нет отката по списку токенов. Выполнение каждого экшена ровно один раз означает, что там могут быть и глобальные побочные эффекты (такие как обновление таблицы символов или другой структуры данных компилятора).

В PEG-парсерах с их неограниченным возвратом по списку токенов у нас есть несколько вариантов:

• Не выполнять никаких экшенов, пока всё не будет проанализировано. Я не буду это рассматривать, так как хочу строить AST прямо во время разбора.
• Выполнять всякий раз, когда его альтернатива распознается. Требуется, чтобы их код был идемпотентным (т.е. имел одинаковый эффект независимо от того, сколько раз он был выполнен). Это означает, что экшен может быть выполнен, но его результат в конечном итоге может быть отброшен.
• Кэшировать результат и выполнять экшен только в первый раз — когда его альтернатива распознаётся в данной позиции.

Я выбрал третий вариант — мы в любом случае кэшируем результат работы метода с помощью алгоритма packrat, поэтому мы также можем кэшировать и результаты.

Что касается содержимого в {curlies}, то по традиции там используется код на C с соглашением на базе $ для ссылки на элементы в распознанной альтернативе (например, $1 для ссылки на первый элемент) и присвоение $$ для указания результата экшена. Это звучит очень старомодно (у меня есть воспоминания об использовании присваивания имени функции в Algol-60 для указания возвращаемого значения), поэтому я сделаю более Pythonic: внутри скобок вам нужно будет поместить один expression, результатом которого будет результат экшена, а ссылки на элементы будут простыми именами, дающими текст элемента. В качестве примера, вот простой калькулятор, который может добавлять и вычитать числа:

start: expr NEWLINE { expr }
expr: expr '+' term { expr + term }
    | expr '-' term { expr - term }
    | term { term }
term: NUMBER { float(number.string) }

Выполним его на примере 100 + 50 - 38 - 70. Он вычислит ответ, т.к. он распознает части, вычисляя ((100 + 50) - 38) - 70, что, конечно, равно 42.

Одна маленькая деталь: в экшене для term переменная number содержит объект TokenInfo, поэтому там нужно использовать его атрибут .string для получения токена в строковой форме.

Что мы делаем, когда у альтернативы есть несколько вхождений с одинаковым именем правила? Генератор парсера даёт каждому вхождению уникальное имя, добавляя 1, 2 и т.д. К последующим вхождениям в рамках одной и той же альтернативы. Например:

factor: atom '**' atom { atom ** atom1 }
      | atom { atom }

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

python3.8 -m story5.driver story5/calc.txt -g story5.calc.CalcParser

Визуализация теперь позволяет перемещаться назад и вперед с помощью клавиш со стрелками влево и вправо!

Лицензия на эту статью и приведенный код: CC BY-NC-SA 4.0