Пример готовой курсовой работы по предмету: Программирование
Содержание
ВВЕДЕНИЕ 3
Основные фазы компиляции: 6
1.Лексический анализ 6
2. Синтаксический анализ 7
3. Семантический анализ 7
4. Оптимизация 7
5. Генерация кода 8
Построение компилятора 8
1. Этапы построения компилятора 8
1.
1. Построение лексического анализатора 8
1.2. Построение синтаксического анализатора 11
Описание в виде правил КС-грамматики 12
Описание грамматики в форме Бэкуса-Наура 15
Описание грамматики на языке синтаксических диаграмм 17
Синтаксический анализатор грамматики операторного предшествования 23
Алгоритм функционирования синтаксического анализатора 27
1.3. Построение дерева разбора 28
1.4. Внутреннее представление 28
1.5. Аннотированное дерево 29
2. Сведения о программе 31
2.1 Общие сведения 31
2.2. Функциональное назначение 31
3.3. Логическая структура программы 31
2.4. Используемые технические средства 33
2.5. Вызов и загрузка 33
2.6. Входные данные 33
2.7. Выходные данные 34
3. Протокол выполнения программы 34
ЗАКЛЮЧЕНИЕ 35
СПИСОК ЛИТЕРАТУРЫ 36
ПРИЛОЖЕНИЕ 1 37
ПРИЛОЖЕНИЕ 2 46
ПРИЛОЖЕНИЕ 3 49
ПРИЛОЖЕНИЕ 4 122
ПРИЛОЖЕНИЕ 5 139
Выдержка из текста
Каждая вычислительная машина имеет свой собственный язык программирования — язык команд или машинный язык — и может исполнять программы, записанные только на этом языке. С помощью машинного языка, в принципе, можно описать любой алгоритм, но затраты на программирование будут чрезвычайно велики. Это обусловлено тем, что машинный язык позволяет описывать и обрабатывать лишь примитивные структуры данных — бит, байт, слово. Программирование в машинных кодах требует чрезмерной детализации программы и доступно лишь программистам, хорошо знающим устройство и функционирование ЭВМ. Преодолеть эту трудность и позволили языки высокого уровня (Фортран, ПЛ/1, Паскаль, Си, Ада, и др.) с развитыми структурами данных и средствами их обработки, не зависящими от языка конкретной ЭВМ.
Алгоритмические языки высокого уровня обладают достаточно высокой изобразительной силой, они дают возможность программисту достаточно просто и удобно описывать алгоритмы решения многих прикладных задач. Такое описание называют исходной программой, а язык высокого уровня — входным языком.
Языковым процессором называют программу на машинном языке, по-зволяющую вычислительной машине понимать и выполнять программы на входном языке. Различают два основных типа языковых процессоров: интерпретаторы и трансляторы [2].
Интерпретатор — это программа, которая в качестве входа допускает программу на входном языке и по мере распознавания конструкций входного языка реализует их, выдавая на выходе результаты вычислений, предписанные исходной программой.
Транслятор — это программа, которая допускает на входе исходную программу и порождает на своем выходе программу, функционально-эквивалентную исходной, называемую объектной. Объектная программа записывается на объектном языке. В частном случае, объектным языком может служить машинный язык, и в этом случае полученную на выходе транслятора программу можно сразу же выполнить на ЭВМ (проинтерпретировать).
При этом ЭВМ является интерпретатором объектной программы в машинных кодах. В общем случае объектный язык необязательно должен быть машинным или близким к нему (автокодом).
В качестве объектного языка может служить некоторый промежуточный язык — язык, лежащий между входным и машинным языками.
Если в качестве объектного языка используется промежуточный язык, то возможны два варианта построения транслятора.
Первый вариант — для промежуточного языка имеется (или разрабатывается) другой транслятор — с промежуточного языка на машинный, и он используется в качестве последнего блока проектируемого транслятора.
Второй вариант построения транслятора с использованием промежу-точного языка — построить интерпретатор команд промежуточного языка и использовать его в качестве последнего блока транслятора. Преимущество интерпретаторов проявляется в отладочных и диалоговых трансляторах, обеспечивающих работу пользователя в диалоговом режиме, вплоть до внесений изменений в программу без ее повторной полной перетрансляции.
Интерпретаторы используются также и при эмуляции программ — ис-полнении на технологической машине программ, составленных для другой (объектной) машины) Данный вариант, в частности, используется при отладке на универсальной ЭВМ программ, которые будут выполняться на специализированной ЭВМ.
Транслятор, использующий в качестве входного языка язык, близкий к машинному (автокод или ассемблер), традиционно называют ассемблером. Транслятор для языка высокого уровня называют компилятором.
В построении компиляторов за последние годы достигнуты значитель-ные успехи. Первые компиляторы использовали так называемые прямые методы трансляции — это преимущественно эвристические методы, в которых на основе общей идеи для каждой конструкции языка разрабатывался свой алгоритм перевода в машинный эквивалент [2].
Эти методы были медленные и не носили структурного характера. В основе методики проектирования современных компиляторов лежит композиционный синтаксически-управляемый метод обработки языков. Композиционный в том смысле, что процесс перевода исходной программы в объектную реализуется композицией функционально независимых отображений с явно выделенными входными и выходными структурами данных. Отображения эти строятся из рассмотрения исходной программы, как композиции основных аспектов (уровней) описания входного языка: лексики, синтаксиса, семантики и прагматики, и выявления этих аспектов из исходной программы в ходе ее компиляции.
Перевод программы с одного языка на другой, в общем случае, состоит в изменении алфавита, лексики и синтаксиса языка программы с сохранением ее семантики. Процесс трансляции исходной программы в объектную обычно разбивается на несколько независимых подпроцессов (фаз трансляции), которые реализуются соответствующими блоками транслятора. Удобно считать основными фазами трансляции лексический анализ, синтаксический анализ, семантический анализ и синтез объектной программы. Тем не менее, во многих реальных компиляторах эти фазы разбиваются на несколько подфаз, могут также быть и другие фазы (например, оптимизация объектного кода) [2].
На рис.1 показана упрощенная функциональная модель транслятора.
Рис.
1. Упрощённая функциональная модель транслятора
Основные фазы компиляции:
1. Лексический анализ. На этом этапе последовательность символов исходного файла преобразуется в последовательность лексем.
2. Синтаксический (грамматический) анализ. Последовательность лексем преобразуется в дерево разбора.
3. Семантический анализ. Дерево разбора обрабатывается с целью установления его семантики (смысла) — например, привязка идентификаторов к их декларациям, типам, проверка совместимости, определение типов выражений и т. д. Результат обычно называется «промежуточным представлением/кодом», и может быть дополненным деревом разбора, новым деревом, абстрактным набором команд или чем-то ещё, удобным для дальнейшей обработки.
4. Оптимизация. Выполняется удаление излишних конструкций и упрощение кода с сохранением его смысла. Оптимизация может быть на разных уровнях и этапах — например, над промежуточным кодом или над конечным машинным кодом.
5. Генерация кода. Из промежуточного представления порождается код на целевом языке.
В конкретных реализациях компиляторов эти этапы могут быть разделены или совмещены в том или ином виде.
1.Лексический анализ
В соответствии с этой моделью входная программа, прежде всего, подвергается лексической обработке. Цель лексического анализа — перевод исходной программы на внутренний язык компилятора, в котором ключевые слова, идентификаторы, метки и константы приведены к одному формату и заменены условными кодами: числовыми или символьными, которые называются дескрипторами. Каждый дескриптор состоит из двух частей: класса (типа) лексемы и указателя на адрес в памяти, где хранится информация о конкретной лексеме. Обычно эта информация организуется в виде таблиц. Одновременно с переводом исходной программы на внутренний язык на этапе лексического анализа проводится лексический контроль — выявление в программе недопустимых слов [3].
2. Синтаксический анализ
Синтаксический анализатор воспринимает выход лексического анализатора и переводит последовательность образов лексем в форму промежуточной программы. Промежуточная программа является, по существу, представлением синтаксического дерева программы. Последнее отражает структуру исходной программы, т.е. порядок и связи между ее операторами. В ходе построения синтаксического дерева выполняется синтаксический контроль — выявление синтаксических ошибок в программе.
Фактическим выходом синтаксического анализатора может быть последовательность применения правил грамматики, на основании которой можно построить форму внутреннего представления.
3. Семантический анализ
Непосредственно генерации объектной программы часто предшествует семантический анализ, который включает различные виды семантической обработки. Один из видов — проверка семантических соглашений. Примеры таких соглашений: единственность описания каждого идентификатора в программе, определение переменной производится до ее использования и т.д. Семантический анализ может выполняться и на более поздних фазах трансляции, например, на фазе оптимизации программы, которая тоже может включаться в транслятор.
4. Оптимизация
Оптимизация программного кода — это модификация программ, выполняемая оптимизирующим компилятором или интерпретатором с целью улучшения их характеристик, таких как производительности или компактности, — без изменения функциональности.
Оптимизация — не обязательный, но важный этап компиляции. В принципе, она может происходить неявно во время трансляции программы, но, как правило, оптимизацию программы выделяют как отдельный этап функционирования компиляторов. Компоновщики так же могут выполнять часть оптимизаций, таких как удаление неиспользуемых подпрограмм или переупорядочивание подпрограмм.
5. Генерация кода
Синтез объектной программы начинается, как правило, с распределения и выделения памяти для основных программных объектов. Затем производится исследование каждого предложения исходной программы, и генерируются семантически эквивалентные предложения объектного языка. В качестве входной информации здесь используется синтаксическое дерево программы и выходные таблицы лексического анализатора — таблица идентификаторов, таблица констант и другие. Анализ дерева позволяет выявить последовательность генерируемых команд объектной программы, а по таблице идентификаторов определяются типы команд, которые допустимы для значений операндов в генерируемых командах [3].
Список использованной литературы
1. Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. – СПб.: Питер, 2002.
2. Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование. Основы построения трансляторов. – СПб.: КОРОНА принт, 2000.
3. Альфред Ахо, Равви Сети, Джеффри Ульман. Компиляторы. Принципы, технологии, инструменты. – М.: Издательский дом «Вильямс», 2003.
