Дипломная работа: Программно-методический комплекс для обучения процессу создания компиляторов

только левый нижележащий узел является листом дерева;

только правый нижележащий узел является листом дерева:

оба нижележащих узла не являются листьями дерева.

Метод четверок

Каждая четверка записывается в виде:

операция, op1, op2, результат,

где операция - это выполняемая объектным кодом функция

op1, op2 - операнды этой операции

Например,

(-a+b)*(c+d)

будет соответствовать такой последовательности четверок

-  a,    T1

+ T1, b    T2

+ c,     d    T3

* T2, T3, T4

Из сформированных четверок нетрудно сгенерировать машинный код.

1.7 Обоснование создания учебного комплекса

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

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

1.8 Обзор существующих разработок

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

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

Руководство по написанию компиляторов Креншоу [5] позволяет создать свой компилятор, но его особенностью является прямой перевод считанного текста в выходной код, что не дает наглядности внутреннего представления компилятора. Этот компилятор является однопроходным, он не хранит и создает в памяти таблиц, вся обработка описывается в процедурах.

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

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

1.9 Обоснование разработки

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

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

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

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

Учебное пособие состоит из:

-     вводной части (теоретические сведения):

1)   описание компиляторов, их суть, назначение;

2)   лексический анализатор (сканер);

3)   синтаксический анализатор, дерево грамматического разбора;

4)   получение промежуточного кода;

-     практической (работа с программами):

1)   обзор компиляторов (Паскаль, C, Delphi);

2)   работа с программой LexAn;

3)   работа с программой SinAn;

4)   работа с программой SinAn;

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

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

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

Лабораторные работы обычно включает в себя:

-     теоретические сведения;

-     порядок выполнения работы;

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

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

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

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

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

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

2.1 Краткое описание учебного компилятора

Учебный компилятор состоит из четырех отдельных модулей, это:

1)   лексический анализатор (сканер) LEXAN;

2)   синтаксический анализатор (парсер) SYNAN;

3)   генератор промежуточного кода PROMKOD;

4)   генератор ассемблерного кода ASMKOD.

На данном этапе реализованы первые два. Эти модули (этапы) взаимодействуют между собой с помощью промежуточных файлов.

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

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

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

Среда ASMKOD генерирует файл ASK, представляющий собой программу на ассемблере.

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

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

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

2.2 Описание учебного языка

Учебный язык построен на основе языка Паскаль.

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

Буквы – это буквы латинского алфавита от а до я, от А до Я, от a до z и от A до Z. В данном языке нет различия между прописными и строчными буквами алфавита, если только они не входят в символьные и строковые выражения.

Цифры – арабские цифры от 0 до 9.

Специальные знаки учебного языка – это символы:

+  -  *  /  =  ,  .  :  ;  <  >  {  }  [  ]  (  )

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

<>  <=  >=  :=

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

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

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

and

begin

div

do

downto

else

end

for

function

if

integer

procedure

program

real

repeat

string

then

to

until

var

while

write

read

Их можно изменять при построении компилятора в соответствующей программной среде LEXAN.

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

Константы.

Последовательность, состоящая из одной или более цифр 0, 1, … , 9, является целой (INTEGER) константой. Данный тип занимает в памяти 2 байта. Последовательность цифр, разделенных точкой, является вещественной (REAL) константой, данный тип занимает в памяти 4 байта. Последовательность любых символов (кроме знака одинарных кавычек), заключенных в одинарные кавычки, является строковой (STRING) константой, длина данного типа варьируется от 1 до 255 байт, в зависимости от числа символов в последовательности.

Выражения.

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

Таблица 5 – Таблица приоритетов

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

Возможные для использования символы:

буквы: а..я, А..Я, a..z, A..Z;

символ, разрешенный при написании имен: _

элементы разделения: ,  ;  :  пробел         

разделитель целой и дробной частей в вещественных числах: .

выделение текста: ′

знаки операторов: + - * /

комментарии:  { }

расстановка приоритетов: ( )

знаки сравнения: > < =  >=  <=  <>

признак окончания программы: .

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

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

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

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

Лексический анализатор позволяет работать со следующими таблицами:

1)    таблица выбранных терминальных символов (формируется из таблицы терминальных символов);

2)    таблица символических имен (идентификаторов);

3)    таблица литералов (констант);

4)    таблица выходных кодов лексем.

Далее описываются структуры таблиц.

2.3.1 Таблица терминальных символов

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

Таблица 6 – Таблица выбранных терминальных символов

Таблица выбранных терминальных символов содержит следующие поля:

№ стр номер строки в таблице выбранных терминальных символов;

Терминальный символ – название терминального символа;

Комментарий описание терминального символа;

Код код терминального символа, определенный в таблице терминальных символов.

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

Некоторые терминальные символы можно изменять – это ключевые слова. Изменение возможно в момент заполнения таблицы выбранных терминальных символов.

2.3.2 Таблица символических имен

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

Таблица 7 Таблица символических имен

Таблица символических имен содержит следующие поля:

Специф спецификатор (номер строки) определяет положение идентификатора в таблице;

Идентификатор имя идентификатора, найденного в тексте программы;

Тип тип распознанного идентификатора (заполняется в программе LEXAN), поле остается не заполненным;

Размер в памяти – размер идентификатора, занимаемый в памяти, определяется в зависимости от типа (заполняется в программе LEXAN), поле остается не заполненным;

Относительный адрес в памяти – адрес относительно начала объявления переменных, формируется в зависимости от размера памяти предыдущих идентификаторов (заполняется в программе LEXAN), поле остается не заполненным.

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

2.3.3 Таблица литералов

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

Таблица 8 Таблица литералов

Таблица содержит следующие поля:

Специф спецификатор, определяет положение идентификатора в таблице;

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

Тип тип распознанного литерала;

Размер в памяти – размер литерала, занимаемый в памяти, определяется в зависимости от типа;

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

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

2.3.4 Работа сканера

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

2.3.5 Структура листинга

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

2.3.6 Структура выходного файла

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

Таблица 9 – Пример промежуточного файла

В качестве примера приводится пример разбора задания, описанного в приложении А.

2.3.7 Примерное задание для студента

Дана некоторая грамматика языка:

1.   <prog>            ::= PROGRAM <prog-name> VAR <dec-list> BEGIN <stmt-list> END.

2.   <prog-name>   ::= id

3.   <dec-list>         ::= <dec> | <dec-list> ; <dec>

4.   <dec>               ::= <id-list> : <type>

5.   <type>             ::= INTEGER

6.   <id-list>           ::= id | <id-list> , id

7.   <stmt-list>       ::= <stmt> | <stmt-list> ; <stmt>

8.   <stmt>             ::= <assign> | <for>

9.   <assign>          ::= id := <exp>

10.       <exp>                   ::= <term> | <exp> + <term> | <exp> - <term>

11.       <term>                 ::= id | int | ( <exp> )

12.       <for>          ::= FOR <index-exp> DO <body>

13.       <index-exp>         ::= id := <exp> TO <exp>

14.       <body>                ::= <stmt> | BEGIN <begin-list> END

Используя программу LEXAN произвести следующие действия:

1.   Заполнить таблицу терминальных символов (таблица 1);

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

3.   Заполнить таблицы:  – символьных имен (таблица 2);

–    литералов (таблица 3);

–    лексического анализа (выходных символов);

4.   Проверить правильность заполнения таблиц встроенным анализатором;

5.   При наличии ошибок исправить имеющиеся, и повторно обработать программой LEXAN;

6.   Получить листинг полученных результатов;

7.   Сохранить результат в файл.

Пример выполнения приведен в приложении А.

2.3.8 Описание работы лексического анализатора

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

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

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

-     Если считанный символ является цифрой, то далее происходит проверка, является ли следующий символ цифрой или точкой. Если полученная литера состоит из одних цифр, то полученное число целого (INTEGER) типа, если в литере есть точка, то число вещественного (REAL) типа.

-     Если считанный символ – одинарная кавычка, то текст, следующий за ней до следующей одинарной кавычки, будет являться строковой константой, а знаки кавычек будут определены как специальные символы.

-     Если считанный символ является знаком «{», то сам знак и следующие за ним символы до знака «}» включительно игнорируются, так как являются комментарием.

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

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

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

В порядке распознавания лексем происходит заполнение таблицы выходных кодов лексем. Если распознанная лексема является терминальным символом, то в ячейку, соответствующую номеру таблицы, заносится номер 1, если является идентификатором – номер 2, если литералом – 3. Спецификатор («код» для терминального символа) заносится в поле «Строка».

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

Имеется возможность получения листинга в отдельный файл с расширением LOG.

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

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

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

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

2.4.1 Таблица переходов

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

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

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

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

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

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

Таблица 10 – Таблица переходов

Продолжение таблицы 10

Страницы: 1, 2, 3, 4, 5