Парсер арифметических выражений

[Андре]

Небольшой подпроект более крупной задачи, который может оказаться кому-то полезен.

Суть - класс, на вход которого подается формула и значения переменных. Класс возвращает результат вычисления.

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

Пример использования (одновременно являющийся unit-тестом):

PHP код:

static void UnitTest(Args _args)
{
    expParser   parser = new expParser('a*8+b*5-d');
    ;
    parser.addVariable('a', 3);
    parser.addVariable('b', 2);
    parser.addVariable('d', 5);

    if (parser.calculate()!=29) print 'false'; else print 'true';

    parser = new expParser('a+3*b-2*a');
    parser.addVariable('a', 2);
    parser.addVariable('b', 5);
    if (parser.calculate()!=13) print 'false'; else print 'true';

    parser = new expParser('a1+b1-2');
    parser.addVariable('a1', 2);
    parser.addVariable('b1', 5);
    if (parser.calculate()!=5) print 'false'; else print 'true';

    parser = new expParser('alfa*3*boo');
    parser.addVariable('alfa', 2);
    parser.addVariable('boo', 5);
    if (parser.calculate()!=30) print 'false'; else print 'true';

    parser = new expParser('a+b+4');
    parser.addVariable('a', 2);
    if (parser.calculate()!=6) print 'false'; else print 'true';

    pause;
} 


p.s. Подозреваю, что что-то подобное уже есть в Axapta, например в Product Builder, но поиск занял бы у меня больше времени, чем написание кода
Хотя, если кто-то ткнет меня носом - буду благодарен.

Комментарии и замечания, естественно приветствуются.

[bucken]

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

Можно чуть поумничаю?
1) Судя по коду - перевод в префиксную форму.
2) Вложенность не поддерживается. нет обработки "( )".
3) вообще посути - это транслятор.

P.s. а вообще просто кайф. только вот к сожалению, приткнуть не к чему. Хотя может если какой нибудь навороченный отчет сделать. Например, таже заморочка, что в критерии отчета соединяются только по "И". С помощью парсера можно создать функционал, что бы пользователь мог строить свои замороченые условия.
А вообще, конечно же надо ориентироваться на цель....

[Vadik]

круто
а чем плохи runBuf() и xppCompiler ?

[mazzy]

см. RunBuf

про ProductBuilder...
см. PBARuleExpression, PBACheckSyntax
Но дело в том, что выражение в ProductBuilder задается в таблице правил, а не в тексте.
См. презентацию по PB: http://www.navision.ru/files/Flash/axaptanew/12.htm

[Zabr]

Код пока не смотрел, но в связи с замечанием bucken'а о том, что не обрабатываются выражения в скобках, возник вопрос: вы изобрели какой-то свой алгоритм? зачем? есть же алгоритм ОПЗ ("обратная польская запись"), который позволяет корректно обрабатывать выражения со скобками и с любой глубиной вложенности этих скобок. Более того, ОПЗ устроен так, что Вы можете придумать какие-то <i>свои, не обычные </i> обозначения операций, которые используются часто именно в ваших условиях, и применять их в формулах (т.е. типа макросов, например Вы часто возводите числа в степень "пи", тогда можно писать что-то вроде "A = pi B").

[bucken]

на самом деле там и есть "обратная польская запись".
Дальше мы будем флудить мне кажется. Андре выложил хороший код. Вопрос куда и где его тыкать, зависит от контекста. Также runBuf() и xppCompiler наверное дело тоже самое.
Лана, усе.

[mazzy]

Код... хм... красивый. Но не супер.

Про парсинг стоит почитать здесь
http://algolist.manual.ru/syntax/ (must read!)

http://bib.com.ua/categ34_3.html
http://pascal.sources.ru/parsing/
http://www.softportal.com/articles/item_txt.php?id=210

еще
http://cs.mipt.ru/docs/comp/rus/prog...cc_rus_07.html

еще
http://www.yandex.ru/yandsearch?rpt=...E6%E5%ED%E8%E9

еще

Цитата:

a> Я вот хочу написать виpтуальный пpоцессоp и компилятоp С-подобного
a> языка для него, что можете посоветовать почитать по этому поводу?

a> линки, ссылки набумажную литеpатуpу и собственные pазмышления на тему
a> пpиветсвуются!

pаньше в pусскоязычном интеpнете обычно два документа маячали:
Д.В.Ваpсанофьев, А.Г.Дымченко "Основы компиляции" осень,1991.
В.А.Сеpебpяков "Лекции по констpуиpованию компилятоpов", Москва 1993.
их в любом поисковике как ключи можно использовать для поиска ссылок,
так как, IMHO, любой сайт посвященный данной тематике любезно
pазмещает у себя. это что касается интеpнета. по идеи и список
литеpатуpы там же. наиболее автоpитетной считается [1]
или более новые издания тех же автоpов. есть и pусский стаpый
аналог [2]. самое интеpесное, что издательство "Вильямс"
все обесчает и обесчает на pусском издать. будем ждать. вообще
"отечественный пpоизводитель" не очень pадует. еще выскажу мнение,
что много внимания в литеpатуpе уделяется компиляции и мало
генеpации кода, а пpо виpтуалные машины еще меньше. если говоpить
о pеализациях на pазных языках, то сколько ты их найдешь зависит от
фантазии. даже на вскидку, сам понимаешь, сколько выплюнет ссылок
тот же ya.ru, если задать для поиска "free compilers".

пpимеpный список литеpатуpы (пpавда, какие там даты):

1. A.Aho, R.Sethi, J.Ullman Compilers: principles,
techniques, and tools. Addison-Wesley, Reading, MA, 1986.
2. Ахо А., Ульман Дж. Теоpия синтаксического анализа, пеpевода
и компиляции.- М.: Миp, 1978.
3.Вайнгаpтен Ф. Тpансляция языков пpогpаммиpования. - М.: Миp, 1977.
4.Гpис Д. Постpоения компилятоpов для цифpовых вычислительных машин. М.:
Миp, 1975.
5.Льюис Ф., Розенкpанц Д., Стpинз Р. Теоpетические основы пpоектиpования
компилятоpов. - М.: Миp, 1979.
6.Рейоуpд-Смит В.Дж. Теоpия фоpмальных языков. Вводный куpс. - М.: Радио и
связь, 1988.
7.Фостеp Дж. Автоматический синтаксический анализ. - М.: Миp, 1975.
8.Хантеp Р. Пpоектиpование и констpуиpование компилятоpов/ Пеp. с англ.: -
М.: Финансы и статистика, 1984. - 232 с.

[Андре]

Если коротко, то так:

1. Скобочки не обрабатываются. Но их всегда можно предварительно раскрыть. Или дописать код - там минут 5 работы.
2. Это часть более крупной задачи, которая и выдвигала к нему определенные требования. Поэтому runBuf() и прочие механизмы, позволяющие выполнять X++ код не очень подходят.

[mazzy]

В любом случае... Андре, мой респект!

[Андре]

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

[Zabr]

+ Mazzy, согласен и с тем что код оригинальный, и с тем что он при этом не супер.
+ Андре, тем не менее респект - за напоминание об этой идее и компактную реализацию. Твердая четверка с плюсом
- Bucken, ты не прав, трансляции в ОПЗ там нет. ОПЗ как раз нужна для разбора выражений со скобками и с произвольными операторами, имеющими разные приоритеты выполнения. Задача обработки скобок не стояла (будем так считать), а приоритеты арифм.операторов задаются прямо в свиче (int pred). То что есть - со своей задачей справляется. Хороший код.

[Андре]

Насчет xppCompiler и аналогичных механизмов - мне они не нравятся Их использование свидетельствует либо о неудачном проектировании, либо о ситуации "когда надо, а деваться больше некуда".
Кроме того, их использование это потенциальная дыра в систему. Либо надо контролировать, что юзер скармливает xppCompiler-у, либо положиться на его честность.

[Андре]

Посмотрел MSDN - есть такая штука, как MSScriptControl.ScriptControl (system32\msscript.ocx). Можно ее использовать, причем в коде, выполняющемся только на клиенте

p.s. Это не польская запись, а простенький конечный автомат.

[mazzy]

Цитата:

Изначально опубликовано Андре
Насчет xppCompiler и аналогичных механизмов - мне они не нравятся Их использование свидетельствует либо о неудачном проектировании, либо о ситуации "когда надо, а деваться больше некуда".
Кроме того, их использование это потенциальная дыра в систему. Либо надо контролировать, что юзер скармливает xppCompiler-у, либо положиться на его честность.

Не-е-е...

Это неправильный подход. Код должен генерить программист, а не пользователь.
Пользователь должен выбирать из возможных вариантов.
Пример - тот же конфигуратор продукции.
Хотя и там есть дыра с запуском произвольного кода.
Но эта дыра управляется правами доступа пользователя.

либо же предлагать пользователю выбор из предопределенных формул.
Как это сделано в производстве в операции.

У тебя формулу генерят пользователи?
Это точно нужно?

[mazzy]

Цитата:

Изначально опубликовано Андре
Посмотрел MSDN - есть такая штука, как MSScriptControl.ScriptControl (system32\msscript.ocx). Можно ее использовать, причем в коде, выполняющемся только на клиенте

Ага. Вот это точно ДЫРА!

[mazzy]

Цитата:

Изначально опубликовано Zabr
+ Андре, тем не менее респект - за напоминание об этой идее и компактную реализацию.

Респект можно добавить здесь http://forum.mazzy.ru/index.php?showuser=66

[Андре]

PHP код:

Хотя и там есть дыра с запуском произвольного кода. 


Мне даже отвечать не надо

Цитата:

либо же предлагать пользователю выбор из предопределенных формул.

Ты употребил слово "предопределенных" - не подходит.

Цитата:

У тебя формулу генерят пользователи?
Это точно нужно?

Ага.

[mazzy]

как скажешь.

[vadikf]

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

[mazzy]

vadikf, интересно!