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

[NitroG]

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

[NitroG]

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

[voidlizard]

Ахо, Сети, Ульман уже написали статью «про это». Большую такую.

[Error_403_Forbidden]

В следующем семестре будем проходить таблицу умножения, сделаю статью про это, если кто-нибудь не напишет

[NitroG]

=) Прошу прощения, не думал, что эта задача для вас окажется такой тривиальной. Просто мне она интересна.

[dsCode]

Да? о чем тогда вообще на Хабре пишут? ;)

[optio]

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

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

[abarmot]

Если посмотреть на дерево из примера без отступов то вы как раз польскую запись и увидите.
Ну в общем да — огурцы с одной грядки :)

[ofigenn]

Я знаю её как обратную польскую нотацию.

[LoneCat]

Ну так инверсная=обратная, нотация=запись, это уже особенности перевода.

[NYBR]

может просто озадачить любой интерперетатор джаваскрипта, а в нем позвать eval?

[corax]

чето как то слишком сложно всё… слишком на низком уровне что ли.

[dsCode]

> чето как то слишком сложно всё… слишком на низком уровне что ли.

Наоборот (если вы про автоматизированные средства построения сканеров и парсеров, типа javacc). Здесь вам не надо самому строить парсеры для LL / LR (1) — грамматик, здесь вы просто описываете формальную грамматику. Да, понадобится знать регулярные выражения, но, все же, это более эффективно и позволит избежать ошибок.

> Ох уж эти велосипедисты

Ну, есть и работы научные и академические, а не только прикладные-потребительские. Кто-то же за вас написал эти автоматизаторы :) Кому-то просто потреблять — мало, им нужно знать, как это работает. И «изобретение велосипеда» — это отличное подтверждение практикой изученной теории.

[rg_software]

В университете — да.
А если этим будет заниматься мой подчинённый в рабочее время — настучу по голове.

[dsCode]

> В университете — да.
> А если этим будет заниматься мой подчинённый в рабочее время — настучу по голове.

Да не только в университетах. Просто условно все задачи можно разделить на:

— задачи на инструментарий (написание языков, сред, фреймворков, виджетов и т.д.)
— прикладные задачи «на данные», с использованием уже готовых вещей из первого пункта.

Естественно, для выполнения первых нужны более глубокие знания — как в конкретной технологии, так и в общей, фундаментальной.

Все это вытекает из усиления абстракций, habrahabr.ru/blogs/webdev/45552/#comment_1152704 — здесь кратко говорил об этом.

И не только в университетах, есть и такие «работы», на которых «подчиненные» пишут для потребителей усиленные абстракции. Далее некоторые потребители сами становятся созидателями (относительно нового уровня абстракции). Вы пользуетесь каким-нибудь фреймворками? Их разве в университетах написали? Нет, так же люди ходят на работу, так же им деньги за это платят.

[rg_software]

Вы пытаетесь делать слишком далеко идущие выводы :)

Я говорю о конкретной простой вещи. Если я попрошу подчинённого добавить в проект компилятор арифметических выражений, а он мне принесёт что-то вроде вышенаписанного, у меня будут большие сомнения по поводу его вменяемости.

То, что В ПРИНЦИПЕ было бы неплохо уметь писать фреймворки и т.п. — ясно и так. Я лишь против изобретения велосипедов в конкретных случаях.

[dsCode]

> Вы пытаетесь делать слишком далеко идущие выводы :)

Я никогда не пытаюсь ;) (либо делаю, либо нет) я лишь размышляю, и делаю выводы (а далеко идущие или нет — это уже другой вопрос)

Да, все зависит лишь от задач конторы. Если у вас прикладные задачи, для которых уже написано тонна готовых решений — нет смысла писать на «ассемблере» интернет-магазин ;)

Если же контора занимается разработкой новых подходов, способных «осчастливить человечество», то — у них и цели здесь другие. Но они так же — работаю и получают зарплату (и, если оценивать справедливо, — получают больше прикладных программистов, поскольку и знаний применяют больше)

По поводу же велосипедов — тоже от уровня и требований зависит. К примеру, у меня в JS всегда свой фреймворк был написан (который легче и быстрее всех этих Prototype'ов.js, jQuery и т.д.).

А полностью подавлять инициативу и самообразование подчиненных — тоже не стоит (иначе — наймите лучше «кодеров» (программистов без собственной мысли), которые будут просто выполнять приказы, не двигаясь ни вправо, ни влево, а не программистов). Наоборот, компания должна сопутствовать образованию своих сотрудников.

Но, другое дело, когда эти «научные изыскания» совсем не связанны с работой — тогда да, здесь уже другой разговор (и вы имеете в виду именно этот случай; я понимаю).

[dsCode]

или jflex + cup (агалоги Си-шных flex'a и bison'a, который часто используются для этих целей) — так же строят сканер и парсер по заданным формальным грамматикам.

[tegger]

Antlr весьма неплох.

[ofigenn]

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

[abarmot]

Про «вычислимое — вычисляемое» можно поспорить. Вычислимое — которое может быть вычислено. Вычисляемое — находящееся в процессе вычисления. Мне кажется первое больше по смыслу подходит.

Про велосипед — согласен. Почему-то не получилось быстро найти готового решения (nanodust, спасиба за инфу!) вот и сделал сам. И мне кажется, что как информация для развития эта статья вполне подходит.

[Baks]

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

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

[whirl]

Давай ^.^

[maxshopen]

Интересно, рассказывайте :)

[michurin]

Расскажите про два стека!
Только мне кажется, что я знаю про что вы ,-)
И я вам сразу хочу напомнить, что автор поста обходится одним стеком (для хранения локальных переменных) и его подход позволяет не следить за стеком вручную — следит язык. Мне очень интересно посмотреть, как вы будете отлаживаться, вылавливать ошибки, тестировать… как от малейшей оплошности вашу аж двустековую машину будет развозить в разные стороны…
Кроме того, метод, про который тут рассказано — это классика (реалиация странновата, правда; всё было бы проще и стройнее, если бы операции хранились бы не в виде сточек, а в виде объектов, но это уже частности и детали).

[Baks]

Эм… я не смог найти у автора стек… возможно, плохо искал…
Метод в 2 стека не мой. Это классическое решение задачи на С.
Разумеется, можно всё запихать в 1 стек, но в оригинале использовалось 2.

Завтра днём опишу и выложу :)
А сейчас у меня 5 утра и спать хочицо :)

[michurin]

Каждый вызов функции — это работа со стеком. Но вы правы — неявная, и вы её не видете. Именно неявность гарантирует, что pop-ов будет солько же, сколько push-ей, и всё будет вовремя и хорошо. А явная работа со стеком — это жуткое болото. Ещё написать такое можно, но вот поддерживать, развивать… не дай бог. Поэтому закладывать сразу стековы дизайн можно только если вы (а) пишите что-то очень маленькое на один день, (б) для вас очень важно быстродействие (обычно стек быстрее) или (ц) вы просто самоубийца :-)

[Baks]

эм… мы наверно о разных стеках разговариваем… :)
в общем минут через 15 выложу пост :)

[fuCtor]

Вы случайно не про метод рекурсивного спуска? Где стек представляет из себя стек вызова функций разбора + стек символов текста.

[EiZeRR]

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

[duncanf1]

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

[fabiaN]

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

[pietrovich]

хе-хе… точно :)
году в 97-98м я в шутку написал подобную лабу в виде обертки, которая принимала выражение, оборачивала паскалем, компилировала с помощью строчного компилятора и запускала скомпиленную прогу которая выдавала ответ. после чего убедил препода что лаба должна быть засчитана т.к. четких ограничений не налагалось а задание было сформулировано так что мой метод тоже подходил :))) в итоге препод меня на лабы перестал пускать, это была «последняя капля». ставил «автомат» лишь бы меня не видеть :D

[glorybox]

нихуёвый eval, я приблизительно так же делал для реализации метода градиентного спуска на C ^_^

[michurin]

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

[konsoletyper]

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

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

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

[HID]

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

[lam0x86]

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

[xonix]

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

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.


[Krizai]

А для чего phrase?
Работать ведь будет если и только последние 3 определения оставить, или я ошибаюсь?

[xonix]

в данном случае phrase нужен чтоб распарсить строку в прологовский терм.

3 ?- Str = "(2+(6/3)*a)*(4+123-b)", phrase(expression(Expr),Str).
Str = [40, 50, 43, 40, 54, 47, 51, 41, 42|...],
Expr = (2+6/3*a)* (4+ (123-b)).


[Krizai]

Ясно.
Хотя конечно как по мне, малой величине кода тут по большей части способствует то, что основную работу берут на себя =… и is

[wersoo]

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

[michurin]

Не верю. Польскую нотацию нельзя разобрать регекспом.
Она относится к контекстно свободным грамматикам и для разобра требует бесконечное (в общем случае) количество состояний. А регексп определеяет конечный(!) автомат. То есть машину с конечным количеством состояний. Регекспом можно ограничться только если ограничить количество волженных конструкций; но уже при глубине 3 регексп становится нечеловеческим.
Так-что, вы либо что-то путаете, либо вы на втором курсе рассматривали очень упрощённый и ограниченный случай.

[chiaroscuro]

Он не путает. Современные Perl-style регексы это не регулярные выражения.

[khayrov]

Гм. И ими таки можно разобрать КС-грамматику? А примерчик? Серьёзно, я вот листаю доку и ничего, не укладывающегося в регулярную грамматику, не вижу. Способа разобрать хотя бы скобочное выражение — тоже.

[chiaroscuro]

Backreference'ы в Перловских регексах уже какбэ убивают «регулярность», вот это:

(.*)\1

не регулярное выражение, и не контекстно-свободная грамматика.

Тут еще такая штука: в большинстве реализаций используется backtracking, а не DFA, и этот самый backtracking дает жуткое время выполнения в некоторых особых случаях.

[apatrushev]

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

[CrazyCoder]

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

[dimasi]

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

[dsCode]

flex (сканер) + bison (парсер)

[khayrov]

Если C++ — худой конец, то, конечно, Spirit рекомендовать сложно, но всё же. С такими «калькуляторными» примерами он неплохо справляется.

[aberezh]

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

[Hanhe]

Этот подход и есть — стандартный. Просто сейчас в качестве одного из стеков(магазина) используется стек функций.

[khayrov]

Алгоритм-то стандартный, но мне лично проще думать в терминах AST и рекурсивного спуска, с которыми можно работать не только в операторной грамматике.

[VtD]

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

[VlK]

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

[xonix]

Напиши, интересно. Можно даже отдельным постом с пояснениями. Так понимаю, в хаскеле используя Parsec?

[VlK]

смотри ниже… что-то я не нашел подсветки для Haskell

[xonix]

спасибо.
хе-хе, чисто субъективно, на прологе проще, выразительнее =)

[VlK]

Не знаю, мне сложно судить. Для того, чтобы оценить выразительность, надо знать оба языка, а Пролог как-то не привелось посмотреть.

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

[VlK]

Простенькая программа, разбирающая выражения при помощи стандартной библиотеки компилятора 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
}

[vpbar]

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