Системное программное обеспечение
.pdfЛекция 21 Генерация и оптимизация объектного кода.
План
1.Основные принципы работы синтаксических анализаторов.
2.Преобразование КС-грамматик, приведенные грамматики.
3.Синтаксические распознаватели с возвратом, распознаватель на основе алгоритма «сдвиг-свертка». Оптимизация кода.
4.Основные методы оптимизации кода. Общие принципы оптимизации кода. Оптимизация линейных участков программы.
5.Другие методы оптимизации программ. Машинно-зависимые методы оптимизации.
Программирования имеет четко заданные и специфицированные семантические соглашения, которые не могут быть проверены на этапе синтаксического разбора. Именно их в первую очередь проверяет семантический анализатор. Примерами таких соглашений являются следующие требования:
−каждая метка, на которую есть ссылка, должна один раз присутствовать в программе;
−каждый идентификатор должен быть описан один раз и ни один идентификатор не может быть описан более одного раза (с учетом блочной структуры описаний);
−все операнды в выражениях и операциях должны иметь типы, допустимые для данного выражения или операции;
−типы переменных в выражениях должны быть согласованы между собой;
−при вызове процедур и функций число и типы фактических параметров должны быть согласованы с числом и типами формальных параметров.
Это только примерный перечень такого рода требований. Конкретный состав требований, которые должен проверять семантический анализатор, жестко связан с семантикой входного языка (например, некоторые языки допускают не описывать идентификаторы определенных типов). Варианты реализаций такого рода семантических анализаторов детально рассмотрены в. Например, если мы возьмем оператор языка Pascal, имеющий вид: а := b + с; то с точки зрения синтаксического разбора это будет абсолютно правильный оператор. Однако нельзя сказать, является ли этот оператор правильным с точки зрения входного языка (Pascal), пока не будут проверены семантические требования для всех входящих в него лексических элементов. Такими элементами здесь являются идентификаторы a, b и с. Не зная, что они собой представляют, невозможно не только окончательно утверждать правильность приведенного выше оператора, но
ипонять его смысл. Фактически, необходимо знать описание этих идентификаторов.
Литература
Основная:
1.Молчанов А.Ю. Системное программное обеспечение. Учебник для вузов. — СПб.: Питер, 2003. — 396 с.
2.Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум.- СПб.: Питер, 2005.- 284 с.
3.Юров В.И. Assembler. Учебник для вузов. 2-е издание - СПб.: Питер.- 2004.- 637 с.
4.Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование: Основы построения трансляторов + FD.- М.: КОРОНА принт.- 2004.- 255 с.
5.Фельдман Ф.К. Системное программирование на персональном компьютере.- 2004.- 512
6.Ахо А.,Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты: Пер. с англ. — М.: Издательский дом «Вильямс», 2003. — 768 с.
7.Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. —
СПб.: Питер, 2002. — 734 с.
8.Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб.: Питер, 2002. — 544
Дополнительная:
1.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2001. – Ч. 1. – 96 с.
2.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2002. – Ч. 2. – 96 с.
3.Ф.Льюис, Д. Розенкранц, Р.Стирнз. Теоретические основы проектирования компиляторов. М., Мир, 1979.
4.Л. Бек. Введение в системное программирование. М.,Мир, 1988.
5.В.Е.Котов, В.К.Сабельфельд. Теория схем программ. -М.: Наука, 1978
6.Автоматное управление асинхронными процессами в ЭВМ и дискретных системах /Под ред. В.И.Варшавского. -М.:Наука.
7.Питерсон Дж. Теория сетей Петри и моделирование систем.- М.: Наука. 1984.
8.Минский М. Вычисления и автоматы. - М.: Мир.- 1971.
9.Котов В.Е. Сети Петри. - М.: Наука. - 1984.-
10.Ахо А.,Хопкрофт Дж., Ульман Дж.Построение и анализ вычислительных алгоритмов. - М.: Мир. -1979.
11.Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. –
М.: Мир, 1984. – 264 с.
Лекция 22 Синтаксические анализаторы
План
1.Синтаксический анализ. Контекстно-свободные грамматики. Нисходящие анализаторы. Метод рекурсивного спуска.
1.Синтаксический анализ. Контекстно-свободные грамматики. Нисходящие анализаторы. Метод рекурсивного спуска.
Синтаксический анализ - это процесс, который определяет, принадлежит ли некоторая последовательность лексем языку, порождаемому грамматикой. В принципе, по любой грамматике можно построить синтаксический анализатор, но грамматики, используемые на практике, имеют специальную форму. Например, известно, что для любой контекстно-свободной грамматики может быть построен анализатор, сложность которого не превышает O(n3) для входной строки длины n, но в большинстве случаев по заданному языку программирования мы можем построить такую грамматику, которая позволит сконструировать и более быстрый анализатор. Анализаторы реально используемых языков обычно имеют линейную сложность; это достигается, например, за счет просмотра исходной программы слева направо с заглядыванием вперед на один терминальный символ (лексический класс).
Вход синтаксического анализатора - последовательность лексических и таблицы, например, таблица внешних представлений, которые являются выходом лексического анализатора.
Выход синтаксического анализатора - дерево разбора и таблицы, например, таблица идентификаторов и таблица типов, которые являются входом для следующего просмотра компилятора (например, это может быть просмотр, осуществляющий контроль типов).
Отметим, что совсем необязательно, чтобы фазы лексичекого и синтаксического анализа выделялись в отдельные просмотры. Обычно эти фазы взаимодействуют друг с другом на одном просмотре. Основной фазой такого просмотра считается фаза синтаксического анализа, при этом синтаксический анализатор обращается к лексическому анализатору каждый раз, когда у него появляется потребность в очередном терминальном символе.
Большинство известных методов анализа принадлежат одному из двух классов, один из которых объединяет нисходящие (top-down) алгоритмы, а другой - восходящие (bottom-up) алгоритмы. Происхождение этих терминов связано с тем, каким образом строятся узлы синтаксического дерева: либо от корня (аксиомы грамматики) к листьям (терминальным символам), либо от листьев к корню.
Нисходящие анализаторы строят вывод, начиная от аксиомы грамматики и заканчивая цепочкой терминальных символов. С нисходящими
анализаторами связаны так называемые LL-грамматики, которые обладают следующими свойствами:
•Они могут быть проанализированы без возвратов
•Первая буква L означает, что мы просматриваем входную цепочку слева направо (left-to-right scan)
•Вторая буква L означает, что строится левый вывод цепочки
(leftmost derivation).
Популярность нисходящих анализаторов связана с тем, эффективный нисходящий анализатор достаточно легко может быть построен вручную, например, методом рекурсивного спуска. Кроме того, LL-грамматики легко обобщаются: грамматики, не являющиеся LL-грамматиками, обычно могут быть проанализированы методом рекурсивного спуска с возвратами.
Сдругой стороны, восходящие анализаторы могут анализировать большее количество грамматик, чем нисходящие, и поэтому именно для таких методов существуют программы, которые умеют автоматически строить анализаторы. С восходящими анализаторами связаны LR-грамматики. В этом обозначении буква L по-прежнему означает, что входная цепочка просматривается слева направо (left-to-right scan), а буква R означает, что строится правый вывод цепочки (rightmost derivation). С помощью LRграмматик можно определить большинство использующихся в настоящее время языков программирования.
Литература
Основная:
1.Молчанов А.Ю. Системное программное обеспечение. Учебник для вузов.
— СПб.: Питер, 2003. — 396 с.
2.Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум.- СПб.: Питер, 2005.- 284 с.
3.Юров В.И. Assembler. Учебник для вузов. 2-е издание - СПб.: Питер.- 2004.-
637с.
4.Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование: Основы построения трансляторов + FD.- М.: КОРОНА принт.- 2004.- 255 с.
5.Фельдман Ф.К. Системное программирование на персональном компьютере.- 2004.- 512
6.Ахо А.,Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты: Пер. с англ. — М.: Издательский дом «Вильямс», 2003. — 768 с.
7.Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. —
СПб.: Питер, 2002. — 734 с.
8.Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб.: Питер, 2002. — 544
Дополнительная:
1.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2001. – Ч. 1. – 96 с.
2.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2002. – Ч. 2. – 96 с.
3.Ф.Льюис, Д. Розенкранц, Р.Стирнз. Теоретические основы проектирования компиляторов. М., Мир, 1979.
4.Л. Бек. Введение в системное программирование. М.,Мир, 1988.
5.В.Е.Котов, В.К.Сабельфельд. Теория схем программ. -М.: Наука, 1978
6.Автоматное управление асинхронными процессами в ЭВМ и дискретных системах /Под ред. В.И.Варшавского. -М.:Наука.
7.Питерсон Дж. Теория сетей Петри и моделирование систем.- М.: Наука. 1984.
8.Минский М. Вычисления и автоматы. - М.: Мир.- 1971.
9.Котов В.Е. Сети Петри. - М.: Наука. - 1984.-
10.Ахо А.,Хопкрофт Дж., Ульман Дж.Построение и анализ вычислительных алгоритмов. - М.: Мир. -1979.
11.Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. –
М.: Мир, 1984. – 264 с.
Лекция 23 Семантические анализаторы.
План
1.Назначение семантического анализа.
Синтаксический разбор – это основная часть компилятора на этапе анализа. Она выполняет выделение синтаксических конструкций в тексте исходной программы, обработанном лексическим анализатором. На этой же фазе компиляции проверяется синтаксическая правильность программы. Синтаксический разбор играет главную роль – роль распознавателя текста входного языка программирования (этот процесс описан в главе 4 «Синтаксические анализаторы»). Семантический анализ – это часть компилятора, проверяющая правильность текста исходной программы с точки зрения семантики входного языка. Кроме непосредственно проверки семантический анализ должен выполнять преобразования текста, требуемые семантикой входного языка (например, такие, как добавление функций неявного преобразования типов). В различных реализациях компиляторов семантический анализ может частично входить в фазу синтаксического разбора, частично – в фазу подготовки к генерации кода (в данной книге семантический анализ более подробно рассмотрен в главе 5 «Генерация и оптимизация кода»).
1.Назначение семантического анализа
Здесь уже неоднократно упоминалось, что практически все языки программирования, строго говоря, не являются КС-языками. Поэтому полный разбор исходной программы компилятор не может выполнить в рамках КС-языков с помощью КС-грамматик и МП-автоматов. Полный распознаватель для большинства языков программирования может быть построен в рамках КЗ-языков, поскольку все реальные языки программирования контекстно-зависимы. Итак, полный распознаватель для языка программирования можно построить на основе распознавателя КЗ-языка. Однако известно, что такой распознаватель имеет экспоненциальную зависимость требуемых для выполнения разбора исходной программы вычислительных ресурсов от длины входной цепочки. Компилятор, построенный на основе такого распознавателя, будет неэффективным с точки зрения скорости работы (либо объема необходимой памяти). Поэтому такие компиляторы практически не используются, а все реально существующие компиляторы выполняют анализ исходной программы в два этапа: первый – синтаксический анализ на основе распознавателя для одного из известных классов КС-языков; второй– семантический анализ.
Для проверки семантической правильности исходной программы необходимо иметь всю информацию о найденных лексических единицах языка.
Литература
Основная:
1.Молчанов А.Ю. Системное программное обеспечение. Учебник для вузов.
— СПб.: Питер, 2003. — 396 с.
2.Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум.- СПб.: Питер, 2005.- 284 с.
3.Юров В.И. Assembler. Учебник для вузов. 2-е издание - СПб.: Питер.- 2004.- 637 с.
4.Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование: Основы построения трансляторов + FD.- М.: КОРОНА принт.- 2004.- 255 с.
5.Фельдман Ф.К. Системное программирование на персональном компьютере.- 2004.- 512
6.Ахо А.,Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты: Пер. с англ. — М.: Издательский дом «Вильямс», 2003. — 768 с.
7.Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. —
СПб.: Питер, 2002. — 734 с.
8.Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб.: Питер, 2002. — 544
Дополнительная:
1.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2001. – Ч. 1. – 96 с.
2.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2002. – Ч. 2. – 96 с.
3.Ф.Льюис, Д. Розенкранц, Р.Стирнз. Теоретические основы проектирования компиляторов. М., Мир, 1979.
4.Л. Бек. Введение в системное программирование. М.,Мир, 1988.
5.В.Е.Котов, В.К.Сабельфельд. Теория схем программ. -М.: Наука, 1978
6.Автоматное управление асинхронными процессами в ЭВМ и дискретных системах /Под ред. В.И.Варшавского. -М.:Наука.
7.Питерсон Дж. Теория сетей Петри и моделирование систем.- М.: Наука. 1984.
8.Минский М. Вычисления и автоматы. - М.: Мир.- 1971.
9.Котов В.Е. Сети Петри. - М.: Наука. - 1984.-
10.Ахо А.,Хопкрофт Дж., Ульман Дж.Построение и анализ вычислительных алгоритмов. - М.: Мир. -1979.
11.Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. –
М.: Мир, 1984. – 264 с.
Лекция 24 Генератор кода.
План
1.Разбиение на модули, реализующие генератор списка триад.
2.Модуль описания допустимых типов триад.
3.Модуль описания структур данных для триад.
4.Модуль построения списка триад по дереву синтаксического разбора.
5.Модуль вычисления значений триад на этапе компиляции.
Впроцессе СУ-перевода и СУ-компиляции не только вырабатываются цепочки текста выходного языка, но и совершаются некоторые дополнительные действия, выполняемые самим компилятором. В общем случае схемы СУ-перевода могутпредусматривать выполнение следующих действий:
−помещение в выходной поток данных машинных кодов или команд ассемблера, представляющих собой результат работы (выход) компилятора;
−Q выдачу пользователю сообщений об обнаруженных ошибках и предупреждениях (которые должны помещаться в выходной поток, отличный от потока, используемого для команд результирующей программы);
−порождение и выполнение команд, указывающих, что некоторые действия должны быть произведены самим компилятором (например, операции, выполняемые над данными, размещенными в таблице идентификаторов).
Ниже рассмотрены основные технические вопросы, позволяющие реализовать схемы СУ-перевода и СУ-компиляции. Но прежде чем рассматривать их, необходимо разобраться со способами внутреннего представления программы в компиляторе. От того как исходная программа представляется внутри компилятора, во многомзависят методы, используемые для обработки команд этой программы.
Вставления программы в компиляторе на основе результатов синтаксического анализа. Теперь построим вариант алгоритма генерации кода, который получает на входе дерево операций и создает по нему фрагмент объектного кода для линейного участка результирующей программы. Рассмотрим примеры схем СУ-перевода для арифметических операций. Эти схемы достаточно просты, и на их основе можно проиллюстрировать, как выполняется СУ-перевод в компиляторепри генерации кода.
В качестве формы представления результатов синтаксического разбора возьмем дерево операций (метод, построения дерева операций рассмотрен выше). Для построения внутреннего представления объектного кода (в дальнейшем – просто кода) по дереву операций может использоваться простейшая рекурсивная процедура обхода дерева. Можно использовать и другие методы обхода дерева – важно, чтобы соблюдался принцип, что нижележащие операции в дереве всегда выполняются перед вышележащими операциями (порядок выполнения операций
одного уровня не важен, он не влияет на результат и зависит от порядка обхода вершин дерева).
Процедура генерации кода по дереву операций, прежде всего, должна определить тип узла дерева. Он соответствует типу операции, символом которой помечен узел дерева. После определения типа узла процедура строит код для узла дерева в соответствии с типом операции. Если все узлы следующего уровня для текущего узла есть листья дерева, то в код включаются операнды, соответствующие этим листьям, и получившийся код становится результатом выполнения процедуры. Иначе процедура должна рекурсивно вызвать сама себя для генерации кода нижележащих узлов дерева и результат выполнения включить в свой порожденный код. Фактически, процедура генерации кода должна для каждого узла дерева выполнить конкатенацию цепочек команд, связанных с текущим узлом и с нижележащими узлами. Конкатенация цепочек выполняется таким образом, чтобы операции, связанные с нижележащими узлами, выполнялись до выполнения операции, связанной с текущим узлом.
Поэтому для построения внутреннего представления объектного кода по дереву вывода в первую очередь необходимо разработать формы представления объектного кода для четырех случаев, соответствующих видам текущего узла деревавывода:
−оба нижележащих узла дерева – листья, помеченные операндами;
−только левый нижележащий узел является листом дерева;
−только правый нижележащий узел является листом дерева;
−оба нижележащих узла не являются листьями дерева.
Рассмотрим построение двух видов внутреннего представления по дереву вывода:
1.построение списка триад по дереву вывода;
2.построение ассемблерного кода по дереву вывода.
Далее рассматриваются две функции, реализующие схемы СУ-перевода для каждого их этих случаев.
Литература
Основная:
1.Молчанов А.Ю. Системное программное обеспечение. Учебник для вузов.
— СПб.: Питер, 2003. — 396 с.
2.Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум.- СПб.: Питер, 2005.- 284 с.
3.Юров В.И. Assembler. Учебник для вузов. 2-е издание - СПб.: Питер.- 2004.-
637с.
4.Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование: Основы построения трансляторов + FD.- М.: КОРОНА принт.- 2004.- 255 с.
5.Фельдман Ф.К. Системное программирование на персональном компьютере.- 2004.- 512
6.Ахо А.,Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты: Пер. с англ. — М.: Издательский дом «Вильямс», 2003. — 768 с.
7.Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. —
СПб.: Питер, 2002. — 734 с.
8.Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб.: Питер, 2002. — 544
Дополнительная:
1.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2001. – Ч. 1. – 96 с.
2.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2002. – Ч. 2. – 96 с.
3.Ф.Льюис, Д. Розенкранц, Р.Стирнз. Теоретические основы проектирования компиляторов. М., Мир, 1979.
4.Л. Бек. Введение в системное программирование. М.,Мир, 1988.
5.В.Е.Котов, В.К.Сабельфельд. Теория схем программ. -М.: Наука, 1978
6.Автоматное управление асинхронными процессами в ЭВМ и дискретных системах /Под ред. В.И.Варшавского. -М.:Наука.
7.Питерсон Дж. Теория сетей Петри и моделирование систем.- М.: Наука. 1984.
8.Минский М. Вычисления и автоматы. - М.: Мир.- 1971.
9.Котов В.Е. Сети Петри. - М.: Наука. - 1984.-
10.Ахо А.,Хопкрофт Дж., Ульман Дж.Построение и анализ вычислительных алгоритмов. - М.: Мир. -1979.
11.Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. –
М.: Мир, 1984. – 264 с.