Рекурсия в парсер-комбинаторах

[thedeemon]

Я летом писал про классические парсер-комбинаторы на Окамле и жаловался, что у меня не получилось сделать рекурсивные, вроде такого:

let rec p_exp =  p_char 'a' ||| (p_char '(' >>> p_exp >>> p_char ')')

Такой парсер должен разбирать строки 'a', '(a)', '((a))' и т.д., но ругаться на '((a)'.

При попытке компиляции приведенной строчки выдавалось малоинформативное сообщение This kind of expression is not allowed as right-hand side of `let rec'. Оказывается, все очень просто. В правой части let rec может быть очень ограниченный набор конструкций, если они содержат одно из рекурсивно определяемых имен. Одна из поддерживаемых - fun. Все начинает компилироваться и правильно работать, если обернуть правую часть в нее:

let rec p_exp = fun s -> (p_char 'a' ||| (p_char '(' >>> p_exp >>> p_char ')')) s

Comments

[thedeemon.livejournal.com]

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