Компилятор выражений

Спасибо большое за решение! Разберусь, перепишу на си и буду использовать в своих лабораторных =)

Польская Инверсная Запись? Чувствуется что похоже, только загримировано. Так же формальные правила для построения дерева операций, которое потом обходится для вычисления.

Или алгоритм построения дерева никак с ней не связан?

Вычислимое — Вычисляемое!
И да, зачем изобретать велосипед? «Всё уже украдено до нас».

Никогда не любил этот метод :(
Если нужно просто вычислить значение выражения – то куда проще делать это просто в 2 стека.
Старый добрый алгоритм, который значительно проще чем разбиение на дерево.

Если кому интересно если есть те, кто не знает могу рассказать. :)

C YACC не нужно изобретать велосипед, к нему к тому же есть java-обертка.

Если бы не дата рождения, подумал бы что автор просто лабу по программированию делал :)

Я помню мы лабы такие делали на первых курсах, правда на паскале :)

Я против велосипедов, но я за такие пуликации. Слава тем, кто пишет быстро, используя уже готовые библиотеки; но дважды слава тем, то знает, как эти библиотеки устроены, какие алгоритмы используют.
Недостаток статьи — очень много кода. Было бы полезней привести пример разбора выражений только с двумя операциями (скажем, сложение и умножение). И понять было бы проще и расширить проще.
Ну и надо было всё называть своими именами. Автор, как я понял, использует метод рекурсивного спуска.

Хм, думаю встраивание логики вычисления выражения в классы, описывающие AST, не есть хорошо. Вообще, для таких случаев в языках без алгебраических типов и сопоставления с образцом используют паттерн «посетитель». Да и использовать строки для хранения типа операторов, как-то не очень… Собственно, то же касается bool'а для того, чтобы определять, унарный ли это минус или not. Кстати, не стоит делать поля элементов AST private'ами.

Не совсем правильно называть приведённую штуку «компилятором выражений». Скорее всего, это лексический + синтаксический анализаторы + вычислитель (evaluator). Всё-таки компилятор должен порождать код или байт-код, а тут интерпретируется сразу AST.

Наконец, скажу одно слово: ANTLR (в дополнение к упомянутому yacc'у).

Круто, сюда прикрутить парочку методов многомерной оптимизации и получим утилтку для нахождения корней скалярной функции векторного аргумента.

Друзья, по-моему, вы загоняетесь по поводу использования ANTLR-ов и тому подобных решений. Всё намного проще: java-source.net/open-source/expression-languages

Вот набросал на прологе что-то похожее

integer(I) -->
        digit(D0),
        digits(D),
        { number_chars(I, [D0|D])
        }.

digits([D|T]) -->
        digit(D), !,
        digits(T).
digits([]) -->
        [].

digit(D) -->
        [D],
        { code_type(D, digit)
        }.

alnum([H | T]) :- code_type(H, alnum), alnum(T), !.
alnum([]).

identifier(A) -->
    [H | T],
    {
     code_type(H, alpha),
     alnum(T),
     string_to_atom([H | T], A)
    }.

expression0(Expr) -->
    integer(Expr),
    !.

expression0(Expr) -->
    identifier(Expr),
    !.

expression0(Expr) -->
    "(",
    expression(Expr),
    ")".

operand(+) --> "+".
operand(-) --> "-".
operand(*) --> "*".
operand(/) --> "/".

expression(Expr) -->
    expression0(Expr0),
    operand(Op),
    expression(Expr1),
    {Expr =.. [Op, Expr0, Expr1]},
    !.

expression(Expr) -->
    expression0(Expr).

eval(Str, Vars, Res) :-
    phrase(expression(Expr), Str),
    eval0(Expr, Vars, Res).

eval0(Expr, Vars, Res) :-
    Expr =.. [Op, Arg1, Arg2],
    eval0(Arg1, Vars, Arg1Evaled),
    eval0(Arg2, Vars, Arg2Evaled),
    Expr1 =.. [Op, Arg1Evaled, Arg2Evaled],
    Res is Expr1,
    !.

eval0(N, _, N) :- number(N), !.
eval0(K, Vars, V) :- member(K=V, Vars).
    


Как работает:

?- eval("(2+(6/3)*a)*(4+123-b)", [a=2,b=122], Res).
Res = 30.


помню легко это делал на С# на втором курсе, сначала переводя все в польскую нотацию (по заданию), а потом регэкспом

Замените первое предложение на фразу про образовательные цели и статья приобритет качественно другой окрас.

Кроме указанных выше jflex/antlr и прочих можно взять готовую библиотеку, например www.japisoft.com/formula/.

А есть ли библиотека делающая подобное на C или на худой конец на C++?
Спасибо.

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

Я когда надо было вычислять выражения в приложении генерировал простенький исходник и компилировал его gcc, ответ писал в файл. Решение некрасивое, но быстрое.

Я, наверное, поздно, но нечто подобное мне доводилось делать на Haskell. Получилось короче, чем приведенный выше на Прологе. Кому-нить интересно?

Простенькая программа, разбирающая выражения при помощи стандартной библиотеки компилятора GHC, и преобразующая их в формат Latex. Использовать ее предполагалось в интерактивном режиме компилятора для разбора выражений а ля Matlab на лету и вставки в исходник диплома.

Это был вроде как эксперимент, я потом сравнивал результат с довольно своим ж уродливым кодом на Elisp и ужасался своим страданиям.

В общем-то, если нужно тупо вычислять выражения, то получится раза в полтора меньше. :-)

module Parser (runExpr) where

import IO
— import System
import Text.ParserCombinators.Parsec
import Text.ParserCombinators.Parsec.Expr hiding (Operator)

data Tree a = Leaf a
| Sum (Tree a) (Tree a)
| Substract (Tree a) (Tree a)
| Multiply (Tree a) (Tree a)
| Divide (Tree a) (Tree a)
| Power (Tree a) (Tree a)
deriving Show

type ExprTree = Tree String

type Operator = (ExprTree -> ExprTree -> ExprTree)

(+!) :: Operator
(+!) a b = Sum a b

(-!) :: Operator
(-!) a b = Substract a b

(*!) :: Operator
(*!) a b = Multiply a b

(/!) :: Operator
(/!) a b = Divide a b

(^!) :: Operator
(^!) a b = Power a b

run :: Show a => Parser a -> String -> IO ()
run p input
= case (parse p "" input) of
Left err -> do{ putStr «parse error at „
; print err
}
Right x -> print x

runExpr :: String -> String
runExpr input
= case (parse expr “» input) of
Left err -> show err
Right x -> (makeLatex x)

expr :: Parser ExprTree
expr = buildExpressionParser table factor
<?> «expression»

table = [[op "^" (^!) AssocLeft]
,[op "*" (*!) AssocLeft, op "/" (/!) AssocLeft]
,[op "+" (+!) AssocLeft, op "-" (-!) AssocLeft]]
where
op s f assoc
= Infix (do{ string s; return f}) assoc

factor :: Parser ExprTree
factor = do{ char '('
; x < — expr
; char ')'
; return x
}
<|> symbol
<?> «simple expression»

symbol :: Parser ExprTree
symbol = do{ s < — letter
; ss < — many (alphaNum <|> char '_')
; return (Leaf (s:ss))
}
<?> «symbol»

makeLatex :: ExprTree -> String
makeLatex x = case x of
(Leaf name) ->
case (parse subsymbolParser "" name) of
Left err -> «Subsymbol parse error»
Right x -> x
(Sum l r ) -> (makeLatex l) ++ " + " ++ (makeLatex r)
(Substract l r) -> (makeLatex l) ++ " — " ++ (makeLatex r)
(Multiply l r) -> (makeLatex l) ++ " \\cdot " ++ (makeLatex r)
(Divide l r) -> "\\frac{" ++ (makeLatex l) ++ "}{" ++ (makeLatex r) ++ "}"
(Power l r) -> "(" ++ (makeLatex l) ++ ")" ++ "^{" ++ (makeLatex r) ++ "}"

subsymbolParser :: Parser String
subsymbolParser = do{ m < — many1 alphaNum
; do{char '_'; s < — (many alphaNum)
; return (m ++ "_{" ++ s ++ "}")
}
<|> return m
}

Ндаа. Я умный :) Был по крайней мере. Нам в педвузе на практике задали сделать калькулятор. Так вот я извратился и сделал что-то такое. Правда с меньшим числом классов и сильно рекурсивными функциями.
Это потом когда появился инет и я прочитал книгу дракона я понял что сделал через .. очень странную реализацию классического парсера. Жаль, конечно, что изобретал велосипед, но я все равно горд собой, что додумался этого сам.
Кстати кроме книги дракона я наткнулся на сайт softcraft.ru, на есть котором довольно понятные уроки по грамматикам и трансляторам. Это если кому тема интересна.
.