Построить функцию из грамматики OCaml

Я пытаюсь создать синтаксический анализатор на основе универсальной грамматики,
но сначала меня просят изменить грамматику на основе этой (A — начальный символ):

(A,[(A,[C;B;C]);
    (A,[C]);
    (B,[A]);
    (C,[B])])

Что-то вроде этого:

   (A,
   function
   | A -> [[C;B;C];[C]]
   | B -> [[C]]
   | C -> [[B]])


как создать средство сопоставления с образцом на основе информации из списка?
Сопоставитель шаблона (функция | шаблон | ... | шаблон) определяется программистом, как создать его на лету с информацией из списка, который имеет эту структуру (A,[[C;B;C] ;[C]])::отдых ?

Если вы хотите изучить более широкую грамматику, которая имеет больше смысла, посмотрите на этот вопрос.


ocaml context-free-grammar
person Miramontes Orlando    schedule 25.01.2013    source источник
comment
(Я не могу найти здесь вопрос.)   -  person Jeffrey Scofield    schedule 26.01.2013
comment
Мне интересно, как сгенерировать эту структуру данных, учитывая список, который выглядит так (A,[[C;B;C];[C]])::rest   -  person Miramontes Orlando    schedule 26.01.2013

Ответы (2)


arrow_upward
1
arrow_downward

Вы должны посмотреть на ocamllex и menhir, которые представляют собой инструменты, предназначенные для лексирования и анализа.

person Thomash    schedule 26.01.2013
comment
Спасибо, я знал об этих инструментах, но это не то, что мне нужно - person Miramontes Orlando; 26.01.2013

arrow_upward
1
arrow_downward

Хорошо, я думаю, что могу понять ваш вопрос. Структура данных, начинающаяся с функции, является функцией! В OCaml функции — это объекты первого класса, и вы можете создавать новые, хранить их в структурах данных и т. д. Чтобы сохранить чистоту, вы не можете получить доступ к текстовому представлению функции (как это возможно в некоторых языках), но вы все равно можете комбинировать функции полезными способами.

Вот крошечный пример. Функция maketest принимает значение k и возвращает функцию, которая проверяет k.

# let maketest k = fun x -> x = k;;
val maketest : 'a -> 'a -> bool = <fun>
# let t8 = maketest 8;;
val t8 : int -> bool = <fun>
# t8 3;;
- : bool = false
# t8 8;;
- : bool = true

Функция union принимает две тестовые функции (подобные тем, что сгенерированы maketest) и возвращает функцию, которая проверяет объединение двух наборов значений:

# let union f g = fun x -> f x || g x;;
val union : ('a -> bool) -> ('a -> bool) -> 'a -> bool = <fun>
# let t812 = union t8 (maketest 12);;
val t812 : int -> bool = <fun>
# t812 8;;
- : bool = true
# t812 12;;
- : bool = true
# t812 14;;
- : bool = false
#

Функция sequence принимает две проверочные функции (подобные тем, что сгенерированы maketest) и проверяет список, начинающийся с целых чисел, который по очереди соответствует двум функциям.

# let sequence f g = function
  | []|[_] -> false
  | a :: b :: _ -> f a && g b;;
val sequence : ('a -> bool) -> ('a -> bool) -> 'a list -> bool = <fun>
# sequence (maketest 1) (maketest 4) [1;4;7];;
- : bool = true
# sequence (maketest 1) (maketest 4) [1;8;7];;
- : bool = false
#

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

person Jeffrey Scofield    schedule 26.01.2013
comment
Я вижу вашу точку зрения. Мне нужно немного больше помощи. Я перефразировал вопрос. - person Miramontes Orlando; 26.01.2013
comment
Предполагая, что вы читаете новый вопрос... Я как бы понимаю, как я могу получить то, что хочу, с помощью (fun x -> fx ||...), но он должен быть сопоставим с (function | .. | ..) . Я не думаю, что вы можете сравнить это с (=) с вашим подходом. - person Miramontes Orlando; 26.01.2013