Стековая организация данных
Для создания анализатора синтаксических выражений необходимо создать рассмотреть структуру на основе, которой данный анализатор будет основан. В ходе экспериментов в области программирования было вявлено, о наиболее удобная структура для анализа скобочных выражений это стек.
Стек (англ. stack) - это абстрактная структура данных для хранения набора элементов, обработка которого допустима только с одного конца, называемого вершиной стека. Положение вершины в стеке отображает указатель стека sp (англ. stack pointer). Через вершину в стеке можно добавить новый элемент или извлечь последний добавленный элемент, изменяя при этом соответствующим образом указатель стека. Извлекать элементы из стека и добавлять элементы в стек можно не однократно, пока стек не пуст и не переполнен, соответственно. Реализуемая стеком дисциплина обслуживания набора данных называется LIFO (LastIn, FirstOut - последним пришел, первым вышел).
Структура стека прежде всего должна иметь высокую степень защиты, поэтому описание класса стека находиться в классе, у которого невозмоно извлечь переменные для их редактирования в памяти. Листинг, описываемого класса стека с фиксированным буфером представлен ниже:
|
public class FixStack { private int sp; private int ssize; private char[] sbuf;
public FixStack() { … }
public FixStack(int size) { … }
public void push(char ch) { … }
public char pop() { … }
public int getState() { … }
public void setSize(int size) { … } } |
Листинг 1.5. Листинг класса FixStack.
Рассмотрим структуру стека подробнее. Как упоминалось выше sp – это вершина стека, которая меняет своё значение в зависмости от количества символов стека. Когда она в нулевом состоянии, тогда стек считается пустым. Для хранения данных в стеке выделяется специальный буфер sbuf (stack buffer). В данном случае буфер стека реализуется одномерным массивом, длина которого устанавливает предельный размер стека ssize (stack size), задаваемый при создании стека. Такая организация стека называется стеком с фиксированным буфером (FixStack). Логическую структуру стека с фиксированным буфером, в котором содержатся 3 элемента: A, B, C отображает следующий рисунок.
Рис. 1. Логическая структура стека с фиксированным буфером.
Для работы состеком используются три процедуры: push, pop и getState, которые обеспечивают извлечение данных из стека, загрузку данных в стек и оценку состояния стека, соответственно.
Примитив push загружает новый элемент в вершину стека и увеличивает на 1 значение указателя стека. Тип элемента должен соотвествовать типу данных принимаемых стеком. Другими словами, он должен соотвествовать типу буфера, который хранит эти элементы. Ниже представлен код, характеризующий данную процедуру:
|
public void push(char ch) { sbuf[sp] = ch; sp++; } |
Листинг 1.6. Листинг метода push.
Визуально работу данного метода можно отобразить на рисунке, представленном ниже:
Рис. 2. Диаграмма загрузки в стек.
Примитив pop уменьшает на 1 величину указателя стека и возвращает значение текущего элемента из вершины стека. Результат возврата примитива pop может быть присвоен соответствующей по типу переменной программы, использующей стек. Листинг данного метода изображён ниже:
|
public char pop() { sp--; return sbuf[sp]; } |
Листинг 1.7. Листинг метода pop.
Работу примитива pop иллюстрирует следующая диаграмма извлечения данных из стека.
Рис. 3. Диаграмма извлечения данных из стека.
Извлечённые элементы, как видно из рисунка, не уничтожаются, а остаются в буфере стека до того момента пока не будут заменены новыми элементами. Очевидно, что процедура добавления данных в стек имеет деструктивный эффект т.е. новый элемент будет сохранён поверх предыдущего элемента на его позиции. Рассмотренные примитивы push и pop обеспечивают желаемую обработку стека с фиксиксированным буфером, когда он не переполнен (sp < ssize) и не пуст (sp = 0), соответственно.
Для оценки текущего состония стека используется примитив getState. Данная процедура также представляет собой геттер, о значении которого было описано выше. Однако в данном случае геттер имеет модифицированную структуру, которую необходимо описать. Данный метод обеспечивает оценку заполненности стека по возвращаемому значению его указателя. Целесообразной представляется следующая кодировка возврата примитива getState. Если при оценке в буфере стека нет свободного места для размещения новых данных, т.е. буфер заполнен полностью, возвращается отрицательный код. В противном случае, когда в буфере стека есть свободное пространство для размещения новых элементов, при оценке стека примитивом getState возвращается текущее значение указателя стека. Очевидно, когда стек пуст примитив getState будет возвращать нулевое значение.
Листинг примитива getState:
|
public int getState() { if ( sp < ssize ) return sp; else return -sp; } |
Листинг 1.7. Листинг метода getState.
На следующем рисунке представлены 3 диаграммы состояний для пустого, допустимо заполненного и переполненного стека, которые иллюстрируют принятую кодировку возврата примитива getState.
Рис. 4. Диаграмма состояний стека.
Помимо выше приведённых процедур необходимо добавить конструкторы стека. Конструкторов класса может быть несколько. Это вызвано тем, что разработчик посредством разных конструкторов может передавать разные входные данные классу, либо оставлять класс в начальных условиях. Листинг конструкции из двух таких конструкторов представлен ниже. Первый конструктор рассматривает начальные значения стековой структуры, второй принимает на вход начальный размер стека.
|
public FixStack() { sp = 0; ssize = 32; sbuf = new char[32]; }
public FixStack(int size) { sp = 0; ssize = size; sbuf = new char[size]; } |
Листинг 1.8. Листинг конструкторов класса FixStack.