Парсеры с состоянием и нехватка полиморфизьма
Некоторое время назад меня пытались убедить, что Окамл недостаточно хорош для парсер-комбинаторов, потому что стоит попытаться добавить в парсеры состояние, как тут же возникают трудности, связанные с нехваткой полиморфизма. Проблема там вот в чем. Мой вариант простых парсеров не содержал состояния, и парсером там была функция типа char list -> 'a parse_result, где тип результата выглядел так:
type 'a parse_result = Parsed of 'a * char list | Failed
В определенном смысле какое-то состояние в таких парсерах есть - это текущая позиция в разбираемом тексте, определяемая неразобранным остатком текста, возвращаемым в случае успеха. Для разбора контекстно-зависимых грамматик иногда хочется, чтобы парсер имел какое-то дополнительное состояние. Например, при разборе текста на С++ хорошо бы помнить имена описанных ранее классов, чтобы понимать, что означает some_name(42). Расширим наше определение парсера и добавим передачу произвольного состояния:
type ('res, 'state) parse_result =
Parsed of 'res * ('state * char list) | Failed
Парсер будет принимать на вход не просто список символов, а пару из состояния и списка символов. На выходе будет только что описанный parse_result, возможно с новым состоянием.
Тогда базовый парсер, разбирающий один символ, удовлетворяющий заданному предикату, будет выглядеть так:
let p_pred p (st, lst) =
match lst with
| [] -> Failed
| h::t -> if p h then Parsed(h, (st, t)) else Failed
Теперь попробуем его использовать для описания парсера, разбирающего одну цифру:
let isdigit c = c>='0' && c<='9'
let p_digit = p_pred isdigit
При попытке это скомпилировать окамл ругается:
The type of this expression, '_a * char list -> (char, '_a) parse_result, contains type variables that cannot be generalized.
Фишка в том, что мы использовали карринг, опустив последний параметр p_pred, но этот параметр должен быть полиморфным - он содержит состояние, тип которого еще не определен. Алгоритм вывода типов в окамле умеет выводить полиморфные типы для имен, заданных в конструкции let, но не для тех, что были опущены при карринге. Простейшим решением проблемы было бы дописать недостающий параметр:
let p_digit s = p_pred isdigit s
Такой вариант компилируется нормально, но это некрасиво, т.к. придется везде писать эти лишние параметры, код раздуется, потеряется DSL-ность. Однако выход есть, и очень простой!
Вынесем типовый параметр состояния на уровень выше - в параметр модуля.
Заключим нашу библиотеку комбинаторов в функтор:
module Parsers(S : sig type t end) = struct
type 'res parse_result = Parsed of 'res * (S.t * char list) | Failed
...(* здесь все базовые комбинаторы *)
end
Теперь
let p_digit = p_pred isdigit
прекрасно компилируется, т.к. тип опущенного параметра известен, он содержит тип состояния S.t, который будет передан функтору при его использовании.
Базовые комбинаторы выглядят практически так же, как в случае без состояния:
let p_many p =
let rec loop s =
match p s with
| Parsed(_, s') -> loop s'
| Failed -> Parsed((), s) in
loop
let (>>>) p1 p2 s =
match p1 s with
| Parsed(_, s') -> p2 s'
| Failed -> Failed
let p_many1 p = p >>> p_many p
let (>>=) p1 f s =
match p1 s with
| Parsed(x, s') -> f x s'
| Failed -> Failed
let return x s = Parsed(x, s)
let updateState f (st, lst) = Parsed((), (f st, lst))
А вот так выглядит их использование. Сделаем парсер, принимающий непустую последовательность маленьких латинских букв и подсчитывающий количество вхождений буквы 'e', причем это количество будет храниться в состоянии парсера, т.е. в данном случае тип состояния - int:
let isalpha c = c>='a' && c<='z'
module P = Parsers(struct type t = int end)
open P
let myletter =
p_pred isalpha >>= fun c ->
if c='e' then updateState ((+) 1) else return ()
let parser = p_many1 myletter
Используем его для подсчета вхождений буквы 'e' в слове 'engineering':
let lst = String.explode "engineering" in
match parser (0, lst) with
| Parsed(_, (n, _)) -> print_int n
| Failed -> print_string "failed"
Запускаем, получаем ответ - 3. Парсеры с состоянием готовы, все базовые комбинаторы от типа состояния абстрагированы, использование их требует лишь пары дополнительных строк: передать в функтор тип состояния и открыть получившийся модуль.
type 'a parse_result = Parsed of 'a * char list | Failed
В определенном смысле какое-то состояние в таких парсерах есть - это текущая позиция в разбираемом тексте, определяемая неразобранным остатком текста, возвращаемым в случае успеха. Для разбора контекстно-зависимых грамматик иногда хочется, чтобы парсер имел какое-то дополнительное состояние. Например, при разборе текста на С++ хорошо бы помнить имена описанных ранее классов, чтобы понимать, что означает some_name(42). Расширим наше определение парсера и добавим передачу произвольного состояния:
type ('res, 'state) parse_result =
Parsed of 'res * ('state * char list) | Failed
Парсер будет принимать на вход не просто список символов, а пару из состояния и списка символов. На выходе будет только что описанный parse_result, возможно с новым состоянием.
Тогда базовый парсер, разбирающий один символ, удовлетворяющий заданному предикату, будет выглядеть так:
let p_pred p (st, lst) =
match lst with
| [] -> Failed
| h::t -> if p h then Parsed(h, (st, t)) else Failed
Теперь попробуем его использовать для описания парсера, разбирающего одну цифру:
let isdigit c = c>='0' && c<='9'
let p_digit = p_pred isdigit
При попытке это скомпилировать окамл ругается:
The type of this expression, '_a * char list -> (char, '_a) parse_result, contains type variables that cannot be generalized.
Фишка в том, что мы использовали карринг, опустив последний параметр p_pred, но этот параметр должен быть полиморфным - он содержит состояние, тип которого еще не определен. Алгоритм вывода типов в окамле умеет выводить полиморфные типы для имен, заданных в конструкции let, но не для тех, что были опущены при карринге. Простейшим решением проблемы было бы дописать недостающий параметр:
let p_digit s = p_pred isdigit s
Такой вариант компилируется нормально, но это некрасиво, т.к. придется везде писать эти лишние параметры, код раздуется, потеряется DSL-ность. Однако выход есть, и очень простой!
Вынесем типовый параметр состояния на уровень выше - в параметр модуля.
Заключим нашу библиотеку комбинаторов в функтор:
module Parsers(S : sig type t end) = struct
type 'res parse_result = Parsed of 'res * (S.t * char list) | Failed
...(* здесь все базовые комбинаторы *)
end
Теперь
let p_digit = p_pred isdigit
прекрасно компилируется, т.к. тип опущенного параметра известен, он содержит тип состояния S.t, который будет передан функтору при его использовании.
Базовые комбинаторы выглядят практически так же, как в случае без состояния:
let p_many p =
let rec loop s =
match p s with
| Parsed(_, s') -> loop s'
| Failed -> Parsed((), s) in
loop
let (>>>) p1 p2 s =
match p1 s with
| Parsed(_, s') -> p2 s'
| Failed -> Failed
let p_many1 p = p >>> p_many p
let (>>=) p1 f s =
match p1 s with
| Parsed(x, s') -> f x s'
| Failed -> Failed
let return x s = Parsed(x, s)
let updateState f (st, lst) = Parsed((), (f st, lst))
А вот так выглядит их использование. Сделаем парсер, принимающий непустую последовательность маленьких латинских букв и подсчитывающий количество вхождений буквы 'e', причем это количество будет храниться в состоянии парсера, т.е. в данном случае тип состояния - int:
let isalpha c = c>='a' && c<='z'
module P = Parsers(struct type t = int end)
open P
let myletter =
p_pred isalpha >>= fun c ->
if c='e' then updateState ((+) 1) else return ()
let parser = p_many1 myletter
Используем его для подсчета вхождений буквы 'e' в слове 'engineering':
let lst = String.explode "engineering" in
match parser (0, lst) with
| Parsed(_, (n, _)) -> print_int n
| Failed -> print_string "failed"
Запускаем, получаем ответ - 3. Парсеры с состоянием готовы, все базовые комбинаторы от типа состояния абстрагированы, использование их требует лишь пары дополнительных строк: передать в функтор тип состояния и открыть получившийся модуль.