Небольшое введение в библиотеку LPEG для новичков

Введение

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

Что такое LPEG?

LPEG это Parsing Expression Grammars For Lua (c) LPEG это библиотека для Lua, написанная одним из создателей последнего, которая позволяет работать с PEG в Lua. Взять её можно тут, в сборку SciTE-Ru она включена по-умолчанию.

Что такое PEG?

Расшифровывается PEG как Parsing Expression Grammars, подробно об этом есть в Википедии. Если коротко: это один из удобных способов задания формальных грамматик. Это страшное словосочетание из теории формальных языков на самом деле знакомо большинству програмистов: каждый раз изобретая регулярное выражение вы делаете ничто иное как описание формальной грамматики. Различия же:

в "мощности": при помощи PEG можно описать гораздо больше языков, чем регулярными выражениями ("чистыми" регулярными выражениями невозможно проверить, сбалансированные ли скобки в строке. В PCRE если я не ошибаюсь, такая возможность есть);
и в "читаемости": что делает вот это регулярное выражение: ("(\\"|\\\\|[^"])*"|/\*.*\*/|//[^\r]*) (оно ловит комментарии в С-подобном языке);

Модуль lpeg.re

Этот модуль позволяет записывать в коде скрипта паттерны очень близко к "книжной" форме, поэтому знакомство с LPEG имеет смысл начинать с него. Я не буду подробно останавливаться на описании синтаксиса и самого модуля, это есть в документации, вместо этого почти сразу перейду к примерам.

re.find vs re.match

re.find (subject, pattern [, init]) начиная с позиции init ищет в строке subject место, где выполняется pattern

re.match (subject, pattern) проверяет строку subject на соответствие pattern (т.е. как бы автоматически ставит символ ^ в начало регулярного выражения - если бы это были регулярные выражения - проверяя pattern только в начале строки).

re.compile

re.compile (string, [, defs]) компилирует грамматику, заданную в PEG, в паттерн.

Простые примеры

Является ли строка числом?

#!lua
print( re.match('123','[0-9]+') ) --> 4
print( re.match('text','[0-9]+') ) --> nil
print( re.match('123text','[0-9]+') ) --> 4

По результату в третьей строчке мы видим, что паттерн [0-9]+ несовершенен. Он соответствует регэкспу ^[0-9]+, а нужен ^[0-9]+$. Для этого используется паттерн !., который можно прочесть так: В этом месте не должно быть любого символа (! - отрицание, . - любой символ). Наш паттерн выглядит теперь так:

#!lua
print( re.match('123','[0-9]+!.') ) --> 4
print( re.match('123text','[0-9]+!.') ) --> nil

и возвращает верный результат.

Если же задача найти число в строке, то можно воспользоваться функцией re.find:

#!lua
print( re.find('text123text','[0-9]+') ) --> 5
print( re.find('text123text','{[0-9]+}{}') ) --> 5 123 8

Разберём результаты: первый паттерн нашёл число 123 начиная с пятого символа, а функция find вернула этот номер. Во втором паттерне пары { и }: { p } означает верни текст, на котором сработал p, а {} - верни текущую позицию.

С функцией re.match сложнее (она проверяет паттерн только в начале строки), нужно изменить паттерн так, чтобы он "сам" искал то, что нам нужно:

#!lua
print( re.match('text123text','({}{[0-9]+}{} / .)*') ) --> 5 123 8

Он работает следующим образом:

Проверить [0-9]+ в текущей позиции. Если подходит, то вернуть позицию начала числа, само число и позицию его окончания. Или (символ /)
Проверить . в текущей позиции, т.е. пропустить один символ. Если пропускать нечего, то закончить.
Перейти на 1. (повтор обеспечивает символ *)

Примеры с грамматиками

(Не зря же я столько написал про PEG)

Проверка сбалансированных скобок:

#!lua
b = re.compile[[  balanced <- "(" ([^()] / balanced)* ")"  ]]
print(b:match'(some(balanced(brackets)()))') --> 29
print(b:match'(some(un(balanced(brackets)()))') --> nil
print(b:match('(a)(x')) --> 4

Остановимся на первой строчке подробнее: Первое правило грамматики считается корнем, в нашем случае это balanced

Раскрывается (проверяется) оно так:

Проверяем наличие символа (
Внутри скобок 0 или более раз может встречаться одно из двух: любой символ, кроме (), или подстрока, соответствующая правилу balanced
Проверяем наличие символа )

Данная грамматика работает только для строк, начинающихся со скобки, к тому же, позиция остановки возможно не совсем то, что нам надо (см. 3 строку). Исправим эти недостатки:

#!lua
b = re.compile[[  balanced <- [^()]* "(" ([^()] / balanced)* ")" [^()]* ]]

#!lua
b = re.compile[[  
    btext <- balanced !.
    balanced <- [^()]* "(" ([^()] / balanced)* ")" [^()]* 
]]
print(b:match'__(some(balanced(brackets)()))') --> 31
print(b:match'(some(un(balanced(brackets)()))') --> nil
print(b:match('text(a)text(x')) --> nil

Теперь перед открывающей и после закрывающей скобок допустимы любые символы (кроме скобок, [^()]*)
Останавливаться паттерн должен в конце строки (!.)

Поиск кода цвета в строке

Цвета задаются последовательностью #hex, где hex - 2,4 или 6 16-ричных цифр.

#!lua
local search_hex = re.compile[[
    hex <- "#" {HH HH^-2} / [^#]+ hex
    HH <- HEXDIGIT HEXDIGIT
    HEXDIGIT <- [0-9A-Fa-f]
]]
print(search_hex:match'as#124AFD123qwe') --> 124AFD
print(search_hex:match'#AF1') --> AF1
print(search_hex:match'#A') --> nil

где HH^-2 означает от 0 до 2х раз паттерн HH

Понятное дело, то же самое можно записать и короче, но тогда пострадает читаемость.

to be continued...

Wiki

scite-ru.bitbucket.org / LPEG_Usage