Компилятор на С - Курсовая работа

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

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

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

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

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

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

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

В качестве среды разработки для реализации программы предполагалось использовать язык программирования C и среду программирования QT 4.8.6.

Описание входного языка

Входной язык представляет собой подмножество языка программирования C в упрощенном виде.

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

Текст на входном языке задается в виде текстового файла. Предусмотрены следующие варианты операторов входной программы: оператор присваивания вида =;

зарезервированные слова и символы: 1) типы: «array», «int», «char»;

2) оператор цикла: «while(…)»;

3) оператор условия: «switch(…)»;

арифметические операции: сложения ( ), вычитания (-), умножения(*), деления(/);

логические операции: «меньше» (), «равно» (=), «не равно» (!=), «лог. И» (&&), «лог. ИЛИ» (||);

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

все идентификаторы должны восприниматься как переменные. Тип переменных - integer, длина ограничена 16 символами;

допускается присутствие комментария, оформленного в виде: //комментарий

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

Данный язык относится к КС-языкам, поэтому может быть описан следующей грамматикой: >”0” | ”1” | ”2” | ”3” | ”4” | ”5” | ”6” | ”7” ;

>”A” |….| ”Z” |….| ”a” |….| ”z”;

>” ”|”-”;

>|

|

;

> |

;

>|

|

;

>|

;

> “ ” | “-”| “*” | “/”;

> “” | “=”|“!=” | “&&” | “||”;

>|

|

;

>“;”|

“;”|

“;”;

>|

”{””}”;

>”=”|

”=”|

”=””;”

>|

|

|

;

>|

|

|

|

;

>”while””(””;””;””)”

“;”;

>

”switch””(” ”;””;””)”

“{””case””:””;”’}’|

”switch””(” ”;””;””)”

“{””default””:””;””}”|

”switch””(” ”;””;””)”

“{””case””:””;”

”default””:””;””}”

>”//”;

> ”{” ”}”.

Организация таблицы идентификаторов

Назначение таблицы идентификаторов

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

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

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

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

Хеш-адресация с использованием метода рехеширования с помощью произведения

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

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

Чтобы избежать коллизий используют разные методы. Одним из них является метод, рехеширования с помощью произведения. Для решения проблемы коллизии используем метод рехеширования с помощью произведения, новую хеш-функцию получаем по формуле: hi(A) = ( h(A)•i ) mod Nm, где i - число возникновения коллизий, а Nm - максимальное значение из области значений

Согласно этому методу - если для элемента A адрес n0 = h(А), вычисленный с помощью хэш-функции, указывает на уже занятую ячейку, то необходимо вычислить значение функции n1 = h1(А) и проверить занятость ячейки по адресу n1. Если и она занята, то вычисляется значение h2(A), и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение hi(A) не совпадет с h(А). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет - выдается информация об ошибке размещения идентификатора в таблице.

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

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

Рис. 1.1 - Блок-схема метода рехеширования с помощью произведения а) - Блок-схема алгоритма простого рехеширования с помощью произведения;

б) - Блок-схема функции поиска идентификатора;

в) - Блок-схема функции добавления идентификатора

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

Назначение лексического анализатора

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

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

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

Это следующие причины: упрощается работа с текстом исходной программы на этапе синтаксического разбора и сокращается объем обрабатываемой информации, так как лексический анализатор структурирует поступающий на вход исходный текст программы и удаляет всю незначащую информацию;

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

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

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

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

Таблица лексем и содержащаяся в ней информация

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

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

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

Схема распознавателя

Описание: Н - начальное состояние

К - конечное состояние

Т1.(1-2) - состояния соответствующие комментарию в “//”

Т2.(1-5) - состояния соответствующие ключевому слову “while”

T3.(1-6) - состояния соответствующие ключевому слову “switch”

T4.(1-3) - состояния соответствующие ключевому слову “int”

T5.(1-5) - состояния соответствующие ключевому слову “array”

T6.(1-4) - состояния соответствующие ключевому слову “char”

T7.(1-4) - состояния соответствующие ключевому слову “case”

T8.(1-7) - состояния соответствующие ключевому слову “default”

Ц - любая цифра

Б - любая буква

Б(*) - буква, кроме перечисленных в скобках

Ц(*) - цифра, кроме перечисленных в скобках

Е - “ошибка”

ID - соответствующая идентификатору

П - пробел, табуляция, переход на новую строку , “:”, “(”, “)”, “{”, “}”…

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

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

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

Древо вывода

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

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

Длину идентификаторов и строковых констант считать ограниченной 32 символами.

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

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

Программирование работы недетерминированного МП-автомата - это сложная задача. Разработанный алгоритм, позволяет для произвольной КС-грамматики определить, принадлежит ли ей заданная входная цепочка (алгоритм Кока-Янгера-Касами).

Доказано, что время работы этого алгоритма пропорционально n3, где n - длина входной цепочки. Для однозначной КС-грамматики при использовании другого алгоритма (алгоритм Эрли) это время пропорционально n2. Подобная зависимость делает эти алгоритмы требовательными к вычислительным ресурсам. На практике и не требуется анализ цепочки произвольного КС-языка - большинство конструкций языков программирования может быть отнесено в один из классов КС-языков, для которых разработаны алгоритмы разбора, линейно зависящие от длины входной цепочки.

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

Одним из таких классов является класс грамматик предшествования. Они используются для синтаксического разбора цепочек с помощью алгоритма “сдвиг-свертка”. Выделяют следующие типы грамматик предшествования: простого предшествования;

расширенного предшествования;

слабого предшествования;

смешанной стратегии предшествования;

операторного предшествования.

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

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

Алгоритм построения синтаксического анализатора включает следующие этапы: Составление правил грамматики языка;

Выявление множества крайних правых и крайних левых терминальных и нетерминальных символов;

Построение матрицы предшествования.

Генерация объектного кода

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

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

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

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

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

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

Основные методы оптимизации

Исключение лишних операций - исключение избыточных вычислений (лишних операций) заключается в нахождении и удалении из объектного кода операций, которые повторно обрабатывают одни и те же операнды. Операция линейного участка с порядковым номером i считается лишней операцией, если существует идентичная ей операция с порядковым номером j, j < 1 и ни какой операнд, обрабатываемый операцией с порядковым номером i, нс изменялся никакой другой операцией, имеющей порядковый номер между i и j. Алгоритм исключения лишних операций просматривает операции в порядке их следования. Так же как и алгоритму свертки, алгоритму исключения лишних операции проще всего работать с триадами, потому что они полностью отражают взаимосвязь операций.

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

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

Простейший вариант свертки - выполнение в компиляторе операций, операндами которых являются константы.

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

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

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

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

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

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

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

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

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

идентификатор компилятор рехеширование

1. Системное программное обеспечение: Учебник для вузов/ А.Ю. Молчанов- СПБ.: Питер, 2003.- 396 с.

2. Альфред Ахо, Рави Сети, Джеффри Ульман Компиляторы: принципы, технологии и инструменты: 2003. - 768с.: ил.

3. Кампапиец Р.II. Манькоп Е.В., Филатов Н.Е. Системное программирование. Основы построения трансляторов: Учеб. пособие для высших и средних учебных заведений. - СПБ.: КОРОНА Принт, 2000. - 256 с

4. Креншоу Д. Пишем компилятор: СПБ.:Наука и Техника 2003. - 293с.

5. Молчанов А. Ю. Системное программное обеспечение. Лабораторный практикум. - СПБ.: Питер, 2005 - 284 с.

6. Гордеев А. В. Молчанов Л. Ю. Системное программное обеспечение, - СПБ.: Питер. 2002. - 734с.

Размещено на .ru