РГЗ построение компилятора (стр. 1 )

МИНОБРНАУКИ РОССИИ

ФГБОУ ВПО Череповецкий государственный университет

Институт информационных технологий

Кафедра: Математического и

программного обеспечения ЭВМ

РГЗ построение компилятора

Листов 69

Руководитель
Исполнитель
студентка группы	1ИВТб – 41
Оценка
Подпись

Череповец, 2014 год.

Аннотация

Количество листов в документе – 69

Количество иллюстраций – 24

Количество приложений – 4

Содержание

Введение        4

1. Общие сведения        6

2. Функциональное назначение        6

3. Описание логической структуры        6

4. Технические средства        8

5. Вызов и загрузка        8

6. Входные данные        9

7. Выходные данные        9

8. Построение лексического анализатора        9

9. Построение синтаксического анализатора        11

9.1. Грамматика        12

9.1.1. Представление грамматики в виде правил КС-грамматики        13

9.1.2. Описание грамматики в форме Бекуса-Наура        15

9.1.3. Описание грамматики на языке синтаксических диаграмм        17

9.2. Предиктивный анализатор        20

9.3. Построение множеств крайних левых и крайних правых символов        21

9.4. Построение таблицы разбора        25

9.5. Построение дерева разбора        27

Заключение        30

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

ПРИЛОЖЕНИЕ 1. Техническое задание        32

ПРИЛОЖЕНИЕ 2. Руководство пользователя        38

ПРИЛОЖЕНИЕ 3. Листинг программы        44

ПРИЛОЖЕНИЕ 4. Блок-схемы алгоритмов        66

Введение

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

Языковой процессор – это программа на машинном языке, позволяющая вычислительной машине понимать и выполнять программы на входном языке.

Языковые процессоры делятся на интерпретаторы и трансляторы.

Транслятор – это программа, которая на входе имеет исходную программу, а на выходе – программу, функционально эквивалентную исходной, – объектную.

  Транслятор для языка высокого уровня называют компилятором.

Трансляторы бывают двух типов: компиляторы и интерпретаторы.

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

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

Компиляция состоит из двух основных частей: анализа и синтеза.

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

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

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

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

Общие сведения

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

описание и работа с классами языка Си.

Программа производит построение дерева вывода.

Программа написана на языке Pascal в среде программирования Borland Delphi 7.

2. Функциональное назначение

Программа выполняет следующие функции:

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

3. Описание логической структуры

Работа программы построена на последовательном выполнении этапов компиляции. Основные фазы компиляции:

лексический анализ; синтаксический анализ; семантический анализ; генерация промежуточного кода; оптимизация кода;

Цели лексического анализа:

Перевод исходной программы на внутренний язык компилятора, в котором ключевые слова, идентификаторы, метки и константы приведены к одному формату и заменены условными кодами: числовыми или символьными, которые называются дескрипторами. Каждый дескриптор состоит из двух частей: класса-типа лексемы и указателя на адрес в памяти, где хранится информация о конкретной лексеме. Эта информация организуется в виде таблиц; Лексический контроль – выявление в программе недопустимых слов.

  Цели синтаксического анализа:

Перевод последовательности образов лексем в форму промежуточной программы; Синтаксический контроль – выявление синтаксических ошибок в программе.

Цель семантического анализа – проверка семантических ошибок в исходной программе. Например, проверка типов, единственность описания каждого идентификатора.

Синтез объектной программы – построение объектного кода программы на основании внутреннего представления и информации, содержащейся в таблице идентификаторов. Основные этапы синтеза: генерация промежуточного кода, оптимизация кода и генерация кода.

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

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

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

В курсовой работе реализованы фазы лексического синтаксического и семантического анализов, генерация промежуточного.

4. Технические средства

Для корректной работы программы необходимы:

процессор не ниже Intel Pentium 140 MHz; операционная система Microsoft Windows 98/2000/XP/7/8; объем оперативной памяти не менее 256 Мб; свободное место на диске не менее 300 Мб; клавиатура, мышь.

5. Вызов и загрузка

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

6. Входные данные

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

Данная строка в соответствие с заданием на курсовую работу может содержать следующие конструкции:

описание простых типов данных; оператор присваивания; знаки пробел, ; , : , ( , ) , { , }

7. Выходные данные

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

8. Построение лексического анализатора

Лексический анализатор — это часть компилятора, которая читает литеры программы на исходном языке и строит из них слова (лексемы) исходного языка. Лексемой (лексической единицей языка) называется структурная единица языка, кото­рая состоит из элементарных символов языка и не содержит в своем составе дру­гих структурных единиц языка.

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

Основные функции лексического анализатора:

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

Распознавателем на этапе лексического анализа являются конечный автомат М(Q, V, δ, q0, F), где: