Принципы разработки компиляторов - Программирование, компьютеры и кибернетика курсовая работа

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


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Компилятор - программный модуль, задачей которого является перевод программы, написанной на одном из языков программирования (исходный язык) в программу на язык ассемблера или язык машинных команд.
Большинство компиляторов переводят программу с некоторого высокоуровневого языка программирования в машинный код, который может быть непосредственно выполнен компьютером.
Целью данной курсовой работы является изучение составных частей, основных принципов построения и функционирования компиляторов, практическое освоение методов построения составных частей компилятора для заданного входного языка.
Курсовая работа заключается в создании отдельных частей компилятора заданного языка.
В первой части работы ставится задача разработать программу, которая получает на входе набор идентификаторов, организует таблицу по заданному методу и позволяет осуществить многократный поиск идентификатора в этой таблице.
Во второй части работы требуется разработать программу, которая выполняет лексический анализ входного текста по заданной грамматике и порождает таблицу лексем с указанием их типов и значений.
В третьей части работы требуется разработать программу, которая на основании таблицы лексем выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора.
Результатами курсовой работы являются программная реализация заданного компилятора и пояснительная записка, оформленная в соответствии с требованиями стандартов и задания на курсовую работу.
В качестве среды разработка для реализации программы использован язык программирования C ++ и среда программирования Visual Studio C ++ 2012 .
Входной язык представляет собой подмножество языка программирования Pascal.
Программа на данном языке может включать в себя символы латиницы, цифры, знак “ _ “, символьные константы, различные операторы. Текст на входном языке содержится в текстовом файле.
Набор идентификаторов организуются в таблицу по методу упорядоченного списка. Необходима возможность осуществления многократного поиска идентификатора в этой таблице. Список идентификаторов считать заданным в виде текстового файла. Длина идентификатора ограничена 32 символами. Он может включать в себя символы кириллицы и латиницы, цифры, знаки “ ^ ” и ” _ ”. Идентификатор не может начинаться с цифры.
Предусмотрены следующие варианты операторов входной программы:
- зарезервированные слова If, Else, Then, While, Do, Prog, End;
- арифметические операции (+, -, /, *);
- операндами в выражениях могут выступать идентификаторы и константы (один символ, заключенный в одинарные кавычки);
- все идентификаторы должны восприниматься как переменные;
- допускается присутствие комментариев оформленных виде: //комментарий
Для выделения лексем заранее строится конечный автомат.
Данный язык относится к КС-языкам, поэтому может быть описан следующей грамматикой:
<буква>>” A ” |….| ” Z ” |….| ” a ” |….| ” z ” |”_”
<арифм.опер.>>” +” | ”-” | ”*” |”/”
< цифра> >” 0 ” |”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”
<арифм.в ыр.>> <операнд><арифм.оп.> <операнд>
<блок опер.> ><оператор> ”;” <оператор>
<оп.цикла>> “ do ” <тело > “ while ” ”(” <арифм.выр.>”)” ”;”
|“ do ””{“ <оператор> ”}” “ while ””(” <арифм.выр.>”)””;”
<услов.оп>> if “(”<арифм.выр>“)”” then ”<тело>” else ”<тело>
| if “(” <арифм.выр>“)”” then ”<тело>
| if “(”<арифм.выр>“)” then ”<оператор>” else ”<оператор>
| if “(” <арифм.выр>“)”” then ”<оператор>
| if “(”<арифм.выр>“)”” then ”<оператор>” else ”<тело>
| if “(”<арифм.выр>“)”” then ”<тело>” else ”<оператор>
Далее, используя эту грамматику по методу сдвиг-свертка, производится проверка входного языка на синтаксические ошибки.
Проверка правильности семантики и генерация кода требуют знания характеристик идентификаторов, используемых в программе на исходном языке. Эти характеристики выясняются из описаний и из того, как идентификаторы используются в программе и накапливаются в таблице символов или таблице идентификаторов. Любая таблица символов состоит из набора полей, количество которых равно числу идентификаторов программы. Каждое поле содержит в себе полную информацию о данном элементе таблицы. Под идентификаторами подразумеваются переменные.
Основными характеристиками метода построения идентификаторов является скорость поиска, объем памяти. Оптимальное сочетание этих параметров определяет выбор метода. В данной работе используется метод упорядоченного списка.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Лексический анализатор (или сканер) - это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного языка. На вход лексического анализатора поступает текст исходной программы, а выходная информация передается для дальнейшей обработки компилятором на этапе синтаксического анализа и разбора.
В основном лексические анализаторы выполняют исключение из текста исходной программы комментариев и незначащих пробелов, а также выделение лексем следующих типов: идентификаторов, строковых, символьных и числовых констант, ключевых (служебных) слов входного языка.
Распознаватель лексем языка для данной грамматики задан конечным детерминированным автоматом, схема которого представлена на рисунках 3, 4 и 5.
V - любой определенный алфавитно-цифровой символ (буквы латинского алфавита, знак «_», десятичные цифры);
V(*) - любой символ кроме перечисленных в скобках;
B - буквы латинского алфавита и знак «_»;
B(*) - любая буква кроме перечисленных в скобках;
Р - пробел, табуляция, перенос строки;
D - недопустимые символы (все кроме перечисленных);
F - сохранение (ID - в таблице идентификаторов; L -в таблице лексем);
P1, P2, P3, P4 - состояния, соответствующие ключевому слову “prog”;
En1, En2 - состояния, соответствующие ключевому слову “end”;
I1, I2 - состояния, соответствующие ключевому слову “if”;
E1, E2, E3, E4 - состояния, соответствующие слову “else”;
T1, T2, T3, T4 - состояния, соответствующие слову “then”;
W1, W2, W3, W4, W5 - состояния, соответствующие ключевому слову “while”;
D1, D2 - состояния, соответствующие ключевому слову “do”;
S1, S2, S3 - состояния, соответствующие символьное константе:
A1, A2 - состояния, соответствующие оператору присваивания “:=”;
Программа, реализованная на основе данного автомата, выполняет лексический анализ текста программы на заданном языке.
Спроектированный лексический анализатор выполняет лексический анализ входного текста в соответствии с заданной грамматикой и порождает таблицу лексем с указанием их типов. Программа выводит также сообщения о наличие во входном тексте ошибок. Этот алгоритм послужит в дальнейшем базой для построения дерева вывода в 3 части курсовой работы.
4. ПОСТРОЕНИЕ СИТАКСИЧЕСКОГО АНАЛИЗАТОРА
Лексический анализатор выделяет в тексте лексемы языка. Полученная после лексического анализа цепочка во второй части программы рассматриваться в соответствии с алгоритмом разбора. После построения цепочки вывода на ее основе строится дерево разбора.
Программа выполняет лексический анализ входного языка, порождает таблицу лексем и выполняет синтаксический разбор текста по заданной грамматике с построением дерева разбора. Текст на входном языке задается в виде символьного (текстового) файла. Программа должна выдавать сообщения о наличие во входном тексте ошибок.
Длину идентификаторов и строковых констант считать ограниченной 32 символами.
Перед синтаксическим анализатором стоят две основные задачи: проверить правильность конструкций программы, которая представляется в виде уже выделенных слов входного языка, и преобразовать ее в вид, удобный для дальнейшей семантической (смысловой) обработки и генерации кода. Одним из таких способов представления является дерево синтаксического разбора.
Программирование работы недетерминированного МП-автомата - это сложная задача. Разработанный алгоритм, позволяет для произвольной КС-грамматики определить, принадлежит ли ей заданная входная цепочка (алгоритм Кока-Янгера-Касами).
Доказано, что время работы этого алгоритма пропорционально n 3 , где n - длина входной цепочки. Для однозначной КС-грамматики при использовании другого алгоритма (алгоритм Эрли) это время пропорционально n 2 . Подобная зависимость делает эти алгоритмы требовательными к вычислительным ресурсам. На практике и не требуется анализ цепочки произвольного КС-языка - большинство конструкций языков программирования может быть отнесено в один из классов КС-языков, для которых разработаны алгоритмы разбора, линейно зависящие от длины входной цепочки.
КС-языки делятся на классы в соответствии со структурой правил их грамматик. В каждом из классов налагаются дополнительные ограничения на допустимые правила грамматики.
Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма “сдвиг-свертка”. Выделяют следующие типы грамматик предшествования:
- смешанной стратегии предшествования;
Алгоритм построения синтаксического анализатора включает следующие этапы:
1) составление правил грамматики языка;
2) выявление множества крайних правых и кайних левых терминальных и нетерминальных символов;
3) построение матрицы предшествования.
Рассмотрим эти этапы более подробно.
Множество правил грамматики имеет вид:
<буква>>” A ” |….| ” Z ” |….| ” a ” |….| ” z ” |”_”
<цифра>>”0”|”1”|”2”|”3”|”4”|”5”|”6”|”7”|”8”|”9”
<арифм.выр.>> <операнд><арифм.оп.><операнд>
<блок опер.> ><оператор> ”;” <оператор>
<оп.цикла>> “ do ”<тело>“ while ” ”(” <арифм.выр.>”)” ”;”
|“ do ””{“ <оператор> ”}” “ while ””(” <арифм.выр.>”)””;”
<услов.оп>> if “(”<арифм.выр>“)”” then ”<тело>” else ”<тело>
| if “(” <арифм.выр>“)”” then ”<тело>
| if “(”<арифм.выр>“)” then ”<оператор>” else ”<оператор>
| if “(” <арифм.выр>“)”” then ”<оператор>
| if “(”<арифм.выр>“)”” then ”<оператор>” else ”<тело>
| if “(”<арифм.выр>“)”” then ”<тело>” else ”<оператор>
Грамматика является грамматикой операторного предшествования, так как она не содержит -правил и правые части правил не содержат смежных нетерминальных символов. Построим множества крайних левых и крайних правых символов L ( U ), R ( U ) относительно всех нетерминальных символов грамматики.
Таблица 3.1 - Множества крайних правых и крайних левых символов
На основе полученных множеств построим множества крайних левых и крайних правых терминальных символов L t ( U ), R t ( U ) относительно всех нетерминальных символов грамматики.
Таблица 3.2 - Множества крайних правых и крайних левых терминальных символов
На основе этих множеств и правил грамматики G построим матрицу предшествования грамматики:
Таблица 3.3 - Матрица предшествования исходной грамматики
Генерация объектного кода -- это перевод компилятором внутреннего представления исходной программы в цепочку символов выходного языка.
Генерация объектного кода порождает результирующую объектную программу на языке ассемблера или непосредственно на машинном языке (в машинных кодах). Внутреннее представление программы может иметь любую структуру в зависимости от реализации компилятора, в то время как результирующая программа всегда представляет собой линейную последовательность команд. Поэтому генерация объектного кода (объектной программы) в любом случае должна выполнять действия, связанные с преобразованием сложных синтаксических структур в линейные цепочки.
Генерацию кода можно считать функцией, определенной на синтаксическом дереве, построенном в результате синтаксического анализа, и на информации, содержащейся в таблице идентификаторов. Поэтому генерация объектного кода выполняется после того, как выполнены синтаксический анализ программы и все необходимые действия по подготовке к генерации кода: распределено адресное пространство под функции и переменные, проверено соответствие имен и типов переменных, констант и функций в синтаксических конструкциях исходной программы.
Характер отображения входной программы в последовательность команд, выполняемую генерацией, зависит от входного языка, архитектуры вычислительной системы, на которую ориентирована результирующая программа, а также от качества желаемого объектного кода.
Задача генератора кода - построение для программы на входном языке эквивалентной машинной программы. Обычно в качестве входа для генератора кода служит некоторое промежуточное представление программы.
Генерация кода включает ряд специфических, относительно независимых подзадач: распределение памяти (в частности, распределение регистров), выбор команд, генерацию объектного (или загрузочного) модуля. Конечно, независимость этих подзадач относительна: например, при выборе команд нельзя не учитывать схему распределения памяти, и, наоборот, схема распределения памяти (регистров, в частности) ведет к генерации той или иной последовательности команд. Однако удобно и практично эти задачи все же разделять, обращая при этом внимание на их взаимодействие.
В какой-то мере схема генератора кода зависит от формы промежуточного представления. Ясно, что генерация кода из дерева отличается от генерации кода из троек, а генерация кода из префиксной записи отличается от генерации кода из ориентированного графа. В то же время все генераторы кода имеют много общего, и основные применяемые алгоритмы отличаются, как правило, только в деталях, связанных с используемым промежуточным представлением.
Задача оптимизации кода состоит в создании эффективного (с точки зрения размера памяти и времени выполнения) целевого кода. Желаемая степень оптимизации будет зависеть от обстоятельств. Иногда она не нужна, например, если у программы малое время выполнения, умеренные запросы к памяти и, возможно, малый срок жизни.
Необходимость оптимизации может требоваться для программ с большим временем выполнения либо значительными запросами к памяти и, возможно, с длительным временем существования. Стоимость оптимизации главным образом оценивается в терминах времени компиляции. Некоторые виды оптимизации могут быть дорогостоящими в смысле времени компиляции, другие - сравнительно дешевыми. Обычно более дешевые типы оптимизации всегда стоит осуществлять, а более дорогие - не всегда.
Некоторые компиляторы, в зависимости от требуемой степени оптимизации, могут работать в более чем одном режиме.
В средах, где основной является качественная диагностическая информация, лучше всего полностью отказаться от оптимизации, чтобы избежать возможной путаницы вследствие некорректных сообщений.
//Подключаем необходимые заголовочные файлы
#include "states.h" //функции переходов автомата
#include "common.h" //вспомогательные функции
//по умолчанию используем пространство имен "std"
//таким образом делаем переменные видимыми в разных модулях
//extern lexem* idtable[MAXHASH]; //таблица идентификаторов
extern lexem** idtable = NULL;//таблица идентификаторов
extern lexem* lexTableHead = NULL; //указатель на начало (начальный елемент) таблицы лексем
extern lexem* lexTableEnd = NULL; //указатель на конец (последний елемент) таблицы лексем
int _tmain(int argc, _TCHAR* argv[])
setlocale( LC_ALL,"Russian" ); //данная строчка необходима для корректного отображения кириллицы
//cout << "Введите путь и имя файла \n";
//считаем содерживое файла (текст программы) в строку
string programText = readFile(fileName);
string lexem = ""; //переменная для хранения имени лексемы
STATE currState = sBEGIN; //текущее состояние автомата
//текс программы разберем посимвольно в цикле
for(unsigned int i = 0; i < programText.length(); i++){
char c = toupper(programText[i]); //текущий символ
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
/////////////////////////////////////////
currState = comment1State(c,lexem);
/////////////////////////////////////////
currState = comment2State(c,lexem);
/////////////////////////////////////////
/////////////////////////////////////////
//освободим ресурсы (удалим содержимое таблиц)
wcout << endl << L"Для завершения программы нажмите любую клавишу...";
В результате выполнения курсовой работы для заданного входного языка были построены отдельные части компилятора.
В первой части работы был разработан программа, которая получает на входе набор идентификаторов, организует таблицу идентификаторов методом упорядоченного списка, позволяет осуществить многократный поиск идентификатора в этой таблице.
Во второй части работы была написана программа, которая выполняет лексический анализ входного текста и порождает таблицу лексем с указанием их типов и значений.
Третья часть курсовой работы была посвящена разработке программы, которая порождает таблицу лексем и выполняет синтаксический разбор текста с построением дерева разбора.
Отдельные части компилятора, разработанные в данной курсовой работе, дают представление о технике и методах, лежащих в основе построения компиляторов.
1. Гордеев А.В. Молчанов Л.Ю. Системное программное обеспечение, - СПб.: Питер. 2002. - 734с.
2. Кампапиец Р.II. Манькоп Е.В., Филатов Н.Е. Системное программирование. Основы построения трансляторов: Учеб. пособие для высших и средних учебных заведений. - СПб.: КОРОНА Принт, 2000. -256 с.
3. Гордеев А.В. Операционные системы: Учебник для вузов.
2-е изд.-СПб.: Питер, 2004. - 416 с.
4. Олифер В.Г., Олифер Н.А. Сетевые операционные системы. - СПб.: Питер. 2002. - 544 с.
5. Брайан Оверленд C++ без страха,- СПб.: Питер. 2005. - 432с.
6. Марченко А.Л. C++ Бархатный путь,- СПб.: Питер. 2005. - 401с.
Описание компиляторов языка С/С++: MinGW, Borland Builder, Watcom, Intel C++, Visual. Сравнение характеристик выполнения программ на примере простого кода. Проведение тестов для компиляторов, оценка скорости выполнения и компилирования, их опций. курсовая работа [1,6 M], добавлен 05.10.2012
Проектирование программы-анализатора, состоящей из двух частей: лексического анализатора, разбивающего исходный текст программы на лексемы и заполняющего таблицу имен; синтаксического анализатора, проверяющего соответствие текста заданной грамматике. курсовая работа [2,0 M], добавлен 14.06.2010
Порядок описание процесса разработки модели для разрешения задачи программирования с помощью средств языка программирования. Структуры данных и основные принципы их построения. Этапы компьютерного моделирования. Этапы и значение написания программы. курсовая работа [19,5 K], добавлен 19.05.2011
Принцип работы компиляторов. Синтаксически-неоpиентиpованные алгоритмы, достоинства этого класса. Метод нисходящего разбора - рекурсивный спуск, суть данного метода. Преобразования программы компилятором с реализацией работы с процедурами с параметрами. курсовая работа [31,6 K], добавлен 25.03.2011
Разработка анализирующей части компилятора для выполнения проверки исходной программы на соответствие грамматике языка, правилам семантики и построения внутреннего представления. Описание анализаторов: лексического, синтаксического и семантического. контрольная работа [704,9 K], добавлен 01.02.2013
Компиляторы - инструменты для решения вычислительных задач с использованием бинарного кода. Проблема выбора "правильного" компилятора. Применение компиляторов языка С++. Оценка MinGW, Borland Builder, Intel C++ Professional Edition, Watcom и Visual Studi. контрольная работа [4,5 M], добавлен 05.10.2012
Доэлектронный период создания механических счетных устройств. Появление первых электронных машин и их недостатки. Начало коммерческого применения ЭВМ для обработки данных. Разработка программного обеспечения, компиляторов. Принципы работы современных ЭВМ. презентация [226,9 K], добавлен 19.12.2014
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Принципы разработки компиляторов курсовая работа. Программирование, компьютеры и кибернетика.
Курсовая работа по теме Документний потік з питань сільського господарства
Курсовая Работа На Тему Особенности Организации Боевой Службы Маневренной Группы В Горно-Лесистой Местности
Преступления Против Общественной Нравственности Курсовая
Реферат по теме Обратная сила уголовного закона
Курсовая работа: Общественное разделение труда и развитие общественного характера производства
Электрический Ток Реферат По Электротехнике
Сочинение По Стихотворению Гумилева Шестое Чувство
Реферат: Творчество Ван Дейка. Скачать бесплатно и без регистрации
Реферат по теме Реферирование журналов
Эссе Почему Я Выбрала Медицинский
Цель Создания Реферата
Реферат по теме Лукреций
Реферат: История развития компьютеров IBM PC на примере ЦПУ корпорации Intel
Физическое Воспитание Курсовая Работа
Дипломная работа по теме Организационные основы оптимизации двигательной активности детей с задержкой психического развития
Пример Анализа Курсовой Работы
Контрольная Работа 11 Класс Геометрия Объем
Сочинение по теме Дети в романе "Преступление и наказание"
Какие Требования Необходимо Выполнять При Создании Реферата
Дипломная работа по теме Спрос, предложение и равновесная цена
Облачные хранилища данных - Программирование, компьютеры и кибернетика курсовая работа
Скрипковий цикл Богдана Шиптура з епіграфами із поезії Марійки Підгірянки для дітей - Музыка статья
Методика обучения учащихся профессионального училища на внеурочных занятиях по курсу "Роспись по ткани в технике батик" - Педагогика курсовая работа