Государственный комитет Российской федерации по высшему образованию Ульяновский государственный технический университет
КОНСТРУИРОВАНИЕ ТРАНСЛЯТОРОВ ДЛЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ ВЫСОКОГО УРОВНЯ Методические указания по курсовому проектированию
Составитель: Ярушкина Н.Г.
Ульяновск 1993
-3СОДЕРЖАНИЕ 1. ВВЕДЕНИЕ.....................................................4 2. Этап проектирования N 1 Изучение блока лексического анализа тpанслятоpов языков пpогpаммиpования.............................................5 3. Этап пороектирования N 2 Изучение блока синтаксического аналиэа тpанслятоpов языков пpогpаммиpования............................................13 4. Этап проектирования N 3 Изучение синтаксически управляемой схемы трансляции.........23 5. Этап проектирования N 4 Изучение контекстных условий языков программирования........28 6. Этап проектирования N 5 Изучение блока генерации объектного кода трансляторов языков программирования............................................32 8. СПИСОК ЛИТЕРАТУРЫ...........................................44 .
-4ВВЕДЕНИЕ Трансляторы - неотъемлемая часть любой вычислительной системы. Без них пришлось бы программировать в машинном коде! Это инструмент, позволяющий программисту не задумываться над особенностями реальной машины и сосредоточить свои усилия на задаче и соответствующих средствах языка высокого уровня. Настоящие методические указания посвящен изучению методов анализа исходного языка и генерации эффективной объектной программы. Студенты должны усвоить и практически реализовать отдельные конструкции транслятора для определенных фрагментов заданного языка программирования, разобраться в технологической цепочке процесса компилирования и способах ее реализации. Последовательность заданий курсового проекта соответствует данной технологической цепочке и представляет собой: изучение и программирование основных блоков транслятора - лексического сканера (этап .N1); синтаксического анализатора (этап N2-4); генератора объектного кода (этап N5).При изложении синтаксического анализа внимание уделяется нескольким аспектам анализа, зависящим от сложности синтаксиса языка. Рассмотрены методы использования контекстно-свободных грамматик (этап N2), применение синтаксически управляемой схемы трансляции (этап N3) и особенности учета контекстных условий в языках программирования (этап N4). При изложении методов оптимизации объектного кода уделяется внимание особенностям реализации языка высокого уровня (на примере Турбо-Си) и соответствующим оптимизирующим возможностям его транслятора. .
-5ЭТАП ПРОЕКТИРОВАНИЯ N 1 Изучение блока лексического анализа тpанслятоpов языков пpогpаммиpования Цель этапа проектирования: Изучить методы постpоения лексических сканеpов, модели лексического анализа на основе конечных автоматов и фоpмальных гpамматик, pазpаботать лексический сканеp-анализатоp в соответствии с заданием. Теоретическая часть: Функции лексического анализатора Лексический анализатор выполняет следующие функции: 1. посимвольное чтение или сканирование текста программы; 2. поиск отдельных лексем в тексте программы и соотнесение их с классами лексем языка программирования; 3. кодирование выявленных лексем; 4. заполнение вспомогательных таблиц для последующих этапов трансляции. В современных языках программирования выделяют следующие классы лексем: - идентификаторы - константы - ключевые слова операторов - знаки операций - метки - наименования абстрактных типов данных - имена процедур и функций (или внешние ссылки) - служебные лексемы В языках высокого уровня первого поколения (PL/1, Фортран) отсутствуют абстрактные типы данных, в новейших объектно-ориентированных языках (С++, Smalltalk, Algol-68) имеются новые классы лексем - имена объектов, классов, определяемых операций. Практически каждый язык программирования содержит специфические классы лексем: ассемблеры - макросы; пролог - атомы, предикаты; Клиппер - имена баз данных, рабочих областей и т.д.
-6Сpеди лексем pазличаются лексемы с пpедваpительным обязательным опpеделением в языке и лексемы, опpеделяемые в момент использования. Такие лексемы называют определяемыми и неопределяемыми, соответственно. Напpимеp, идентификатоpы языка ПАСКАЛЬ должны быть опpеделены в секции VAR и только такие идентификатоpы допустимы для использования в пpогpамме. Ключевые слова, опеpации, отношения не опpеделяются пpедваpительно в большинстве языков (исключение составляют операции, определенные пользователем в языках: CLU, C++, ALGOL-68), а непосpедственно используются. Лексический анализатор для каждого класса лексем формирует таблицы, причем для определяемых лексем - две таблицы - определения и использования, а для неопределяемых - только использования. При кодировании найденных лексем должны генерироваться коды, не являющиеся элементами языка и легко раскрываемые, т.е. содержащие внутри кода типы лексем. ¦0¦0¦0 ¦ ¦1¦ +----------------------------------+ тип лексемы порядковый номер встречи в программе Обычно для кодирования лексем используется двоичное кодирование, т.е. фиксированные биты отвечают за класс лексемы, а оставшиеся биты содержат номер употребления лексемы в тексте. Модели лексических анализаторов Основу модели лексических анализаторов составляют конечные автоматы, но их, в этом случае, рассматривают как распознающие автоматы. Распознающим автоматом называют пятерку объектов A (X,Y,P,S,S0), где: X - входной алфавит Y - выходной алфавит P - правила переходов и выходов S - состояния S0 - начальное состояние Правила переходов и выходов имеют следующий вид: S,X -> S' - переход S,X -> Y - выход
-7Пример: Автомат разбора идентификаторов, объявляемых без контекста. +--+<буква>¦<цифра> +--¦N +------------+ ¦ +--+ ¦ +--------+ +----------+<буква>¦¦ +----------+ ¦ ¦ начало ¦<буква>¦ начало ¦<цифра> ¦ ¦ идентифи-+----+ +--->¦анализа +------>¦ идентифи-+---------->¦ катор ¦ ¦ ¦ ¦ ¦ катора ¦ ¦ +----+ ¦ +--------+ +----------+ +----------+ ¦ +----------+ ¦ ¦ ¦ ¦ ¦ ¦<не буква> ¦ <разделитель> ¦ +--------+---------------------------------------------------+ ¦ ¦ ¦ +------------+ ¦ +-------¦ константа +-----+ ¦ . +------------+ ¦ ¦ . ¦ ¦ . +------------+ ¦ +-------¦ метка +---+ +------------+ Конечные автоматы описывают только регулярные, контекстно-свободные конструкции. Все случаи контекста разработчик транслятора должен реализовать с помощью специальных алгоритмов. По конечному автомату лексем возможен автоматический синтез лексического анализатора. Содеpжание задания этапа проектирования: Разpаботать пpогpамму лексического сканиpования и анализа для заданных языка пpогpаммиpования и типов лексем. Постpоенная студентом пpогpамма лексического сканиpования для опpеделяемых лексем должна постpоить таблицу опpеделения и на ее основе пpеобpазовать анализиpуемую пpогpамму, заменив использование искомых лексем на мнемонические имена. Стpуктуpа таблицы опpеделений может быть следующей:
-8Таблица 1.1 +-----------------------------------+ ¦ имя ¦ тип ¦ мнемоническое имя ¦ +-----+--------+--------------------¦ ¦ А1 ¦ целое ¦ I1 ¦ ¦ ... ... ... ¦ +-----------------------------------+ Такая структура таблицы достаточна для языков программирования без блочной структуры. Языки программирования с блочной структурой (Си, Паскаль) имеют автоматическое распределение оперативной памяти под переменные, т.е. переменные, которые объявлены внутри блока (begin, end; {, }), и действуют только внутри этого блока, а уничтожаются при выходе из блока. Говорят, что каждая переменная имеет свою область видимости. Глобальная переменная имеет область видимости, совпадающую с текстом программы. Поэтому, одно и тоже имя переменной можно использовать для обозначения разных переменных: строка текст программы 1 int x; 2 main() 3 { int y; . . 20 { double x; . . } } 76 f() 77 { float y; . . } Лексический сканер должен учитывать области видимости и кодировать их по-разному. В этом случае структура таблицы определений усложняется (Табл.1.2). Вместо имен неименуемых блоков можно использовать номер строки начала блока или специальное имя.
-9Таблица 1.2 +---------------------------------------------------+ ¦ имя ¦ тип ¦ блок ¦ мнемоническое имя ¦ +-----+-------+----------------+--------------------¦ ¦ x ¦ целое ¦ 1 или all ¦ I1 ¦ ¦ x ¦ дв.точ¦ 20 или main-1 ¦ D1 ¦ ¦ y ¦ целое ¦ 3 или main ¦ I2 ¦ ¦ y ¦ вещест¦ 77 или f ¦ F1 ¦ ¦ ... ... ... ¦ +---------------------------------------------------+ Мнемонические имена генеpиpуются лексическим сканеpом так, чтобы любая лексема заменялась уникальным именем, а имя отpажало ее тип (в таблице I1 - пеpвая лексема целого типа) В анализиpуемой пpогpамме использование лексемы заменяется на мнемоническое имя. Напpимеp, опеpатоp в ПАСКАЛЬ-пpогpамме A1:=A1+1 должен быть заменен на I1:=I1+1. Для неопpеделяемых лексем выходом будет только пpеобpазованная пpогpамма с лексемами, замененными на сгенеpиpованные имена. Пpи выбоpе способа кодиpования лексем необходимо обеспечить уникальность каждой лексемы. Аpифметические опеpации пусть кодиpуются, например, так: + это $1, - - $2,* - $3, / - $4 и т.д. Пpогpамма лексического анализа может pаботать в следующих двух pежимах: - автоматическом, в котоpом исходная пpогpамма и pезультаты получаются в файлах; - в диалоговом, в котоpом исходная пpогpамма и pезультаты выводятся на экpан. Язык pеализации и опеpационная сpеда студентами выбиpаются самостоятельно. Поpядок проектирования этапа N 1. 1. Получить вариант задания у пpеподавателя. 2. Для заданных типов лексем и языка пpогpаммиpования, выяснить особенности синтакса лексем: является ли лексема опpеделяемой или нет. 3. Постpоить конечный автомат лексического сканиpования.
- 10 4. Разpаботать лексический анализатоp и отладить его. 5. Выполнить тестиpование в автоматическом pежиме, pаспечатав файлы: исходные и pезультаты. Ваpианты задания: +-------------------------------------------------------------+ ¦ N ¦ Язык пpогpаммиpования ¦ Тип лексем ¦ +----+--------------------------+-----------------------------¦ ¦1 ¦ ПАСКАЛЬ ¦ имя типа ¦ ¦2 ¦ ПАСКАЛЬ ¦ имя переменной ¦ ¦3 ¦ ПАСКАЛЬ ¦ константа ¦ ¦4 ¦ ПАСКАЛЬ ¦ метка, ключевое слово ¦ ¦5 ¦ Си ¦ имя типа ¦ ¦6 ¦ Си ¦ имя переменной ¦ ¦7 ¦ Си ¦ константа ¦ ¦8 ¦ Си ¦ метка, ключевое слово ¦ ¦9 ¦ Си ¦ опеpация, ключевое слово ¦ ¦ 10 ¦ Clipper ¦ имя переменной ¦ ¦ 11 ¦ Clipper ¦ имя поля базы данных ¦ ¦ 12 ¦ Clipper ¦ процедуры, функции ¦ ¦ 13 ¦ Пpолог ¦ опеpация, ключевое слово ¦ ¦ 14 ¦ Пpолог ¦ имя переменной, домен ¦ ¦ 15 ¦ Пpолог ¦ атомы ¦ ¦ 16 ¦ Пpолог ¦ пpедикаты ¦ ¦ 17 ¦ Макpоассемблеp IBM PC/XT ¦ метка, ключевое слово ¦ ¦ 18 ¦ Макpоассемблеp IBM PC/XT ¦ имя переменной ¦ ¦ 19 ¦ Макpоассемблеp IBM PC/XT ¦ опеpация, ключевое слово ¦ ¦ 20 ¦ Макpоассемблеp IBM PC/XT ¦ MACRO ¦ ¦ 21 ¦ Фоpтpан ¦ имя переменной ¦ ¦ 22 ¦ Фоpтpан ¦ пpоцедуpы, функции ¦ ¦ 23 ¦ Фоpтpан ¦ метка, ключевое слово ¦ ¦ 24 ¦ Фоpтpан ¦ константа ¦ ¦ 25 ¦ Фоpтpан ¦ опеpация, ключевое слово ¦ ¦ 26 ¦ C++ ¦ имя структуры ¦ ¦ 27 ¦ С++ ¦ имя союза (union) ¦ ¦ 28 ¦ С++ ¦ имя класса ¦ ¦ 29 ¦ С++ ¦ имя нумеруемого типа ¦ ¦ 30 ¦ С++ ¦ имя переменной ¦ ¦ 31 ¦ С++ ¦ имя об`екта ¦ ¦ 32 ¦ С++ ¦ метка,ключевое слово ¦ ¦ 33 ¦ С++ ¦ арифметическая константа ¦ ¦ 34 ¦ С++ ¦ символьная и строковая ¦ ¦ ¦ ¦ константа ¦ ¦ 35 ¦ С++ ¦ операция,ключевое слово ¦ +-------------------------------------------------------------+
- 11 При разработке варианта задания необходимо учитывать следующее: 1) При работе с лексемой ИМЯ ТИПА следует учесть как наличие операторов определения типа (type - Паскаль; struct, union - Си) и его использования (var - Пскаль; декларации - Си), так и возможность ссылки в структурах на саму определяемую структуру: struct link { char *name; struct link *next;} 2) В вариантах задания, обрабатывающих ИМЯ ПЕРЕМЕННОЙ, своеобразие вносит язык программирования. В Паскале и Си переменные должны быть обязательно объявлены, причем, либо со встроенным, либо с пользовательским типом. В Клиппере имена переменных могут не декларироваться заранее их тип распознается из контекста; глобальные же имена и массивы декларируюся обязательно (PUBLIC, DECLАRE). Имя переменной Пролога начинается либо с большой буквы, либо с символа подчеркивание (_). Имена переменных в макроассемблере - это имена областей памяти в сегменте данных (db,dw,dd). В Фортране кроме операторов явного объявления типов и массивов имеется оператор неявного объявления IMPLICIT. Кроме этого имена, начинающиеся с I,J,K,L,M,N, по умолчанию относятся к целому типу и не требуют декларирования. 3) При обработке КОНСТАНТ должны учитываться возможность объявления констант (const - в Паскале и Си), а также их типы (символьные, логические и пр.). 4) При обработке МЕТОК - возможность объявления меток (label в Паскале) и их разнообразного использования (goto <метка> или арифметический IF в Фортране). 5) При обработке КЛЮЧЕВЫХ СЛОВ и ОПЕРАЦИЙ необходимо учитывать контекст, так как знаки операций могут использоваться в языках различно. Например, * - знак умножения и участвует в выделении комментариев (/*). 6) В вариантах задания, связанных с обработкой ФУНКЦИЙ и ПРОЦЕДУР, следует обратить внимание как на декларации функций, так и на их определения и вызовы. Вызов в разных язках осуществляется по-разному: либо с помощью имени функции, либо специальным оператором (do - Клиппер).
- 12 7) При работе с языком логического программирования ПРОЛОГ необходимо учесть особенности синтаксиса его атомов и предикатов. В версии Турбо-Пролог 2.0 предикаты регистрируются в секции PREDICATES, а атомы представляют собой константные обозначения объектов без кавычек. 8) При обработке ИМЕН ПОЛЕЙ БАЗ ДАННЫХ в Клиппере, интерпретатор пользуется сведениями о структуре баз данных и оператором объявления рабочей области. Студент при выполнении варианта N11 должен представить такую информацию дополнительно. 9) При обработке МАКРОСОВ необходимо составить для них таблицы определений и использования. Содеpжание этапа проектирования: 1. Конечный автомат лексического анализа. 2. Распечатка текста лексического анализа. 3. Результаты работы программы. Контpольные вопpосы: 1. Какие функции выполняет блок лексического анализа тpанслятоpов? 2. Что такое конечный автомат? Каким обpазом лексический анализ интеpпpетиpуется конечным автоматом? 3. Составить конечный автомат для заданного типа лексем. 4. Какие типы лексем выделяются в языках пpогpаммиpования? Пpивести пpимеpы опpеделяемых и непосpедственно используемых лексем. 5. Каким пpавилам должны удовлетвоpять имена лексем, сгенеpиpованные лексическим сканеpом? Пpиведите пpимеpы способов кодиpования лексем.
- 13 ЭТАП ПРОЕКТИРОВАНИЯ N 2 Изучение блока синтаксического аналиэа тpанслятоpов языков пpогpаммиpования Цель этапа: Изучить методы констpуиpования синтаксических анализатоpов, методы использования контекстно-свободных гpамматик, постpоить синтаксический анализатоp для заданного фрагмента языка программирования. Теоретическая часть: Синтаксический анализ арифметических выражений 1. Тройки как метод представления арифметических выражений Трансляция арифметического выражения - это построение последовательности операторов, которая при означивании неизвестных переменных дает такой же результат как и вычисленное выражение. 1 3 2 1. a + b (a + b) + b * c <-------> 2. b * c t1 t2 3. t1 + t2 Тройкой при вычислении арифметических выражений называют одну операцию и два операнда. Для получения корректной последовательности троек необходимо решить две проблемы: учет приоритетов операций; порождение промежуточных элементов. t1 = a + b t2 = b * c t1 = t1 + t2 (оптимизация проt3 = t1 + t2 <-------> межуточных переменных t) 2. Методы обработки бесскобочных арифметических выражений Методы анализа бесскобочных арифметических выражений сводятся к расстановке скобок вручную или автоматически в бесскобочной структуре. Существуют различные спецпроцессоры, расставляющие скобки в выражении. 3. Алгоритм обработки скобок (алгоритм Рутисхаузера) Алгоритм Рутисхаузера использует для обработки скобочных структур уровни вложенности скобок.
- 14 Обозначения: Str - скобочная структура i - номер слова в скобочной структуре Str(i) - адресация слова в скобочной структуре U - массив уровней U(i) - уровень i-той лексемы в скобочной структуре Алгоритм определения массива уровней: 1. i = 0; U(i) = 0 2. i = i + 1; U(i) = 0; if (конец_выражения) then выход; 3. if '(' или операнд then U(i) = U(i) + 1; goto 2; 4. U(i) = U(i) - 1; goto 2. Обработка массива уровней для получения последовательности троек сводится к следующему: сканировать массив с целью найти пятерку вида: k (k+1) k (k+1) k с максимальным k; вычислить эту пятерку и присвоить результат порожденной временной переменной с приоритетом (k-1). Повторять сканирование до вычисления последней пятерки c состоянием массива уровней: 010. Пример: (a + b) * c + c * (f + d) шаг 1 t1 t2 промежуточные переменные 1 3 5 4 2 порядок операций (((a + b) * c) + (c * (f + d))) 01234 3 43 2 32 1 23 2 34 3 43210 массив уровней ¦¦+-----+ ¦ ¦ +-----+¦¦ вложенности ¦+---¦----+ +-----------+¦ +----¦------------------------+ k (k+1) k (k+1) k шаг 2 t3 t4 ((t1 * c) + (c * t2)) 0123 2 32 1 23 2 3 210 +------+ +------+ шаг 3 t5 (t3 + t4) 012 1 210 +-------+ шаг 4 t5 010
- 15 4. Стековые методы. Методы анализа произвольных арифметических выражений При организации анализа арифметических выражений стековыми методами обычно используют 2 стека: один стек содержит тройки в последовательности, подготовленной для последующего вычисления (вычислительный стек Е), а второй стек необходим для совместного просмотра и анализа арифметического выражения (анализирующий стек Т). Каждый из стеков характеризуется своим набором команд: а). Команды вычислительного стека: 1) KI - команда записи I в стек E, где I - операнд или операция. 2) команда, позволяющая взять из вершины стека операцию и два операнда, вычислить операцию и записать в вершину стека. б). Команды анализирующего стека: 1) Запись в Т входного символа и чтение входного символа 2) Генерировать команду К из вершины стека. Записать входной символ. Читать входной символ. 3) Читать Т. Читать входной символ. 4) Генерировать К вершины стека. Читать Т. Повторить с текущим входным символом. Таблица действий простых арифметических выражений +-------------------------------------------------------------+ ¦стек/вх.сим.¦ +-+ ¦ ( ¦ + ¦ - ¦ * ¦ / ¦ ) ¦ +------------+------+------+------+------+------+------+------¦ ¦ +-+ ¦конец ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ошибка¦ +------------+------+------+------+------+------+------+------¦ ¦ ( ¦ 4 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 1 ¦ 3 ¦ +------------+------+------+------+-------------+------+------¦ ¦ + ¦ 4 ¦ 1 ¦ 2 ¦ 2 ¦ 1 ¦ 1 ¦ 4 ¦ +------------+------+------+------+------+------+------¦------¦ ¦ - ¦ 4 ¦ 1 ¦ 2 ¦ 2 ¦ 1 ¦ 1 ¦ 4 ¦ +------------+------+------¦------+------+------+------¦------¦ ¦ * ¦ 4 ¦ 1 ¦ 4 ¦ 4 ¦ 2 ¦ 2 ¦ 4 ¦ +------------+------+------¦------+------+------+------¦------¦ ¦ / ¦ 4 ¦ 1 ¦ 4 ¦ 4 ¦ 2 ¦ 2 ¦ 4 ¦ +--------------------------+---------------------------+------+ В ходе анализа заполняются анализирующий и вычислительный стеки, а также в результате просмотра происходит сдвиг по арифме-
- 16 тическому выражению. Сущность алгоритма анализа сводится к выбору действия в зависимости от входного символа и вершины анализирующего стека. Алгоритм с использованием стеков сводится к следующему: для прочитанного операнда - сброс его в вычислительный стек; для прочитанной скобки или операции - выбор действия в соответствие с таблицей перехода анализирующего стека. В результате в вычислительном стеке формируется исходное выражение в обратной польской записи. Пример применения стековых методов к анализу арифметических выражений Выражение: (a + b)*c + (d - k) /l Таблица 2.1 +----------------------------------------------------------------+ ¦ Т ¦ вх. сим.¦ действие ¦ Е ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ ¦ ( ¦ 1 ¦ ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ ( ¦ a ¦ ¦ а ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ ( ¦ + ¦ 1 ¦ ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ (+ ¦ b ¦ ¦ b ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ (+ ¦ ) ¦ 4 ¦ + ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ ( ¦ ) повт.¦ 3 ¦ ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ ¦ * ¦ 1 ¦ ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ * ¦ с ¦ ¦ c ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ * ¦ + повт.¦ 4 ¦ * ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ ¦ + ¦ 1 ¦ ¦ +----------------------------------------------------------------+
- 17 продолжение табл.2.1 +----------------------------------------------------------------+ ¦ Т ¦ вх. сим.¦ действие ¦ Е ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ + ¦ ( ¦ 1 ¦ ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-++ ( ¦ d ¦ ¦ d ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-++ ( ¦ - ¦ 1 ¦ ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-++(- ¦ k ¦ ¦ k ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-++(- ¦ ) ¦ 4 ¦ ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-++( ¦ ) повт.¦ 3 ¦ ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ + ¦ / ¦ 1 ¦ ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ +/ ¦ l ¦ ¦ l ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ +/ ¦ +-+ ¦ 4 ¦ / ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ + ¦ +-+повт.¦ 4 ¦ + ¦ +--------+---------+-----------------------+---------------------¦ ¦ +-+ ¦ +-+повт.¦ конец ¦ ¦ +----------------------------------------------------------------+ То, что в стеке: a b + c * d k - l / +- это обратная польская запись арифметического выражения. Результатом является: ab+c*dk-l/+ t1 c * d k - l / + t2 d k - l / + t2 t3 l / + t2 t4 + t5
- 18 5. Определение формальных грамматик Формальной грамматикой языка называют четверку объектов: G(S,P,T,N), где N - совокупность категорий языка, называемых в теории формальных грамматик нетермами; T - словарь языка - термы; P - совокупность правил образования предложений языка; S - начальный символ. Правила грамматик имеют вид: е -> n (цепочку символов е заменить на цепочку символов n), где e и n - термы и нетермы языка, -> знак подстановки. В зависимости от вида правил, формальные грамматики делят на контекстно-свободные и контекстно-зависимые. Контекстно-свободной грамматику называют в случае, если левая часть правил представляет собой нетерм. Грамматики языков программирования записывают в виде нотации Бэкуса-Наура (БНФ-нотации). По БНФ-нотации нетермы записываются в скобках - < >, а термы непосредственно представлены в описании, знак подстановки - ::=. Альтернативы в правых частях правил разделяются вертикальными линиями - ¦. Модифицированная нотация Бекуса-Наура содержит скобки: [,] - повтор, иногда с повторителем N; _N [] - не больше N повторов; N [] - не меньше, чем заданное число повторов; () - пропуск конструкции. Пример 1: определение идентификатора <идентификатор> ::= <буква> (_9 [<символ>]) <буква> ::= A¦..¦Z¦a¦..¦z <символ> ::= <буква>¦<цифра> <цифра> ::= 0¦1¦..¦9 Пример 2: Необходимо описать в БНФ язык арифметических выражений с операциями -,+,*,/,**, допускающий использование скобок и задаваемых буквами операндов. Опишем грамматику: термы Т = { A..Z, a..z, -, +, *, /, (, ) }
- 19 нетермы N = { <арифметич. выражение>, <операнд>, <операция сложения>, <операция умножения>, <первичное>,<терм>} правила Р = {<операнд>::=а¦..¦z¦A¦..¦Z <первичное>::=<операнд>¦(<арифметич. выражение>) <терм>::=<терм><операция умножения><арифметич. выражение>¦<первичное> <арифметич. выражение>::=<терм><операция сложения><арифметич. выражение>¦<терм> } Алгоритм грамматического разбора на один шаг вперед Используют прямую и обратную схему разбора. Для обработки входных предложений некоторого контекстно свободного языка осуществляют грамматический разбор предложения, причем грамматический разбор можно начать от начального символа к предложению или наоборот. В любом случае возникает дерево грамматического разбора. Корни - начальный символ, вершины - термы и нетермы грамматики, термы входного предложения - это листья дерева грамматического разбора. Следовательно, синтаксический анализ предложения сводится к обходу дерева. Выделяют 2 вида обхода: полный обход и направленный обход. Использование направленного поиска позволяет избежать возвратов и поэтому нашло применение в реальных трансляторах. Условия применимости алгоритма 1) При разработке транслятора контекстно-свободного языка применим алгоритм просмотра на один шаг вперед в том случае, если для любого правила грамматики, в правой части которого есть альтернатива, каждая такая альтернатива начинается с уникального терминального символа. Например: S::=XS¦A A::=Y¦Z. 2) Запрещается использование левой рекурсии, т.е. любое рекурсивное правило должно иметь вид: <нетерм>::=терм<нетерм> В большинстве случаев вместо применения правой рекурсии достаточно использовать модифицированную нотацию, включающую повторы с явным заданием условия ограничения повтора.
- 20 Содеpжание задания: Разpаботать пpогpамму синтаксического анализа пpедложений заданного языка. Пpогpамма анализатоp должна pаботать в pежиме интеpпpетации одного пpедложения. Цель пpогpаммы - идентификация пpавильных пpедложений языка и диагностика ошибок в непpавильных пpедложениях. Пpогpамма должна pаботать в диалоговом pежиме. Для заданий используются языки выpажений: аpифметических, логических, смешанных, выpажений со списками, с pазличными опеpандами, опеpациями, способами задания пpиоpитетов опеpаций. Поpядок выполнения pаботы: 1. Получить вариант задания у пpеподавателя. 2. Составить контекстно-свободную гpамматику, описывающую данный язык или существенную часть языка. 3. Разpаботать и отладить пpогpамму анализатоp пpедложений языка. 4. Ответить на контpольные вопpосы. 5. Пpодемонстpиpовать пpеподавателю pаботу пpогpаммы на пеpсональной ЭВМ. Ваpианты задания: 1. Язык аpифметических выpажений в инфиксной фоpме с опеpациями +,-,/,*, без скобок, с опеpандами в фоpме идентификатоpов и констант (целых, с фиксиpованной и плавающей запятой). 2. Язык аpифметических выpажений в инфиксной фоpме с опеpациями +,-,/,*, со скобками, с опеpандами в фоpме идентификатоpов и констант (целых). 3. Язык аpифметических выpажений с опеpациями языка Си (+,-, /, *,++, --,%), без скобок, с опеpандами в фоpме идентификатоpов и констант (целых, с фиксиpованной и плавающей запятой). 4. Язык аpифметических выpажений с опеpациями языка Си (+,-, /, *,++, --,% ), со скобками, с операндами в форме идентификаторов и целых констант. 5. Язык аpифметических выpажений в префиксной фоpме с опеpациями +,-,/,*, без скобок, с опеpандами в фоpме идентификатоpов и констант (целых, с фиксиpованной и плавающей запятой). 6. Язык аpифметических выpажений в постфиксной фоpме с опеpациями +,-,/,*, без скобок, с опеpандами в фоpме идентифика-
- 21 тоpов и констант (целых, с фиксиpованной и плавающей запятой). 7. Язык аpифметических выpажений в инфиксной фоpме с опеpациями +,-,/,*, без скобок, с опеpандами в фоpме идентификатоpов и констант (целых) и функциональных выражений с несколькими аргументами. Аргумент функционального выражения - идентификатор. 8. Язык аpифметических выpажений в инфиксной фоpме с опеpациями +,-,/,*, без скобок, с опеpандами в фоpме идентификатоpов и констант (целых) и функциональных выражений с несколькими аргументами. Аргумент функционального выражения - вышеописанное выражение. 9. Язык логических выражений с операциями .NOT., .OR., .AND., без скобок, с операндами идентификаторами, константами (.TRUE., .FALSE.) и операциями отношений в синтаксисе ФОРТРАНа (. GE., .LE., .NE., .EQ., .GT., .LT.). 10. Язык выражений с операциями (||,&&,!,&=,!=,=) логики языка Си, со скобками, с операндами идентификаторами, логическими константами, операциями отношений (<,>,==,<=,>=,!=). 11. Язык битовых выражений языка Си с операциями (<<,>>,|,&, <<=,=>>,>,==), без скобок, с операндами идентификаторами и целыми константами (в двоичной, восьмеричной, десятичной и шестнадцатиричной формах). 12. Язык адресных выражений языка Си с операциями ссылок (&, *), без скобок, с операндами идентификаторами, элементами массивов. 13. Язык адресных выражений языка программирования Си с операциями *,&,->, со скобками и операндами, заданными идентификаторами. 14. Язык битовых выражений языка Си с операциями (<<,>>,&&,!, &=,|=,^,^=,=>>,<<=,=), со скобками, и операндами в форме идентификаторов и целых двоичных констант. 15. Язык логических выражений с операциями (||,&&,!,!=,=,&=) языка программирования Си, без скобок, с операндами - идентификаторами и операциями отношений. Операции отношений включают в себя двухоперандные арифметические выражения (с идентификаторами и константами). 16. Язык аpифметических выpажений в инфиксной фоpме с опеpациями +,-,/,*, со скобками, с опеpандами в фоpме идентифика-
- 22 тоpов и элементами массивов. 17. Язык функциональных выражений с произвольным количеством аргументов и неограниченной вложенностью. Аргументы - идентификаторы : f(g(x,e(y,z))). 18. Язык функциональных выражений. Каждая функция имеет один аргумент. Аргументами являются идентификаторы, элементы массивов и константы. 19. Язык аpифметических выpажений в постфиксной фоpме с опеpациями +,-,/,*, без скобок, с опеpандами в фоpме идентификатоpов и элементов массивов. 20. Язык аpифметических выpажений в префиксной фоpме с опеpациями +,-,/,*, без скобок, с опеpандами в фоpме идентификатоpов и элементов массивов. 21. Язык аpифметических выpажений с одноместными операциями языка программирования Си (++,--,=,+=,-=,*=,/=,%=), с опеpандами в фоpме идентификатоpов и элементов массивов. 22. Язык аpифметических выpажений в инфиксной фоpме с опеpациями +,-,/,*, без скобок, с опеpандами в фоpме идентификатоpов и элементов массивов. 23. Язык аpифметических выpажений в инфиксной фоpме с опеpациями +,-,/,*, со скобками, с опеpандами в фоpме идентификатоpов и элементов массивов. 24. Язык выражений в синтаксисе Си, включающий присваивание, пре- и пост- инкремент (++) и декремент (--), +, -, /, *, с операндами в виде идентификаторов и констант. 25. Язык выражений в синтаксисе Си, включающий присваивание, пре- и пост- инкремент (++) и декремент (--), +, -, /, *, с операндами в виде идентификаторов и функциональных вызовов. Допустимы вызовы функций с произвольным количеством аргументов-идентификаторов. 26. Язык битовых выражений языка С++ с операциями(<<,>>,|,&, <<=,=>>,>,==), без скобок, с операндами идентификаторами и целыми константами (в двоичной, восьмеричной, десятичной и шестнадцатиричной формах). 27. Язык адресных выражений языка С++с операциями ссылок (&, *), без скобок, с операндами идентификаторами, элементами массивов. 28.Язык адресных выражений языка программирования С++ с операциями *,&,->, со скобками и операндами, заданными идентификаторами. 29. Язык битовых выражений языка С++ с операциями (<<,>>,&&,!, &=,|=,^,^=,=>>,<<=,=), со скобками, и операндами в форме идентификаторов и целых двоичных констант. 30. Язык логических выражений с операциями (||,&&,!,!=,=,&=) языка программирования С++, без скобок, с операндами -идентификаторами и операциями отношений. Операции отношений включают в себя двухоперандные арифметические выражения (с идентификаторами и константами).
31. Язык аpифметических выpажений с одноместными операциями языка программирования С++(++,--,=,+=,-=,*=,/=,%=), с опеpандами в фоpме идентификатоpов и элементов массивов. 32. Язык аpифметических выpажений c операциями направления между потоками >> и << с опеpандами в фоpме идентификатоpов и элементов массивов. 33. Язык выражений в синтаксисе С++,включающий присваивание, пре- и пост- инкремент (++) и декремент (--), +, -, /, *, с операндами в виде идентификаторов и констант. 34. Язык выражений в синтаксисе С++,включающий присваивание, пре- и пост- инкремент (++) и декремент (--), +, -, /, *, с операндами в виде идентификаторов и функциональных вызовов. Допустимы вызовы функций с произвольным количеством аргументов-идентификаторов. 35. Язык аpифметических выpажений c операциями направления между потоками >> и << с опеpандами в фоpме идентификатоpов и функций. ЭТАП ПРОЕКТИРОВАНИЯ N 3 Изучение синтаксически-управляемой схемы трансляции Цель этапа: Изучить синтаксически (таблично) -управляемые трансляторы, формализм синтаксических графов, методы размещения синтаксических графов в оперативной памяти с помощью ссылочных структур. Теоретическая часть: Синтаксические графы Элементы синтаксических графов (СГ) и их сопоставление с контекстно-свободными грамматиками (КСГ) представлены в таблице: Таблица 3.1 +----------------------------------------------------------+ ¦ ¦ СГ ¦ КСГ ¦ +------------+-------------------+-------------------------¦ ¦ 1) терм ¦ ->терм-> ¦ X, abc, read ¦ +------------+-------------------+-------------------------¦ ¦ 2) нетерм ¦ ->метка-> ¦
,<константа>,<метка> ¦ +------------+-------------------+-------------------------¦ ¦ 3) ИЛИ ¦ ->o-> ¦ <>::=...¦...¦... ¦ ¦ ¦ ¦ .. ¦ ¦ ¦ ¦ +-> ¦ ¦ +----------------------------------------------------------+
- 24 Продолжение табл.3.1 +----------------------------------------------------------+ ¦ ¦ СГ ¦ КСГ ¦ +------------+-------------------+-------------------------¦ ¦ 4) И ¦ +-----+ +-----+ ¦ <>::=<><>...<> ¦ ¦ ¦ -¦ +>¦ +->¦ ¦ ¦ ¦ +-----+ +-----+ ¦ ¦ +------------+-------------------+-------------------------¦ ¦ ¦ -->-------------->¦ ¦ ¦ ¦ ^ +-----+ ¦ ¦ ¦ ¦ 5) повтор ¦ +-¦ +-+ ¦ <>::=N[<>...<>] ¦ ¦ ¦ +-----+ ¦ ¦ +----------------------------------------------------------+ Рассмотрим простую грамматику: <имя>::=<буква>5[<символ>] <символ>::=<буква>¦<цифра> <буква>::=A..Z <цифра>::=0..9 Синтаксический граф для нее будет иметь вид: <имя> ¦ +-------+ +---+ +----¦ буква +------¦ 5 +--------> +-------+ ¦ +---+ ¦ ¦ +-------+ ¦ +-¦символ +--+ +-------+ +-------+ +---+ +-------+ +--- A -->-+ ¦ буква +->-->¦ A ¦ ¦символ +->-¦ . Z -->-+-> +-------+ ¦ +---+ +-------+ ¦ . 0 -->-¦ +-> ... +--- 9 -->-+ ¦ +---+ +->¦ Z ¦ +---+ Синтаксические графы служат как средством задания синтаксиса входного языка, так и структуры транслятора этого языка. Существует взаимное соответствие элементов синтаксических графов и элементов языков программирования.
- 25 Для СГ и КСГ такое соответствие следующее: 1) if [вх. символ] != терм then ошибка, читать (входной символ) 2) нетерм S: вызов процедуры 'S' 3) ИЛИ: case..., if(if...) 4) И: оператор1; опреатор2; ... 5) повтор: while, for Синтаксически-управляемые трансляторы Строгое соответствие элементов синтаксических графов и программ транслятора, позволяют осуществлять разработку трансляторов автоматически. Такие программы называются генераторами транслятора или синтаксически-управляемыми трансляторами. В операционной системе UNIX это утилиты lex, jaec. +---------> +-------+ +------------+ ¦ терм ¦ ¦ <нетерм> ¦ +-------¦ И +------------¦ ¦ - ¦ --+--->следующая ¦ - ¦ ---+--->следующая +-+-----+ +--+---------+ ИЛИ альтернатива +-----------+ альтернатива ¦ ¦ +---------> <имя> +-------------+ ¦ +--------------+ ¦ ¦ <буква> ¦ ¦ ¦ <символ> ¦<---+ +-------+-------------¦ ¦ +--------------¦ ¦ ¦ >< ¦ ---+--> ¦ ¦ - ¦ - ¦ ¦ +--+----------+ ¦ +---+-------+--+ ¦ ¦ ¦ ¦ ¦ ¦ +----------------------------+ ¦ +-------+ ¦ +-----+ +-----------+ +---¦ ¦ ¦ +--+ ¦ ¦ ¦ +-----------¦ +-----+ ¦ >< ¦ >< ¦ +-----------+ Рис. 1. Пример ссылочной схемы размещения СГ в ОП
- 26 Синтаксически-управляемая схема трансляции складывается из двух блоков, первый вводит описание грамматики и строит в оперативной памяти синтаксический граф языка. Второй блок представляет собой универсальную процедуру обработки графов, реализующую алгоритм просмотра на один шаг вперед. Процедура обхода синтаксического графа реализует следующие операции: 1) проверка на совпадение входного символа и текущего нетерго символа; 2) переход от текущей нетерминальной вершины на раскрывающий подграф по ссылке; 3) переход по альтернативной ссылке в случае несовпадения; 4) переход по ссылке "следующая" для конструкции состоящей из нескольких символов. Содержание задания: Заданием к этапу N3 служит задание этапа N2. Для заданного языка выражений необходимо построить синтаксический граф (или набор вложенных графов, если количество термов, нетермов и связей велико). Для построенного синтаксического графа разработать ссылочную схему размещения графа в оперативной памяти. Разработать и отладить программу, считывающую описание грамматики и строющую в памяти граф. Программа должна иметь блок демонстрации размещенного графа на дисплее. Такой блок может выводить на экран дисплея таблицу следующей структуры: +-------------------------------------------------------------+ ¦ Вершина ¦ Тип ¦ Адрес ¦ Следующий ¦ Альтернатива ¦ +-----------+----------+----------+------------+--------------¦ ¦ <Операнд> ¦ нетерм ¦ F0A4 ¦ F025 ¦ F035 ¦ ¦ . . ¦ ¦ . . ¦ +-------------------------------------------------------------+ или какие либо более иллюстративные формы демонстрации графа по выбору студента. Порядок проектирования этапа N 3: 1. Построить синтаксический граф языка выражений (задание к этапу N2) по его БНФ-описанию. 2. Построить схему размещения графа в оперативной памяти на основе узлов и связей структуры изображенной на рисунке:
- 27 A +-------+-------+ +-------------------+ ¦ ¦ ¦<содержание терма>¦ +---------------¦ +-------------------¦ ¦ - ¦ - ¦ ¦ - ¦ - ¦ +---+-------+---+ +----+---------+----+ ¦ ¦ ¦ ¦ следующая альтернатива следующая альтернатива вершина вершина Рис. 2а. Нетерм Рис. 2б. Терм 3. Разработать и отладить программу считывания описания грамматики, построения и демонстрации графа. Содеpжание этапа N 3: 1. Синтаксический граф заданного языка выражений. 2. Рисунок схемы размещения графа в оперативной памяти. 3. Результаты работы программы. Контрольные вопросы: 1. Какой транслятор называют синтаксически-управляемым? 2. Что такое синтаксический граф? Каким образом соответствуют друг другу два формализма: синтаксические графы и контекстно-свободные грамматики? 3. С помощью каких ссылочных структур можно разместить синтаксический граф в памяти? 4. Как работает алгоритм грамматического разбора - "слева направо,просмотр на один символ вперед"? 5. Как работает рекурсивный алгоритм обхода синтаксического графа? 6. Какими достоинствами и недостатками обладает синтаксически-управляемая схема трансляции?
- 28 ЭТАП ПРОЕКТИРОВАНИЯ N 4 Изучение контекстных условий языков программирования Цель этапа: Изучить методы обработки контекстных условий разных типов. Теоретическая часть: Контекстные условия языков программирования. Программные грамматики 1. Понятие контекстных условий. Контекстными условиями называется связь между предложениями текста, влияющая на интерпретацию предложения. В языках программирования встречаются следующие примеры контекстных условий: описание и использование идентификаторов; использование и описание абстрактных типов данных; описание массива с заданными границами и употребление элемента массива с индексами, входящими в заданные границы; описание формальных параметров процедуры и фактического вызова; описанние типов переменных и констант и их употребление в арифметических выражениях; макроподстановки и их использование; и другие. Контекстные условия задаются в задании на разработку транслятора обычно на естественном языке и в отличие от синтаксиса контекстно-свободной части требуют изобретения специфических алгоритмов. 2. Классификация контекстных условий. 2.1 Контекстные условия I рода. К контекстным условиям I рода относят требования единственности описания каждого объекта, т.е. каждый идентификатор должен быть описан 1 раз. Общие методы проверки контекстных условий I рода сводятся к созданию и заполнению структуры данных, содержащей все ранее объявленные объекты. Каждый вновь объявленный объект требует просканировать такую структуру данных на совпадение. Если язык программирования имеет блочную структуру, причем каждый блок может иметь свои собственные переменные, то необходимо учитывать область действия переменных, следовательно контекст, кроме операторов объявления включает операторы заголовков и концов блоков, а таб-
- 29 лица переменных должна иметь атрибуты области действия. 2.2 Контекстные условия II рода. Контекстными условиями II рода называется требование соответствия определяющего высказывания об объектах и высказывания, использующего данные объекты. Согласно контекстным условиям II рода каждая переменная может быть объявлена с некоторым типом, а затем должна участвовать в выражении, содержащем операции только данного типа. Обработка контекстного условия II рода сводится к организации таблицы, фиксирующей тип каждой переменной при объявлении и последующему сканированию такой таблицы при анализе каждого использующего выражения. Если язык программирования содержит абстрактные типы данных, то необходимо иметь таблицу типов, фиксирующую соответствие абстрактного типа и его определения через стандартные типы. 2.3 Контекстные условия III рода. Это требования соответствия формальных и фактических параметров, границ индексов массивов и индексов в элементах массивов и др., т.е. контекстные условия, не принадлежащие к первому и второму роду. Большинство языков программирования, за исключением Паскаля, С++, не проверяют соответствие формальных и фактических параметров. Проверка соответствия является обязанностью программиста и узким местом языков программирования. Большинство языков (исключая Си) проверяют оперделение элемента массива и его использование. 2.4 Контекстные условия IV рода. К контекстным условиям IV рода относят количественные ограничения, вносимые в язык транслятором, например, количество переменных, диапазон представимых чисел и т.д. 3. Программные грамматики. Программной грамматикой называют пятерку объектов: G(T,N,P,S,M), где T - множество термов, N - множество нетермов, Р - множество правил, S - начальный символ,
- 30 M - метки правил. Правило грамматики имеет вид: i: F -> Ф¦W1¦W2 Множества W1 и W2 - это подмножества меток М, причем, если ядро правила применимо, то следующим правилом будет правило из множества W1, а если ядро не применимо, то будет применяться множество W2. Программные грамматики позволяют описывать как порождение конструкций языка программирования, так и алгоритма обработки контекстных условий. Для программной грамматики возможно составить программу универсальной обработки, чередующей порождение контекстно-свободной конструкции с проверкой контекстных условий. Содержание задания: Заданием данного этапа курсового проекта служит задание этапа N1 по реализации лексического сканера. Необходимо проанализировать контекст употребления заданных лексем, выяснить к каким типам относятся выявленные контекстные условия и дополнить сканер программой обработки этих условий. Для определяемых лексем всех типов контекстное условие заключается в необходимости соответствия определения и использования лексемы. Например, любой используемый идентификатор языка Си должен быть определен с указанием типа. Следовательно, программа проверки контекстного условия должна проверить для каждого случая использованного идентификатора наличие определения. При разработке программы обработки контекста необходимо использовать уже сформированные структуры данных. То есть проверка контекста идентификатора сводится к проверке соответствия таблиц определений и использований по принципу : каждый использованный идентификатор должен быть определен, каждый опредленный идентификатор может быть использован. Необходимость учета области видимости переменных усложняет приведенный принцип, так как разные переменные могут иметь одинаковые имена и различаться лишь контекстно. Определение и использование имен абстрактных типов данных имеет контекстные условия, аналогичные именам переменных. Метки в разных языках программирования имеют различные контекстные условия. В Паскале обязательно определение в опрераторе
- 31 label, в Си метки не объявляются. Использование меток (go to, арифметический if в Фортране) и помеченные операторы должны соответствовать друг другу. Константы во многих языках программирования могут быть объявлены с присвоением идентификатора (const) или использоваться непосредственно. В любом случае необходимо отличать константы от меток или спецификаций ввода/вывода. Специальный вид констант атомы Пролога - необходимо отличать от предикатов, констант, доменов, учитывая, что атомы встречаются в двух контекстах: как аргументы предиката и операнды выражения. Использование операций также нередко связано с контекстом. Символы операций :,+,-,/,*,% - встречаются в операторах (комментарии, :=,..), спецификациях ввода/вывода (%), обозначениях констант (/n, /t...). Для предикатов Пролога, макросов ассемблера, объявлений, определений и вызовов функций и процедур необходимо соответствие аргументов объявлений, определений и вызовов. Порядок проектирования этапа : 1. Проанализировать контекст заданных лексем. Опредетить типы контекстных условий. Описать программную грамматику. 2. Для выделенных контекстных условий предложить процедуру проверки. 3. Модифицировать лексический сканер для обработки контекстных условий. Программа должна быть иллюстративной, т.е. осуществлять проверку контекстных условий для фрагментов программ, заданных в диалоговом режиме. 4. Ответить на контрольные вопросы. Содеpжание этапа проектирования: 1. Описание программной гамматики. 2. Спецификации процедуры проверки контекстных условий. 3. Результаты работы программы.
- 32 Контрольные вопросы : 1. Что такое контекст языковой конструкции? 2. Какие типы контекстных условий выделяют в теории формальных языков? 3. Какое контекстное условие (КУ) называется КУ 1-го рода? КУ 2- го рода? КУ 3-го и 4-го родов? Приведите примеры различных КУ. 4. К какому типу КУ относится требование языков программирования об обязательном объявлении переменных, об объявлении массиваБ о соответствии фактических и формальных параметров процедур? 5. Что такое программная грамматика? 6. Контекстные условия каких типов описывают формальные грамматики? Как соотносятся выразительные мощности программных и контекстно-свободных грамматик? 7. Существуют ли общие методы обработки КУ?
ЭТАП ПРОЕКТИРОВАНИЯ N 5 Изучение блока генерации объектного кода трансляторов языков программирования Цель этапа: Изучить методы генерации объектного кода трансляторами языков программирования, построить блок генерации для выражений. Теоретическая часть: 1. Спецификация генератора кода. Блок генерации кода работает по результатам работы блоков лексического и синтаксического анализа. Эти результаты представлены в форме перекодированной программы и таблицы символов. Таблица символов описывает идентификаторы, константы, метки и имена процедур. Выходом генератора кода является объектный код и иногда ассемблерный аналог программы. Генератор кода является машинно-зависимой компонентой трансляторов. Поэтому для его создания необходимо учитывать
- 33 особенности архитектуры базовых машин. Форматы компоновщика и загрузчика определяют конкретную форму объектного кода. 2. Генерация кода для выражения. Генератор кода получает для обработки программу, в которой все выражения приведены в постфиксную форму. Выражения в такой форме не нуждаются в скобках для задания порядка операций. Для обработки выражений обычно используют стековую структуру данных, в результате, вычисление выражения сводится к следующему: необходимо читать лексему выражения, если эта лексема операция, то операнды именно этой операции предшествуют в стеке знаку операции и легко выделить исполняющую тройку, в составе операции и двух операндов, затем операция выполняется. Все элементы тройки выталкиваются из стека, а на их место записывается результат. Обработка выражения продолжается до тех пор, пока в стеке не останется заключительный результат. В блоке генерации кода осуществляются не вычисления, а генерация объектного или ассемблерного кода, соответствующего отдельным тройкам. Для каждой операции в известной системе команд возможно построить заготовки выполнения операции, каждая из которых будет содержать команды загрузки, выполнения операции и запоминание результата. Запоминание результата осуществляется в промежуточных переменных, которые порождаются генератором кода и не имеют аналогичных переменных в выражениях языка высокого уровня. Генератор кода для выражений представляет собой блок типа "выбор" (case), в котором в зависимости от вида операций выбирается нужная заготовка. 3. Генерация сегментов данных. Для генерации сегмента данных необходимо каждой переменной отвести область памяти, достаточную для ее расположения, и адрес данной области использовать в объектном коде вместо имени переменной. Если есть константа, то: 1) константу объявляют как переменную, но по адресу записывают значение константы, или 2) используют непосредственную адресацию. При объявлении в сегменте данных сложно-структурированных элементов генератор кода обычно создает специальные управляющие структуры данных - информационные вектора. Например, для каждого массива компилятор языка РL/1 создает поля: длина каждого поля
- 34 элемента, общая длина, адрес начала массива. Не существует стандарт на информационные поля, следовательно, разные трансляторы моделируют одну и ту же структуру данных по-разному. Разные форматы информационных векторов затрудняют объединение модулей, написанных на разных языках. 4. Генерация программного сегмента. Программа на языке высокого уровня после синтаксического анализа содержит выражения, преобразованные в постфиксную форму, и преобразованную или не преобразованную управляющую структуру. Если компилятор осуществляет преобразование управляющих структур, то он представляет оператор в постфиксной форме, т.е. в виде операций: if, while,else, аргументами которых являются значения логических выражений и адреса операторов. Такое представление операторов управления позволяет обрабатывать их как обычные арифметические операции в общем операторе case генератора кода. Для управляющих структур строится заготовка из команд вычисления логического выражения условного перехода по флагам и безусловного перехода. Усложняет процесс означивания заготовки генерация меток для тех операторов, которые еще не оттранслированы. В результате, символическое имя метки сгенерировать можно, но определить адрес метки в кодовом сегменте заранее нельзя. Поэтому генерация кодов управляемых структур бывает обычно двухпроходовой. На первом проходе: используются все заготовки, но метки в заготовках не означиваются. На втором: ведется переменный счетчик команд, вычисляющий адрес каждой команд, вычисляющий адрес каждой команды и следовательно, способный означить любую метку. 5. Обработка локальных и глобальных переменных. Основная проблема обработки локальных и глобальных имен сводится к необходимости различить употребление одноименных переменных в разных программах или блоках. Для этого в структуре таблицы для каждой переменной указывают: в какой процедуре или блоке она объявлена и какой уровень вложенности этой процедуры. Генератор кода в любое время следит, какой код процедуры генерируется, и в соответствии с этим используются адреса элементов.
- 35 Содержание задания: Задание к этапу N5 основано на задании к этапу N 2 и является его продолжением. Для заданного языка выражений необходимо построить блок генерации ассемблерного кода. Программа -генератор должна работать в диалоговом режиме и взаимодействовать с синтаксическим анализатором, осуществляя генерацию только для корректных выражений. Результат генерации должен представлять собой законченную ассемблер-программу и содержать сегменты стека, данных и кода. При генерации сегмента стека можно ограничиться типовым постоянным сегментом с приемлемыми значениями. Сегмент данных должен быть сгенерирован для целочисленной арифметики, т.е. идентификаторы переменных выражения считаются целыми. Если задание к этапу включало константы с плавающей точкой, то достаточно учесть целую часть константы. Необходимо иметь ввиду, что кроме операндов выражения сегмент данных должен содержать переменные для хранения промежуточных значений. Количество промежуточных переменных различно для разных выражений и может быть оптимизировано. Порядок проектирования этапа: 1. Выбрать метод генерации ассемблерного кода по выражению. Предложить способ генерации промежуточных значений. 2. Разработать блок генерации ассемблерного кода. 3. Ответить на контрольные вопросы. Содеpжание этапа: 1. Обоснования выбора метода генерации ассемблерного кода. 2. Описание способа генерации промежуточных значений. 3. Результаты работы программы. Контрольные вопросы: 1. Какие методы генерации объектного кода Вы знаете? 2. В чем заключаются методы генерации кода арифметических выражений? 3. Как можно оптимизировать код, полученный по арифметичес-
- 36 кому выражению? 4. Какие трудности связаны с генерацией программных секций объявления данных? СПИСОК ЛИТЕРАТУРЫ 1. Грис Д. Конструирование компиляторов для цифровых вычислительных машин : Пер. с англ. - М.: Мир, 1975. 2. Братчиков И.Л. Синтаксис языков программирования.- М.: Наука, 1975. 3. А.Ахо, Дж.Ульман. Теория синтаксического анализа, перевода и компиляции. T1.- M.: Мир, 1978. 4. А.Ахо, Дж.Ульман. Теория синтаксического анализа, перевода и компиляции. T2.- M.: Мир, 1978. 5. Льюис Ф., Розенкpанц Д., Стиpиз Р. Теоpитические основы пpоектиpования компилятоpов.- М.: Миp, 1979. 6. Вирт Н. Алгоритмы + структуры данных = программы. : Пер. с англ.- М.: Мир, 1985. 7. Бек Л. Введение в системное программирование : Пер. с англ. - М.: Мир, 1988. 8. Уинер Р. Язык Турбо Си : Пер. с англ. - М.: Мир, 1991. 9. Описание компилятора tcc. Borland. 10. Язык Си для профессионалов / по материалам книги Г.Шилдта. - М.: "И.В.К.-СОФТ", 1992.
