Потоковые процессоры для разбора текста

Что такое потоковые процессоры и зачем они нужны?

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

Потоковые процессоры представляют собой реагирующую систему а-ля Hoare CSP (Communicating Sequential Processes). Они получают сообщения из какого-то множества входных и выдают на выход результат - значения из множества выходных значений.

В принципе, разборщик методом "в ширину" и представляет из себя такой потоковый процессор - на входе он получает очередной символ входного потока а на выход выдает возможный результат успешного разбора (если он существует для уже просмотренной строки). Вот его-то мы и попытаемся построить.

Как их строить

Тип данных для потоковых процессоров:

data SP i o =
        Null
    |   Get (i -> SP i o)
    |   Put 0 (SP i o)

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

Дополнительные примитивы

Нам понадобится функция mapSP, принимающая на вход функцию и процессор, и применяющая функцию ко всем результатам работы процессора.

mapSP f Null = Null
mapSP f (Put o sp) = Put (f o) (mapSP f sp)
mapSP f (Get spf) = Get (\i -> mapSP f (spf i))

Вроде, все просто: в пустом процессоре отображать нечего, для процессора с готовым выходом надо отобразить выход и результаты работы процессора-продолжения и для ожидающего сообщения процессора надо отобразить результаты процессора, полученного после разбора сообщения.

Примитивные парсеры

Разбор пустого входа

Первый парсер будет самым простым:

pempty x = Put x Null

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

Разбор входа из одного токена

Второй будет чуть сложнее:

ptoken t = Get (\i -> if i == t then Put i Null else Null)

Для того, чтобы разобрать входной токен, нам надо его получить (отсюда Get), и, если он эквивалентен требуемому (i == t), то вернуть именно входной токен (Put i ..), поскольку нам интересно то, что прийдет на вход, а не наш известный токен.

Эквивалентность токенов лучше всего проверять только по их тэгу, примерно так:

(TokenVariableName _) == (TokenVariableName _) == True

Поэтому, если мы получим на входе (TokenVariableName "x") то мы успешно сравним его с (TokenVariableName $ error "constant value"), но на выход попадет именно входной токен (TokenVariableName "x").

Простые парсеры закончились. ;)

Простые комбинаторы

Комбинатор альтернативного выбора

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

ppar (Put o sp) spb = Put o (sp `ppar` spb)
ppar sp (Put o spb) = Put o (sp `ppar` spb)

Особого значения порядок выдачи готовых данных не имеет. Поэтому "левая альтернатива вперед" - вполне достойный выбор.

ppar Null sp = sp
ppar sp Null = sp

Если нам нечего выбирать в одной из альтернатив, то мы перейдем к другой.

Остается только вариант, когда обе альтернативы ждут входной токен:

ppar (Get fa) (Get fb) = Get (\i -> (fa i) `ppar` (fb i))

Комбинатор последовательного разбора

pseq Null _ = Null

Если мы не смогли разобрать начало строки, то мы гарантировано не сможем разобрать всю строку.

pseq (Get fsp) spb = Get (\i -> (fsp i) `pseq` spb)

Если мы ждем токен, необходимый для разбора префикса строки, то мы должны подождать этот токен (Get), получить вытекающий из него разборщик начала строки за входным токеном (fsp i) и продолжить разбор строки (`pseq` spb).

А если у нас есть готовый выход, то мы считаем его функцией, которую мы применим к результату разбора остатка входной строки. И, также, нам надо разобрать новый префикс (sp из первого Put) и еще один суффикс (spb). Возможно, один из этих вариантов сработает, поэтому мы используем ppar.

pseq (Put o sp) spb =(mapSP o spb) `ppar` (sp `pseq` spb)

Тип pseq на данный момент будет:

pseq :: SP i (a->b) -> SP i a -> SP i b

Его можно реализовать и так, что он будет иметь тип

pseq :: SP i a -> (a -> SP i b) -> SP i b

тогда можно будет реализовать класс Monad, и использовать do-нотацию.

Бонус ;)

pfail = Null

Все понятно? ;)

Применение разбора ко входу

prun parser tokens = runp parser tokens
	where
		runp (Put o sp) tokens = (o,tokens):runp sp tokens
		runp Null tokens = []
		runp (Get f) [] = []
		runp (Get f) (t:ts) = runp (f t) ts

Мы запустим выполнение потокового процессора, комбинируя выдаваемые им результаты с оставшимся списком входных токенов. Если потоковый процессор пуст, то мы завершим работу. Если для продолжения разбора требуется токен, но его нет - мы завершим работу. Если же токен есть, то мы применим его (f t), получим новый потоковый процессор и продолжим разбор с оставшимся входом.

Пример

Реализация разбора списка:

pmany p = pmany1 p `ppar` pempty []

Она основана на разборе списка из одного и более элементов:

pmany1 p = (pempty (:) `pseq` p) `pseq` pmany p

которая основана на разборе списка элементов.

Вот, как этим пользоваться:

test = pmany (ptoken '1' `ppar` ptoken '2')

И результат использования:

Parser> prun (pmany $ (ptoken '1' `ppar` ptoken '2')) "1213"
[("","1213"),("1","213"),("12","13"),("121","3")]
(557 reductions, 871 cells)
Parser>

Вот. Мы сконструировали разборщик, который умеет распознавать список из единичек и/или двоечек, и применили его ко входу, который содержит неверный символ - '3'.

В результате мы получили список промежуточных результатов, последний из которых не содержал пустой список в качестве остатка входа, что означает ошибку.

Итоги

В двадцать восемь строчек кода (в строке "В двадцать восемь строчек кода" двадцать шесть букв) мы получили работающий набор комбинаторов и функций для разбора и даже один полезный парсер - парсер списка.

Haskell never ceases to amuze me. ;)

Заключение

В этом подходе, тем не менее, есть серьезный недостаток - этот набор комбинаторов не очень подходит для реального использования. Даже при реализованном предпросмотре мне не удалось добиться достаточной эффективности: токенизер из строки в несколько токенов разных типов благополучно исчерпывает всю память на довольно коротких строчках. У него получается не линейная, а более высокой степени полиномиальная зависимость от длины входа (но не экспонента, что тоже хорошо).

В чем дело - пока не знаю, просто не было времени разобраться.

Может, вы попробуете? ;)