Компилятор модельного языка программирования

Компилятор модельного языка программирования

Содержание

Введение

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

. Формальная модель задачи

. Спецификация основных процедур и функций

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

.2 Синтаксический анализатор

.3 Семантический анализатор

.3.1 Обработка описаний

.3.2 Анализ выражений и проверка правильности операторов

.4 Генерации внутреннего представления программы

.5 Интерпретатор программы

. Структурная организация данных

.1 Спецификация входной информации

.2 Спецификация выходной информации

. Укрупненная схема алгоритма программного средства

.1 Конечный автомат

. Руководство пользователя

Заключение

Список использованной литературы

Приложение

Введение

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

Эта теория возникла в 50-е годы в работах американского лингвиста

Н. Хомского. По характеру используемого математического аппарата теория формальных грамматик и языков близка к теории алгоритмов и к теории автоматов.

Но уже в следующем десятилетии синтаксические методы нашли широкое практическое применение в области разработки и реализации языков программирования.

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

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

Цель курсовой работы:

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

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

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

1.      Составить формальное описание модельного языка программирования с помощью:

-       РБНФ;

-       диаграмм Вирта;

-       формальных грамматик.

.        Написать пять примеров программ.

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

.        По диаграмме с действиями написать функцию сканирования текста входной программы на модельном языке.

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

.        Реализовать синтаксический анализатор текста программы на модельном языке.

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

.        Дополнить синтаксический анализатор процедурами проверки семантической правильности программы на модельном языке в соответствии с контекстными условиями своего варианта.

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

.        Записать правила вывода грамматики с действиями по переводу в ПОЛИЗ программы на модельном языке.

.        Пополнить разработанное программное средство процедурами, реализующими генерацию внутреннего представления введенной программы в форме ПОЛИЗа.

.        Разработать интерпретатор ПОЛИЗа программы на модельном языке.

.        Составить набор контрольных примеров, демонстрирующих:

а)      все возможные типы лексических, синтаксических и семантических ошибок в программах на модельном языке;

б)      перевод в ПОЛИЗ различных конструкций языка;

в)      представить ход интерпретации синтаксически и семантически правильной программы с помощью таблицы.

2. Формальная модель задачи

Определение понятия «идентификатор» с использованием РБНФ имеет вид

<идентификатор> ::= <буква> | <идентификатор> <цифра>

<буква>:: =A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W |X |Y | Z |a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

<цифра>:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<целое>::= <двоичное> | <восьмеричное> | <десятичное> |

<шестнадцатеричное>

<двоичное>::= {/ 0 | 1 /} (B | b)

<восьмеричное>::= {/ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 /} (O | o)

<десятичное>::= {/ <цифра> /} [D | d]

<шестнадцатеричное>::= <цифра> {<цифра> | A | B | C | D | E | F | a | b || d | e | f} (H | h)

В соответствии с данными правилами синтаксис модельного языка будет выглядеть следующим образом

<буква>:: =A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W |X |Y | Z |a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

<цифра>::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<идентификатор>::= <буква> { <буква> | <цифра> }

<число> ::= {/< цифра> /}

<ключевое_слово>::= plus | min | or | mult |div | and | end | dim | integer|| boolean |as | if | then | else | for | to |do | while| read |write | true | false | NE | EQ | LT | LE | GT | GE

<разделитель>::= ~ | : | , | [ | ] | \n | ( | ) | { | }

<программа>= {/(<описание> | <оператор>) (: | переход строки) /} end

<описание>::= dim <идентификатор> {, <идентификатор> } <тип>

<оператор>::= <присваивания> | <условный> | <условного_цикла> | <составной> | <фиксированного_цикла> |<ввода> |<вывода>

<присваивания>::= <идентификатор> as <выражение>

<условный>::= if <выражение> then <оператор> [ else <оператор>]

<условного_цикла>::= while <выражение> do <оператор>

<составной>::= «[» <оператор> { ( : | перевод строки) <оператор> } «]»

<фиксированного_цикла>::= for <присваивания> to <выражение> do <оператор>

<ввода>::= read «(»<идентификатор> {, <идентификатор> } «)»

<вывода>::= write «(»<выражение> {, <выражение> } «)»

<выражение>:: = <операнд> {<операции_группы_отношения> <операнд>}

<операнд>::= <слагаемое>{<операции_группы_умножения> <слагаемое>}

<слагаемое>::=<множитель>{<операции_группы_умножения> <множитель>}

<множитель>::=<идентификатор> |<число> |<логическая_константа> |<унарная_операция> <множитель> |<<(>> <выражение> <<)>>

Формальные грамматики

P ® telo® OperL | Opis | telo; OperL; | telo; Opis® Oper; | Oper; OperL® Type Id1® Id | Id1, Id® Byk | Byk Id | Cifra Id® A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T || V | W | X | Y | Z | a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p| r | s | t | u | v | w | x | y | z® 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9® integer | real | boolean® [Sost] | Prisv | IF | F_C | WH_C | Vvod | Vivod® Oper | Oper Znak Sost® : | \n® Id as Virag® if Virag then Oper | if Virag then Oper else Oper_C ® for Prisv to Virag do Oper_C ® while Virag do Oper® read(IdList)® write(ViragList)® Virag | Virag,ViragList® Op | Op NE Virag | Op EQ Virag | Op LT Virag | Op LE Virag | Op GT Virag | Op GE Virag® Sum | Sum plus Op | Sum min Op | Sum or Op® Mn | Mn mult Sum | Mn div Sum | Mn and Sum® Id | Ch | LC | UN Mn | (Virag)® ~® Ze | De® true | false® Bin | Oo | Dd | Hh® Bin1 Bin2® 0 | 1 | 0 Bin1 | 1 Bin2® B | b® Oo1| Oo2® O1 | O1 Oo1® 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7® O | o® Dd1 Dd2® Cifra | Cifra Dd1® D | d® H1 H2® Cifra | H1 H3® Cifra | A | B | C | D | E | F | a | b | c | d | e | f® H | h® Chst Por | . Chst | Chst . Chst | . Chst Por | Chst . Chst Por® Cifra | Cifra Chst® E1 Chst | E1 Pm Chst® E | e® + | -

Описание синтаксиса модельного языка с помощью диаграмм Вирта

3. Спецификация основных процедур и функций

программирование компилятор модельный язык

3.1 Лексический анализатор

Лексический анализатор (ЛА) - это первый этап процесса компиляции, на котором символы, составляющие исходную программу, группируются в отдельные минимальные единицы текста, несущие смысловую нагрузку - лексемы. Функции, реализующие лексический анализ приведены в Таблице 1.

Таблица 1 - Функции лексического анализа

.2 Синтаксический анализатор

Задача синтаксического анализатора: провести разбор текста программы, сопоставив его с эталоном, данным в описании языка. Для синтаксического разбора используются контекстно-свободные грамматики (КС-грамматика).

Один из эффективных методов синтаксического анализа - метод рекурсивного спуска.

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

Таблица 2 - Функции синтаксического анализа

.3 Семантический анализатор

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

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

Соблюдение контекстных условий для языка М предполагает три типа проверок:

) обработка описаний;

) анализ выражений;

) проверка правильности операторов.

Рассмотрим три типа проверок подробнее.

.3.1 Обработка описаний

Функции, реализующие обработку описаний, описаны в Таблице 3.

Таблица 3 - Обработка описаний

3.3.2 Анализ выражений и проверка правильности операторов

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

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

Задачи проверки правильности операторов:

) выяснить, все ли переменные, встречающиеся в операторах, описаны;

) установить соответствие типов в операторе присваивания слева и справа от символа присваивания;

) определить, является ли выражение в операторах условия и цикла булевым. Функции, реализующие анализ выражений и проверку правильности операторов, описаны в Таблице 4.

Таблица 4 - Анализ выражений и проверка правильности операторов

3.4 Генерации внутреннего представления программы

В качестве языка для представления промежуточной программы выберем постфиксную запись - ПОЛИЗ (польская инверсная запись).

Функции, реализующие генерацию, описаны в Таблице 5.

Таблица 5 - Генерации внутреннего представления программы

.5 Интерпретатор программы

Интерпретатор анализирует и тут же выполняет программу по одной команде, по мере поступления её исходного кода на вход интерпретатора.

Запись программы в форме ПОЛИЗа удобна для последующей интерпретации (выполнения программы) с помощью стека. Массив ПОЛИЗа просматривается один раз слева направо, при этом:

) если очередной элемент ПОЛИЗа является операндом, то его значение заносят в стек;

) если очередной элемент операция, то на «верхушке» стека находятся ее операнды, которые извлекаются из стека, над ними выполняется соответствующая операция, результат которой заносится в стек;

) интерпретация продолжается до тех пор, пока не будет считан из ПОЛИЗа признак окончания ПОЛИЗа, стек при этом должен быть пуст.

В данной реализации интерпретатор представлен в виде отдельного программного модуля. Для реализации интерпретатора были использованы функции, описанные в Таблице 6.

Таблица 6 - Интерпретатор программы

4. Структурная организация данных

.1 Спецификация входной информации

В программе используется три типа класса:LexicalAnalysis для лексического анализа;Parsing для синтаксического, семантического и генерация внутреннего представления программы;PolIW для интерпретации программы.

Таблица 7 - Входные данные

В программе используются следующие пользовательские типы данных:

Таблица 8 - Описание структуры для хранения информации о лексеме (struct LexStuct)

Таблица 9 - Описание структуры для хранения всей информации, необходимой для обработки описаний (struct DescriptionStruct)

4.2 Спецификация выходной информации

Таблица 10 - Спецификация выходной информации

5. Укрупненная схема алгоритма программного средства

Укрупненная схема алгоритма программного средства представлена на рисунке 1.

Рисунок 1 - Укрупненная схема алгоритма программного средства

5.1 Конечный автомат

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

Рисунок 2 - Диаграмма состояний для модельного языка

6. Руководство пользователя

Минимальные требования к аппаратному обеспечению:

.        128 Мб оперативной памяти;

.        32 Мб видеопамять;

.        20 Мб свободной памяти на жестком диске;

.        устройство ввода (клавиатура, мышь);

.        разрешение монитора: 800x600.

Минимальные требования к программному обеспечению:

.        операционная система Windows XP/Vista /Win7;

.        наличие установленного пакета .Net Framework 4 (4.5).

Установка программного средства:

.        скопировать исполнительный файл Com.exe;

.        скопировать библиотеку ComLibrary.dll.

Для начала работы с программным средством необходимо запустить исполняемый файл. Появляется главное окно программы (рисунок 3).

Рисунок 3 - Вид главного окна программы

В данном окне можно вводить, редактировать, текст программы на модельном языке, а так же выполнить лексический, синтаксический, семантический анализ, перевод текста программы в ПОЛИЗ и интерпретацию программы. А также считать программу из файла и сохранить в файл.

Рисунок 4 - Выполнение программы на модельном языке

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

Для операции ввода и вывода используется следующая форма на рисунке 5.

Рисунок 5 - Форма ввода и вывода

Заключение

Разработали на языке программирования C# в среде Microsoft Visual Studio 2010 на базе Microsoft NET Framework 4 (4.5) программное средство реализующее компилятор модельного языка программирования. Программное средство способно выполнять следующие функции:

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

подсветку синтаксиса введенных программ, опираясь на таблицу служебных слов;

производить лексический анализ программ;

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

переводить программы в ПОЛИЗ;

интерпретировать программы на модельном языке, записанных в форме ПОЛИЗа.

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

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

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

Приложения

Приложение А

«Таблицы служебных слов и ограничителей»

Таблица 11 - Таблица служебных слов

Таблица 12 - Таблица ограничителей

Приложение Б

«Таблица двухместных операций»

Таблица 13 - Таблица двуместных операций

Приложение В

«ПОЛИЗ программы. Интерпретация ПОЛИЗа»

dim integer qq:= q plus 1q

ПОЛИЗ программы представлен на рисунке 6.

Рисунок 6 - ПОЛИЗ программы

Обозначения:

@ num - адрес переменой.

^ pos - переход в заданную метку ПОЛИЗа.

Таблица 14 - Ход интерпретации ПОЛИЗа программы

Приложение Г

«Цепочка вывода и дерево разбора»

dim integer qqas q plus 1q

Цепочка вывода:

®P

®telo

®dim telo \n OperL end

®dim Opis \n OperL end

®dim Type Id1 \n OperL end

®dim Type Id, Id1 \n OperL end

®dim Type Byk, Id1 \n OperL end

®dim Type q, Id1 \n OperL end

®dim q, Id Opis \n OperL end

®dim Type q Byk \n OperL end

®dim Type q \n OperL end

®dim integer q \n OperL end

®dim integer q \n Oper \n OperL end

®dim integer q \n read Id1 \n OperL end

®dim integer q \n read Id \n OperL end

®dim integer q \n read Byk \n OperL end

®dim integer q \n read q \n OperL end

® dim integer q \n read q \n Oper \n OperL end

® dim integer q \n read q \n Prisv \n OperL end

® dim integer q \n read q \n Id as Virag \n OperL end

® dim integer q \n read q \n OperL end

® dim integer q \n read q \n q := Virag \n OperL end

® dim integer q \n read q \n q := Sum \n OperL end

® dim integer q \n read q \n q := Sum plus Op \n OperL end

® dim integer q \n read q \n q := Id plus Sum \n OperL end

® dim integer q \n read q \n q := Byk plus Sum \n OperL end

® dim integer q \n read q \n q := q plus Sum \n OperL end

® dim integer q \n read q \n q := q plus Op \n OperL end

® dim integer q \n read q \n q := q plus Ch \n OperL end

® dim integer q \n read q \n q := q plus De \n OperL end

® dim integer q \n read q \n q := q plus Cifra Dd \n OperL end

® dim integer q \n read q \n q := q plus 1 \n OperL end

® dim integer q \n read q \n q := q plus 1 \n Oper end

® dim integer q \n read q \n q := q plus 1 \n write (Virag) end

® dim integer q \n read q \n q := q plus 1 \n write Sum end

® dim integer q \n read q \n q := q plus 1 \n write Op end

® dim integer q \n read q \n q := q plus 1 \n write Id end

® dim integer q \n read q \n q := q plus 1 \n write Byk end

® dim integer q \n read q \n q := q plus 1 \n write q end