Программная реализация абстрактного автомата для транслятора языка высокого уровня

Размещено на http://www.allbest.ru/



Содержание

Аннотация

Введение

1. Общая часть

1.1 Теория формальных языков

1.2 Абстрактный автомат и транслятор

1.3 Объектно-атрибутная архитектура для реализации абстрактного автомата и транслятора языка

2. Специальная часть

2.1 Постановка цели и задач работы и выбор метода ее решения

2.2 Разработка архитектуры автомата

2.3 Разработка виртуальных устройств и их программная реализация

2.4 Тестирование (разработка тестов, результаты тестирования)

Выводы

Список литературы

Приложения



Аннотация

Фокусом работы является программная реализация абстрактного автомата с магазинной памятью. Автомат создается для применения в качестве ядра компилятора языка высокого уровня. Работа включает в себя две части. Первая посвящена теоретическим вопросам, необходимым для достижения цели работы: теория формальных языков, теория распознающих автоматов, объектно-атрибутная архитектура (на ее базе реализуется автомат). Вторая часть содержит описание программной реализации автомата. Отличительной особенностью разрабатываемого автомата является то, что он реализуется на базе dataflow парадигмы вычислений. Поэтому автомат представляет собой множество относительно автономных виртуальных устройств, обменивающихся данными между собой. Поэтому приводится описание архитектуры автомата, алгоритмов работы отдельных виртуальных устройств и принцип их взаимодействия. Для проверки работоспособности программы был разработан экспериментальный синтаксический анализатор. Результаты его работы также проиллюстрированы.

The focus of the work is the software realization of an abstract machine with stack memory. The automata is created for use in high-level language compiler core. The work includes two parts. The first one is devoted to the theoretical issues necessary to achieve the goal of the work: the theory of formal languages, the theory of recognizing automata, object-attribute architecture (it is the basis the automata implementation). The second part contains a description of the software implementation of the automata. A distinctive feature of the developed automata is that it is based of dataflow computing paradigm. Therefore, the machine is a set of relatively autonomous virtual devices that communicate with each other. Therefore, a description of the architecture of the machine, the algorithms of individual virtual devices and the principle of their interaction. The experimental syntax analyzer is developed to check the program operability. The results of his work of the experimental syntax analyzer are also illustrated.



Введение

В основном в настоящее время синтаксический анализ языков высокого уровня реализуется на базе абстрактного автомата (автомат для распознания языка) [1], программно реализованного в классической парадигме вычислений (control-flow), в частности, применяется автоматное программирование [2]. Однако существует парадигма dataflow, практически не применяющаяся для этой цели, обладающая определенными преимуществами перед парадигмой классической: удобная реализация параллельных вычислений, гибкость вычислительного процесса, удобная реализация кроссплатформенных приложений, создание и модификация сложных структур данных во время вычислительного процесса. Настоящая работа направлена на то, чтобы реализовать абстрактный автомат с магазинной памятью (МП-автомат) на базе dataflow. МП-автомат был выбран для реализации, т.к. он достаточен для распознания контекстно-свободных языков, к которым относятся практически все языки программирования высокого уровня.

Тема абстрактных автоматов для реализации трансляторов языка достаточно широко освещается в различных литературных источниках [3, 4]. Однако по теме программной реализации абстрактного автомата количество литературных источников значительно меньше. В частности, здесь можно выделить такого автора как Шалыто, автора switch-технологии [2]. Также можно выделить несколько статей, с описанием реализации автомата на базе объектно-атрибутной (ОА) архитектуры вычислительной системы, относящейся к классу dataflow [5, 6, 7]. Автомат на базе ОА-архитектуры представляет собой множество автономных виртуальных устройств, обменивающихся данными между собой. Виртуальные устройства могут быть реализованы как аппаратно, так и программно. Такая система позволяет наиболее гибко организовать вычислительный процесс, обеспечить кроссплатформенность программы, объединить в рамках одного автомата синтаксический и семантический анализ языка. Данный подход к программной реализации автомата и был применен в настоящей ВКР.

Объектом проектирования является программная реализация конечного абстрактного МП-автомата, являющегося ядром транслятора языка высокого уровня. Функциональность ядра транслятора включает в себя реализацию: абстрактного автомата с магазинной памятью, лексического и синтаксического анализов, таблицы переменных транслятора.

Цель работы - программная реализация конечного абстрактного автомата с магазинной памятью на базе парадигмы dataflow.

Задачами работы являются:

1. Разработка архитектуры программы

2. Разработка системы команд и алгоритмов работы виртуальных устройств, входящих в программный модуль

3. Программная реализация абстрактного автомата с магазинной памятью

4. Разработка и запуск тестовых примеров для программной реализации автомата.

Абстрактный автомат реализуется на базе ОА-архитектуры вычислительной системы. При создании программы широко используются подходы: объектно-ориентированный, паттерный (библиотека STL).

Виртуальная машина (язык реализации виртуальных устройств и язык управления их работой).



1. Общая часть

Данный раздел состоит из двух частей. Первая - теория формальных языков, которая служит для описания правил порождения языка; вторая - теория конечных автоматов, применяемая для распознания цепочек символов, принадлежащих к определенному языку. Конечный автомат в большинстве случаев является ядром транслятора языка высокого уровня. Теория формальных языков (в частности форма Бекуса-Наура) применяется для описания синтаксиса языка. Создание транслятора обычно начинается с описания языка с помощью формальной грамматики, а затем по данной грамматике создается алгоритм на основе конечного автомата.

1.1 Теория формальных языков

Язык (как естественный язык, так и язык программирования) поддаются формализации. Н. Хомским в середине 1950-х годов был предложен аппарат формальных грамматик. Формальная грамматика - это четверка (1):

G={T, N, P, S}

Где

T - множество терминалов,

N - множество нетерминалов,

P - множество правил вывода (продукций),

S - начальный символ (S?N).

Терминальные символы представляют собой те символы, которые выводятся на «терминал», т.е. те символы, которые видит пользователь. Нетерминалы - это «виртуальные» символы, использующиеся для синтеза языка. Синтез цепочки символов начинается с начального символа S, относящегося к множеству нетерминальных, с помощью правил синтеза P. Продукция описывает преобразование фрагмента цепочки символов. Оно состоит из левой и правой частей. В левой части помещается подстрока, которую следует заменить на подстроку, расположенную в правой части продукции. В левой части обязательно должен присутствовать хотя бы один нетерминальный символ. Продукция может быть применена только в том случае, если в синтезируемой цепочке символов присутствует подстрока из левой части продукции. Синтез цепочки символов осуществляется путем случайного применения продукций и прекращается в тот момент, когда в цепочке не остается ни одного нетерминального символа.

Хомский ввел деление грамматик на 4 типа в зависимости от сложности языка:

Тип 0: неограниченная (нет никаких ограничений на правила продукций).

Тип 1: контекстно-зависимая. В таких грамматиках продукций имеет следующий вид (левая и правая части разделяются с помощью знака «->»):

1 0 2 -> 132

где

1, 2, 3 - подстроки, состоящие из терминалов и/или нетерминалов,

0 - подстрока, включающая хотя бы один нетерминальный символов.

Тип 2: контекстно-свободная, где продукция представлена в следующем виде:

N->.

Где N - нетерминальный символ.

- цепочка из терминальных и нетерминальных символов.

Тип 3: автоматная, где продукция имеет вид:

N->aB, N->Ba, N->a. 

Где

N, B - нетерминальные символы

a - терминальный символ.

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

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

N={S}

T= {0..9, +,-,(,)}

P:

1. S -> (S)

2. S -> S + S

3. S -> S - S

4. S->D

D->0D | 1D | 2D | 3D | 4D | 5D | 6D | 7D | 8D | 9D

D->0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Приведем последовательность синтеза строки “2+(3+5)”:

S -> S + S -> S + (S) -> S + (S+S) -> D + (S + S) -> D + (D + S)

-> D + (D + D) -> 2 + (D + D) -> 2 + (3 + D) -> 2 + (3 + 5)

Также нам представляют интерес автоматные грамматики, использующиеся для распознания лексем языка (лексического анализа языка). Для описания автоматного языка кроме грамматики можно применять и аппарат регулярных выражений [8, 9].

Регулярные выражения - формальный язык поиска и осуществления манипуляций с подстроками в тексте, основанный на использовании метасимволов. Во время поиска используется образец («шаблон», «маска»). Такой шаблон состоит из символов и метасимволов, а также создает правило поиска. Практически все символы в регулярном выражении представляют сами себя. Исключением являются специальные символы:

[,],\,/,^,$,.,|,?,,*,+,(,),{,}

Спецсимвол точки (.) означает один любой символ.

Если набор символов находится в `[', `]', то такой набор называется символьным классом и обозначает, что в строке может быть один из данных символов. Например, выражение [qwe] означает возможность появления одного из трех представленных символов. Предусмотрено указание диапазонов символов, например [A-Za-z] соответствует всем буквам английского языка.

Чтобы обозначить символы, не входящие в набор, применяется символ `^' внутри квадратных скобок. Пример: [^0-9] задает последовательность из всех символов кроме цифр.

Для квантификации применяются символы: `?', `*', `+', то есть, если расположить их после символа, группы или символьного класса, они определяют сколько раз это выражение будет встречаться.

- `?' - обозначает, что выражение повторяется ноль или один раз;

- `*' - соответствует нолю или более повторениям;

- `+' - определяет как минимум одно повторение.

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

Для более компактного описания контекстно-свободного языка применяется форма Бэкуса-Наура (БНФ), расширенная форма Бэкуса-Наура (РБНФ).

Бэкуса-Наура форма (БНФ) представляет собой естественный способ описания синтаксиса языка. Каждое понятие, которое определяется в БНФ, называется металингвистической переменной (или в терминах формальных грамматик, нетерминальный символ). Данная переменная может принимать значение любой конструкции из некоторого, определенного для этого понятия, набора конструкций. Каждая металингвистическая форма определяет одну металингвистическую переменную, состоящая из двух частей: правую и левую. В левую часть, при помощи угловых скобок `<' и `>', записываются определяемые переменные. Данные скобки не входят в алфавит определяемого языка и являются служебными. Например: <цифра>, <метка>, <переменная>, <константа>. Правая часть выражения описывает конструкцию языка, которая должна быть заменена на конструкцию, описанную в левой части выражения (аналогично правилу в формальной грамматике). Правая и левая части разделаются с помощью символа “::=”. Правая и левая части представляют собой цепочки терминальных и металингвистических переменных (нетерминальных символов). В отличие от формальных грамматик, в конструкцию правой части выражения добавляются некоторые служебные символы, существенно упрощающие описание синтаксиса языка. Так, «|» - обозначает альтернативу, т.е. в конструкции может присутствовать одна из цепочек символов, описанных слева или справа от знака. Например, <цифра>|<символ> обозначает, что в синтаксической конструкции может присутствовать либо символ, либо цифра.

Приведем примеров описания синтаксиса целых чисел с помощью БНФ:

<Цифра> ='0'|'1'|…|'9'

<ЧислоЦел> = <Цифра>

<ЧислоЦел> = <ЧислоЦел> <Цифра>

<Число> = <ЧислоЦел>

<Число> = <ЧислоЦел> `.' <ЧислоЦел>

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

Существует и формализм для еще более компактной записи грамматики - расширенная Бэкуса-Наура форма (РБНФ). Ее синтаксис отличается следующим образом.

- вводится элемент «[», «]». Данные скобки показывают, что конструкции, которые помещены в них, могут отсутствовать.

- добавлен элемент «{», «}». Они используются для обозначения повторения (возможно, 0 раз).

- введены круглые скобки «(» и «)» использующиеся для ограничения альтернативных конструкций.

- для обозначения повторения как минимум 1 раз используются фигурные скобки с косой чертой «{/» и «/}»

Для примера приведем описание синтаксиса чисел в БРНФ:

Цифра ='0'|'1'|…|'9'

ЧислоЦел = Цифра | (ЧислоЦел Цифра)

Число> = ЧислоЦел | (ЧислоЦел `.' ЧислоЦел)

1.2 Абстрактный автомат и транслятор

Существует и обратная задача - проверить имеющуюся цепочку символов на то, что она соответствует правилам синтаксиса языка. Для решения данной задачи имеется формализм под названием теория конечных распознающих автоматов.

Для распознания контекстно-свободных языков, к которым относится большинство языков программирования, применяется автомат с магазинной памятью (МП-автомат). В общем случае автомат с магазины памятью - это односторонний недетерминированный распознаватель, имеющий бесконечную вспомогательную ленту, работающую по принципу магазина. В любой момент времени доступ имеется только к верхнему элементу магазина. Как правило, в магазин помещаются символы, обозначающие начало скобочных конструкций языка, а извлекаются после того, как под считывающей головкой автомата оказывается лексема, обозначающая закрытие скобочной конструкции. Цепочка символов считается соответствующей синтаксису языка, если по завершению цепочки символов автомат находится в одном из конечных состояний и в магазине не осталось символов, обозначающих начало скобочной конструкции.

Рисунок 1 - Модель автомата с магазинной памятью

Автоматом с магазинной памятью называется семерка:

P=(Q, ?, ?, д, q0, Z0, F), где:

Q - конечное множество состояний автомата;

? - конечный алфавит входных символов;

? - алфавит символов стека;

д - функция переходов, задающая отображение множества QЧ?Ч?Ч?ЧQ;

q0Q - начальное состояние устройства;

Z0 - символ дна магазина (стека)

FQ - множество заключительных состояний

Для описания работы МП-автомата можно воспользоваться графическим методом, называемым графом состояний автомата. Узлы графа соответствуют состояниям автомата, а дуги - переходам из одного состояний в другое. К каждой дуге приписываются три символа, разделенных знаком «/». Первый - текущий символ на ленте; второй - символ на верхушке стека; третий - символ, помещаемый в стек. Приведем пример диаграммы состояний автомата, распознающего арифметические выражения (в выражении число может равняться только «1», а арифметической операций может быть только «+». См. рисунок 2, где «*» - символ, по которому автомат пропускает символ в верхушке стека, а «» обозначает удаление символа из верхушки стека.

Рисунок 2 - Иллюстрация диаграмма состояний МП-автомата

Ниже приведены примеры выражений, которые правильно распознаются данным МП-автоматом

y= (1+1)+1+((1+1)+1)

y= 1+(1)

Также приведен пример неверных выражений:

y=1(1) - в данном случае на диаграмме состояний автомата не описан переход в другое состояние, а в этом случае автомат попадает в состояние ошибки;

y=1+(1)) - встречается закрывающаяся скобка, но в стеке нет открывающейся, поэтому автомат переходит в состояние ошибки;

y=1(1 - в данном случае на диаграмме состояний автомата не описан переход в другое состояние, а в этом случае автомат попадает в состояние ошибки;

y=1+ - здесь автомат после окончания символов на ленте оказывается на в конечном состоянии.

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

Для лексического анализа языка (т.е. анализа языка автоматного типа) применяется автомат без магазинной памяти. Формально такой автомат можно представить как:

P=(Q, ?, д, q0, F), где:

Q - конечное множество состояний автомата;

? - конечный алфавит входных символов;

д - функция переходов из одного состояния автомата в другое, отображающая элементы QЧ?ЧQ;

q0Q - начальное состояние автомата;

FQ - множество заключительных состояний автомата

Транслятор - это программа, которая переводит текста на одном языка в текст на другом языке. Если конечный язык представляет собой машинный язык, то транслятор называется компилятором. Задачей компилятора является создание программы, которая написана на некотором языке программирования, понятной компьютеру. Как правило, языком исходной программы для компилятора является язык высокого уровня.

Трансляторы в машинный код делятся на два класса:

- Компилятор;

- Интерпретатор.

Основной задачей компилятора является перевод исходной программы в программу на машинном языке, который делает её понятной компьютеру. Целевой программой называется программа, полученная по результату выполнения работы компилятора. Программа запускается, только после того, как будет полностью сформирован машинный код.

Процесс компиляции проходит два этапа:

- Анализ;

- Синтез.

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

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

Любой компилятор состоит из нескольких частей, которые должны быть связаны в определённом порядке.

Составными частями компилятора являются анализаторы:

- лексический,

- синтаксический,

- семантический (смысловой анализ),

а также как минимум один генератор кода и оптимизатор (для оптимизации кода программы).

К составным частям компилятора также относят дополнительные инструменты - сборщик и компоновщик.

Лексический анализ является первым этапом работы компилятора.

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

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

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

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

Дальше существует несколько путей построения различных компиляторов. Зачастую после этапа семантического анализа программа переводится в промежуточный код. Этот код может быть использован для создания кода под различные аппаратные платформы, а также байт-кодов для виртуальных машин.

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

Схематично работа компилятора и её этапы представлены на рисунке 3 , где чёрным цветом обозначены обязательные для любого компилятора компоненты, а серым - факультативные части.

Рисунок 4 - Основные блоки компилятора

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

Дополнительные компоненты могут быть как встроенными в компилятор, так и иметь вид отдельно запускаемых после завершения работы самого компилятора программ.

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

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

Существуют языки, предназначенные только для однопроходной компиляции, например “С”. Объявление функций в нем происходит еще до первого их использования, именно поэтому компилятор не тратит время на объявление элементов с подписью функции. Однако более современные языки (например, С#) позволяют вызвать функцию до её определения. Это не позволяет компилироваться программе за один проход, иначе проверка типов не даст успешный результат, так как не знает о представлении функции в момент встречи с ней.

Реальные компиляторы обычно делают 2-5 проходов. Чаще всего встречаются трехпроходные компиляторы. Во время первого прохода выполняется лексический анализ, а синтаксический и семантический анализы проводятся на следующем этапе; на конечном, третьем, проходе оптимизируется и генерируется код программы.

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

Flex является генератором лексических анализаторов. Он представляет из себя улучшенную версию программы Lex. На вход программы поступают текст из любого источника и правила, по которым будут выделяться лексемы. По окончанию работы Flex выдает функцию на языке Си (код анализатора). Данную функцию надо использовать для генератора синтаксических анализаторов. Регулярные выражения служат для задания правил анализа. Чаще всего flex применяют с Bison.

Bison является генератором синтаксических анализаторов [10]. Он получает грамматики и на их основе присваивает соответствующие значения каждым элементам входящего потока.

1.3 Объектно-атрибутная архитектура для реализации абстрактного автомата и транслятора языка

Целью ВКР является программная реализация абстрактного автомата, работающего по принципу dataflow. Данная парадигма основывается на управлении вычислениями с помощью потока данных [11, 12].

Базой для реализации автомата стала объектно-атрибутная (ОА) [13] архитектура вычислительной системы, относящаяся к классу dataflow. Основное ее преимущество - предельная простота, обеспечивающая минимальный расход вычислительных ресурсов.

Основное понятие архитектуры - информационная пара (ИП). Она представляет собой двойку:

c=<a,l>, где a - атрибут, l - нагрузка (данные или ссылка). Атрибут служит для идентификации нагрузки. Обработкой потока информации занимаются функциональные устройства (ФУ). Они представляют собой совокупность контекста ФУ (внутренних устройств) и алгоритма работы, обеспечивающего выполнение некоторого набора милликоманд. Милликоманда (МК) является ИП, в которой содержится информация для ФУ о том, как необходимо обработать данные, переданные ей. Набор ИП называется капсулой. Она может применяться для описания объектов любого типа. Для описания программы для ФУ и информационных конструкций применяется специализированный ОА-язык. Например, описания переменной на ОА-языке выглядит следующим образом:

Переменная{Тип=Double Значение=57 Использование=public}, где

- {} соответствуют началу и концу капсулы;

- `=' означает соответствие атрибута и нагрузки.

`Переменная' - имя информационной капсулы.

Последовательность МК, предназначенных для выдачи на ФУ, находящихся в капсуле, называется миллипрограммой.

Описание МК состоит из двух полей, разделенных символом `.' (слева находится имя ФУ, справа - атрибут данных, по которому ФУ их интерпретирует. Например Lex.Stop значит, что МК поступает на ФУ, имеющее имя «Lex» (ФУ лексического разбора), и атрибут данных, обозначающий, что требуется остановить лексический разбор. В данном случае у МК пустая (нулевая) нагрузка, поэтому после нее не ставится знак `=' и нагрузка. Приведем пример МК с нагрузкой: Lex.Lexing=”int i=0; i++”, где присутствует нагрузка в виде строковой константы (это - МК лексического разбора одной строки кода программы).

ОА вычислительная система имеет следующую структуру: множество различных ФУ обмениваются между собой МК через устройство «Шина», выполняющее роль коммутатора. ФУ могут быть реализованы как аппаратно, так и программно. При программной реализации роль Шины выполняет специализированное ФУ. Архитектура ОА вычислительной системы представлена на рисунке 5.

Рисунок 5 - архитектура ОА вычислительной системы

Наиболее схожей с программной реализацией ОА архитектуры является акторное программирование [14, 15], где обработкой информации занимаются акторы. Актор представляет собой обычную процедуру, для которой, однако, все операнда поступают через ее интерфейс не одновременно, а последовательно в виде токенов. Слоты (поля) интерфейса бывают входными и выходными (выходные поля аналогичны передаче параметров по ссылке в классическом программировании). Каждый токен соответствует определенному слоту в интерфейсе актора: входной слот ожидает прихода токена, с выходного слота происходит выдача токенов с результатами работы актора. Актор начинает вычисления только после того, как во все входные слоты поступят входные операнды. Программу в акторной парадигме можно представить в виде потокового графа, где узлами являются акторы, а каждая дуга соответстсвует входному и выходному слоту. Топология потокового графа может задаваться программистом с помощью специального графического редактора или с помощью языка разметки, аналогичного XML.

ФУ, по сути, представляет собой актор с универсальным интерфейсом. ФУ имеет только два поля: атрибут и данные - это два поля, входящие в состав МК. Таким образом, программно реализованный ФУ может за один раз принимать только один токен (МК). Применение универсального интерфейса для актора, реализующего ФУ, значительно повышает гибкость программирования, т.к. жесткий интерфейс актора вызывает значительные затруднения при модификации программы, в результате которой приходится изменять интерфейсы акторов (изменение интерфейса приводит к необходимости изменения и потокового графа, что весьма трудозатратно).

Теоретические основы для реализации автомата на базе ОА-архитектуры (ОА-архитектура) изложены в источниках [5, 6, 7, 16]. По данному принципу уже реализован детерминированный конечный автомат для компилятора ОА-языка, входящего в систему ОА программирования и имитационного моделирования. Ее основой стали ФУ трех типов FULex (лексический анализатор) и FUList (список, используемый для реализации состояний ОА-автомата), FUFind (ФУ поиска в одном ИК, также применяемая для реализации состояния ОА-автомата). ФУ реализации состояния ОА-автомата, назовем исполнительным устройством. Первый тип осуществляет лексический разбор текста и пересылку выделенных лексем, оформленных в виде МК на исполнительные ФУ типов FUList и FUFind. Каждое исполнительное ФУ ассоциируется с состоянием автомата. FULex в своем контексте хранит указатель на исполнительное ФУ, которое ассоциируется с текущим активным состоянием. Выделенная лексема поступает на FUList или FUFind, которое ее распознает и соответствующим образом обрабатывает: запускает процедуры обработки данных и выдает МК записи в FULex адреса исполнительного ФУ, которое на следующем такте будет являться активным.

Следует рассказать об реализации автомата с магазинной памятью. В магазин ОА-автомата в отличие классического автомата помещаются не символы, а ИК, что дает возможность более глубокой абстракции. Стек этот строится на базе ОА-списка, контролируемого FUList. Управление этим ФУ описано в программах, запускаемых исполнительными устройствами. Новая ИК помещается в вершину ОА-списка, и изымается также из вершины стека.



2. Специальная часть

Специальная часть работы посвящена проектированию и программной реализации МП-автомата, работающего в парадигме dataflow. Процесс проектирования охватывает этапы:

- проектирование архитектуры автомата;

- проектирование виртуальных устройств, реализующих функционал МП-автомата;

- программная реализация виртуальных устройств;

- реализация экспериментального синтаксического анализатора на базе реализованного МП-автомата.

Следует заметить, что кроме МП-автомата была дополнительно реализована таблица идентификаторов переменных, которая является неотъемлемой частью компилятора или интерпретатора.

2.1 Постановка цели и задач работы и выбор метода ее решения

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

В качестве базиса была выбрана объектно-атрибутная архитектура вычислительной системы, относящаяся к классу dataflow. ОА-вычислительная система представляет собой совокупность автономных исполнительных устройств, обменивающихся между собой сообщениями, оформленными в виде токенов (в ОА-архитектуре они именуются информационными парами или милликомандами (МК)). Поэтому автомат должен состоять из множества функциональных устройств (ФУ), обменивающихся между собой данными, оформленными в виде МК. Поэтому задачами работы являются:

- разработка архитектуры и общего принципа работы абстрактного МП-автомата на базе ОА-архитектуры;

- выделение основных типов ФУ, входящих в состав автомата;

- проектирование отдельных типов ФУ (разработка состава и основных типов команд);

- программная реализация основных типов ФУ, входящих в состав ОА-автомата;

- создание тестового компилятора для проверки корректности работы ОА-автомата (компилятор должен проверить функционирование магазина автомата и таблицы идентификаторов переменных);

- тестирование ОА-автомата.

Для быстрой и эффективной программной реализации были применены следующие средства и методики:

- теория формальных языков, используется для описания синтаксиса языка программирования;

- теория конечных распознающих автоматов, применяется при распознании синтаксиса языка программирования;

- объектно-ориентированное программирование существенно облегчает процесс программирования, делает структуру программы более понятной для программиста;

- паттерное программирование (библиотека STL [17]) освобождает программиста от рутинной работы по программированию часто встречаемых, однотипных задач;

- ОА-архитектура позволяет достаточно эффективно реализовывать dataflow-парадигму вычислительного процесса благодаря своей простоте;

- виртуальная машина (ВМ), позволяет создать машину, работающую в другой парадигме вычислений, нежели ЭВМ, на котором она запускается. Также ВМ обеспечивает кроссплатформенность программы, написанной для ВМ.

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

- Быстродействие (насколько быстро выполняется программа, созданная на данном языке);

- Применение в HPC - практика применения языка для создания программ для высокопроизводительных вычислительных систем.

- Наличие специализированных библиотек. Разрабатываемая программа будет поддерживаться и развиваться впоследствии, и далее может потребоваться решение специализированных задач.

- Паттерны для работы с векторами и множествами. Данные паттерны существенно облегчают создание программы абстрактного автомата, т.к. в программе достаточно часто встречается обработка множеств и векторов.

Сравнение различных языков программирования по вышеприведенным критериям приведена в таблице 1.

Таблица 1 - Сравнение языков программирования

	С++	Delphi	Objective-C	Python	Basic
Быстродействие	+	-	+	-	-
Наличие специализированных библиотек	+	-	-	+	-
Паттерны для работы с векторами и множествами	+	-	-	+	-
Распространенность	7,562%	1,526%	1,477%	8,376%	1.108%
Применение в HPC	+	-	+	-	-

В результате проведенного анализа был сделан вывод в пользу языка С++ [18, 19].



2.2 Разработка архитектуры автомата

В ходе ВКР была разработана структура ОА-автомата, являющегося ядром транслятора ЯВУ, представленная на рисунке 6. В состав автомата входят несколько типов ФУ: генератор строк (StrGen), лексический анализатор (Lex), поисковик (Find), список (List), шина (Bus). Далее приведем описание функциональности этих типов ФУ.

Рисунок 6 - Структура ОА-компилятора

StrGen необходим для того, чтобы принимать анализируемый текст из различных источников (файл, текстовый редактор, консоль и т.д.). StrGen является поставщиком информации в ОА-автомат. StrGen считывает строку из источника и пересылает ее на лексический анализатор, который выделяет из текста лексемы. Далее лексемы передаются на ФУ Find и List, которые выполняют роль состояния ОА-автомата. Find выполняет роль состояния только с двумя выходными дугами, а List - c тремя и более (каждой дуге соответствует одна линия списка). List также применяется для реализации таблицы идентификаторов и стека автомата.

В функциональность ФУ-List входит поиск информации и запуск соответствующих подпрограмм по результатам поиска. Для того, чтобы отделить ИП для поиска и программу, применяется специальный атрибут ProgAtr. Его можно использовать двумя способами. Первый: размещение ссылки на программу в ИП с атрибутом ProgAtr. List при успешном поиска в определенной линии, находит ИК с программой по данной ссылке. Второй: размещение программы после ИК с атрибутом ProgAtr (в нагрузке ИП находится нулевой указатель). В этом случае при удовлетворении критерию поиска, запускается программа, находящаяся после ИП с атрибутом ProgAtr.

Рис. List

Отдельно необходимо сказать об обработке мнемоник, выделенных Lex. Если все прочие лексемы пересылаются на текущее ФУ-состояние, а мнемоники - на ФУ-List под названием MnemoTable. MnemoTable, получив мнемонику, пытается найти ее в списке (каждая линия списка соответствует описанию одной переменной или зарезервированного слова). Если мнемоника найдена, то последняя лексема, хранящаяся в буфере Lex, заменяется на найденное описание переменной или зарезервированного слова, а затем Lex выдает его на ФУ-приемник. Если мнемоника на найдена, то она без изменений передается на ФУ-приемник.

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

Обмен сообщениями между ФУ производится через ФУ Bus.

Синтаксическая и лексическая корректность анализируемого текста проверяется по нескольким признакам:

- если нет описания перехода из определенного состояния ОА-автомата в другое состояние, то выдается сообщение об ошибке (на случай, если не сработает ни одно программа перехода, выполняется программа обработки ошибки);

- если в конце разбора текста автомат находится не в конечном состоянии (StrGen в конце генерации строк текста запускает проверку нахождения автомата в множестве конечных состояний).

- если в конце разбора теста стек не пуст (StrGen в конце генерации строк текста запускает проверку пустоты стека.

2.3 Разработка виртуальных устройств и их программная реализация

Следующим этапом работы было создание программного кода для всех типов ФУ, входящих в состав ОА-автомата. Контекст каждого ФУ представляет собой класс, хранящий контекст ФУ, а также методы, реализующие логику его работы.

Информационная пара (ИП) представляет из себя класс, который хранит числовое значение атрибута и указатель на нагрузку с типом её данных. Сам указатель представляет из себя класс, где поле «type» по-умолчанию обозначает неизвестный тип. В этом классе также содержатся процедуры конвертации типа переменной в переменную определенного типа. ИП может сбросить свою нагрузку, дублировать её, установить тип константы или переменной.



Рисунок 7 - Описание ИП (Листинг)

Информационная капсула является вектором ИП.

Каждое ФУ имеет общую часть, которая содержит в себе ссылку на контекст шины (Bus), указывается диапазон МК для каждого ФУ (FUMkRange), и микропрограмма для выполнение общих МК для ФУ (CommonMk). Реализация логики работы ФУ представлена в поле ProgFU.

На вход для CommonMk поступают данные с кодом милликоманды и указатель на нагрузку с типом данных, если индекс МК не совпал ни с одной из МК для данного типа ФУ. Таким образом процедура CommonMk предназанчена для обработки МК, общих для всех ФУ. На данный момент процедура обрабатывает только две МК:

- ProgExec - выполнить миллипрограмму, адрес которой был передан в нагрузке МК.

- ContextOut - выдать ссылку на контекст ФУ.

- ContextOutMk - выдать ссылку на контекст ФУ.

Также в данном разделе приведено описание класса Search, который не является ФУ, но входит в состав ФУ List и Find.

Диспетчер виртуальных устройств (Bus). Данное ФУ используется для организации пересылки сообщений между ФУ, участвующих в процессе выполнения программы; создания и уничтожения ФУ и запуска корневой программы. Состав контекста ФУ приведен на рисунке 8 .



Рисунок 8 - Структура контекста диспетчера виртуальных устройств (Bus)

Контекст ФУ включает следующие виртуальные регистры:

- FUs - Вектор указателей на контексты ФУ.

- FUTempl - Указатель на контекст шаблона ФУ.

- FUMkRange - Диапазон МК для каждого ФУ.

- FUTypeCorrect - Коррекция номера типы ФУ (для согласования со старой ОА-средой)

Таблица 2 - Милликоманды ФУ Bus

Контекст (Mnemo)	Значение
MakeFU	Создать ФУ (в нагрузке передаётся тип ФУ)
ProgExec	Выполнить последовательность МК из ИК
FileOldProgExec	Выполнить последовательность МК из индексного файла старого формата
NFUOut	Выдать количество ФУ, подключенных к шине

Генератор строк (StrGen).

На вход ФУ поступает файл, который разбирается на строки. После обработки строки поочередно передаются на лексический анализатор или на любое другое ФУ.

Контекст ФУ состоит из следующих виртуальных регистров:

- ReceiverMK - поле типа int, хранящее индекс МК для ФУ-получателя лексем.

- work - поле типа bool, обозначающее состояние работы ФУ.

- Source - поле типа ifstream, входной файловый поток.

- Filename - поле типа string, хранит имя файла источника текста.

- TimeStart, TimeLong - Время начала компиляции, время конца компиляции.

- LineCount - счетчик считанных строк.

- str_buf - Буфер строк.

- str_buf_size - Размер буфера строк.

- str_bufCount - Индекс текущей строки в буфере.

Приведем МК, выполняемые ФУ StrGen.

Таблица 3 - Милликоманды ФУ StrGen

Контекст (Mnemo)	Значение
ReceiverSet	Установить ссылку на приемник строк
ReceiverMkSet	Установить МК для приемника строк
Start	Начать генерацию
Stop	Прервать процесс генерации строк
Pause	Приостановить процесс генерации строк
Continue	Продолжить процесс генерации строк
ModeSet	Выбор режима работы (0 - обычный, 1 - преобразование букв к нижнему регистру)
TimeOut	Выдать время компиляции в секундах
TimeMkOut	Выдать МК со временем компиляции в секундах
LineBufSizeSet	Установить размер буфера строк
LineCountOutMk	Выдать МК с количеством обработанных срок
LastLineBufOutMk	Выдать МК с последней строкой из буфера
LineBufOutMk	Выдать МК со строками из буфера

Лексический анализатор и ядро автомата (Lex).

На вход ФУ поступает МК с текстовой строкой. Далее ФУ производит выделение из текста лексем и выдачу их ФУ-получателю лексем. Также ФУ производит определение лексических ошибок и запуск подпрограммы их обработки.

Контекст ФУ состоит из следующих виртуальных регистров:

- ReceiverMK - поле типа int, хранящее индекс МК для ФУ-получателя лексем.

- MnemoAtr, SeperatAtr, IntAtr, DoubleAtr, BoolAtr, StrAtr - поля типа int, хранящие индексы атрибутов различных типов лексем: мнемоника, разделитель, целое значение, дробное значение, логическое (булево) значение, строковое значение.

- SizeBuf - размер буфера лексем

- LexBuf - буфер лексем (массив ИП)

- ErrProg - Ссылка на программу, запускаемую при лексической ошибке

- UnicAtr - Список специфических атрибутов, по которым идет обработки другими ФУ, для которых необходимо выполнить другую МК.

Таблица 4 - Милликоманды ФУ Lex

Контекст (Mnemo)	Значение
ReceiverMkSet	Установить МК для приемника лексем
ErrProgSet	Установить на программу-обработчик ошибки
UnicAtrSet	Установить уникальный атрибут
UnicMkSet	Установить МК для уникального атрибута
LexemaReplaceToReceiver	Выдать лексему из нагрузки МК получателю, заменив текущую лексему в буфере
LexemaReplaceCopyTo Receiver	Выдать копию лексемы из нагрузки МК получателю, заменив текущую лексему в буфере
LexemaToReceiver	Выдать лексему из нагрузки МК получателю
LexemaCopyToReceiver	Выдать копию лексемы из нагрузки МК получателю
LastLexemaToReceiver	Выдать последнюю лексему получателю
LastLexemaCopyToReceiver	Выдать копию последней лексемы получателю
LastLexemaOutMk	Выдать MK c последней лексемой
LastLexemaCopyOutMk	Выдать МК с копией последней лексемы
LastLexemaAtrSet	Установить атрибут последней лексемы
LastLexemaLoadSet	Установить нагрузку у последней лексемы
LastLexemaLoadCopySet	Установить копию нагрузки у последней лексемы
LastLexemaVarSet	Установить тип переменной для нагрузки последней лексемы
Stop	Остановить лексический анализ
Lexing	Лексический разбор строки



Лексический анализ в ФУ Lex реализован на базе автомата без магазинной памяти. Диаграмма состояний этого автомата приведена на рисунке 9. ФУ Lex в состоянии выделать следующие лексемы: мнемоника, разделители (скобки, точка, запятая и т.д.) целочисленная, дробная, логическая или строковая константа.

Рисунок 9 - Диаграмма состояний автомата для лексического анализа Searcher.

Данный класс не является самостоятельным ФУ, но он входит в состав других ФУ. Он используется для сравнения двух и более ИК и может выполнять 3 различных типа поиска: поиск «И», поиск «ИЛИ», поиск «Исключающее ИЛИ»

Таблица 5 Милликоманды ФУ Lex

Контекст (Mnemo)	Значение
Template	Шаблон для поиска
Obj	ИК для поиска
MkMode	Режим выполнения всех МК в ИК-шаблоне (МК-ой считается любой атрибут, индекс которого больше 0)
MkAtr	Список атрибтов, представляющих МК, выполняющиеся в случае успешного поиска
MainFU	Ссылка на главное ФУ, короторое пользуется функционалом searcher-а
Rez	Результат поиска
IPTemplPoint	Указатели на найденные ИП в шаблоне и в ИК
Prog_atr	Атрибут программы, выполняющейся при успешном поиске (<0 атрибут не учитывается)
FindOr	Поиск ИЛИ
FindAnd	Поиск И
FindXor	Поиск XOR

Ниже на рисунке 10 представлены блок-схемы алгоритмов методов поиска данных в ИК

а) б)

в)

Рисунок 10 - а) FindOr, б) FindAnd, в)_FindXor



Информационный поиск в информационной капсуле (Find).

На вход ФУ подается ИК, в которой надо найти ту (те) или иную (иные) ИП. Для выполнения данной задачи, используется подпрограмма Searcher.

Также ФУ сообщает об успешном или неудачном результате поиска.

Таблица 6 Милликоманды ФУ Find

Контекст (Mnemo)	Значение
Set	Установить указатель на шаблон для поиска
MkModeSet	Режим выполнения всех МК в ИК-шаблоне (МК-ой считается любой атрибут, индекс которого больше 0). При пустой нагрузке режим устанавливается
SuccessProgSet	Установить указатель на программу, выполняемую при удачном поиска в линии списка
SuccessAfterProgSet	Установить указатель на программу, выполняемую при удачном поиска в линии списка после обработки программ линии
FailProgSet	Установить указатель на программу, выполняемую в случае неудачного поиска в линии списка
FailAfterProgSet	Установить указатель на программу, выполняемую в случае неудачного поиска в линии списка после обработки программ линии
ProgAtrSet	Установить атрибут программы
BackOut	Выдать входной объект для поиска
BackOutMk	Выдать МК со входным объектом для поиска
CopyBackOutMk	Выдать МК с копией входного объекта для поиска
RezOut	Выдача результата сравнения
RezOutMk	Выдача МК с результатом сравнения
FindOr	Поиск ИЛИ
FindAnd	Поиск И
FindXor	Поиск XOR
FindAndSource	Поиск И в источнике

Информационный поиск в списке информационных капсул (List).

Это ФУ необходимо для того, чтобы определять и хранить новые лексемы, которые на него поступают. Для выполнения сравнения поступающих лексем с уже имеющимися используется класс Searcher.

Таблица милликоманд ФУ List представлена в Приложении А.

2.4 Тестирование (разработка тестов, результаты тестирования)

Для подтверждения работоспособности программной реализации ОА-автомата был создан экспериментальный синтаксический анализатор ОА-языка. Его синтаксис описываются с помощью следующих правил расширенной формы Бэкуса-Наура:

Symb='a'|'b'|…|'z'|'_'|'A'|'B'|…|'Z'

Digit='0'|'1'|…|'9'

Numb=[-]Digit[{Digit }] ['.' Digit[{Digit }]

Mnemo= Symb[{Symb | Digit }]

Atr= Mnemo

AtrIni= Mnemo `*' Numb

StrConst=' ” ' { Digit | Symb } ' ” '

BoolConst = `true'|'false'

Const= Numb | StrConst | BoolConst

VarIni= Mnemo `=' (Numb | BoolConst | CapsMnemo)

Var= Mnemo

FU=Mnemo

MK=Mnemo

CapsName=Mnemo

MK_EX=FU `.' MK

IP_MK =MK `#” (Const | Var | Caps)

IP = Atr `#” (Const | Var)

Caps='{' (IP_MK | IP) `#' (Const | Var | ([CapsName] Caps)) { (IP_MK | IP) `#' (Const | Var | ( [CapsName] Caps ))}`}'

CapsIni=Mnemo `=' Caps

Prog= {AtrIni | VarIni | CapsIni | IP_MK | Caps}

Далее был разработан абстрактный ПМ-автомат, имеющий 10 состояний, при этом каждое состояние именуется своим уникальным именем. Диаграмма состояний автомата представлена на рисунке 11. Для каждого состояния автомата создается свой ФУ-List, обрабатывающий события данного состояния автомата.

Рисунок 11 - Диаграмма состояний автомата

где

- FU - атрибут функционального устройства,

- МК - атрибут Милликоманды,

- Int - атрибут целого числа,

- Mnemo - атрибут мнемоники,

- Var - атрибут переменной,

- Const - атрибут константы,

- `^' - знак, означающий удаление символа из верхушки стека.

Для управления ФУ, входящих в состав ОА-автомата, применялся уже созданный ранее компилятор “Millicom” [20, 21], с помощью которого код экспериментальнгого синтаксического анализатора на ОА-языке (Приложение Б) был транслирован в некое подобие байт-кода java-машины (индексный файл) для реализованной в ходе настоящей работы ОА-вычислительной системы.

Далее был разработан набор тестов, предназначенный для проверки следующий функционал абстрактного МП-автомата:

- переход из одного состояния в другое;

- использование таблицы идентификаторов переменных;

- использование стека;

- выдача сообщение об лексических и синтаксических ошибках;

- фиксация ошибки расстановки программных скобок (нет закрывающейся скобки, закрывающаяся скобка без открывающейся)

- выдача сообщения о корректности программы.

Таблица тестирования синтаксического анализатора приведена в Приложении В.

Согласно всем выполненным тестам можно сделать вывод, что программа синтаксического анализатора работает корректно.

Листинг программной реализации ОА-автомата приведен в Приложении Г.



Выводы

В ходе выполнения ВКР был разработан программный модуль для реализации абстрактного конечного автомата для применения в качестве ядра компилятора языка высокого уровня. Данный автомат состоит из нескольких виртуальных устройств, которые работают по принципу управления потоком данных (dataflow). Разработанное ПО разработано в среде Visual Studio на языке С++ под ОС Windows и обладает функционалом:

...