37 Грамматики разбора на основе выражений

Emacs Lisp предоставляет несколько инструментов для разбора и сопоставления текста, от регулярных выражений (см. Регулярные выражения) до полноценных грамматических анализаторов, работающих слева направо (т.н. LL) (см. (bovine)Разработка парсера Bovine). Грамматики разбора на основе выражений (PEG) представляют собой ещё один подход к разбору текста, который предлагает больше структурированности и компонуемости, чем регулярные выражения, но меньшую сложность, чем контекстно-свободные грамматики.

Грамматика разбора на основе выражений (PEG) описывает формальный язык в терминах набора правил для распознавания строк в этом языке. В Emacs PEG-парсер определяется как список именованных правил, каждое из которых сопоставляет текстовые шаблоны и/или содержит ссылки на другие правила. Разбор инициируется функцией peg-run или макросом peg-parse (см. ниже) и разбирает текст после точки в текущем буфере, используя заданный набор правил.

Каждое правило в PEG называется разбирающим выражением (PEX) и может быть задано как литеральная строка, символьный диапазон или набор, подобный регулярному выражению, конструкция, специфичная для PEG, напоминающая вызов функции Emacs Lisp, ссылка на другое правило или комбинация любых из этих элементов. Грамматика выражается в виде дерева правил, в котором одно правило обычно рассматривается как “корневое” или “входное” правило. Например:

((number sign digit (* digit))
 (sign   (or "+" "-" ""))
 (digit  [0-9]))

После определения грамматики могут использоваться для разбора текста после точки в текущем буфере различными способами. Макрос peg-parse является самым простым:

Макрос: peg-parse &rest pexs ¶

Сопоставить pexs в точке.

(peg-parse
  (number sign digit (* digit))
  (sign   (or "+" "-" ""))
  (digit  [0-9]))

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

Макрос: with-peg-rules rules &rest body ¶

Выполнить body с rules, списком PEX, в действии. Внутри BODY разбор инициируется вызовом peg-run.

Функция: peg-run peg-matcher &optional failure-function success-function ¶

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

По окончании разбора вызывается одна из функций failure-function или success-function, в зависимости от того, удался ли разбор или нет. Если предоставлена success-function, она должна быть функцией, которая принимает в качестве единственного аргумента анонимную функцию, выполняющую все действия, собранные в стеке во время разбора. По умолчанию эта анонимная функция просто выполняется. Если разбор завершается неудачей, будет вызвана функция, переданная как failure-function, со списком выражений PEG, которые не удалось сопоставить во время разбора. По умолчанию этот список отбрасывается.

Аргумент peg-matcher, передаваемый в peg-run, создаётся вызовом peg:

Макрос: peg &rest pexs ¶

Преобразовать pexs в единое сопоставляющее выражение (peg-matcher), пригодное для передачи в peg-run.

Приведённый выше пример peg-parse раскрывается в набор вызовов этих функций и может быть записан полностью как:

(with-peg-rules
    ((number sign digit (* digit))
     (sign   (or "+" "-" ""))
     (digit  [0-9]))
  (peg-run (peg number)))

Такой подход обеспечивает более явный контроль над “входной точкой” разбора и позволяет комбинировать правила из разных источников.

Отдельные правила также можно определять с помощью синтаксиса, более похожего на defun, используя макрос define-peg-rule:

Макрос: define-peg-rule name args &rest pexs ¶

Определить name как PEG-правило, которое принимает args и сопоставляет pexs в точке.

Например:

(define-peg-rule digit ()
  [0-9])

Аргументы могут передаваться правилам с помощью PEG-правила funcall (см. Определения PEX).

Другая возможность — определить именованный набор правил с помощью define-peg-ruleset:

Макрос: define-peg-ruleset name &rest rules ¶

Определить name как идентификатор для rules.

(define-peg-ruleset number-grammar
  ;; `digit' здесь ссылается на определение выше.
  (number () sign digit (* digit))
  (sign () (or "+" "-" "")))

Определённые таким образом правила и наборы правил могут использоваться по имени в последующих вызовах peg-run или with-peg-rules:

(with-peg-rules number-grammar
  (peg-run (peg number)))

По умолчанию вызовы peg-run или peg-parse не дают никакого вывода: разбор просто перемещает точку. Чтобы возвращать или иным образом действовать на разобранные строки, правила могут включать действия, см. Действия при разборе.

• Определения PEX
• Действия при разборе
• Написание PEG-правил