Интерпретация строковых выражений как функций

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

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

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

1/(5*6 + x^0.5 + y*0.8) или 
(A == B AND C != 5) OR (D != 'abc')

Эти выражения являются сложными, но их можно свести к простому виду

[ПЕР1] [Функция1] [ПЕР2]

Операторы сравнения также являются функциями, например оператор != получает значения 2-х переменных и возвращает "0" или "1". Пусть [Функция1] возвращает значение [Значение1], тогда процесс упрощения строки может вестись следующим образом:

$A == 34 AND $C != 5
[ПЕР1] = $A, [ПЕР2] = 34, [Функция1] = "=="

После выделения функции заменяем ее в исходной строке возвращаемым значением:

[Значение1] AND $C != 5,
[Значение1] AMD [Значение2],
[Значение3]

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

# Массив аргументов - констант
my @F_args_const;
my $Ch_args_const;

# Ассоциативный массив аргументов - переменных
my %zn_p;

# Массив аргументов - результатов функций
my $F_rez;

# Массив указателей на аргументы функции
my @F_args_p;

# Указатель на функцию
my $F_Name_p;

# Два указателя на аргументы функции
my $F_arg_p1;
my $F_arg_p2;

Для тех, кто не знаком с синтаксисом PERL поясню, что если перед именем переменной стоит знак "$", то переменная является скаляром и может содержать любое единичное значение: строку, число, указатель на объект. Если "@", то это массив скаляров, обращаться к каждому элементу массива можно используя имя массива с указанием перед ним знака "$" (то есть элемент массива - скаляр) и индекса в квадратных скобках после имени. Если "%", то это ассоциативный массив, обращаются к нему так же, как и к обычному, только вместо индекса в квадратных скобках указывается строковое выражение в фигурных.

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

# Определение функции "=="
sub ravno_ch
{
my $str1 = $_[0];
my $str2 = $_[1];
if ($str1 == $str2) {return 1;};
return 0;
};

# Значения, полученные из начальной строки
my $ARG1 = '$A';
my $ARG2 = '34';
my $FUNC = '==';

# Заполнение данных о функции
if ($FUNC eq '==')
{
$F_Name_p = \&ravno_ch;
};

# Запоминаем ЗНАЧЕНИЕ $ARG2 в мессиве констант
$F_args_const[0] = $ARG2;
# Запоминием УКАЗАТЕЛЬ на первый аргумент функции
$F_arg_p1 = \$zn_p{$ARG1};
# Запоминием УКАЗАТЕЛЬ на второй аргумент функции
$F_arg_p2 = \$F_args_const[0];

Теперь несколько слов о вызове функции и о задании её аргументов. С константным аргументом всё просто, его значение сохранено в массиве констант и при каждом расчете значения функции оно будет использоваться. Значение же переменной $A будет храниться в элементе ассоциативного массива $zn_p{'$A'}. Его можно будет легко задавать перед каждым расчетом.

# Запоминаем текущее значение переменной
$zn_p{'$A'} = 12;
# Вызываем функцию
$F_rez = &$F_Name_p($$F_arg_p1, $$F_arg_p2);

Знак "$$" перед именем переменных F_arg_p1 и F_arg_p2 означает, что при расчете нужно брать не значения этих переменных (в них лежат указатели), а данные, на которые они указывают. Знак "&$" перед именем F_Name_p означает, что нужно вызвать функцию, указатель на которую записан в переменной $F_Name_p.

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

Оставить комментарий

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

Если вы не являетесь зарегистрированным пользователем, то вам необходимо зарегистрироваться. Регистрация бесплатна. Если вы уже зарегистрированы на CodeNet, то вам необходимо ввести логин и пароль в верхней (Alt-U) части страницы.

Комментарии