Использование конечных автоматов для вычисления арифметических выражений. Выполняли



Дата17.04.2016
өлшемі94.32 Kb.
Использование конечных автоматов для вычисления арифметических выражений.
Выполняли:

Богданов Дмитрий

Томкевич Алина

Руководитель:

Лапо Анжелика Ивановна


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

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

  • Исследовать преимущества, недостатки и особенности автоматного подхода к решению задач


Конечный автомат – математическая абстракция.
Конечный автомат представляет собой:

  • Множество состояний Q

  • Начальное состояние q0

  • Множество конечных состояний F Ì Q

  • Допустимый входной алфавит A

  • Множество возможных выходных действий Z

  • Функция перехода δ: Q ´ A ® Q

  • Отображение λ: Q ´ A ® Z

Конечный автомат по входной последовательности символов допустимого алфавита генерирует последовательность выходных действий. В начальный момент времени (t = 0) он находится в начальном состоянии s[0] = q0. Затем в каждый дискретный момент времени (t > 0) он получает очередной символ входной последовательности x[t]A и генерирует свое следующее положение




и очередное выходное действие

Если по завершению входной последовательности автомат находится в конечном состоянии, то считается, что последовательность им принята, иначе – отклонена.

Другими словами, автомат можно представить в виде ориентированного графа, в котором каждому состоянию соответствует вершина, а каждой дуге ­­– некоторый символ и выходное действие. В момент времени t = 0 мы находимся в начальной вершине, и каждый раз, получая символ, переходим по дуге, соответствующей этому символу, выполняя также и выходное действие, соответсвующее этой дуге. Передвигаясь по дугам графа, мы должны придти в конечное состояние, и тогда последовательность будет считаться принятой.
Ход работы
Работа выполнялась поэтапно. На первом этапе был выбран способ представления автомата, на втором реализована поддержка арифметических операторов и вещественных чисел. Далее была добавлена поддержка скобок и функций.
1ый этап – конечный автомат в поставленной задаче.
Реализовать конечный автомат удобно в виде класса. На самом деле – нас абсолютно не интересует, как именно будет реализован в автомате граф, нам нужна только возможность создать автомат, добавить в нем переход и получить результат. Класс назвали TFsm (по-английски finite state machine – конечная машина состояний). Выполнение выходных действий логично отделить от функционирования автомата, для этой цели мы выделили класс TPerformer.

Итак, для класса TFsm нам необходимо определить следующие методы:



TFsm(int nStates, TState begin) – конструктор, создает граф на нужное количество вершин и устанавливает начальное состояние.

void setFinite(TState finite) – устанавливает состояние конечным.

void addArc(TState a, TState b, symbols, TAction action) – добавляет переходы (дуги в графе) из состояния a в состояние b по символам symbols с выполнением действия action.

Заметим, что мы несколько отходим от первоначальной концепции, в которой переход шёл по одному символу, а не по нескольким. Такое расширение удобно, т.к. часто из одного состояния в другое с одним и тем же действием идет не один, а несколько переходов (например, по всем цифрам или по всем операторам). Также возможна реализация этого метода с передачей функции проверки bool suits(char с) вместо string symbols. Функция проверяет, нужно ли переходить по данному символу.



TResult* make(string x) – осуществляет работу автомата со строкой x. В случае успешного завершения возвращает указатель на результат (хранится в исполнителе), иначе NULL, что означает, что строка не принята автоматом (или в какой-то момент по текущему символу не нашлось никакого перехода).

Нам кажется, что концепция класса автомата и класса исполнителя пригодна для использования при решении различных задач.
2ой этап – ожидаемые преимущества.
v.1.0, целые числа и оператор сложения.

Для построения схемы автомата нам потребуются состояния числа (NUMBER) и оператора (OPERATOR). Если в данный момент мы находимся в состоянии NUMBER, и к нам приходит цифра, то нужно остаться в этом состоянии, изменив текущее число (действие addDigit), а если оператор, то прибавить к сумме текушее число (doOperator), при этом переходя в состояние OPERATOR. После оператора может идти только цифра и соответственно, состояние NUMBER. Успешной работа автомата может считаться в том случае, если выражение закончилось числом, которое при этом нужно прибавить. Для этой цели добавим также в конце выражения символ = (End) и переход по нему в состояние END (конечное) с действием finalize (прибавляет текущее число к результату). Начинаться выражение должно с числа – значит, начальным состоянием будет NUMBER. Схема автомата будет выглядеть так:

(x0,x1,x3 – символы алфавита по которым будет происходить переход, z0,z1,z3 соответствующие действия. Например x1 – isDigit, т.е. переход по цифре, z1 – addDigit, т.е. добавить цифру к текущему числу)
На данном этапе исполнитель поддерживает три выходных действия addDigit, doOperator, finalize. Необходимо хранить текущее число и текущую сумму. Собрав вместе вышесказанное, получаем:



V.1.1, вычитание.

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





V.1.2, умножение и деление.

Чтобы добавить оператор умножения (а также и деления), нужно учитывать приоритет операторов. Нужно ли для этого добавлять новое состояние (например OPERATOR_MUL)? Нет, потому что все равно после любого оператора (из состояния OPERATOR) должно идти число (переход в состояние NUMBER), и не имеет смысл загружать структуру автомата состоянием, из которого идут те же самые переходы. Может быть тогда следует сделать новый переход с новым выходным действием (например doOperatorMul)? Тоже нет, но по иным соображениями: у нас имеется два уровня абстракции – автомат и исполнитель. Автомат встречает оператор умножения, синтаксически этот оператор ничем не отличается от оператора сложения, с точки зрения автомата нужно просто его выполнить, а вот как – это уже дело исполнителя.

Таким образом, если четко сформулировать наши соображения:


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

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

Для реализации умножения и деления в исполнителе использовался следующий подход – выражение представляется как сумма произведений чисел: хранится текущее произведение и текущая сумма произведений. Соотвественно нужно хранить как последний символ с приоритетом 2 (сложение или вычитание), так и с приоритетом 1 (умножение или деление).

V.1.3, вещественные числа

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

Введем состояние FRAC для дробной части. Из состояния NUMBER добавим в него переход по точке. Из него могут идти те же переходы, что и из состояния NUMBER (в END, в OPERATOR), и переход в себя с добавлением цифры к числу справа (addFracDigit, в дробную часть). Важно, что переход из FRAC по точке не существует, это причина, по которой мы ввели это состояние. На схеме – часть внесённых изменений.

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



  • состояние EXPONENT, аналогичное FRAC.

  • состояние E, соответствующее символу е. Возникает вопрос, почему мы не добавили состояние точка (POINT), а E добавили? Потому что, если мы сразу из состояния NUMBER перейдем в состояние EXPONENT, то не ясно, что делать, если в состоянии EXPONENT придет минус. Он может означать как лидирующий минус в экспоненте, так и конец числа, а это разные переходы. Значит, нам необходимо дополнительное состояние, в котором будет возможен по минусу только один переход.

  • состояние MINUS_EXPONENT, после которого переход только в состояние EXPONENT, чтобы не допустить повторения двух минусов подряд (сначала лидирующий, а потом сразу после него арифметический).

Соответственно, нужно добавить и новые переходы.

Вернемся к исполнителю. Нужна переменная чтобы хранить экспоненту, мы ее добавили и выделили класс TNumber, в котором будет храниться все, что относится к текущему числу. Также добавили поле isPlusE, значение которого определяет знак экспоненты (действие setExponentMinus устанавливает его равным true).


3ий этап – Неожиданные возможности
v.2.0, скобки.

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

Для реализации такого рекурсивного подхода исполнитель будет поддерживать стек текущих выражений. Каждый его фрейм будет содержать те же данные, что и исполнитель в предыдущей версии программы. Все действия, не связанные со скобками, будут исполняться над самым верхним фреймом стека. При переходе в состояние OPEN мы будем выполнять действие newFrame, при переходе в состояние CLOSE – deleteFrame. Новое действие newFrame добавляет в стек новый фрейм, а deleteFrame подсчитывает значение верхнего фрейма, устанавливает его в текущее число num предыдущего, попутно удаляя из стека верхний фрейм (фактически производит возврат из рекурсии).

Добавить переходы в OPEN нужно из OPERATOR, из OPEN – в NUMBER, в CLOSE из всех состояний на которые может заканчиваться число (NUMBER, FRAC, EXPONENT), из CLOSE в OPERATOR. Кроме того, будет удобно сделать OPEN начальным состоянием, a CLOSE конечным, и изначально заключить наше выражение в скобки.

Заодно аналогично MINUS_EXPONENT, можно добавить поддержку лидирующего минуса у числа, добавив состояние MINUS_NUMBER и соответствующие переходы.



v.3.0, функции.

Для поддержки функций мы



  1. Добавим оператор запятая (состояние COMMA) для разделения параметров функции, который позволит вместо одного числа в качестве текущего результата хранить список чисел. Когда мы переходим в состояние COMMA, мы завершаем вычисление текущего выражения, добавляем в этот список новый элемент, над которым будем проводить вычисление выражения после запятой. То есть значением выражения 1,2+2,3 будет список (1,4,3).

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

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



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

  2. Изменяем действие deleteFrame: теперь, если в предыдущем фрейме у нас есть идентификатор, то в текущее число предыдущего фрейма мы устанавливаем значение функции от результата верхнего фрейма. Ловко?

На этом «наворачивание» нашего автомата мы заканчиваем. Версия 3.0 содержит 11 состояний и 37 переходов, и нарисовать схему автомата уже не так просто…



Пришло время для выводов.
Выводы

  • Последовательно добавляя возможности, был разработан автомат, вычисляющий арифметическое выражение.

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

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

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

  • Грамотно построенный автомат, по определению содержит массу проверок на ошибки различного рода, которую сложно реализовать в полном объеме используя другие методы программирования.

  • Было сформулировано несколько важных принципов для решения задач при помощи конечных автоматов.

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

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

  • Автоматный подход – удобный и перспективный подход к решению сложных задач, имеет массу преимуществ.


Достарыңызбен бөлісу:


©netref.ru 2019
әкімшілігінің қараңыз

    Басты бет