Общая идея
Мне нужны были эффективные комбинаторы для создания парсеров типа Строка -> СинтаксическоеДерево. Причем, что самое интересное, мне было необходимо разбирать текст пошагово, имея на каждом шагу информацию о будущих возможных символах - так называемое "множество первых символов" текущей части грамматики.
Здесь я и попытаюсь описать процесс их построения (кстати, я еще не закончил).
Общие идеи я почерпнул из "Deterministic, Error-Correcting Combinator Parsers" by S. Doaitse Swierstra and Luc Duponcheel.
Общий набор комбинаторов
Для работы нам потребуются следующие комбинаторы:
pempty :: a -> p s a
psym :: s -> p s a
ppar :: Ord s => p s a -> p s a -> p s a
pseq :: Ord s => p s (a -> b) -> p s a -> p s b
pisempty :: p s a -> Bool
pfset :: Show s => p s a -> String
- pempty: позволяет создать разборщик, который на вход принимает пустую строку (тот тип разборщика, который подходит для разбора конца файла).
- psym: создает разборщик, принимающий на вход входной символ, и возвращающий его же.
- ppar: из двух разборщиков p и q выражение p `ppar` q сконструирует разборщик, который может разобрать либо p либо q.
- pseq: из разборщика p, выдающего на выход функцию a->b и разборщика q, выдающего на выходе значение типа a создаст разборщик, который разберет последовательное соединение всех строк p со всеми строками q и на выходе даст значение типа b.
- pisempty: может ли данный разборщик разобрать пустую строку?
- pfset: вернет строковое представление возможных значений, которые может принять на вход данный разборщик.
Поскольку мы будем последовательно строить несколько разных версий наших комбинаторов и при создании очередных будем активно пользоваться предыдущими, то всем им мы будем давать различные префиксы - empty_psym, firstset_pempty...
Итак, создайте файл p.hs, загрузите его в ghci (ghci -fglasgow-exts p.hs) или в hugs (hugs -98 p.hs), откройте его же в редакторе и начнем.
Разбор пустой строки
----------------------------------------------------------------------------------------------------------
-- empty parsers
data E s a =
E (Maybe a)
empty_pempty x = E (Just x)
empty_psym s = E Nothing
empty_ppar a@(E (Just ae)) _ = E $ Just ae
empty_ppar _ (E b) = E b
empty_pseq (E Nothing) _ = E Nothing
empty_pseq (E (Just f)) (E be) = E $ case be of
Just x -> Just $ f x
Nothing -> Nothing
empty_pisempty (E (Just x)) = True
empty_pisempty _ = False
empty_pfset (E (Just x)) = "deriving empty"
empty_pfset _ = ""
To be continued
