PEG: грамматики вместо регулярок

В Janet нет регулярных выражений. Вместо них PEG прямо в стандартной библиотеке. Это не бедность, а выбор, и в этом уроке разберём, чем он оплачен и что даёт взамен.

Почему не регулярные выражения

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

{:pair (* "(" :nested ")")
 :nested (any :pair)
 :main (* :nested -1)}

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

Регулярки нечитаемы. Выражение вида ^(?:[a-z]+)=(?:[^\n]*)$ приходится расшифровывать посимвольно. PEG-грамматика это обычные структуры данных Janet: их можно отформатировать, прокомментировать, собрать из частей программно.

PEG-грамматику можно собирать из кусков. Правила это записи в таблице, их можно переиспользовать, подменять и генерировать. Регулярка это монолитная строка.

Цена. PEG многословнее. Для задачи “найти в строке подстроку из цифр” регулярка короче. Поэтому в Janet для простых задач есть string/find, string/split, string/replace, и начинать стоит с них. PEG берут тогда, когда структура сложнее одного шаблона.

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

Первое совпадение

peg/match принимает шаблон и строку:

Два момента сразу сбивают с толку.

Тильда ~ обязательна. Шаблон это структура данных, и её надо процитировать, иначе Janet попытается её вычислить. Механика та же, что в уроке про код как данные.

Пустой массив @[] означает успех. Результат peg/match это массив захватов. Если захватов не просили, массив пуст, но он не nil, а значит истинен. Не совпало это nil.

Совпадение начинается с начала строки, но не обязано доходить до конца:

Искать по всей строке умеют peg/find и peg/find-all, их разберём в 31-janet/11 · Захваты, именованные правила и парсер конфига.

Дальше по уроку держи под рукой песочницу: она разбирает шаблоны по-настоящему, так что любой пример можно поменять и посмотреть, что будет.

Примитивы

Строка совпадает сама с собой:

Число N совпадает с любыми N символами:

Отрицательное число проверяет, что осталось меньше стольких символов. Сначала два голых примера:

-1 значит “осталось меньше одного символа”, то есть ноль. Отсюда идиома, которая читается как “здесь конец строки”:

Классы символов записываются ключевыми словами:

Класс	Что совпадает
:d	цифра
:a	буква ASCII
:w	буква или цифра
:s	пробельный символ
:h	шестнадцатеричная цифра

Заглавная буква означает отрицание: :D не цифра, :S не пробел.

Диапазон и множество задают классы вручную:

Комбинаторы

Полная форма	Короткая	Смысл
(sequence a b)	(* a b)	сначала a, затем b
(choice a b)	(+ a b)	a или b, первый подошедший
(any x)		ноль или больше x
(some x)		один или больше x
(between 2 3 x)		от двух до трёх x
(not x)	(! x)	x здесь нет, ввод не потребляется
(look 0 x)	(> 0 x)	x здесь есть, ввод не потребляется

Короткие формы это то, что ты увидишь в реальном коде, поэтому дальше берём их. Ноль в look это смещение: проверяем прямо в текущей позиции, не сдвигаясь. Другое смещение понадобится редко.

Выбор не откатывается, и это главное отличие от регулярок. (+ a b) берёт первую подошедшую альтернативу и назад не возвращается. Проследим по шагам, как (* (+ "=" "==") -1) разбирает строку ==:

1. Выбор пробует первую альтернативу "=". Совпала, съеден один символ.
2. Выбор на этом закончен: первая подошедшая победила, остальные больше не рассматриваются.
3. Грамматика идёт дальше, к -1. А в строке остался второй =, так что это тупик.
4. Вернуться внутрь выбора и попробовать "==" PEG не станет. Итог: nil.

Практическое следствие: более длинные альтернативы ставь первыми. (+ "==" "=") разберёт ==, а (+ "=" "==") не разберёт никогда, потому что сначала совпадёт одиночное =. Попробуй оба порядка в песочнице выше, пресет “упорядоченный выбор” стоит именно на этой ловушке.

Грамматика из правил

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

Правило :pair требует открывающую скобку, что-то вложенное и закрывающую. :nested это ноль или больше пар. Рекурсия между ними и даёт вложенность любой глубины, ту самую, на которой регулярка сдаётся. Этого синтаксиса хватит для домашки; всерьёз именованные правила поработают в следующем уроке, в парсере конфига.

Что запомнить

• В Janet нет регулярок, есть PEG в стандартной библиотеке.
• Тильда перед шаблоном обязательна: шаблон это данные.
• @[] это успех без захватов, nil это провал.
• Совпадение идёт с начала строки и не обязано доходить до конца.
• Число N это N любых символов, -1 это конец строки.
• Классы :d :a :w :s :h, заглавная буква означает отрицание.
• * последовательность, + выбор, any и some повторения, ! и > предикаты без потребления ввода.
• Выбор упорядоченный и без отката. Длинные альтернативы ставь первыми.
• Таблица правил: :main это вход, правила ссылаются друг на друга по имени, рекурсия разрешена.

Упражнения

Дальше

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