Лабораторная работа «Построение лексического анализатора»
В И Ш Н Я К О В Ю.М.
Б А Л А Б А Е В А И.Ю.
Проектирование
трансляторов
Руководство к циклу лабораторных работ по курсу
«Теория языков программирования и методы трансляции»
Таганрог 2008
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Технологический институт
Федерального государственного образовательного
учреждения высшего профессионального образования
“Южный федеральный университет”
ВИШНЯКОВ Ю.М.
БАЛАБАЕВА И.Ю.
Руководство к циклу лабораторных работ по курсу
«Теория языков программирования и методы трансляции»
Проектирование трансляторов
Для студентов направления «Информатика и вычислительная техника»
010503 «Математическое обеспечение и администрирование информационных систем» (специалитет),
230105 «Программное обеспечение вычислительной техники и автоматизированных систем» (специалитет),
230100 «Информатика и вычислительная техника» (бакалавриат)
Таганрог 2008
УДК 681.3×5 (075.8)
Рецензенты:
Вишняков Ю.М., Балабаева И.Ю. Проектирование трансляторов: Руководство к циклу лабораторных работ по курсу «Теория языков программирования и методы трансляции». – Таганрог: Изд-во ТТИ ЮФУ, 2008. – __с.
Руководство к циклу лабораторных работ охватывает все аспекты проектирования трансляторов языков программирования высокого уровня: лексический анализ, синтаксический анализ, преобразование исходной программы во внутреннее представление в виде обратной польской записи и генерация объектного кода программы из внутреннего представления.
Содержание цикла лабораторных работ основано на материалах, используемых авторами в учебном процессе ТТИ ЮФУ по курсу «Теория языков программирования и методы трансляции».
Пособие предназначено для студентов направления «Информатика и вычислительная техника»: специальностей 010503 «Математическое обеспечение и администрирование информационных систем», 230105 «Программное обеспечение вычислительной техники и автоматизированных систем» и бакалавриата по направлению 230100 «Информатика и вычислительная техника».
Библиогр.: _назв.
© Ю.М. Вишняков, И.Ю. Балабаева, 2008
© ТТИ ЮФУ, 2008
Оглавление
Введение. 7
1 Лабораторная работа «Построение лексического анализатора». 8
1.1 Основные понятия лексического анализа. 8
1.2 Лексемы простого PL-подобного языка программирования. 8
1.3 Функции и таблицы лексического анализа. 11
1.4 Диаграмма состояний лексического процессора. 15
2 Лабораторная работа «Перевод исходной программы в обратную польскую запись». 21
2.1 Понятие обратной польской записи. 21
2.2 Алгоритм Дейкстры.. 21
2.3 Перевод выражений, содержащих переменные с индексами, в ОПЗ. 23
2.4 Перевод в ОПЗ выражений, содержащих указатели функций. 26
2.5 Перевод условных выражений в ОПЗ. 29
2.6 Перевод оператора присваивания в ОПЗ. 31
2.7 Перевод оператора безусловного перехода и меток в ОПЗ. 33
2.8 Перевод условного оператора в ОПЗ. 36
2.9 Перевод описаний переменных и процедурных блоков в ОПЗ. 37
2.10 Комплексный пример перевода исходной программы в ОПЗ. 42
3 Лабораторная работа № 3 «Перевод ОПЗ исходного выражения в текст на выходном языке. Генерация машинного кода». 47
3.1 Базовые понятия. 47
3.2 Правила генерации машинного кода. 47
3.3 Комплексный пример перевода ОПЗ исходной программы в машинный код 50
4 Лабораторная работа № 4 «Построение синтаксического анализатора» 55
Варианты заданий. 66
Порядок выполнения лабораторных работ и требования к их оформлению 69
Приложение. Описание языков программирования, выбранных в качестве входных языков. 71
Введение
Цикл лабораторных работ призван закрепить теоретические знания по дисциплине «Теория языков программирования и методы трансляции» и способствовать выработке у студентов профессиональных компетенций в области разработки сложного и комплексного программного обеспечения, каким является транслятор (компилятор).
Цикл лабораторных работ построен таким образом, что охватывает все этапы проектирования трансляторов (лексический и синтаксический анализ, двухэтапную генерацию машинного кода). Поэтому при выполнении всего цикла работ в результате будет построен компилятор, а поскольку студент получает индивидуальный вариант задания, то у него появляется уникальная возможность проявить элементы инженерного творчества как в выборе программного инструментария, так и в самой технологии разработки.
Основные понятия лексического анализа
Лексический анализ всегда предшествует синтаксическому анализу и заключается в предварительной обработке программы и ее перекодировании к виду, удобному для синтаксического анализа. Лексический анализ принято отделять от синтаксического анализа для сокращения времени компиляции, поскольку синтаксис (морфология) слов всегда проще, чем синтаксис программ.
Лексический анализ сводится к разбиению текста программы на лексические единицы (слова, лексемы) – конструкции, которые выступают в качестве терминальных символов для синтаксического анализа. Лексемы еще иногда называют символами или атомами.
Большинство лексем в языках программирования можно сгруппировать в следующие классы:
- класс идентификаторов;
- класс служебных слов;
- класс констант (числовых или символьных);
- класс операций (одно-, дву- или многолитерных);
- класс разделителей (однолитерных или двулитерных).
В лексическом анализе лексема представляется в виде пары (класс, значение). Значение может быть непосредственным (литеральным) или представлять собой ссылку на некоторую таблицу, в которой хранятся значения лексем.
Тело процедуры
END;
4. Операторы:
– присваивания =;
– безусловного перехода имеет вид
GOTO Идентификатор;
– условный логический оператор
IF Условие THEN Оператор;
– оператор конца процедуры END;
5. Выражения:
– операции
сложения +;
умножения *;
отношений <,>, <>;
– скобки (,);
6. Константы:
– числовые (целые и вещественные с фиксированной точкой);
– символьные (произвольная последовательность символов, заключенная в апострофы);
7. Метки вида
Идентификатор: ;
8. Разделители:
пробел, конец строки, « , » « ; » « . »
9. Комментарии: произвольная последовательность символов от знака // до конца строки.
Построим таблицу классов лексем для рассматриваемого языка (табл. 1.1).
Таблица 1.1. Классы лексем подмножества языка PL/1.
| Типы лексем | Обозначение | |||
| Служебные слова | W | |||
| Идентификаторы | I | |||
| Операции | O | |||
| Разделители | R | |||
| Константы | N | |||
| C | ||||
Для оптимизации и ускорения поиска данных часто таблицу констант разделяют на две: таблицу N (для числовых констант) и таблицу С (для символьных констант).
Алгоритм Дейкстры
Исследованию формальных способов преобразования арифметических и логических выражений в ОПЗ посвящены многочисленные исследования, однако в практике системного программирования наибольшее распространение получили способы преобразования на основе алгоритма Дейкстры.
Суть алгоритма Дейкстры можно представить следующим рисунком:
Из этого рисунка следует, что на вход алгоритма посимвольно поступает исходное выражение. Операнды исходного выражения пропускаются на выход и формируют так же посимвольно выходную строку. Операции обрабатываются по определенным правилам на основе стека.
Для реализации такой обработки известное в системном программировании понятие стека используется также в алгоритме Дейкстры для размещения в нем операций. При этом предварительно каждой операции приписывается свой приоритет на основе таблицы приоритетов, которая приведена ниже (табл. 2.1).
Таблица 2.1
| Входной элемент | Приоритет |
| ( | |
| ) | |
| V | |
| & | |
| Отношения | |
| + - | |
| * / | |
| возведение в степень |
С учетом этой таблицы сформулируем правила работы со стеком.
Если рассматриваемый символ является операцией, то с ним производятся следующие действия путем сравнения его приоритета с приоритетом верхнего символа стека:
- Если стек пуст, операция заносится в стек.
- Если в стеке верхний элемент (операция) имеет более высокий приоритет, то рассматриваемая операция проталкивается в стек.
- Если в стеке верхний элемент (операция) имеет более низкий или равный приоритет, то из стека в выходную строку выталкиваются все элементы (операции) до тех пор, пока не встретится операция с приоритетом выше, чем у рассматриваемой операции, после чего операция из входной строки проталкивается в стек.
- Если входной символ "(", то он всегда проталкивается в стек. Если входной символ ")", то он выталкивает из стека все символы операций до ближайшей "(". Сами скобки взаимно уничтожаются и в выходную строку не попадают.
Приведем пример перевода выражения в ОПЗ:
| Выходная строка | a | b | + | - | < | c | - | q | + | = | & | |||||||
| С Т Е К | + | < | - | & | - | = | + | |||||||||||
| < | & | & | = | |||||||||||||||
| & | ||||||||||||||||||
| Входная строка | a | + | b | < | - | & | - | c | = | + | q | n |
Базовые понятия
Перевод ОПЗ в текст на выходном (машинном) языке представляет собой следующий этап трансляции исходной программы в машинные коды. Для реализации этой процедуры также используется автомат с магазинной памятью (МП-автомат).
Эту процедуру можно схематично представить следующим образом:
Чтение символов операций из ОПЗ инициирует семантические процедуры, которые генерируют соответствующие заготовки машинного кода. Так же обрабатываются собранные в стеке операнды данной. Например, в случае обработки переменных и констант извлекается соответствующая им информация из таблиц идентификаторов и констант, которая используется для образования правильных адресных частей соответствующих машинных команд.
Варианты заданий
Каждый вариант задания представляет собой пару: входной язык и машинный, или выходной, язык (см. табл. 5.1). В качестве входного языка предлагается один из языков программирования высокого уровня, в который должно быть обязательно включено следующее подмножество языковых конструкций и операторов:
- идентификаторы;
- числовые константы целого типа и вещественного типа, представленные с фиксированной и плавающей точкой;
- символьные (строковые) константы;
- переменные с индексами (массивы и элементы массивов);
- комментарии (строчные и блочные);
- имена функций пользователя;
- арифметические операции;
- операции сравнения (меньше, больше, равно, не равно, меньше или равно, больше или равно);
- операторы описания данных (идентификаторов и массивов);
- операторы описания процедур и функций (если предусмотрены в языке);
- операторы условного и безусловного перехода;
- метки (если предусмотрены в языке).
В качестве машинного языка предлагаются различные языки высокого уровня и язык Ассемблера (см. таблицу 5.1).
Таблица 5.1
| № варианта | Входной язык | Выходной язык |
| Паскаль | Си | |
| Бейсик | Си | |
| Perl | Си | |
| Фортран | Си | |
| JavaScript | Си | |
| Паскаль | Perl | |
| Бейсик | Perl | |
| Си | Perl | |
| Фортран | Perl | |
| JavaScript | Perl | |
| Паскаль | Фортран | |
| Бейсик | Фортран | |
| Perl | Фортран | |
| Си | Фортран | |
| JavaScript | Фортран | |
| Паскаль | Бейсик | |
| Си | Бейсик | |
| Perl | Бейсик | |
| Фортран | Бейсик | |
| JavaScript | Бейсик | |
| Паскаль | JavaScript | |
| Бейсик | JavaScript | |
| Perl | JavaScript | |
| Фортран | JavaScript | |
| Си | JavaScript | |
| Паскаль | Ассемблер | |
| Си | Ассемблер | |
| Бейсик | Ассемблер | |
| Perl | Ассемблер | |
| Фортран | Ассемблер | |
| JavaScript | Ассемблер | |
| Си | Паскаль | |
| Бейсик | Паскаль | |
| Perl | Паскаль | |
| Фортран | Паскаль | |
| JavaScript | Паскаль |
Приступая к выполнению лабораторных работ, студент должен внимательно ознакомиться со своим вариантом задания, сформировать согласованное с преподавателем подмножество конструкций выбранной версии входного языка и используемые инструментальные средства разработки.
Порядок выполнения лабораторных работ и требования к их оформлению
Цикл состоит из четырех лабораторных работ:
1. Построение программы лексического анализатора, корректно распознающего все перечисленные выше лексемы и формирующего таблицы лексем и внутреннее представление проанализированного текста.
На вход программы подается файл, содержащий тест на входном языке программирования. Результатом работы программы должен быть файл, содержащий последовательность кодов лексем входной программы, а также один или несколько файлов, содержащие все таблицы лексем.
Отчет по работе должен содержать описание правил записи перечисленных выше элементов заданного входного языка, стандартные таблицы лексем, диаграмма состояний сканера, листинг программы и комментарии к нему, пример лексического разбора.
2. Построение программы для перевода закодированного текста исходной программы в обратную польскую запись.
Программа получает на входе файл - результат лексического анализа и строит обратную польскую запись исходной программы.
Отчет по работе должен содержать полное описание алгоритма Дейкстра для конкретного языка: таблицу приоритетов операторов и операций, а также алгоритм работы со стеком. Листинг программы и комментарии к нему, пример.
3. Разработка программы для формирования по обратной польской записи текста на выходном (машинном) языке.
Программа получает на входе файл, содержащий ОПЗ исходной программы, и строит текст программы на машинном язык в соответствии с заданием.
Отчет по работе должен содержать описание правил записи перечисленных выше элементов заданного выходного языка, алгоритм работы МП-автомата и описание семантических процедур, листинг программы и комментарии к нему, пример.
4. Разработка программы синтаксического анализатора исходного текста.
Программа получает на входе файл - результат лексического анализа и выполняет синтаксический анализ исходной программы. Результатом работы должно быть сообщение о корректности программы или сообщение об первой обнаруженной ошибке с указанием строки и конструкции языка, при разборе которых обнаружена ошибка.
Отчет по работе должен содержать полную грамматику заданного подмножества входного языка, описание алгоритма синтаксического разбора, листинг программы и комментарии к нему, пример.
5. На рейтинговой неделе для получения допуска к экзамену студент должен представить единый отчет по циклу лабораторных работ, полную версию разработанного программного комплекса и продемонстрировать его работу преподавателю на примере.
Приложение. Описание языков программирования, выбранных в качестве входных языков
Идентификаторы
Произвольная последовательность букв и цифр, начинающаяся с буквы. Может включать символы подчеркивания.
Арифметические операции
Сложение +
Вычитание -
Умножение *
Деление /
Возведение в степень ^
Операции сравнения
Меньше <
Больше >
Равно =
Не равно <>
Меньше или равно <=
Больше или равно >=
Оператор присваивания
Имеет вид «:=». Слева стоит идентификатор или элемент массива, а справа – выражение. Заканчивается символом «;», например:
a:=b+с;
b[2,i-9]:=12;
Операторы блока
Begin – начало блока
…
End; - конец блока
Оператор описания программы
Программа начинается оператором Program с указанием имени программы. Затем могут идти описания даны, процедур и функций, а затем тело программы, заключенное в операторы блока, оканчивающееся точкой.
Program <идентификатор>;
…
Begin
…
End.
Операторы описания данных (идентификаторов и массивов)
Начинается оператором Var и может содержать несколько строк описаний, состоящих из перечисления идентификаторов через запятую и после двоеточия ключевое слово типа.
Var
A,b: real;
C: integer;
Типы переменных: integer (целый), real (вещественный), string (строковый)
Для массивов после двоеточия указывается ключевое слово массива «array of», в квадратных скобках через запятую перечисляются границы изменения каждого из индексов разделенные символами «..», и затем тип элементов:
Var
a,b,c : array of [1..3, 10..20] of integer;
Оператор условного перехода
Начинается с ключевого слова «if», имеет полный и неполный формат:
If <условие> then <оператор_1> else <оператор_2>;
If <условие> then <оператор_1>;
Язык программированияJava Script
(ECMA-262 - Netscape)
Идентификаторы
Произвольная последовательность букв и цифр, начинающаяся с буквы. Может включать символы подчеркивания.
Арифметические операции
Сложение +
Вычитание -
Умножение *
Деление /
Возведение в степень ^
Операции сравнения
Меньше <
Больше >
Равно ==
Не равно !=
Меньше или равно <=
Больше или равно >=
Оператор присваивания
Имеет вид «=». Слева стоит идентификатор или элемент массива, а справа – выражение. Заканчивается символом «;», например:
a=b+с;
b[2]=12;
Операторы блока
{ – начало блока
…
} - конец блока
Операторы описания данных (идентификаторов и массивов)
Начинается оператором Var и может содержать список идентификаторов через запятую. Типы отсутствуют.
var <имя переменной>;
var x,y,z;
Для одномерных массивов после идентификатора указывается ключевое слово массива « = new array» и в круглых скобках указывается количество элементов:
var <идентификатор> = new array(количество элементов)
var с = new array(100)
Многомерные массивы в языке JavaScript отсутствуют.
Операторы описания функций
Оператор условного перехода
Начинается с ключевого слова «if», имеет полный и неполный формат:
if (логическое выражение)
{
операторы
}
if (логическое выражение)
{
Операторы_1
}
else
{
Операторы_2
}
Язык программированияBasic
(Microsoft Turbo Basic)
Идентификаторы
Произвольная последовательность букв и цифр, начинающаяся с буквы. Последний символ имени определяет тип идентификатора:
a$ - символьный
a% - целый
a& - длинный целый
a! - вещественный обычной точности
а# - вещественный двойной точности
Арифметические операции
Сложение +
Вычитание -
Умножение *
Деление /
Возведение в степень ^
Операции сравнения
Меньше <
Больше >
Равно =
Не равно <>
Меньше или равно <=
Больше или равно >=
Оператор присваивания
Имеет вид «=». Слева стоит идентификатор или элемент массива, а справа – выражение. Заканчивается символом «;», например:
a%=b%+с%
b$(2,i-9)=”12”
Оператор останова
Прерывает выполнение программы:
STOP
Операторы описания массивов
Описание массивов осуществляется с помощью оператора DIM с указанием размеров. Например, оператор
DIM a(10), b(10:20, 25:45)
описывает одномерный массив a, элементы которого имеют индексы от 0 до 10, и двухмерный массив b, элементы которого имеют индексы :
первый от 10 до 20, второй от 25 до 45.
Если нижняя граница индексов в описании не указана, то она считается равной 0.
В описании массивавместо константы может использоваться переменная. Например,
DIM a(n)
Значение n должно быть предварительно определено.
Оператор условного перехода
Начинается с ключевого слова «if», имеет полный и неполный формат:
IF <условие> THEN <оператор1> [ELSE <оператор2>]
Например:
IF a < b THEN t=15 ELSE t=17
Если после THEN или после ELSE располагается целая группа операторов, то можно использовать IF блок, который имеет следующую структуру
IF <условие> THEN
<операторы1>
ELSE
<операторы2>
END IF
При этом ELSE и операторы за ним могут отсутствовать, т.е. возможна конструкция
IF <условие> THEN
<операторы>
END IF
Язык программированияС++
(ISO/IEC 14882)
Идентификаторы
Произвольная последовательность букв и цифр, начинающаяся с буквы. Может включать символы подчеркивания и начинаться с них.
Арифметические операции
Сложение +
Вычитание -
Умножение *
Деление /
Операции сравнения
Меньше <
Больше >
Равно ==
Не равно !=
Меньше или равно <=
Больше или равно >=
Оператор присваивания
Имеет вид «=». Слева стоит идентификатор или элемент массива, а справа – выражение. Заканчивается символом «;», например:
a=b+с;
b[2][i-9]=12;
Операторы блока
{ – начало блока
…
} - конец блока
Структура программы
Программа начинается операторами описания данных. Затем могут идти описания данных и функций, а затем основная функция программы void main () и ее тело, заключенное в операторы блока, оканчивающееся точкой.
Описания
void main()
{
…
}
Операторы описания данных (идентификаторов и массивов)
Начинается с ключевого слова типа и содержит перечисление идентификаторов через запятую. Оканчивается знаком «;»
<тип> <список элементов>;
Типы переменных: int (целый), float (вещественный), char (символьный)
Элементом списка может быть массив, для которого указывается идентификатор и размерности:
int a,b,c;
float d[3][4], c[78];
Операторы описания функций
Функции имеют заголовок вида
<тип> <идентификатор> (<список формальных параметров>);
и тело – список операторов, заключенный в операторы блока
{ … };
Например:
int abc (float r)
{
float r1,r2;
y:=sinr(r1)/cos(r2)*tan(r);
}
В теле функции может присутствовать оператор
return (<значение>);
Оператор условного перехода
Начинается с ключевого слова «if», имеет полный и неполный формат:
if (логическое выражение) оператор_1 else оператор_2;
if (логическое выражение) оператор_1;
Вместо отдельных операторов могут использоваться блоки операторов:
if (логическое выражение)
{операторы_1}
else
{операторы_2}
Язык программированияPerl
(5.003 for FreeBSD 2.1.0.)
Идентификаторы
Произвольная последовательность букв и цифр, начинающаяся со специального символа или буквы. Может включать символы подчеркивания и начинаться с них.
Специальный начальный символ определяет тип идентификатора:
Отсутствие символа означает, что идентификатор является именем процедуры
$ - идентификатор обозначает обычную переменную
@ - идентификатор является именем массива (структуры)
Обращения к подпрограммам
Идентификатор, следующий после знака «&», после которого в круглых скобках следует последовательность выражений-аргументов, разделенных запятыми. При отсутствии аргументов скобки не ставятся:
&F(12, 4, $i);
&f($av-6);
&g;
Арифметические операции
Сложение +
Вычитание -
Умножение *
Деление /
Возведение в степень **
Операции сравнения
Меньше <
Больше >
Равно ==
Не равно !=
Меньше или равно <=
Больше или равно >=
Оператор присваивания
Имеет вид «=». Слева стоит идентификатор или элемент массива, а справа – выражение. Заканчивается символом «;», например:
$a=$b+$с;
@b[i-9]=12;
Операторы блока
{ – начало блока
…
} - конец блока
Структура программы
Программа представляет собой произвольную последовательность операторов и подпрограмм.
Операторы описания данных (идентификаторов и массивов)
Операторы описания данных в языке отсутствуют.
Оператор условного перехода
Начинается с ключевого слова «if», имеет полный и неполный формат:
if (<логическое выражение>)
{
<оператор_1>;
}
else
{
<оператор_2>;
}
или
if (<логическое выражение>)
{
<оператор>;
}
Идентификаторы
Произвольная последовательность прописных букв и цифр, начинающаяся с буквы.
Арифметические операции
Сложение +
Вычитание -
Умножение *
Деление /
Возведение в степень **
Операции сравнения
Больше .GT.
Меньше .LT.
Больше равно .GE.
Меньше равно .LE.
Не равно .NE.
Равно .EQ.
Оператор присваивания
Имеет вид «=». Слева стоит идентификатор или элемент массива, а справа – выражение, например:
A=B+С
B(2,I-9)=12
Структура программы
Структура программ является строково-ориентированной. Так, 1-й символ строки служит для маркировки текста как комментария (символом C), с 1-го по 5-й символ располагается область меток, а с 7-го по 72-ой располагается собственно текст оператора или комментария. Колонки с 73-й по 80-ю транслятором игнорируются. Если текст оператора не вписывается в отведённое пространство (с 7-й по 72-ю колонку), в 6-ой колонке следующей строки ставится признак продолжения, и затем оператор продолжается на ней.
Располагать два или более оператора в одной строке нельзя.
Программа имеет заголовок вида
PROGRAM <ИМЯ ПРОГРАММЫ>
Затем следуют операторы описания данных, за ними – исполняемые операторы основной программы, оканчивающиеся операторами
STOP
END
После основной программы располагаются одна или несколько подпрограмм.
Операторы описания данных (идентификаторов и массивов)
Описание переменных с ключевого слова типа и содержит перечисление идентификаторов через запятую
<тип> <список элементов>
Типы переменных:
INTEGER (целый),
REAL (вещественный),
CHARACTER (символьный).
Например,
REAL A,B
Для описания массивов используется оператор DIMENSION, в котором указывается его имя и список размерностей в круглых скобках через запятую:
DIMENSION <имя массива> (размерность)
Например:
DIMENSION MASSIVE(A1,…,An)
Операторы описания функций
Функции имеют заголовок вида
<тип> FUNCTION <идентификатор>
PARAMETER <список формальных параметров>
и тело – список операторов, начинающийся операторами описания данных и оканчивающийся операторами
RETURN
END
Оператор условного перехода
Начинается с ключевого слова «IF», имеет только неполный формат:
IF (логическое выражение) оператор
Список литературы
Вишняков Юрий Муссович
Балабаева Ирина Юрьевна
Проектирование трансляторов
Руководство к циклу лабораторных работ по курсу
«Теория языков программирования и методы трансляции»
Ответственный за выпуск Балабаева И.Ю.
Редактор _________
Корректор __________
|
| ||||
«С»
Издательство Технологического института
Южного федерального университета
ГСП 17А, Таганрог, 28, Некрасовский, 44
Типография Таганрогского технологического института ЮФУ
Южного федерального университета
ГСП-17А, Таганрог, 28, Энгельса, 1
В И Ш Н Я К О В Ю.М.
Б А Л А Б А Е В А И.Ю.
Проектирование
трансляторов
Руководство к циклу лабораторных работ по курсу
«Теория языков программирования и методы трансляции»
Таганрог 2008
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Технологический институт
Федерального государственного образовательного
учреждения высшего профессионального образования
“Южный федеральный университет”
ВИШНЯКОВ Ю.М.
БАЛАБАЕВА И.Ю.
Руководство к циклу лабораторных работ по курсу
«Теория языков программирования и методы трансляции»
Проектирование трансляторов
Для студентов направления «Информатика и вычислительная техника»
010503 «Математическое обеспечение и администрирование информационных систем» (специалитет),
230105 «Программное обеспечение вычислительной техники и автоматизированных систем» (специалитет),
230100 «Информатика и вычислительная техника» (бакалавриат)
Таганрог 2008
УДК 681.3×5 (075.8)
Рецензенты:
Вишняков Ю.М., Балабаева И.Ю. Проектирование трансляторов: Руководство к циклу лабораторных работ по курсу «Теория языков программирования и методы трансляции». – Таганрог: Изд-во ТТИ ЮФУ, 2008. – __с.
Руководство к циклу лабораторных работ охватывает все аспекты проектирования трансляторов языков программирования высокого уровня: лексический анализ, синтаксический анализ, преобразование исходной программы во внутреннее представление в виде обратной польской записи и генерация объектного кода программы из внутреннего представления.
Содержание цикла лабораторных работ основано на материалах, используемых авторами в учебном процессе ТТИ ЮФУ по курсу «Теория языков программирования и методы трансляции».
Пособие предназначено для студентов направления «Информатика и вычислительная техника»: специальностей 010503 «Математическое обеспечение и администрирование информационных систем», 230105 «Программное обеспечение вычислительной техники и автоматизированных систем» и бакалавриата по направлению 230100 «Информатика и вычислительная техника».
Библиогр.: _назв.
© Ю.М. Вишняков, И.Ю. Балабаева, 2008
© ТТИ ЮФУ, 2008
Оглавление
Введение. 7
1 Лабораторная работа «Построение лексического анализатора». 8
1.1 Основные понятия лексического анализа. 8
1.2 Лексемы простого PL-подобного языка программирования. 8
1.3 Функции и таблицы лексического анализа. 11
1.4 Диаграмма состояний лексического процессора. 15
2 Лабораторная работа «Перевод исходной программы в обратную польскую запись». 21
2.1 Понятие обратной польской записи. 21
2.2 Алгоритм Дейкстры.. 21
2.3 Перевод выражений, содержащих переменные с индексами, в ОПЗ. 23
2.4 Перевод в ОПЗ выражений, содержащих указатели функций. 26
2.5 Перевод условных выражений в ОПЗ. 29
2.6 Перевод оператора присваивания в ОПЗ. 31
2.7 Перевод оператора безусловного перехода и меток в ОПЗ. 33
2.8 Перевод условного оператора в ОПЗ. 36
2.9 Перевод описаний переменных и процедурных блоков в ОПЗ. 37
2.10 Комплексный пример перевода исходной программы в ОПЗ. 42
3 Лабораторная работа № 3 «Перевод ОПЗ исходного выражения в текст на выходном языке. Генерация машинного кода». 47
3.1 Базовые понятия. 47
3.2 Правила генерации машинного кода. 47
3.3 Комплексный пример перевода ОПЗ исходной программы в машинный код 50
4 Лабораторная работа № 4 «Построение синтаксического анализатора» 55
Варианты заданий. 66
Порядок выполнения лабораторных работ и требования к их оформлению 69
Приложение. Описание языков программирования, выбранных в качестве входных языков. 71
Введение
Цикл лабораторных работ призван закрепить теоретические знания по дисциплине «Теория языков программирования и методы трансляции» и способствовать выработке у студентов профессиональных компетенций в области разработки сложного и комплексного программного обеспечения, каким является транслятор (компилятор).
Цикл лабораторных работ построен таким образом, что охватывает все этапы проектирования трансляторов (лексический и синтаксический анализ, двухэтапную генерацию машинного кода). Поэтому при выполнении всего цикла работ в результате будет построен компилятор, а поскольку студент получает индивидуальный вариант задания, то у него появляется уникальная возможность проявить элементы инженерного творчества как в выборе программного инструментария, так и в самой технологии разработки.
Лабораторная работа «Построение лексического анализатора»
Основные понятия лексического анализа
Лексический анализ всегда предшествует синтаксическому анализу и заключается в предварительной обработке программы и ее перекодировании к виду, удобному для синтаксического анализа. Лексический анализ принято отделять от синтаксического анализа для сокращения времени компиляции, поскольку синтаксис (морфология) слов всегда проще, чем синтаксис