Здраствуйте все при все!
Вопрос у меня такой:
Нужно написать интерпритатор мат выражений на Ocaml ,есть знаки : '+','-','*','/' т.е.
чтоб такие вещи обрабатывал
(((1+1)+(4-5))*3+14/3)/3-43+(53+61)
ну как я это задание понимаю надо на вход такую вот строчку подать
и распихать её значения в список (list)
все скобочки,знаки и числа от 0-9 спокойно в такой лист влезают как символы
Но числа типа 14,53... и общим словом более 1ого знака в char не лезут
=> нужно делать список строк,так вот собственно вопрос:
1)Как мне это сделать если для роботы с исходной строкой я юзаю s.[count] — а это символ?
2)Есть ли функции для того чтоб сивол преобразовать в строку?
(Обыскался нигде не нашел?и прямо в лоб string_of_char 'c' такого нету...)
3)Если кто может посоветовать какие нибудь идеи по реализации хорошие,пишите буду рад
Заранее всем спасибо кто откликнулся
Re: Помогите с Ocaml кто чем сможет,как написать...
Здравствуйте, MacDed, Вы писали:
MD>Нужно написать интерпритатор мат выражений на Ocaml ,есть знаки : '+','-','*','/' т.е. MD>чтоб такие вещи обрабатывал MD> (((1+1)+(4-5))*3+14/3)/3-43+(53+61) MD>ну как я это задание понимаю надо на вход такую вот строчку подать MD>и распихать её значения в список (list)
А зачем в список? AST на базе алгебраических типов, т.е. datatype, рулит.
MD>все скобочки,знаки и числа от 0-9 спокойно в такой лист влезают как символы MD>Но числа типа 14,53... и общим словом более 1ого знака в char не лезут
Ну так задай что-то вроде (OCaml не знаю, так что пример на родственном StandardML):
datatype Expr = RealLiteral of real | Sum of Expr*Expr | Product of Expr*Expr;
а потом при помощи паттерн-матчинга без проблем эту штуковину интерпретируешь.
MD>3)Если кто может посоветовать какие нибудь идеи по реализации хорошие,пишите буду рад
У меня вот лежит реализация StandardML, называется MoscowML. В ней есть встроенные yacc/lex. Выглядит (за счёт функционального стиля) гораздо симпатичнее, чем аналогичная версия для C. Наверняка, что-то подобное имеется для OCaml. Так можно либо непосредственно интерпретатор сделать, либо вначале получить AST, а потом пропускать его через evaluator (так универсальнее).
... << RSDN@Home 1.2.0 alpha rev. 672>>
Re: Помогите с Ocaml кто чем сможет,как написать...
Здравствуйте, MacDed, Вы писали:
MD>Здраствуйте все при все! MD>Вопрос у меня такой: MD>Нужно написать интерпритатор мат выражений на Ocaml ,есть знаки : '+','-','*','/' т.е. MD>чтоб такие вещи обрабатывал MD> (((1+1)+(4-5))*3+14/3)/3-43+(53+61)
Я так понимаю, задача учебная (кстати, любопытно, это где у нас теперь Окамл изучают?).
Поэтому всю тяжелую артилерию (ocamllex/ocamlyacc, menhir, streams & parsers library) отбрасываем, полезнее будет сделать все вручную.
У тебя есть следующие подзадачи:
1. Лексер: из исходной строки получает список токенов (на этом ты и застрял, я так понимаю).
2. Парсер: из списка токенов строим AST. Тебе надо определить тип данных, представляющий синтаксическую структуру выражения:
type Exp = Const of float | Plus of (Exp * Exp) | ...
Это один возможный вариант, выражение также может быть представлено в виде стека (гуглим по словам "Дейкстра", "Обратная польская нотация", там же узнаешь, как написать парсер математических выражений).
В конце концов, парсер может не строить промежуточных структур, а вычислять все на ходу (этот вариант мне меньше всего нравится, хотя иногда он будет самым эффективным).
3. Собственно, интерпретатор. Это будет функция типа Exp -> float. Эскиз:
eval exp = match exp with
| Const c -> c
| Plus (x, y) -> eval x +. eval y
(* etc *)
MD>1)Как мне это сделать если для роботы с исходной строкой я юзаю s.[count] — а это символ? MD>2)Есть ли функции для того чтоб сивол преобразовать в строку?
let string_of_char c = String.make 1 c
(* или даже так *)let string_of_char = String.make 1
Разбить выражение на список подстрок можно еще так (нужно подключить модуль str.cma):
let split_expr_str = Str.split (Str.regexp "[()+-/* ]")
Re[2]: Помогите с Ocaml кто чем сможет,как написать...
Здравствуйте, palm mute, Вы писали:
PM>У тебя есть следующие подзадачи:
PM>1. Лексер: из исходной строки получает список токенов (на этом ты и застрял, я так понимаю).
Вот, кстати, человек спрашивал, в скписке какого типа всё это упихнуть. Нужно юзать не список символов, а опять же, определить свой тип:
type Token = LeftParen | RightParen | Plus | Star | Number of real | ...;
на выходе лексера нужно получить список Token'ов, т.е. [Token]. А потом этот список отдать синтаксическому анализатору, который (методом рекурсивного спуска) получит по нему AST.
... << RSDN@Home 1.2.0 alpha rev. 672>>
Re[2]: Помогите с Ocaml кто чем сможет,как написать...
Здравствуйте, palm mute, Вы писали:
PM>2. Парсер: из списка токенов строим AST. Тебе надо определить тип данных, представляющий синтаксическую структуру выражения: PM>
PM>type Exp = Const of float | Plus of (Exp * Exp) | ...
PM>
Только наверное, чтобы не городить варианты,
type Operator = Plus|Minus|Mult|Div|...| Custom of string
type Expr = Literal of float | Identifier of string | Unary of (Operator*Expr) | Binary of (Operator*Expr*Expr)
PM>3. Собственно, интерпретатор. Это будет функция типа Exp -> float. Эскиз:
unop : Operator -> (float -> float)
binop : Operator -> (float -> float -> float)
unop o = match o with
| Plus -> (+.) 0
| Minus -> (-.) 0
| _ -> error "Unexpected unary operator"
binop o = match o with
| Plus -> (+.)
| Minus -> (-.)
| Mult -> (*.)
| Div -> (/.)
| _ -> error "Unexpected binary operator"
eval expr = match expr with
| Literal c -> c
| Identifier n -> lookupValueSomewhereElse n
| Unary (o,x) -> unop o (eval x)
| Binary (o,x,y) -> binop o (eval x) (eval y)
Кстати говоря, можно не интерпретатор сделать, а генератор функции.
ast2fun : Expr -> (Set of string) -> (Set of string)*(Map of string*float -> float)
(* на входе выражение и множество уже найденных переменных *)
(* на выходе - множество входящих в него переменных *)
(* и функция, принимающая таблицу значений *)
(* типы Set и Map - вымышленные. смотрите их аналоги в документации *)
ast2funS e s = match e with
| Literal c -> (s, const c)
| Identifier n ->
let sn = append s n in
let f m = lookup m n in
(sn, fn)
| Unary (o,ex) ->
let fo = unop o in
let (sx,fx) = ast2funS ex s in
let f m = fo (fx m) in
(sx, f)
| Binary (o,ex,ey) ->
let fo = binop o in
let (sx,fx) = ast2funS ex s in
let (sy,fy) = ast2funS ey sx in
let f m = fo (fx m) (fy m) in
(sy, f)
ast2fun e =
let (_,f) = ast2funS e emptySet
in f
Хаскелльщики без труда разглядят здесь монаду State (и даже Writer) в генераторе и привет от монады Reader в его выходной функции.
ЗЫ. Если налажал в синтаксисе, извиняйте. Давно не камлал с этим бубном.
Перекуём баги на фичи!
