Программирование САПР
.pdfЛингвистическое программное обеспечение САПР
подготовил Визигин Д.В
Введение. Установка и настройка интегрированной среды для ведения разработки на языке Java.
Java – это объектно-ориентированный язык, разработанный компанией Sun Microsystems. Программы на Java транслируются в байт-код, выполняемый виртуальной машиной Java (JVM) — программой, обрабатывающей байтовый код и передающей инструкции оборудованию как интерпретатор. Байтовый код при этом обрабатывается намного быстрее, чем обычный текст.
Для ведения разработки САПР на языке java наиболее удобно использовать сторонние инструменты, не являющиеся стандартными, но которые популярны в данный момент. Такими средствами являются интегрированные среды разработки (англ. Integrated Development Environment) и соответсвующие необходимые им плагины.
В начале рассмотрим, что из себя представляет функционально среда разработки
программного обеспечения (также интегрированная среда разработки, IDE), это программный
пакет, используемый программистами для разработки программного обеспечения. Из наиболее известных Eclipse IDE, IntelliJ IDEA и Netbeans.
Для ведения разработки мы будем использовать Eclipse IDE в виду наибольшей распространённости, популярности, наращиваемости и простоты использования данного пакета. Eclipse IDE является свободно распротраняемой средой разработки с открытым исходным кодом, поэтому это делает возможным её установку под разные системы. Рассмотрим установку и настройку данного пакета в системе Windows:
1. Первое, что необходимо сделать это загрузить средства разработки Java, включающие компилятор, интерпретатор и основные функциональные элементы, с официцального сайта разработчика (www.oracle.com). Рекомендуется загружать наиболее полную версию JRE (Java Runtime Environment), которая включает минимальную версию виртуальной машины.
2.Далее, необходимо загрузить дистрибутив пакета Eclipse IDE с официального сайта www.eclipse.org/downloads.
3.При запуске вам необходимо указать директорию, в которой будут храниться ваши проекты и разработки.
Лабораторная работа 1. Анализатор скобочных алгебраических выражений.
Цель работы: практическое изучение программной реализации стека с использованием объектно-ориентированной модели языка программирования высшего уровня, на основе алгоритма синтаксического анализа расстановки скобок в алгебраическом выражении.
Формулировка задания: требуется разработать программу synAnalyzer для синтаксического анализа произвольного синтаксического выражения с целью проверки правильности расстановки в нём круглых скобок, квадратных и фигурных скобок. Подготовить данную программу для дальнешего наращивания.
Исходными данными анализатора является строка символов, алгебраическое выражение. Строка алгебраического выражения должна передаваться программе из потока стандартног ввода
(System.in).
Результатом работы программы, на данном этапе является оценка соответствия открывающих и закрывающих скобок во входном алгебраическом выражении. Результат оценки должен быть представлен текстовым сообщением о результате соотвествия количества скобок, либо ошибкой о каком-либо несоотвествии скобок. Результатом будет является сообщение в потоке стандартного вывода (System.out).
Общая обработка программы должна управляться отдельным классом-парсером. Для синтаксического анализа расстановки скобок требуется применить стековый алгоритм обработки скобок, использующий стек с фиксированным буфером.
1.1. Общая схема парсера
Парсер – это сленговое слово от английского parse (анализ, разбор, произволить структурный анализ). В общем смысле, так назвают программы, которые производят соответсвующее действие, разбивая исходный объект на отдельные части и анализируя каждую часть своим алгоритмом. Примерами работы таких программ может быть: анализ, а в последствии подсветка кода в регулярно-используемых выражениях языков программирования, проверка текста на наличие синтаксических ошибок и граматических ошибок и тд. Понимать структуру работы парсера прежде всего важно потому, что все компиляторы и интепретаторы основаны на таких парсерах. Отличается только алгоритм анализа и обработки данных.
Задача синтаксического анализатора – создание последовательности символов дерева операций конечного языка. Схема его работы представлена на рисунке 1.
Грубо описать его работу можно на примере обычного цикла который перебирает все значения входной строки и проверяет в ней наличие известных лексических едениц (лексем).
Лексемой может являться число, оператор либо как в нашем случае тот или иной вид скобки. Для анализа конкретной лексемы будет использоваться свой собственный класс, который определённым образом определяет ту или иную лексему.
Ниже приведён листинг, который отображает общую реализацию парсера для любой лексемы. Проведём разбор каждого метода в данной реализации.
Листинг класса TokensParser:
public class TokensParser {
private List<TokenParser> parsers; private int pos;
public TokensParser() {
…
}
public List<TokenParser> getParsers() {
…
}
public void parse(String source) {
…
}
}
interface TokenParser {
public boolean parseToken(String source, int currentIndex);
}
Листинг 1.1. Листинг класса TokensParser.
Так как мы подразумеваем в дальнейшем расширять нашу программу, нам необходимо где-то хранить все созданные нами анализаторы, поэтому инициализируем переменную parser типа <List>. Она будет хранить их по мере того как мы будем добалять их в программу. Тип <List> аналогичен типу Array, за исключением того, что он более защищён и значения в нём можно перебирать без инициализации дополнительной переменной итерации i. Переменная pos отвечает за перемещение по строке символов т.е. когда на вход нашей программы подаётся строка мы начинаем анализ с нулевого символа и двигаемся от символа к символу проверяя в строке наличие определённых нами лексем.
Первый метод, называется конструктором класса т.е. при вызове класса TokensParser зарезервированным словом new автоматически выполниться метод TokensParser(). Формально метод-конструктор – это начальные условия какого либо класса, к которому мы обращаемся. Поэтому в
правилах хорошего тона программирования неоходимо, чтобы инициализация всех переменных класса происходила именно в этом методе-конструкторе. Помимо этого, необоходимо добавить все анализаторы, которые будут работать по своим особенным алгоритмам. Не будем использовать какую-либо переменную под анализаторы, а просто добавим (add) их в список обычными конструкторами класса.
Ниже представлен листинг метода-конструктора TokensParser:
public TokensParser()
{
pos = 0;
parsers = new ArrayList<TokenParser>(); parsers.add(new BracketParser());
}
Листинг 1.2. Листинг метода TokensParser.
Далее рассмотрим следующий метод также являющийся методом-геттером (англ. get – получать). Мы создали данный метод для того, чтобы поле списка анализаторов было защищено и в памяти не хранилась информация о данном поле. Этот один из методов объектноориентированного программирования, может помочь реализовать механизм инкапсуляции. Структура данного метода позволяет получить все анализаторы в виде объекта типа List.
Листинг метода getParsers:
public List<TokenParser> getParsers()
{
return parsers;
}
Листинг 1.3. Листинг метода getParsers.
Прежде чем описывать главный метод данного класса, который реализует его сущность, следует рассмотреть всю структуру программы. Допустим, мы хотим создать анализатор, который будет анализировать не алгебраическое выражение, а организм человека. В основе каждого анализатора лежит разложение какой-либо структуры на составляющие части. Каждая часть при этом, обладает своим собственным набором характеристик. Поэтому для каждой части нужно создать свой особый анализатор, который также является уникальным. Но если части не имеют общих характеристик, которые определяют их однозначно, то анализаторы имеют данную характеристику. Эта характеристика называется парсингом или анализом. Эту характеристику мы включили в так называемый интерфейс класса. Она определяет все общие методы, которые мы должны задействовать в наше программе.
Полный листинг интерфейса представлен выше (листинг 1.1). Он содержит общий метод для всех анализаторов parseToken. Метод анализа текущего символа на наличие лексемы.
И наконец, главный метод данного класса. Метод – parse. Его листинг представлен ниже. Он реализует анализ поступившей строки, определяемой переменной source. Прежде всего нам необходимо определить переменную, которая будет хранить промежуточные результаты анализа выражений. Далее выполняем проверку на пустоту строки, потому что если она пуста то не имеет смысла проделывать дальнейшие операции. Сущность данного метода заключается в структуре представленной ниже. Первым описан бесконечный цикл с предусловием. Бесконечность в данном случае реализуется за счёт применения ключевого слова true в качестве предусловия. Вторым описан цикл с итерацией записанной в специфической форме. Язык Java позволяет данную запись, когда она применяется в рассмотрении списка. Данный цикл можно описать так:
«Перебираем все анализаторы в списке parsers, поочерёдно задавая их переменной parser». Тело цикла начинается с проверки на отсутсвие анализатора. В случае, если анализатор был удалён, то просто переходим к следующему анализатору в списке. Далее в теле цикла описан метод parseToken, который анализирует строку с символа определяющейся по значению поля pos. Данный метод возвращает логическое выражение того, опознан ли символ данным анализатором. Если символ распознан, то позиция автоматически инкрементируется. В случае если не одним анализатором выражение не было распознано, то значение промежуточных результатов анализа даёт команду на выход из бесконечного цикла.
public void parse(String source)
{
boolean statusParsing = false;
if (source == null)
{
throw new IllegalArgumentException("Поступившее выражение является пустой строкой");
}
while (true)
{
for( TokenParser parser : getParsers() )
{
if( parser==null ) continue;
statusParsing = parser.parseToken(source, pos); if( statusParsing )
{
pos++; break;
}
}
if( !statusParsing ) break;
}
}
Листинг 1.4. Листинг метода parse.
1.2. Стековая организация данных
Для создания анализатора синтаксических выражений необходимо создать рассмотреть структуру на основе, которой данный анализатор будет основан. В ходе экспериментов в области программирования было вявлено, о наиболее удобная структура для анализа скобочных выражений это стек.
Стек (англ. 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.