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

Общее описание сайта и математическая теория создания фрактальных изображений здесь.

Одна из основных задач, которые пришлось решить в ходе создания сайта «Fun with Fractals», заключается в следующем:

Задача. На основе понятного для человека описания функции комплексного переменного составить ее представление, позволяющее вычислять ее значения при помощи JavaScript или WebGL.

Постановка задачи

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

a * (cosh z + 0i3.0) ^ 2 - c

(детали — в справке). Эта форма может содержать следующие базовые элементы:

  • Вещественные числа в обычном для языков программирования формате (целая часть отделяется от дробной точкой), например, 3.1415 или -2.
  • Комплексные числа в формате
    <действительная часть>(i|j)<мнимая часть>

    например 0i1 (мнимая единица), -1j5.5, 2.818i-3.2.

  • Комплексные переменные, обозначаемые большими и малыми латинскими буквами, например, A, T, c, x. Переменная z имеет смысл аргумента определяемой функции. Остальные переменные служат параметрами функции; они позволяют упростить ее запись.
  • Бинарные арифметические операции (+, -, *, /, ^).
  • Унарные функции комплексного переменного: sinh, cosh, exp, log и так далее. Некоторые из этих функций (например, логарифм), строго говоря, не являются однозначными; в этом случае под значением функции подразумевается одна из ее ветвей.
  • Скобки, позволяющие изменять приоритет операций.

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

a * (cosh z + 0i3.0) ^ 2 - c

соответствует обратная польская запись

a z cosh 0i3.0 + 2.0 ^ * c -

При вычислении функции обратная польская запись интерпретируется так:

  • числам и переменным соответствуют операции помещения в стек;
  • операции означают извлечение соответствующего количества аргументов и стека и помещения в стек результата операции.

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

Решение

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

1. Лексический анализ

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

В результате для приведенного выше примера получается список элементов

Приоритеты для операций соответствуют здравому смыслу:

Операция Базовый приоритет
+, — 0
*, / 1
^ 2
(унарные) 3

2. Обработка чисел и переменных

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

a * (cosh z + _0) ^ _1 - c

где введены две новые переменные _0 = 0i3.0, _1 = 2.0.
В результате выполнения этого этапа получается измененный массив

и переменные

3. Вычисление приоритетов операций

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

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

4. Построение дерева операций

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

Дерево операций
Дерево операций для функции из примера

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

  1. найти в текущем массиве элементов операцию с наибольшим приоритетом;
  2. присоединить к этой операции стоящий справа и слева (в случае бинарной операции) элементы в качестве детей.
  3. повторять шаги 1–2, пока необработанных операций не останется.

Бинарные операции следует обрабатывать слева направо (чтобы, например, результат вычисления 1 / 2 / 4 был равен 0.125 = (1 / 2) / 4, а не 2 = 1 / (2 / 4)). Унарные операции, наоборот, надо обрабатывать справа налево, чтобы запись вроде sinh cosh z имела смысл.

5. Обход дерева

Когда известно дерево операций, построение обратной польской записи становится тривиальной задачей. Для этого достаточно рекурсивно обойти дерево:

Итак, в результате синтаксического анализа получается обратная польская запись и список использованных переменных и чисел. Эти данные используются для рисования фрактала с помощью JavaScript или WebGL.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *