Разрабатываем парсер математических выражений


Содержание
Илон Маск рекомендует:  Кросбраузерная Вставка Flash-анимации

Виктор Зинкевич

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

среда, 5 октября 2011 г.

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

Однажды мне нужно было создать парсер математических выражений. Я взялся за этот труд и сразу же понял, что используя посимвольный разбор, я просто погрязну в большом количестве строк кода. Тогда на помощь пришел очень замечательный инструмент — регулярные выражения. Использовать регулярные выражения в Delphi или Builder’е стало легко возможным благодаря подключению модуля RegExpr.pas, созданного Андреем Сорокиным. Всё о регулярных выражениях Вы можете найти на его сайте: http://RegExpStudio.com/ Итак, приступим к созданию самого парсера.

Нашему парсеру мы передаем выражение в виде строки, а он возвращает результат тоже в виде строки символов.

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

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

Ну, а теперь на деле. Создадим класс TExParser, в который мы заключим все необходимые нам функции.

Разрабатываем парсер математических выражений

Обучение программированию на 1С

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

Что такое парсер выражений?

Парсер – это программа, которая сопоставляет набор лексем формального языка с его грамматикой. Результатом парсинга является дерево лексем, структура представленного выражения.

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

Для чего нужен парсер?

Люди, которые никогда не слышали что такое парсер, могут спросить: «Зачем вообще нужен парсер?»

Конкретно парсер выражений может применяться в следующих ситуациях:

  • При построении регламентированной отчётности в 1С, где определённые строки отчётности складываются по определённым закономерностям.
  • Вычисление формул, заданные пользователем в системе.
  • Построение отчётов СКД с вычисляемыми полями.
  • Динамические алгоритмы, которые можно легко изменить и которые применяются, к примеру, для расчёта сумм документов.
  • Разбор выражений в запросах 1С.

Требования к парсеру.

Требования к алгоритму парсера арифметических выражений должны быть следующими:

  1. Парсер должен разбирать грамматику формального языка за один проход слева направо (в отличие от двухпроходной обработки грамматики в некоторых языках программирования).
  2. Парсер должен включать в себя как лексический, так и синтаксический анализ исходного текста.
  3. Парсер должен правильно обрабатывать исключения.
  4. Парсер должен учитывать приоритет выполняемых операций.
  5. Парсер должен уметь вычислять стандартные математические функции.

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

Формальные грамматики.

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


Набор терминальных символов в данном алфавите будет следующим:

Нетерминальный алфавит следующий:

Правила грамматики языка:

1. Выражение есть два выражения, соединённые знаком:

ВЫРАЖЕНИЕ ? ВЫРАЖЕНИЕ ЗНАК ВЫРАЖЕНИЕ

2. Выражение есть число:

3. Выражение есть выражение в скобках:

4. Выражение есть или плюс, или минус, или умножить, или разделить:

5. Число есть цифра:

6. Число есть число и цифра:

ЧИСЛО ? ЧИСЛО ЦИФРА

7. Цифра есть или 0, или 1, … , или 9:

ЦИФРА ? 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Выведем формулу (25+3) с помощью правил вывода формальной грамматики. Последовательность вывода приведена ниже, каждая текущая замена подчёркнута.

Правило №3: ВЫРАЖЕНИЕ ? (ВЫРАЖЕНИЕ)

Правило №1: ( ВЫРАЖЕНИЕ ) ? ( ВЫРАЖЕНИЕ ЗНАК ВЫРАЖЕНИЕ )

Правило №4: (ВЫРАЖЕНИЕ ЗНАК ВЫРАЖЕНИЕ) ? (ВЫРАЖЕНИЕ + ВЫРАЖЕНИЕ)

Правило №2: (ВЫРАЖЕНИЕ + ВЫРАЖЕНИЕ ) ? (ВЫРАЖЕНИЕ + ЧИСЛО )

Правило №5: (ВЫРАЖЕНИЕ + ЧИСЛО ) ? (ВЫРАЖЕНИЕ + ЦИФРА )

Правило №7: (ВЫРАЖЕНИЕ + ЦИФРА ) ? (ВЫРАЖЕНИЕ + 3 )

Правило №2: ( ВЫРАЖЕНИЕ + 3) ? ( ЧИСЛО + 3)

Правило №6: ( ЧИСЛО + 3) ? ( ЧИСЛО ЦИФРА + 3)

Правило №5: ( ЧИСЛО ЦИФРА + 3) ? ( ЦИФРА ЦИФРА + 3)

Правило №7: ( ЦИФРА ЦИФРА + 3) ? ( 2 ЦИФРА + 3)

Правило №7: (2 ЦИФРА + 3) ? (2 5 + 3)

Программная реализация

Моя программная реализация парсера выражений на языке 1С включает проведение разбора следующих операций:


1. Арифметические операции: «+» (сложение), «-» (вычитание), «*» (умножение), «/» (деление).

2. Изменение приоритета операций: «(» (открывающая скобка), «)» (закрывающая скобка).

3. Операции сравнения: « » (больше), « =» (больше или равно), «=» (равно), «<>» (не равно).

Илон Маск рекомендует:  Работа с полигонами

4. Математические функции:

  • Цел(x1) – Целая часть числа. Параметры: x1 – исходное число;
  • Окр(x1, x2) – Округление. Параметры: x1 – исходное число, x2 – разрядность полученного числа. Если параметр отрицательный, то исходное число округляется до соответствующего разряда целой части;
  • Ln(x1) – Натуральный логарифм. Параметры: x1 – исходное число;
  • Lg(x1) – Десятичный логарифм. Параметры: x1 – исходное число;
  • Sin(x1) – Синус. Параметры: x1 – аргумент функции;
  • Cos(x1) – Косинус. Параметры: x1 – аргумент функции;
  • Tg(x1) – Тангенс. Параметры: x1 – аргумент функции;
  • Asin(x1) – Арксинус. Параметры: x1 – аргумент функции;
  • Acos(x1) – Арккосинус. Параметры: x1 – аргумент функции;
  • Atg(x1) – Арктангенс. Параметры: x1 – аргумент функции;
  • Pow(x1, x2) – Возведение в степень. Параметры: x1 – основание, x2 – показатель степени;
  • Sqrt(x1) – Квадратный корень. Параметры: x1 – аргумент функции;
  • Abs(x1) – Модуль числа. Параметры: x1 – исходное число;
  • Exp(x1) – Число e в степени x1. Параметры: x1 – аргумент функции;
  • Pi(x1) – Число пи в степени x1. Параметры: x1 – показатель степени;
  • Cmp(x1, x2, x3) – Условный переход. Если x1 >= 0, то cmp = x2, иначе cmp = x3. Параметры: x1 – число, сравниваемое с нулём, x2, x3 – значение условий;
  • If(x1, x2, x3) – Условный переход. Если x1 = 0, то if = x2, иначе if = x3. Параметры: x1 – число, сравниваемое с нулём, x2, x3 – значение условий;
  • Min(…) – Минимальное значение;
  • Max(…) – Максимальное значение;
  • And(…) – Логический оператор «И»;
  • Or(…) – Логический оператор «ИЛИ».

5. Выделение символьной строки: «’» (апостроф).

6. Переменные таблицы: ( ). Находит в передаваемой таблице ячейку с определённым значением. Например, функция Об(‘522000’) находит в столбце «Об» в строке с идентификатором «522000» заданное значение. Если такой идентификатор найден не один, то значения ячеек складываются между собой.

Лексический анализатор.

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

К примеру, если в тексте выражения попадается число «5.78», то лексический анализатор воспринимает его не как набор символов, а как единую строку. Выражение «5.78 + 7.12» — это соответственно набор 3 лексем: 2 числа – «5.78» и «7.12» и 1 операция – «+». Пробелы в выражении при этом игнорируются.

Далее полученные лексемы передаются синтаксическому анализатору для выделения из формулы её структуры и последующего вычисления значений.

Синтаксический анализатор.

Синтаксический анализатор строит из преобразованного выражения дерево набора лексем с помощью рекурсивного вызова функций, отвечающих за определённые правила. Построенное анализатором дерево свёртывается согласно порядку вызова функций в 1С и на выходе получается одно итоговое значение, которое и является значением всего арифметического выражения.

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

Обработка 1С.

Для примера функционирования парсера выражений создана обработка «Парсер формул». Вводим формулу, заполняем табличную часть и нажимаем кнопку «Выполнить». В поле «Результат» появляется итог вычисления формулы.

В примере используется формула: if( and( К1(‘Имя’+1) >= abs((-1) * К2), 3 > 2), 2 + 3 * 4 — (143 + 211.50), sqrt(К1(‘Имя’+2) + К2(‘Имя2’))).

eXit’s Blog

Интересный блог о .Net

вторник, 14 февраля 2012 г.

Парсер математических и логических выражений на C#

Код доступен на codeplex.com и github.com. В архиве два проекта: библиотека, в которой содержится весь код парсера и само приложение, содержащее пользовательский интерфейс на WPF.

P.S. Добавлена возможность постоить график функции.
P.P.S. Добавлена возможность парсинга логических выражений.

4 комментария:

Сам .exe файл отлично работает. А вот как использовать парсер в своей проге понять не могу, писал что-то типа

Но прога выдавала вместо 6 ерись какую-то, скажите пожалуйста, как правильно использовать парсер, и еще если не сложно скажите: Вы график рисовали стандартными средствами C# или сторонними типа DirectX или OpenGL?


и будет выдавать 6.

Без функции Calculate у вас получается строится дерево выражений, но само значение не считается.

А график рисуется при помощи стандартных возможностей WPF.

Разрабатываем парсер математических выражений

We recommend upgrading to the latest Google Chrome or Firefox.

Join GitHub today

GitHub is home to over 40 million developers working together to host and review code, manage projects, and build software together.

New pull request

Clone with HTTPS

Use Git or checkout with SVN using the web URL.

Downloading .

Want to be notified of new releases in aTastyCookie/mathematical-expression-parser ?

Launching GitHub Desktop .

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop .

If nothing happens, download GitHub Desktop and try again.

Launching Xcode .

If nothing happens, download Xcode and try again.

Launching Visual Studio .

Permalink

#СИНТАКСИЧЕСКИЙ АНАЛИЗ ВЫРАЖЕНИЯ. ПАРСЕР МАТЕМАТИЧЕСКИХ ВЫРАЖЕНИЙ

##В этой курсовой работе я реализовал возможность получения от пользователя строку с арифметическим выражением, содержащим арифметические операции и скобки, а в ответ вывод результата вычислений.

###В данной программе были реализованы следующие возможности:

  • Работа с основными математическими операциями (+ — * /)
  • Работа со специфическими функциями (%, sqrt, ^)
  • Работа с тригонометрическими функциями (sin, cos, arcsin, arccos, tg, ctg, arctg, arcctg)
  • Работа с гиперболическими функциями (sh, ch, th, cth)
  • Обработка функций (lg, ln, e^_)
  • Встроенные константы (g=9.81, pi=3.14, e=2.71)


Разрабатываем парсер математических выражений

Парсер выражений — это разборщик строк типа sin(pi/4) реализованный на java, c++ и javascript. На основе парсера созданы проекты на java, которые можно скачать или запускать online — это научный калькулятор и построитель графиков

Список поддерживаемых функций и констант

Общие функции

Type Name Latest commit message Commit time
Failed to load latest commit information.
README.md Update README.md Dec 21, 2014
exp(x) = e x — экспонента
log(x) — натуральный логарифм
pow(x, y) = x y — возведение в степень
sqrt(x) — корень квадратный
abs(x) = |x| — модуль
random() — случайное число между 0 и 1
min(x1, x2) — минимум
max(x1, x2) — максимум

Константы

pi = 3.141592653589793
e = 2.718281828459045
sqrt2 = sqrt(2) = 1.4142135623730951
sqrt1_2 = sqrt(1/2) = 0.7071067811865476
ln2 = loge(2) = log(2) = 0.6931471805599453
ln10 = loge(10) = log(10) = 2.302585092994046
log2e = log2(e) = 1/log(2) = 1.4426950408889634
log10e = log10(e) = 1/log(10) = 0.4342944819032518

Тригонометрические функции

sin(x) — синус
asin(x) — арксинус
cos(x) — косинус
acos(x) — арккосинус
tan(x) — тангенс
atan(x) — арктангенс
atan2(x,y) — арктангенс отношения x/y
cot(x)=cos(x)/sin(x) — котангенс
acot(x)=pi/2-atan(x) — арккотангенс
sec(x)=1/cos(x) — секанс
asec(x)=acos(1/x) — арксеканс
csc(x)=1/sin(x) — косеканс
acsc(x)=asin(1/x) — арккосеканс

Гиперболические тригонометрические функции

sinh(x)=(e x -e -x )/2 — гиперболический синус
asinh(x)=log(x+sqrt(x 2 +1)) — гиперболический арксинус
cosh(x)=(e x +e -x )/2 — гиперболический косинус
acosh(x)=log(x+sqrt(x 2 -1)) — гиперболический арккосинус
tanh(x)=(e x -e -x )/(e x +e -x ) — гиперболический тангенс
atanh(x)=log((1+x)/(1-x))/2 — гиперболический арктангенс
coth(x)=(e x +e -x )/(e x -e -x ) — гиперболический котангенс
acoth(x)=log((x+1)/(x-1))/2 — гиперболический арккотангенс
sech(x)=1/cosh(x)=2/(e x +e -x ) — гиперболический секанс
asech(x)=acosh(1/x)=log[(1+sqrt(1-x 2 ))/x] — гиперболический арксеканс
csch(x)=1/sinh(x)=2/(e x -e -x ) — гиперболический косеканс
acsch(x)=asinh(1/x)=log[1/x+sqrt(1+x 2 )/abs(x)] — гиперболический арккосеканс

Функции округления

ceil(x) — округление вверх к ближайшему целому числу
floor(x) — округление вниз к ближайшему целому числу
round(x) — округление к ближайшему целому числу

Числа

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

1.2e1=12
1.2e+1=12
1.2e-1=0.12
1.2e0=1.2
1.2e+0=1.2
1.2e-0=1.2

Скобки

Можно использовать три типа скобок ( ), [ ],

Java парсер

Первый пример

import estimator . ExpressionEstimator ;

public class Example1 <

public static void main ( String [] args )<

try <
double v = ExpressionEstimator . calculate ( «sin(pi/4)» );
System . out . println ( v );
> catch ( Exception e ) <
System . out . println ( e . getMessage ());
>

Параметр функции calculate() — это формула которая может содержать переменные x0, x1, . Если формула содержит переменные, то сначала ее необходимо скомпилировать. Затем вызвать функцию calculate(), передав значения неизвестных как аргумент.

import estimator . ExpressionEstimator ;

public class Example2 <


public static void main ( String [] args ) <
ExpressionEstimator estimator = new ExpressionEstimator ();
try <
estimator . compile ( «x0+x1» );
double [][] values =< < 3 , 6 >, < 8 , 6 >>;
for ( double [] v : values ) <
System . out . println ( estimator . calculate ( v ) );
>
> catch ( Exception e ) <
System . out . println ( e . getMessage ());
>

Более сложный пример

import java . util . Arrays ;

import estimator . ExpressionEstimator ;

public class Example3 <

public static void main ( String [] args ) throws Exception <
String expression []=< "sin(pi/4)" , "1+2+" >;
for ( String s : expression ) <
System . out . print ( «\»» + s + «\»=» );
try <
System . out . println ( ExpressionEstimator . calculate ( s ));
> catch ( Exception e ) <
System . out . println ( e . getMessage ());
>
>

ExpressionEstimator estimator = new ExpressionEstimator ();
expression = new String []< "3*x0+2*x1*x0" , "6*x0" >;
double [][] values =< < 3 , 6 >, < 8 , 6 >>;
double [] v ;
int i = 0 ;
for ( String s : expression ) <
v = values [ i ++];
System . out . print ( «\»» + s + «\»» + Arrays . toString ( v )+ «=» );
try <
estimator . compile ( s );
System . out . println ( estimator . calculate ( v ));
> catch ( Exception e ) <
System . out . println ( e . getMessage ());
>
>

C++ парсер

Первый пример

#include «expressionEstimator.h»
#include

int main () <
try <
ExpressionEstimator :: Init ();
double v = ExpressionEstimator :: calculate ( «sin(pi/4)» );
printf ( «%lf» , v );
> catch ( Exception & e ) <
printf ( «%s\n» , e . what ());
>
return 0 ;
>

В классе ExpressionEstimator есть статический метод Init(), который нужно вызвать если выражение содержит функцию random. Если функция random не будет использоваться, то необходимости вызывать этот метод нет.

Параметр функции calculate() — это формула которая может содержать переменные x0, x1, . Если формула содержит переменные, то сначала ее необходимо скомпилировать. Затем вызвать функцию calculate(), передав значения неизвестных и их количество как аргумент.

#include «expressionEstimator.h»
#include

int main () <
try <
ExpressionEstimator :: Init ();
ExpressionEstimator estimator ;
estimator . compile ( «x0+x1» );

const int arguments = 2 ;
const double values [][ arguments ]=< < 3 , 6 >, < 8 , 6 >>;
const int valuesSize = sizeof ( values )/ sizeof ( values [ 0 ]);
for ( int i = 0 ; i valuesSize ; i ++) <
printf ( «%lf\n» , estimator . calculate ( values [ i ], arguments ) );
>
> catch ( Exception & e ) <
printf ( «%s\n» , e . what ());
>
return 0 ;
>

Более сложный пример

#include «expressionEstimator.h»
#include
#include

std :: string arraytoString ( const double * v , const int arguments ) <
std :: string s = «[» ;
char buff [ 32 ];
for ( int i = 0 ; i arguments ; i ++) <
sprintf ( buff , «%lf» , v [ i ]);
s += buff ;
s += i == arguments — 1 ? «]» : «, » ;
>
return s ;
>

int main () <
ExpressionEstimator :: Init ();
ExpressionEstimator estimator ;
int i ;
const char * s ;
const char * expression []=< "sin(pi/4)" , "1+2+" >;
const int expressionSize = sizeof ( expression )/ sizeof ( expression [ 0 ]);
for ( i = 0 ; i expressionSize ; i ++) <
s = expression [ i ];
printf ( «\»%s\»=» , s );
try <
printf ( «%lf\n» , ExpressionEstimator :: calculate ( s ));
> catch ( Exception & e ) <
printf ( «%s\n» , e . what ());
>
>

const char * expression1 []=< "3*x0+2*x1*x0" , "6*x0" >;
const int expression1Size = sizeof ( expression1 )/ sizeof ( expression1 [ 0 ]);

const int arguments = 2 ;
const double values [][ arguments ]=< < 3 , 6 >, < 8 , 6 >>;
const int valuesSize = sizeof ( values )/ sizeof ( values [ 0 ]);

const double * v ;
for ( i = 0 ; i valuesSize ; i ++) <
v = values [ i ];
s = expression1 [ i ];
printf ( «\»%s\»%s=» , s , arraytoString ( v , arguments ). c_str ());
try <
estimator . compile ( s );
printf ( «%lf\n» , estimator . calculate ( v , arguments ));
> catch ( Exception & e ) <
printf ( «%s\n» , e . what ());
>
>

Javascript парсер

Чтобы использовать javascript парсер необходимо сначала включить script файл

Синтаксический разбор арифметических выражений

Дерево выражения


Рассмотрим арифметические выражения с обычным приоритетом операций. Сложение ( +) и вычитание ( —) имеют равный приоритет и более низкий (выполняются позже), чем умножение ( *) с делением ( /). Кроме этого, пусть существует унарный минус: -5, или -(3+5), или 3+-5=3+(-5). Несмотря на привычную операционную запись арифметических выражений, соответствующие действия являются функциями. Эти функции или бинарны (имеют два аргумента): plus(x, y) это «x+y» или унарны (один аргумент): inv(x) — это -(x).

Арифметическое выражение представимо в виде дерева. Например, дерево выражения 1*2 + 3*4 в корне имеет операцию сложения «+» и затем две ветви, в каждой из которых происходит умножение «*». В общем случае вызов вложенных друг в друга функций всегда образует дерево: Будем описывать арифметическое выражение (функцию) типа op(lf, rt) при помощи структуры вида , где op — это тип операции, lf — первый аргумент, и rt — второй. Так, выражение 1*2+3*4 имеет следующее представление: Статическая функция calc класса Parser, вычисляющая выражение выглядит следующим образом: Результат работы этой функции с выражением 1*2+3*4 в виде структуры, приведенной выше, равен . Аналогичный вид имеет функция Parser.get(expr), которая печатает выражения в виде строки типа: .

Порождающая грамматика

Синтаксис арифметических выражений (с учетом приоритета операций) будем задавать следующей порождающей грамматикой: Грамматика имеет смысл правил, по которым можно делать замены символов E, T1, T2, T3. В процессе таких замен происходит создание (порождение) некоторого арифметического выражения. Дерево начинает строиться с терма E (expression). Его можно заменить на одно из трех выражений (разделённых вертикальной чертой) из первой строки, например на: T1 + E. Затем необходимо сделать две замены для T1 и E, например (T2*T1) + T1. Далее, (T3*T2) + T2 и т.д., пока не доберёмся до числа N, на котором порождение останавливается.

Правила первой строки могут порождать цепочки T1 + T1 + T1 или T1 + T1 — T1 произвольной длины. Повторение терма E в конце правила E :- T1 + E образует «хвостовую» рекурсию, которая и генерит эти цепочки. Аналогичная хвостовая рекурсия стоит в правилах второй строки, определяющей структуру каждого слагаемого. Это даёт выражения вида T2*T2/T2*T2. Будем считать, что операции в таких цепочках выполняются слева направо: T2*(T2/(T2*T2)).

Фактически три терма T1,T2,T3 соответствуют трём уровням приоритета для операций ( + —), ( * /) и унарного минуса ( —). Подстановка правила T3 :- (E) из последней строки порождает вложенные скобки (..(..)..) любой глубины.

Вещественное число NUM также можно описать при помощи порождающей грамматики: Впрочем, это делать не обязательно и стоит воспользоваться средствами JS для конверации строки в число.

Генерация случайных выражений

В качестве демонстрации порождения арифметических выражений при помощи грамматики, напишем четыре функции. Результаты 10 вызовов функции getRandE(5) приведены справа (их можно пересчитать, нажатием кнопки Recalc ):

Функция MS.rand(3) возвращает равновероятно 0,1 или 2, т.е. MS.rand(n) равна Math.floor(Math.random()*n). Параметр max устраняет очень длинные рекурсии. После каждого вызова он уменьшается и, когда достигает нуля, вызываются «нерекурсивные» грамматические правила. Функции getRandT2 и getRandT3 несколько отличаются и уменьшают вероятность унарного минуса и повышают вероятность появления скобок.

Символы вне грамматики

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

Если комментариев нет — достаточно следующей функции: Текущее положение анализатора в строке хранится в переменной Parser.n. Функция Parser.skip(st) принимает строку st и возвращает новое положение, после пропуска (начиная с Parser.n) всех пробельных символов (меняя в себе Parser.n). При дохождении до конца строки, она возвращает -1.

Если есть комментарии, то функцию необходимо усложнить: Чтобы её протестировать, создадим два элемента textarea с соответствующими id и напишем следующий код:

Результаты работы Recalc :

Отметим, что функция Parser.skip не устраняет вложенные комментарии /* /* */ */. Для этого её необходимо модифицировать, подсчитывая число открывающихся ( /*) и закрывающихся ( */) скобок. Впрочем, для языков, поддерживающих строки, необходимо учесть наличие таких последовательностей внутри строк, например: /* » /*» */. Поэтому ограничимся запретом вложенных комментариев.

Синтаксический разбор

Перейдём теперь к синтаксическому разбору строки, в результате которого получится дерево выражения. Стартом для парсинга будет служить функция: Она обнуляет указатель this.n (текущее положение в анализируемой строке) и очищает строку с описанием синтаксических ошибок this.err. Затем вызывается функция парсинга терма E, реализующего грамматику E :- T1 + E | T1 — E | T1 После прочтения терма T1, выясняется наличие арифметических знаков + — и, если они есть, читается второй терм, который снова парсится функцией Parser.parseE (хвостовая рекурсия). Ошибка err будет генериться, например, для выражения вида «2 2».

Аналогично выглядит функция парсинга терма T1 :- T2 * T1 | T2 / T1 | T2:

Здесь уже нет обработки синтаксической ошибки, так как после терма T2 не обязательно идёт операция «*» или «/» (может быть «+», «-«).

Парсер математических выражений (c ++)

В конечном итоге я пытаюсь разобрать математическое выражение из строки (т.е. ((1 + 2) -3 * 45) «), чтобы встроить его в дерево двоичных выражений. Однако цель следующего фрагмента кода состоит только в том, чтобы разобрать символы в массив строк, чтобы сгруппировать отдельные цифры многозначных чисел в один и тот же индекс.

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

Я хочу, чтобы «((1 + 2) -3 * 45)» стало [«(«, «(«, «1», «+», «2», «)», «-«, «3», «*», «45», «)»]

Вот код, с которым я не могу найти проблему. Компилируется нормально но вылетает. Отладчик VS2010 не показывает мне, на какой линии произошел сбой.

Решение

Ты используешь stringArray как массив, но на самом деле это только один элемент.


Лучший способ — использовать std::vector вместо массива в стиле C. Другими словами заменить

И внесите соответствующие изменения в другие места, которые использует ваша программа stringArray , В интернете есть множество учебников о том, как использовать std::vector ,

Виктор Зинкевич

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

среда, 5 октября 2011 г.

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

Однажды мне нужно было создать парсер математических выражений. Я взялся за этот труд и сразу же понял, что используя посимвольный разбор, я просто погрязну в большом количестве строк кода. Тогда на помощь пришел очень замечательный инструмент — регулярные выражения. Использовать регулярные выражения в Delphi или Builder’е стало легко возможным благодаря подключению модуля RegExpr.pas, созданного Андреем Сорокиным. Всё о регулярных выражениях Вы можете найти на его сайте: http://RegExpStudio.com/ Итак, приступим к созданию самого парсера.

Нашему парсеру мы передаем выражение в виде строки, а он возвращает результат тоже в виде строки символов.

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

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

Ну, а теперь на деле. Создадим класс TExParser, в который мы заключим все необходимые нам функции.

[C++]парсер матем. выражений

Уважаемые,
возник такой вопрос: есть ли на С++ парсер несложных математических выражений. На пример «(<1>*<2>)-sin(<3>)/4″, где в <> указан номер элемента массива.
Массив я получаю в ходе выполнения программы, а выражение задается пользователем. Выражения содержат самое необходимое (+ — / * sin() cos() и пр, что есть с стандартной мат библиотеке для С++).
Если такая штука есть под Qt — вообще супер.

а если тебе нужен простой наколенный парсер, то он пишется за пару часов

можно например транслировать нехитрыми заменами твое выражение в ecma и запускать через скриптовый движок в qt ^_^

это руками пишется за полчаса

Могу залить куда-нибудь вечером свою поделку 6-летней давности: всего один классец, работает стабильно и шустро, поддерживает переменные, константы, сокращенную запись умножения

Могу залить куда-нибудь вечером свою поделку 6-летней давности: всего один классец, работает стабильно и шустро, поддерживает переменные, константы, сокращенную запись умножения

если не сложно — spike@me.by

на flex+bison такое пишется за 10 минут

У Страуструпа где-то в первых главах калькулятор с таким парсером приведен в качестве примера. Можно прямо из книжки скопипастить.

> это руками пишется за полчаса

Ну только если предварительно код наизусть выучить, а потом по памяти набирать ;)

Можно у Страуструпа списать. У него как раз в примерах и был калькулятор с четырьмя простейшими действиями. Добавить еще функций будет несложно.

А можно выдрать нужное из bc :)

> на flex+bison такое пишется за 10 минут

Может сделаете скринкаст (ведь всего 10 минту, это как сходить покурить)? Уж очень хочется понаблюдать за работой мастера.


наверное, лучше самому, «посоветовавшись» со Страуструпом)

попробовал, как раз 10 минут уходит на написание и тестирование двух файлов (.l, .y), если делать к этому хозяйству интерфейс, то будет чуть дольше

да простой recursive-descent парсер написать, там нефиг делать же

>да простой recursive-descent парсер написать, там нефиг делать же

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

>а если тебе нужен простой наколенный парсер, то он пишется за пару часов

Начитанным плюсистом нормальный наколенный парсер пишется ещё быстрее, ибо разобран в Страуструпе =)

> Начитанным плюсистом нормальный наколенный парсер пишется ещё

быстрее, ибо разобран в Страуструпе =)

У Страуструпа не совсем то. Во-первых, там нет поддержки функций, а для их добавления нужно существенно переработать и усложнить код. Во-вторых, там и делается не совсем то, ибо расчёт ведётся немедленно, по ходу разбора выражений, а автору надо, скорей всего, сохранять выражение в виде некоего объекта, который потом можно будет многократно вызывать с разными наборами данных, а это тоже проблема несколько другого уровня.

Да ну вас, извращенцев:)

+1 к связке flex+bison

а еще лучше сделать нужных биндингов и просто кормить формулу скрипту, заменив индексы на индексы конкрентного объекта, передаваемого в скрипт.

заменить индексы я могу и regexp’ом и в конце получить исключительно само выражение с цифрами, другое дело, что я заранее не знаю вид этого выражения.

> если не сложно — spike@me.by

Сорри, забыл вчера. Скину сегодня, если еще актуально

Начитанным плюсистом нормальный наколенный парсер пишется ещё быстрее, ибо разобран в Страуструпе =)

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

пока остановился на решении такого рода
«<1>+<2>» заменяется цифрами и получаю типа

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

Как написать парсер математических выражений? Надо реализовать не только операторы ( + , — , / , * ), но и функции, например log , sin , cos , tan и т.д.

У математических выражений довольно простая структура — только бинарные операции («+», «*» — два аргумента), унарные операции («-«, «sin» — один аргумент), и числа.

Один из наиболее простых способов написания парсера — это «рекурсивный спуск», т.е. написание парсера руками, без какого либо генератора парсеров (Bison, Boost.Spirit).

Хотя парсер может вычислять сразу выражение, обычно от парсера ожидается дерево операций, которое уже потом можно вычислить, или например напечатать. В простейшем виде элемент дерева выглядит так:

Парсер математических выражений можно описать с помощью трех основных функций:

  • парсер «токенов» — низкоуровневых элементов выражения — операций и чисел. Например 2 , * , — , 1 для выражения 2 * -1 .
  • парсер простых выражений — числа, унарные операции, выражения в скобках. Например выражения 1 , -1 , (1+2) .
  • парсер бинарных выражений — два простых выражения, и бинарный оператор между ними. Например выражения 1 + 2 , или 3 * (1+2) .


Соответственно можно написать такой класс парсера:

Функция-парсер токенов извлекает из строки один токен, и продвигает input вперед.

Имея парсер токенов, можно написать парсер простых выражений:

И наконец, последняя и самая сложная часть — бинарные выражения. У бинарных операций есть приоритеты, например у + и — приоритет меньше чем у * и / , у ** (возведение в степень) приоритет больше чем у умножения. Напишем функцию, возвращающую приоритет бинарной операции:

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

Функция parse() просто вызывает парсер бинарных выражений, передавая ему нулевой минимальный приоритет операций (любая бинарная операция):

Для строки «3*4/5» код работает так:

Если приоритеты повышаются, например 2+3*4/5 , то во вложенных вызовах parse_binary_expression успевает отработать дольше:

Итак, у нас есть парсер. Но надо еще как-то вычислять результаты парсинга. Это можно сделать одной функцией:

Допустим у нас уже есть простой интерпретатор (калькулятор) арифметического выражения в строке (scalc.c scalc.h) и мы хотим добавить к нему функции.

Калькулятор получает строку с выражением и интерпретирует ее, используя известный алгоритм с двумя стеками (операндов и операций) до первой встреченной ошибки. Несколько упрощенно (выброшен анализ ошибок структуры выражения и вспомогательные функции) его код может быть таким:

Что же нужно сделать с таким кодом, если мы захотим всяких синусов, логарифмов и т.п.?

Понятно, что функция это операция, похожая на унарный минус (который наш лексер выдает как ‘M’), которая в отличии от него применяется к нескольким операндам и заменяет их все своим результатом. Пусть это будет операция ‘F’. А вот синтаксически имя функции похоже на число (цепочка символов), поэтому распознавать его придется не как символы остальных операций. Аргументы функция заключены в скобки и разделены запятыми. Появляется еще одна операция — ‘,’. Она напоминает закрывающую скобку с тем отличием, что дойдя до открывающей скобки в процессе вычисления операций из стека в eval() она не «аннигилирует» вместе с ‘(‘, а исчезает сама, оставив результат на вершине стека операндов.

Функции могут быть вложенными, но это нас уже не пугает, т.к. в этот момент становится очевидно, что также как и другие операции, вызовы функций вместе с информацией об операндах помещаются в стек. Тут встает вопрос, либо менять формат стека операций (сейчас элемент этого стека просто один char, а для реализации функций дополнительно требуются адрес функции и значение SP стека операндов, т.е. точки в стеке операндов, где начинаются аргументы), либо добавить еще один стек для этих данных.

Посмотрев на эти рассуждения мы осознаем, что запросто можем добавить в наш калькулятор переменные, а значит еще одну операцию — присваивание (допустим ‘S’). В отличии от других операций эта будет допустима только в начале выражения.

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

Получаем вот такой интерфейс:

Для доступа к переменным и функциям калькулятора реализуем:

Теперь можно вернуться к коду. Структуры данных:

Изменения и дополнения кода (непосредственно относящиеся к нашему вопросу).

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

Поскольку теперь в стеках хранятся не только элементарные ****** и char, но и структуры в стеке фунцкций, придется модифицировать макросы TOP/POP так, чтобы они возвращали указатель на данные.

В код expr() (выполнение элементарных операций) вставим вызов функции. Это явно системозависимя часть и тестировалась только на x86 (32 и 64 bit). Реализация основывается на том, что у нас все функции получают аргументы типа ****** и функция возвращает результат ******. Если бы это было не так (если бы мы решили реализовать в калькуляторе еще и целые (и строки?)), то для 32-bit x86 понадобилось бы на ассемблере формировать стек вызова перед call, а на 64-bit заполнять аргументы разных типов (откровенно говоря, для linux/gcc только long и ******) данными из нашего стека операндов.

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

Приоритеты операций стали такими

А вот в eval() добавилось довольно много кода

С учетом анализа возможных ошибок в записи выражения код основной функции приобрел вот такой вид

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL