Реферат: Программно-методический комплекс для обучения процессу создания компиляторов
МИНИСТЕРСТВООБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ВОТКИНСКИЙ ФИЛИАЛ ИЖ Г Т У Кафедра Организации вычислительных процессов и систем управления
К защите допустить “____”_________ 2003 г
Зав. кафедрой ___________
дипломныйпроект/> <td/>Программно-методический комплекс для обучения процессу создания компиляторов
ТЕМА:
РАСЧЕТНО - ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
Выполнил студент группы Д – 1061 _________А.И. Кузнецов
Руководитель проекта ст. преподаватель _________
Консультант по профессор, д.т.н. _________
охране труда
Консультант по эко- доцент, к.т.н. _________
номической части
Председатель экс- ст. преподаватель _________
пертной комиссии
Воткинск 2003
Определения
В настоящемдипломном проекте применяются следующие термины с соответствующимиопределениями.
Ассемблер — программа, которая переводит исходную программу, написанную на автокоде или наязыке ассемблера (что, суть, одно и то же), в объектный (исполняемый) код.
БНФ(Бэкуса нормальная форма) – грамматика, состоящая из конечного множестваправил, определяющих в совокупности язык программирования.
Выражение– правила получения нового значения с помощью знаков операций и скобок, частнымслучаем выражения может быть просто одиночный элемент, т.е. константа илипеременная.
Идентификатор– имя переменной, процедуры, функции, программы.
Инструкция– синтаксическая структура, содержащая ключевые, шумовые слова и конструкции.Бывают простые и структурированные. Простые инструкции не содержат в себедругих вложенных инструкций (присваивание, GOTO).Структурированные инструкции могут содержать вложенные инструкции (IF <булево выражение> THEN <безусловныйоператор> ELSE <оператор>).
Компилятор– системная программа, выполняющая преобразование программы, написанной на одном алгоритмическом языке, в программу на языке, близком к машинному, и вопределенном смысле эквивалентную первой.
Лексема– единица программы, получающаяся в результате лексического анализа, например: for, i, 10, integer,+ и т. п.
Лексическийанализ – выделение в исходной программе элементарных составляющих:идентификаторов, ограничителей, символов операторов, чисел, ключевых слов, шумовыхслов, пробелов, комментариев и т. п.
Литера– любой символ, множество литер составляют лексему.
Литерал– численное или строковое значение, заданное один раз, и не изменяемое втечение программы.
Методоператорного предшествования – восходящий метод грамматическогоразбора, основан на анализе пар последовательно расположенных операторовисходной программы и решении вопроса о том, какой из них должен выполнятьсяпервым.
Нетерминальныйсимвол – имя конструкции, определенной внутри грамматики.
Рекурсивныйспуск – нисходящий метод грамматического разбора, основан на том, чтодля каждого нетерминального символа, определенного в грамматике, существуетотдельная процедура обработки. При этом в процессе своей работы она можетвызывать подобные процедуры
Семантикаязыка программирования — это смысл, который закладывается в каждую конструкциюязыка.
Семантическийанализ — это проверка смысловой правильности конструкции. Например,если мы в выражении используем переменную, то она должна быть определена ранеепо тексту программы, а из этого определения может быть получен ее тип. Исходяиз типа переменной, можно говорит о допустимости операции с данной переменной.
Семантическийанализ – в нем обрабатываются структуры, распознанные синтаксическиманализатором, и начинает обретать очертания выполняемый код.
Символьноеимя – одно из имен, разрешенных в языке, не являющееся терминальнымсимволом.
Синтаксисязыка программирования — это правила составления предложений языка из отдельныхслов. Такими предложениями являются операции, операторы, определения функций ипеременных. Особенностью синтаксиса является принцип вложенности(рекурсивность) правил построения предложений. Это значит, что элементсинтаксиса языка в своем определении прямо или косвенно в одной из его частейсодержит сам себя. Например, в определении оператора цикла телом цикла являетсяоператор, частным случаем которого является все тот же оператор цикла.
Синтаксическийанализ (грамматический разбор) – формирует синтаксическую единицу –выражение, инструкцию, вызов подпрограммы, декларацию, которые далееобрабатываются семантическим анализатором. Пример структуры: FOR<выражение> TO int DO <body>.
Синтаксическийразбор – процесс получения дерева синтаксического разбора на основезаданной грамматики.
Сканер(лексический анализатор) – программа распознавания лексем.
Спецификатор– порядковый номер в таблице, куда занесена лексема.
Терминальныйсимвол – конечный неделимый элемент конструкции языка, являетсязарезервированным словом (например READ, (, +).
Транслятор– это системная программа, выполняющая преобразование программы, написанной на одном алгоритмическом языке, в программу на другом алгоритмическом языке вопределенном смысле эквивалентную первой.
Содержание
Введение… 19
1 Анализ предметной области… 20
1.1 Компиляторы… 20
1.2 Логическая структура компилятора… 21
1.3 Лексический анализ. Сканер… 24
1.4 Синтаксический и семантический анализ… 28
1.5 Грамматики… 31
1.6 Формирование промежуточного кода… 34
Метод четверок… 36
1.7 Обоснование создания учебного комплекса… 37
1.8 Обзор существующих разработок… 38
1.9 Обоснование разработки… 39
2 Создание учебной разработки… 42
2.1 Краткое описание учебного компилятора… 42
2.2 Описание учебного языка… 43
2.3 Лексический анализатор LEXAN… 46
2.3.1 Таблица терминальных символов… 47
2.3.2 Таблица символических имен… 48
2.3.3 Таблица литералов… 49
2.3.4 Работа сканера… 50
2.3.5 Структура листинга… 50
2.3.6 Структура выходного файла… 50
2.3.7 Примерное задание для студента… 52
2.3.8 Описание работы лексического анализатора… 53
2.4 Синтаксический анализатор SinAn… 56
2.4.1 Таблица переходов… 56
2.4.2 Правила работы с таблицей переходов… 60
2.4.3 Правилатаблицы переходов для написания программы 62
2.4.4 Формируемая таблица переходов. Правила заполнения 65
2.4.5 Правила заполнения формируемой таблицы переходов 66
2.4.6 Построение деревьев… 81
2.4.7 Семантический анализ… 83
2.5 Формирование промежуточного кода… 85
Циклы… 85
3 Определение трудоемкости по стадиям разработки… 89
3.1 Методика расчета… 89
3.2 Определениезатрат на выполнение проекта по стадиям разработки 92
3.3 Расчет затрат на выполнение проекта по этапам… 94
4 Рекомендации по охране труда при работе с учебным комплексом. 95
Заключение… 97
Список использованных источников… 98
Приложения… 99
/>Введение
Каждыйпреподаватель вправе преподносить материал и обучать студентов по любой издисциплин так, как он считает нужным.
Преподавательжелает, чтобы знания по преподаваемым наукам лучше усваивались студентами.Часто материал не усваивается из-за того, что нет его наглядного представления,нет материалов, будь то программных или выполненных в виде плакатов, стендов,способствующих более глубокому пониманию.
Для того чтобысоздать демонстрационный вспомогательный материал следует наработатьнеобходимую базу. Что занимает много времени и требует определенных усилий ибольших временных затрат. В результате могут быть получены плакаты,методические пособия, программные средства (тестовые, обучающие) и др.Некоторые из них можно применять и в отсутствии преподавателя для самообучения,для контроля знаний и т. п.
Для проверки знаний часто используют тестовые системы, вкоторых проверка знаний происходит в интерактивном режиме. Некоторые из нихлишь выдают какой-то общий результат, другие определяют, где и на каком этапевозникла ошибка, и сообщают об этом пользователям (используется вкомпиляторах).
/>1Анализ предметной области/>1.1 Компиляторы
Транслятор- это программа, которая переводит исходную программу в эквивалентную ейобъектную программу. Если объектный язык представляет собой автокод илинекоторый машинный язык, то транслятор называется компилятором.
Автокодочень близок к машинному языку; большинство команд автокода — точноесимволическое представление команд машины.
Ассемблер- это программа, которая переводит исходную программу, написанную на автокодеили на языке ассемблера (что, суть, одно и то же), в объектный (исполняемый)код.
Компиляторы пишутся как наавтокоде, так и на языках высокого уровня. Кроме того, существуют и специальныеязыки конструирования компиляторов — компиляторы компиляторов.
Компиляторкомпиляторов (КК) – система, позволяющая генерировать компиляторы; на входесистемы — множество грамматик, а на выходе, в идеальном случае, — программа.Иногда под КК понимают язык программирования, в котором исходная программа — это описание компилятора некоторого языка, а объектная программа — самкомпилятор для этого языка. Исходная программа КК — это просто формализм,служащий для описания компиляторов, содержащий, явно или неявно, описаниелексического и синтаксического анализаторов, генератора кодов и других частейсоздаваемого компилятора. Обычно в КК используется реализация схемы т.н.синтаксически управляемого перевода. Кроме того, некоторые из них представляютсобой специальные языки высокого уровня, на которых удобно описывать алгоритмы,используемые при создании компиляторов.
/>1.2 Логическая структуракомпилятора
На рисунке 1 представленаструктурная схема компилятора.
/>
Рисунок 1 – Схема компилятора
Исходнаяпрограмма – текст программы на языке высокого уровня (например Паскаль),который должен быть переведен в машинный код.
Информационныетаблицы — самостоятельные структуры, заранее заполненные (таблицатерминальных символов), а также заполняющиеся в ходе лексического анализа идополняющиеся во время работы.
Лексическийанализатор выполняет распознавание лексем языка и замену их соответствующимикодами. Под лексемами понимаются элементарные единицы, входящие в структуру предложенияязыка, такие как ключевые слова, константы, имена и т.п. Правильность заданияструктуры предложения языка на фазе лексического анализа не выполняется. Результатомявляется поток лексем (кодов – ссылок на таблицы), эквивалентный исходномутексту.
Синтаксическийанализатор необходимдля того, чтобы выяснить, удовлетворяют ли предложения, из которых состоитисходная программа, правилам грамматики этого языка.
Семантическийанализ. На этомэтапе осуществляется контроль типа и вида всех идентификаторов и другихоперандов.
Генерацияпромежуточного кода. Происходит преобразование исходной программы впромежуточную (например, польскую) форму записи.
Оптимизацияпромежуточного кода– выделение общих подвыражений и вычисление константных подвыражений.
Фазаоптимизации предназначена для уменьшения избыточности программы по затратамвремени и памяти. В зависимости от критериев проектирования транслятораданная фаза обработки программы может исключаться из цикла обработкипрограммы.
Распределениепамяти. На этомэтапе выделяются конкретные адреса пользователя под переменные, которыегенерируются компилятором.
Генераторобъектного (ассемблерного) кода – выполняет подстановку кодовых образцов на выходном языке,соответствующих промежуточным кодам программы. Генератору кода могут нетребоваться шаблоны, он весь может быть реализован в процедурном виде.
Машинно-зависимаякомпиляция. Зависитот того, какие используются регистры. Работа этой процедуры зависит отсоглашений, принятых для исполняемой части программы. Например, выделяетсябазовый регистр для текущей активной записи в стеке.
Навсех этих этапах происходит работа с различного рода таблицами. В частности,для каждого блока (если таковые существуют в языке) идентификаторы, описанныевнутри, запоминаются вместе со своими атрибутами. Условно все эти этапы можноизобразить следующим образом:
/>
Рисунок 2 – Работа с таблицами
Очевидназависимость структуры компилятора от структуры ЭВМ, точнее, от имеющейсяпроизводительности системы. Например, при малой памяти увеличивается количествопроходов компиляции (т.н. многопроходные компиляторы), а при наличии памятибольшого объема можно все этапы компиляции произвести за один проход (и тогдамы имеем дело с однопроходным компилятором).
Далеемы рассмотрим некоторые из этих составных частей процесса компиляции.
/>1.3 Лексический анализ.СканерЛексическийанализатор представляет собой модуль разбора текста программы. Разборпроисходит в зависимости от имеющихся у него в памяти терминальных символов иправилами определения типов данных. Каждый язык имеет свои ограничения по типамданных, допущения и особенности создания (строения) конструкций, применениюоператоров и т.п. При работе сканера используются три таблицы: таблицатерминальных символов, таблица символических имен и таблица литералов – этозаполняемые таблицы. Таблица терминальных символов хранит все ключевые слова испециальные символы используемые в языке, а также коды, соответствующие каждомусимволу. Таблица символических имен заполняется в процессе разбора текстапрограммы и хранит в себе имена идентификаторов (символических имен). Таблицалитералов также заполняется в процессе разбора программы и хранит в себелитералы: численные и строковые значения, с указанием типов данных иотносительных адресов.
Распределение по таблицампроисходит следующим образом.
Сканерв процессе анализа текста программы выделяет один из элементов текста исравнивает с каждым терминальным символом. Если такой символ найден, то ввыходной код передаются код таблицы и спецификатор (номер строки в таблице). Вслучае если этот элемент не является терминальным символом проверяется,является ли он идентификатором (первый символ обычно буква, остальные могутбыть либо буквой, либо цифрой), если такой определен, то данный элементзаносится в таблицу символических имен, а к выходному коду добавляется парачисленных значений: номер таблицы и спецификатор найденного элемента. В случаеесли такой элемент в таблице уже имеется, то в выходной код заносится номертаблицы и его спецификатор. В таблицу литералов заносят численные, строковые ииные определенные языком значения. При этом распознается тип значения и тут жезаполняется относительная таблица адресов.
Выходнойкод, сформированный сканером, передается на следующую стадию обработки –синтаксический анализ.
Такимобразом, алгоритм работы простейшего сканера можно описать так:
· просматриваетсявходной поток символов программы на исходном языке до обнаружения очередногосимвола, ограничивающего лексему;
· для выбраннойчасти входного потока выполняется функция распознавания лексемы;
· при успешномраспознавании информация о выделенной лексеме заносится в таблицу лексем, иалгоритм возвращается к первому этапу;
· при неуспешномраспознавании выдается сообщение об ошибке, а дальнейшие действия зависят отреализации сканера — либо его выполнение прекращается, либо делается попыткараспознать следующую лексему (идет возврат к первому этапу алгоритма).
Работапрограммы-сканера продолжается до тех пор, пока не будут просмотрены всесимволы программы на исходном языке из входного потока.
Таблицатерминальных символов в простейшем случае может иметь следующий вид какпоказано в таблице 1.
Таблица 1 – Таблица терминальных символов
№ п.п. Терминальный символ Комментарий (обозначение) 1 PROGRAM Заголовок программы 2 VAR Описание переменных 3 BEGIN Начало тела программы 4 END Конец тела программы 5 INTEGER Целый тип данных 6 FOR Счетный оператор цикла (для) 7 TO Ключевое слово счетного оператора цикла (до) 8 DO Ключевое слово (выполнить)Продолжение таблицы 1
№ п.п. Терминальный символ Комментарий (обозначение) 9 WHILE Оператор цикла с предусловием (пока) 10 DIV Деление целочисленное 11 MOD Остаток от целочисленного деления 12 AND Логическое И 13 OR Логическое ИЛИ 14 := Присвоить значениеСначалазаполняется таблица лексем (терминальных символов), затем начинается считываниеи обработка входного текста программы пользователя. При работе сканерапроисходит заполнение таблиц символических имен и литералов.
Данныетаблицы могут выглядеть следующим образом:
Таблица 2 – Таблица символических имен
№ п.п. Идентификатор Тип Размер, занимаемый в памяти, байт Относительный адрес в памяти 1 I INTEGER 2 Y REAL 3 X1 REAL …Таблица 3 – Таблица литералов
№ п.п. Литерал Тип Размер, занимаемый в памяти, байт Относительный адрес в памяти 1 1 INTEGER 2 2 100 INTEGER 2 2 …Результатомработы сканера является последовательность кодов лексем. Каждый код лексемыобычно представляется кодом таблицы и спецификатором (порядковый номер втаблице, куда занесена лексема). Это позволяет избежать дополнительного поискапо таблицам на следующих этапах трансляции. Например в результате обработкисканером следующего предложения языка Паскаль
FOR I:=1 TO 100DO Y:=X1
будетполучена строка:
<1,06><2,1><1,14><3,1><1,07><3,2><1,08><2,2><1,14><2,3>,
гдев угловых скобках пара чисел задает код таблицы и спецификатор. Можно оформитьи в виде таблицы.
Таблица 4 – Таблица выходных символов
№ п.п. 1 2 3 4 5 6 7 8 9 10 Таблица 1 2 1 3 1 3 1 2 1 2 Строка 6 1 14 1 7 2 8 2 14 3Функционально всканере могут быть выделены следующие модули[4]:
1) выделение из входной строки очередного слова;
2) поиск в таблицах лексем и определение кода лексемы;
3) формирование и вывод выходной строки.
Для модулявыделения слова важна информация о том, какие символы могут быть признакаминачала или конца слова. Например, в языке Паскаль ключевые слова отделяются отдругих элементов предложения пробелами. Сложнее обстоит дело с выделениемидентификаторов и чисел, поскольку разделителем для них может служить любойдругой символ, не входящий по определению в идентификатор или число.
Призаполнении таблиц выполняется проверка на наличие в ней элемента, совпадающегос выделенным идентификатором или константой, и при совпадении занесение втаблицу не выполняется.
В задачипоследнего модуля входит занесение в выходную строку кодов лексем.
В дополнение ксвоей основной функции, распознаванию лексем, сканер обычно также выполняетчтение строк исходной программы и, возможно, печать листинга исходной программы.Комментарии игнорируются сканером, за исключением того случая, когда они должныбыть напечатаны и, таким образом, эффективно удаляются из исходной программыдо начала процесса грамматического разбора.
Следующейстадией анализа является синтаксический разбор.
Лексическийи синтаксический анализаторы взаимодействуют между собой. Существует дваосновных способа взаимодействия:
1) реализуется на основе прямоголексического анализа. От синтаксического анализатора поступает запрос «датьлексему» и указывается тип лексемы;
2) непрямой лексический анализ.Синтаксический анализатор выдает запрос «дать лексему», тип лексемы неуказывается. Нет решающего блока, считаем, что работает группа параллельныхавтоматов.
/>1.4 Синтаксический исемантический анализСинтаксическийанализ — это процесс, в котором исследуется цепочка лексем и устанавливается,удовлетворяет ли она структурным условиям, явно сформулированным в определениисинтаксиса языка. Это – самая сложная часть компилятора.
Синтаксическийанализатор расчленяет исходную программу на составные части, формирует еевнутреннее представление, заносит информацию в таблицу символов и другиетаблицы. При этом производится полный синтаксический и, по возможности,семантический контроль программы. Фактически, это — синтаксически управляемаяпрограмма. При этом обычно стремятся отделить синтаксис от семантики насколькоэто возможно — когда синтаксический анализатор распознает конструкцию исходногоязыка, он вызывает семантическую процедуру, которая контролирует эту конструкцию,заносит информацию куда надо, проверяет на дублирование описания переменных,проверяет соответствие типов и т.п.
Процесссинтаксического анализа может рассматриваться как построение дереваграмматического разбора для транслируемых предложений. Грамматики могутиспользоваться как для порождения так и для распознавания предложений языка.Порождение начинается с начального понятия (или аксиомы грамматики). Прираспознавании с помощью грамматических правил порождается предложение, котороезатем сравнивается с входной строкой. При этом применение правил подстановкидля порождения очередного символа предложения зависит от результатов сравненияпредыдущих символов с соответствующими символами входной строки. Результатанализа исходного предложения в терминах грамматических конструкций удобнопредставлять в виде дерева. Такие деревья обычно называются деревьямиграмматического разбора или синтаксическими деревьями. На рисунке 3изображено дерево грамматического разбора для предложения READ (VALUE).
/> <td/> />Рисунок 3 – Деревограмматического разбора
Методыграмматического разбора разбиваются на два больших класса восходящие и нисходящие– в соответствии с порядком построения дерева грамматического разбора. Нисходящие(методы сверху-вниз) начинаются с аксиомы грамматики, с корня дерева и пытаютсятак его наращивать, чтобы последующие узлы дерева соответствовали синтаксисуанализируемого выражения. Восходящие (методы снизу-вверх) начинают с элементовпредложения (с «листьев») и отыскивают в грамматике какому понятиюони соответствуют, т.е. определяют родительскую вершину для этих элементов, ит.д. пока не приходят к корню дерева (аксиоме грамматики). В современныхкомпиляторах применяются как нисходящие, так и восходящие методы.
Достоинствомвосходящего метода является его несомненная простота, а также высокая скоростьвыполнения (не тратится время на поиск правила редукции).
Однаковсе эти достоинства напрочь меркнут перед главным недостатком данного метода.Дело в том, что здесь практически отсутствует какая бы то ни была диагностика(и тем более — локализация) ошибок. Во вторых, некоторые ошибки в исходномвыражении не диагностируются вовсе. Например, выражения, в которых встречаютсяидущие подряд скобки “(” и “)”.
Поэтому придальнейшем рассмотрении будет рассматриваться нисходящий разбор, как наиболеепригодный метод при ручном написании компилятора [4].
Кроме этого,алгоритмы синтаксического (грамматического) разбора (контроля) делят насинтаксически-ориентированные и синтаксически-неориентированные.Синтаксически-ориентированные алгоритмы являются универсальными для некоторогосемейства языков и переход к распознаванию предложений другого языкавыполняется путем смены грамматики, т.е. грамматика выполняет роль некоей«программы» распознавания предложений языка. Главным достоинствомэтого класса алгоритмов является их универсальность, а недостатком — наличиеизбыточности вследствие ориентации на семейство языков.
Синтаксически-неоpиентиpованныеалгоритмы отличаются тем, что порядок действий в них определяется правиламиграмматики данного конкретного языка. Достоинством этого класса алгоритмовявляется отсутствие избыточности, а недостатком — невозможность перенастройкина распознавание предложений другого языка.
В дальнейшем мыбудем работать с синтаксически-неориентированными алгоритмами, т.к. будемработать лишь с одним языком – учебный язык на основе языка Паскаль.
/>1.5 ГрамматикиГрамматика языка программирования является формальнымописанием его синтаксиса или формы, в которой записаны отдельныепредложения программы или вся программа. Грамматика не описывает семантикуили значения различных предложений. Информация о семантике содержится впрограммах генерации объектного кода. В качестве иллюстрации разницы междусинтаксисом и семантикой рассмотрим два предложения:
I:=J+K
и
I:=X+Y
гдеХ и Y являются действительными переменными, a I, J, К — целыми переменными. Эти два предложения имеют одинаковыйсинтаксис. Оба являются операторами присваивания, в которых присваиваемоезначение определяется выражением, состоящим из двух имен переменных,разделенных оператором сложения. Однако семантика этих двух предложенийсовершенно различна. Первое предложение говорит о том, что переменные ввыражении должны быть сложены с использованием целых арифметических операций, арезультат сложения должен быть присвоен переменной I. Второе предложение задаетсложение с плавающей точкой, результат которого должен быть преобразован вцелое число перед присваиванием. Очевидно, эти два предложения будутскомпилированы в различные последовательности машинных команд, хотя ихграмматическое описание одинаково. Различия между ними проявятся на этапегенерации объектного кода.
На рисунке 4 показаны БНФ грамматики, используемые в дипломном проекте.Подчеркнутые волнистой линией элементы могут опускаться (не использоваться).
1. <prog> ::=PROGRAM <prog-name> VAR <dec-list> BEGIN <stmt-list>END.
2. <prog-name> ::= id ;
3. <dec-list> ::=<dec> {; <dec> } ;
4. <dec> ::=<id-list>: <type>
5. <type> ::=INTEGER | REAL | STRING
6. <id-list> ::=id {, id }
7. <stmt-list> ::=<stmt> { ; <stmt> } ;
8. <stmt> ::=<assign> | <for> | <read> | <write> | <while> |<repeat> | <if>
9. <assign> ::=id := <exp>
10. <exp> ::= – <term> { + <term> | – <term> }
11. <term> ::=<factor> { * <factor> | DIV <factor> | / <factor> }
12. <factor> ::=id | int | real | <text-val> | (<exp>)
13. <read> ::=READ ( <id-list> )
14. <write> ::=WRITE ( <value> {, <value>} )
15. <for> ::=FOR <index-exp> DO <body>
16. <index-exp> ::= id:= <exp> TO|DOWNTO <exp>
17. <body> ::=<stmt> | BEGIN <stmt-list> END
18. <value> ::=<id-list> | <text-val>
19. <text-val> ::=′ <text> ′
20. <text> ::=string
21. <if> ::=IF <сравнение> THEN <body> ELSE <body>
22. <сравнение>::= <factor> <условие> <factor>
23. <условие> ::=> | < | = | >= | <= | <>
24. <while> ::=WHILE <сравнение> DO <body>
25. <repeat> ::=REPEAT <body> UNTIL <сравнение>
Рисунок 4 – Упрощенная грамматика языка Паскаль
Существует несколько различных форм записи грамматик,среди которых мы рассмотрим форму Бекуса—Наура (БНФ). БНФ не самое мощное изизвестных средств описания синтаксиса. Однако эта форма достаточно проста,широко используется и предоставляет достаточные для большинства приложенийсредства. На рис.4 изображена одна из возможных грамматик БНФ.
Грамматика БНФ состоит из множества правил вывода, каждоеиз которых определяет синтаксис некоторой конструкции языка программирования.Рассмотрим, например, правило 13 на рис. 4:
<read> ::= READ ( <id-list> )
Это определениесинтаксиса предложения READ языка Паскаль, обозначенноев грамматике как <read>. Символ ::= можно читатькак «является по определению». С левой стороны от этого символа находитсяопределяемая конструкция языка (в нашем случае— <read>),а с правой—описание синтаксиса этой конструкции. Строки символов, заключенные вугловые скобки < и >, называются нетерминальными символами (т. е.являются именами конструкций, определенными внутри грамматики). То, что незаключено в угловые скобки, называется терминальными символамиграмматики (лексемами). В этом правиле вывода нетерминальными символамиявляются <read> и <id—list>. Терминальными символами являются лексемы READ, (, ). Таким образом, это правило определяет, чтоконструкция <read> состоит из лексемы READ, за которой следует лексема (, за ней следуетконструкция языка, называемая <id—list>,за которой следует лексема ). Пробелы при описании грамматических правил несущественны и вставляются только для наглядности.
Для распознавания нетерминального символа <read>необходимо чтобы было определение для нетерминального символа <id-list>. Это определение даетсяправилом 6 на рис. 4:
<id-list> ::= id{, id }
Этанотация, означает, что конструкция, заключенная в фигурные скобки, может бытьлибо опущена, либо повторяться один или более число раз. Таким образом, правило6 определяет нетерминальный символ <id-list> как состоящий из единственной лексемыid или же из произвольного числа следующих друг за другомлексемid, разделенных запятой. Всоответствии с этим новым определением процедура, соответствующаянетерминальному символу <id-list>,сначала ищет лексемуid, а затемпродолжает сканировать входной текст до тех пор, пока следующая пара лексем несовпадет с запятой иid. Такая записьустраняет проблему левой рекурсии.
/>1.6 Формированиепромежуточного кодаВозможныразличные формы внутреннего представления синтаксических конструкций исходнойпрограммы в компиляторе. Дерево грамматического разбора оказывается неудобным вработе при работе при генерации и оптимизации объектного кода. Поэтому передоптимизацией и непосредственно генерацией объектного кода внутреннеепредставление программы преобразуется в одну из соответствующих форм записи.
Примерами такихформ записи являются:
- обратная польская запись операций;
- тетрады операций;
- триады операций;
- собственно команды ассемблера.
Обратнаяпольская запись — это постфиксная запись операций. Преимуществом ее являетсято, что все операции записываются непосредственно в порядке их выполнения. Оначрезвычайно эффективна в тех случаях, когда для вычислений используется стек.
Тетрадыпредставляют собой запись операций в форме из четырех составляющих:
<операция>(<операнд1>,<операнд2>,<результат>).
Тетрадыиспользуются редко, так как требуют больше памяти для своего представления, чемтриады, не отражают взаимосвязи операций и, кроме того, плохо отображаются вкоманды ассемблера и машинные коды, так как в наборах команд большинствасовременных машин не встречаются операции с тремя операндами.
Триадыпредставляют собой запись операций в форме из трех составляющих:<операция>(<операнд1>,<операнд2>), при этом один или обаоперанда могут быть ссылками на другую триаду в том случае, если в качествеоперанда данной триады выступает результат выполнения другой триады. Поэтомутриады при записи последовательно номеруют для удобства указания ссылок однихтриад на другие. Например, выражение A := B*C + D — B*10, записанное в видетриад будет иметь вид:
1) * ( B, C )
2) + ( ^1, D )
3) * ( B, 10 )
4) — ( ^2, ^3 )
5) := ( A, ^4 )
Здесь операцииобозначены соответствующим знаком (при этом присвоение также являетсяоперацией), а знак ^ означает ссылку операнда одной триады на результат другой.
Командыассемблера удобны тем, что при их использовании внутреннее представлениепрограммы полностью соответствует объектному коду и сложные преобразования нетребуются. Однако использование команд ассемблера требует дополнительныхструктур для отображения их взаимосвязи. Кроме того, внутреннее представлениепрограммы получается зависимым от результирующего кода, а это значит, что приориентации компилятора на другой результирующий код потребуется перестраиватькак само внутреннее представление программы, так и методы его обработки валгоритмах оптимизации (при использовании триад или тетрад этого не требуется).
Для построениявнутреннего представления объектного кода (в дальнейшем — просто кода) подереву вывода может использоваться простейшая рекурсивная процедура. Этапроцедура прежде всего должна определить тип узла дерева — он соответствуеттипу операции, символ которой находится в листе дерева для текущего узла. Этотлист является средним листом узла дерева для бинарных операций и крайним левымлистом — для унарных операций. После определения типа процедура строит код дляузла дерева в соответствии с типом операции. Если все узлы следующего уровнядля текущего узла есть листья дерева, то в код включаются операнды,соответствующие этим листьям, и получившийся код становится результатомвыполнения процедуры. Иначе процедура должна рекурсивно вызвать сама себя длягенерации кода нижележащих узлов дерева и результат выполнения включить в свойпорожденный код.
Поэтому дляпостроения внутреннего представления объектного кода по дереву вывода в первуюочередь необходимо разработать формы представления объектного кода для четырехслучаев, соответствующих видам текущего узла дерева вывода:
оба нижележащихузла дерева — листья (терминальные символы грамматики);
только левыйнижележащий узел является листом дерева;
только правыйнижележащий узел является листом дерева:
оба нижележащихузла не являются листьями дерева.
/>МетодчетверокКаждая четверка записывается ввиде:
операция, 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Создание учебной разработки/>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.
Специальныезнаки учебного языка – это символы:
+ - * / = , . : ; < > { } [ ] ( )
К специальнымзнакам также относятся следующие пары символов:
<> <= >= :=
впрограмме эти символы нельзя разделять пробелами, если они используются какзнаки операций отношения.
Особое место валфавите языка занимают пробелы. Эти символы рассматриваются как ограничителиидентификаторов, констант, чисел, зарезервированных слов. Несколько следующихдруг за другом пробелов считаются одним пробелом.
В учебном языкеимеются следующие зарезервированные слова: