Парсеры с состоянием и нехватка полиморфизьма

Некоторое время назад меня пытались убедить, что Окамл недостаточно хорош для парсер-комбинаторов, потому что стоит попытаться добавить в парсеры состояние, как тут же возникают трудности, связанные с нехваткой полиморфизма. Проблема там вот в чем. Мой вариант простых парсеров не содержал состояния, и парсером там была функция типа 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

( Read more... )