• ‡ Пример: синтаксический анализатор языка a^n b^n c^n (где а,b,c -- символы алфавита, ^n -- n вхождений подряд). Плохой вход должен детектироваться максимально рано.

В основном это перепечатка хранилища 2021 года, т.к. у них оказалось действительно добротно расписано.

А также добротно расписано в 6-м.

<aside> 💡 Парсер — функция, преобразующая последовательность символов в некоторую более сложную структуру.

“Подход, который позволяет из строчечки делать AST вашего мини-языка”

</aside>

<aside> 💡 Парсер-комбинаторы — функции высшего порядка, которые принимают парсеры и, комбинируя их, возвращают парсер.

</aside>

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

module Parser = struct
 type input = char list (** Тип строки может быть более эффективным *)

 type 'a parse_result =
   | Failed
   | Parsed of 'a * input (** Текущий результат и оставшаяся строка *)

 type 'a t = input -> 'a parse_result (** Тип парсера *)

 let return x s = Parsed (x, s)
 let fail _ = Failed

 let ( >>= ) p f s =
   match p s with
   | Failed -> Failed
   | Parsed (h, tl) -> f h tl
 ;;
end

Принципы работы парсеров:

• Парсер имеет доступ к последовательности символов лишь с её начала, то есть не может обработать часть последовательности, находящуюся в её середине, не обработав её начало.
• Если некоторый парсер в последовательности провалил свою работу, то последующие не выполняют никаких вычислений, то есть парсинг в данной “ветви монады” прекращается.
• Парсер, проваливший свою работу, не изменяет оставшуюся последовательность символов.

Примеры “базовых” парсеров:

• “Взятие” указанного символа из последовательности: если следующий символ — указанный, то вернуть его, иначе провалиться.

  let char c = function
   | h :: tl when c = h -> return c tl
   | _ -> Failed
  ;;
  

• Проверка удовлетворения следующим символов условия: вернуть символ, если удовлетворяет, иначе — провалиться.

let satisfy cond = function
 | h :: tl when cond h -> return h tl
 | _ -> Failed
;;

• Запустить некоторый парсер и забыть его результат — нужно, чтобы “удалить” из последовательности символов ненужные, так как иначе парсер не будет иметь доступ к последующим символам.