Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
250 lines (187 sloc) 10.2 KB

Stream Parsers

Первое расширение, предоставляемое Camlp4, – это потоки и парсеры. Поток является значением абстрактного типа 'a Stream.t и похож на список, но в отличие от списка, нам всегда доступен только первый элемент потока. Чтобы получить следующий элемент потока, необходимо удалить предыдущий элемент из потока. Парсер потока – это функция типа 'a Stream.t -> 'b, которая разбирает поток по образцам.

Как комилировать?

Параметр коммандной строки -pp camlp4o для ocamlc/ocamlopt.

Если используется ocamlbuild, то добавить тэг camlp4o. В _tags:

# my_parser использует синтаксис stream parsers
"my_parser.ml": camlp4o

В toplevel:

# #load "dynlink.cma";;
# #load "camlp4of.cma";;
        Camlp4 Parsing version 3.12.1

Потоки

Конструкторы потока

Первый способ создания потока – использование скобок [< и >]. (написать про элементы с ' и без него)

Примеры:

[< '3; '1; '4; '1; '5 >]

Это поток чисел 3, 1, 4 и 5.

# let s = [< '"hello"; '"world" >];;
# let t = [< '"I"; '"say"; s; '"as"; '"an"; '"example" >];;

Этот поток t – поток строк "I", "say", "hello", "world", "as", "an", "example".

Чтобы посмотреть (деструктивно) внутрь потока, мы использовам функцию Stream.next, которая вынимает первый элемент из списка.

Потоки являются ленивыми значениями, так что можно создавать бесконечные потоки, например, как этот поток всех натуральных чисел:

# let rec f n = [< 'n; f (n + 1) >];;
# let s = f 0;;

Построение потоков

Второй способ создания потоков – строители потоков.

  • Stream.of_string возвращает символьный поток, состоящий из символов строки, переданной функции как параметр
  • Stream.of_channel возвращает поток символов ввода
  • Stream.of_list возвращает поток из элементов списка
  • Stream.from создает поток с помощью функции-генератора элементов потока

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

Парсеры

Парсеры – это функции, которые заглядывают внутрь потока. Парсер создается с помощью ключевого слова parser. Он похож на конструкцию языка OCaml function, но с образцами потока вместо просто образцов. Например, функция Stream.next, упомянутая выше, определяется так:

parser [< 'x >] -> x

FIXME что такое "образцы потоков", примеры, [< >], все конструкции обычного матчинга работают (включая 'a'..'z' и when).

Парсер может вернуть тремя разными способами:

  • вернуть регулярное значение, указывающее на то, что образец потока совместился с началом потока
  • вызвать исключение Stream.Failure, указывающее на то, что первый элемент образца не совместился с началом потока. В этом случае поток не модифицируется
  • вызвать исключение Stream.Error, указывающее на то, что первый элемент образца совместился с началом потока, но остальная часть образца не совместилась

Пример:

# let p = parser [< '3; '1; '4 >] -> "hey";;
# p [< '3; '1; '4 >];;
string : "hey"
# p [< '3; '1; '4; '1; '5; '9 >];;
string : "hey"
# p [< '1; '1; '4 >];;
Exception: Stream.Failure
# p [< '3; '2; '4 >];;
Exception: Stream.Error ""

Исключение Stream.Error имеет параметр – строку. Можно указать какую строку это исключение должно возвращать. В парсере, после элемента образца потока добавьте токен ?? и саму строку в двойных кавычках:

# let p = parser [< '3; '1 ?? "1 expected"; '4 ?? "4 expected" >] -> "hey";;

Заметим, что к первому элементу образца потока нельзя применить подобное дополнение, поскольку парсер вызывает исключение Stream.Failure, если начало потока не распознается.

Парсер может сам вызывать другой парсер. Вы можете указать его как элемент образца потока со следующим синтаксисом:

pattern = expression

Пример с рекурсивным вызовом:

# type tok = If | Then | Else | Let | In | Equal | Ident of int;;
# let rec expr = parser
    [< 'If; x = expr; 'Then; y = expr; 'Else; z = expr >] -> "if"
  | [< 'Let; 'Ident x; 'Equal; x = expr; 'In; y = expr >] -> "let"
  ;;

Заметим, что парсер сам по себе не является системой грамматик. Вы не можете использовать left recursion:

(* НЕВЕРНЫЙ ПРИМЕР! *)
# let rec expr = parser [< x = expr; 'Equal; y = expr >] -> x;;

Такая функция зациклится.

Вы также не сможете начать два образца потока тем же самым элементом. Только первый образец потока будет учтён.

# let rec expr = parser
    [< 'If; x = expr; 'Then; y = expr; 'Else; z = expr >] -> "if"
  | [< 'If; x = expr; 'Then; y = expr >] -> "ifnoelse"
  ;;

Если вы хотите делать это, вам нужно left factorize your rules:

# let rec expr = parser
    [< 'If; x = expr; 'Then; y = expr; v = expr_kont >] -> v
  and expr_kont = parser
      [< 'Else; z = expr >] -> "if"
    | [< >] -> "ifnoelse"
  ;;

или с использованием анонимного парсера:

# let rec expr = parser
    [< 'If; x = expr; 'Then; y = expr;
       v = parser
           [< 'Else; z = expr >] -> "if"
         | [< >] -> "ifnoelse" >] -> v
  ;;

TODO алгоритм работы парсера, выбор pattern'а по первому элементу, без откатов (в camlp5 есть функциональные потоки и парсеры с откатом), пример парсера из стрима в стрим

Возможно также использовать конструкцию when <условие> для элементов потока:

parser
  [< x when x <> ' '; ... >]

Действие аналогично использованию when в обычном паттерн матчинге. Из-за специфики потоков, если первый элемент потока был поглощён парсером, далее может быть только два варианта: успешное сопоставление с потоком или исключение Stream.Error. when с условием возвращающим false в начале образца потока вызовет исключение Stream.Failure (выбор другой ветки), в середине образца – Stream.Error.

Отладка

Синтаксис парсеров потоков предоставляется Camlp4-расширением синтаксиса OCaml. Как и для любого расширения, можно посмотреть результат его работы, который уже пойдёт на вход компилятору.

Например, файл source.ml:

let rec loop = parser
  | [< ''a'..'z'; t >] -> print_string "alpha "; loop t
  | [< 'x; t >] -> print_string "other "; loop t
  | [< >] -> print_string "end"

let () = loop (Stream.of_string " a b c")

Компилируем и выполняем:

$ ocamlc -pp camlp4o source.ml -o test
$ ./test
other alpha other alpha other alpha end

Смотрим код:

$ camlp4o q.ml
let rec loop (__strm : _ Stream.t) =
  match Stream.peek __strm with
  | Some ('a' .. 'z') ->
      (Stream.junk __strm; let t = __strm in (print_string "alpha "; loop t))
  | Some x ->
      (Stream.junk __strm; let t = __strm in (print_string "other "; loop t))
  | _ -> print_string "end"

let () = loop (Stream.of_string " a b c")