- •Содержание
- •1 Формальные языки и грамматики
- •1.1 Основные понятия теории формальных языков
- •Определение Цепочка, которая не содержит ни одного символа, называется пустой цепочкой и обозначается .
- •1.2 Способы задания языков
- •1.2.1 Формальные грамматики
- •1.2.1.1 Определение формальной грамматики
- •Определение Цепочка (vtvn)* выводима из цепочки в грамматике(обозначается*), если существует последовательность цепочек (n0) такая, что .
- •1.2.1.3 Эквивалентность грамматик
- •1.2.2 Формы Бэкуса - Наура
- •1.2.3 Диаграммы Вирта
- •1.2.5 Механизмы распознавания языков
- •1.2.5.1 Определение распознавателя
- •1.2.5.2 Схема работы распознавателя
- •1.2.5.3 Классификация распознавателей
- •2 Регулярные грамматики и языки
- •2.1 Регулярные выражения
- •2.2 Лемма о разрастании языка
- •2.3 Конечные автоматы
- •2.3.1 Определение конечного автомата
- •2.3.2 Распознавание строк конечным автоматом
- •Существуют следующие способы представления функции переходов: - командный способ.Каждую команду ка записывают в форме , где.
- •2.3.3 Преобразование конечных автоматов
- •2.3.3.1 Преобразование конечного автомата к детерминированному виду
- •Алгоритм Преобразование нка в дка
- •2.3.3.2 Минимизация конечного автомата
- •2.3.3.2.1 Устранение недостижимых состояний ка
- •2.3.3.2.2 Объединение эквивалентных состояний ка Алгоритм Объединение эквивалентных состояний ка
- •2.4 Взаимосвязь способов определения грамматик
- •2.4.1 Построение ка по регулярной грамматике
- •Выход:ка.
- •3 Контекстно-свободные языки и грамматики
- •3.1 Задача разбора
- •3.1.1 Вывод цепочек
- •Определение Цепочка (vtvn)* выводима из цепочки в грамматике(обозначается*), если существует последовательность цепочек (n0) такая, что .
- •3.1.2 Дерево разбора
- •3.1.2.1 Нисходящее дерево разбора
- •3.1.2.2 Восходящее дерево разбора
- •3.1.3 Однозначность грамматик
- •3.2 Преобразование кс-грамматик
- •3.2.1 Проверка существования языка грамматики
- •3.2.2 Устранение недостижимых символов
- •Алгоритм Устранение нетерминалов, не порождающих терминальных строк Вход: кс-грамматика.
- •Алгоритм Устранение недостижимых символов Вход: кс-грамматика.
- •Определим множество достижимых символов z грамматики g, т.Е. Множество
- •3.2.3 Устранение -правил Алгоритм Устранение -правил Вход: кс-грамматика.
- •3.2.4 Устранение цепных правил Алгоритм Устранение цепных правил Вход: кс-грамматика.
- •3.2.5 Левая факторизация правил Алгоритм Устранение левой факторизации правил Вход: кс-грамматика.
- •3.2.6 Устранение прямой левой рекурсии Алгоритм Устранение прямой левой рекурсии Вход: кс-грамматика.
- •3.3 Автомат с магазинной памятью
- •3.3.1 Определение мп-автомата
- •3.3.2 Разновидности мп-автоматов
- •3.3.3 Взаимосвязь мп-автоматов и кс-грамматик
- •3.3.3.1 Построение мп-автомата по кс-грамматике
- •3.3.3.2 Построение расширенного мп-автомата по кс-грамматике
- •3.4 Нисходящие распознаватели языков
- •3.4.1 Рекурсивный спуск
- •3.4.1.1 Сущность метода
- •3.4.1.2 Достаточные условия применимости метода рекурсивного спуска
- •3.4.2 Распознаватели ll(k)-грамматик
- •3.4.2.1 Определение ll(k)-грамматики
- •3.4.2.2 Необходимое и достаточное условие ll(1)-грамматики
- •3.4.2.3 Построение множества first(1, a)
- •3.4.2.4 Построение множества follow(1, a)
- •3.4.2.5 Алгоритм «сдвиг-свертка» для ll(1)-грамматик
- •Шаг 6. Получили следующую цепочку вывода:
- •3.5.1.1.2 Поиск основы сентенции грамматики
- •3.5.1.1.3 Построение множеств l(a) и r(a)
- •3.5.1.1.5 Алгоритм «сдвиг - свертка» для грамматик простого предшествования
- •Шаг 3. Функционирование распознавателя для цепочки (((aa)a)a) показано в таблице 3.9.
- •3.5.1.2 Грамматика операторного предшествования
- •3.5.1.2.1 Определение грамматики операторного предшествования
- •3.5.1.2.2 Построение множеств Lt(a) и Rt(a)
- •3.5.1.2.4 Алгоритм «сдвиг-свертка» для грамматики операторного предшествования
- •3.5.2 Распознаватели lr(k)-грамматик
- •3.6 Соотношение классов кс-грамматик и кс-языков
- •3.6.1 Соотношение классов кс-грамматик
- •3.6.2 Соотношение классов кс-языков
- •4 Принципы построения языка
- •4.1 Лексика, синтаксис и семантика языка
- •4.2 Определение транслятора, компилятора, интерпретатора и ассемблера.
- •4.3 Общая схема работы компилятора
- •4.4 Лексический анализ
- •4.4.1 Задачи лексического анализа
- •4.4.2 Диаграмма состояний с действиями
- •4.4.3 Функция scanner
- •4.5 Синтаксический анализатор программы
- •4.5.1 Задача синтаксического анализатора
- •4.5.2 Нисходящий синтаксический анализ
- •Теорема Достаточные условия применимости метода рекурсивного спуска
- •4.6 Семантический анализ программы
- •4.6.1 Обработка описаний
- •4.6.2 Анализ выражений
- •4.6.3 Проверка правильности операторов
- •4.7 Генерация кода
- •4.7.1 Формы внутреннего представления программы
- •4.7.1.1 Тетрады
- •4.7.1.2 Триады
- •4.7.1.3 Синтаксические деревья
- •4.7.1.4 Польская инверсная запись
- •Составной оператор begin s1; s2;...; Sn end в полиЗе записывается как s1 s2... Sn.
- •4.7.1.5 Ассемблерный код и машинные команды
- •4.7.2 Преобразование дерева операций в код на языке ассемблера
- •4.8 Оптимизация кода
- •4.8.1 Сущность оптимизации кода
- •4.8.2 Критерии эффективности результирующей программы
- •4.8.3 Методы оптимизации кода
- •4.8.4 Оптимизация линейных участков программ
- •4.8.4.1 Свертка объектного кода
- •4.8.4.2 Исключение лишних операций
- •4.8.5 Оптимизация логических выражений
- •4.8.6 Оптимизация циклов
- •4.8.7 Оптимизация вызовов процедур и функций
- •4.8.9 Машинно-зависимые методы оптимизации
- •4.8.9.1 Распределение регистров процессора
- •4.8.9.2 Оптимизация кода для процессоров, допускающих распараллеливание вычислений
- •5 Формальные методы описания перевода
- •5.1 Синтаксически управляемый перевод
- •5.1.1 Схемы компиляции
- •5.1.4 Практическое применение су-схем
- •5.2 Транслирующие грамматики
- •5.2.1 Понятие т-грамматики
- •5.3 Атрибутные транслирующие грамматики
- •5.3.1 Синтезируемые и наследуемые атрибуты
- •5.3.2 Определение и свойства ат-грамматики
- •5.3.3 Формирование ат-грамматики
- •Решение
4.8.9.2 Оптимизация кода для процессоров, допускающих распараллеливание вычислений
Многие современные процессоры допускают возможность параллельного выполнения нескольких операций. Как правило, речь идет об арифметических операциях.
Тогда компилятор может порождать объектный код таким образом, чтобы в нем содержалось максимально возможное количество соседних операций, все операнды которых не зависят друг от друга. Решение такой задачи в глобальном объеме для всей программы в целом не представляется возможным, но для конкретного оператора оно, как правило, заключается в порядке выполнения операций. В этом случае нахождение оптимального варианта сводится к выполнению перестановки операций (если она возможна, конечно). Причем оптимальный вариант зависит как от характера операции, так йот количества имеющихся в процессоре конвейеров для выполнения параллельных вычислений. Например, операцию A+B+C+D+E+F на процессоре с одним потоком обработки данных лучше выполнять в порядке ((((A+B)+C)+D)+Е)+F. Тогда потребуется меньше ячеек для храпения промежуточных результатов, а скорость выполнения от порядка операций в данном случае не зависит.
Та же операция на процессоре с двумя потоками обработки данных в целях увеличения скорости выполнения может быть обработана в порядке ((А+В)+С)+ +((D+E)+F). Тогда по крайней мере операции А+В и D+E, а также сложение с их результатами могут быть обработаны, в параллельном режиме. Конкретный порядок команд, а также распределение регистров для хранения промежуточных результатов будут зависеть от типа процессора.
На, процессоре с тремя потоками обработки данных ту же операцию можно уже разбить на части в виде (A+B)+(C+D)+(E+F). Теперь уже три операции А+В, C+D и E+F могут быть выполнены параллельно. Правда, их результаты уже должны быть обработаны последовательно, но тут уже следует принять во внимание соседние операции для нахождения наиболее оптимального варианта.
5 Формальные методы описания перевода
5.1 Синтаксически управляемый перевод
5.1.1 Схемы компиляции
Выделяют две основные схемы компиляции:
- последовательную;
- интегрированную.
Последовательная схема представляет собой - совокупность последовательно выполняемых программных компонентов, каждый из которых соответствует одному этапу компиляции (рис. 5.1.1). Последовательная схема предполагает не менее одного просмотра (прохода) программы на каждом этапе. Например, при генерации кода может выполняться два просмотра, а каждый метод машинно-независимой оптимизации требует по крайней мере одного просмотра. Рассмотренные методы построения промежуточной программы не требуют наличия разбора, и синтаксический анализатор может вообще не выполнять никакого преобразования программы. Последовательная схема, несомненно, проста и понятна, но она громоздка (по объему занимаемой памяти и времени компиляции программы) и применяется редко.
Интегрированная схема компиляции – схема, в которой компоненты выполняются под управлением синтаксического анализатора. Синтаксический анализатор, осуществляя разбор программы, вызывает лексический анализатор для сборки лексемы, когда в этом возникает необходимость. После завершения распознавания каждой синтаксической единицы программы вызывается семантический анализатор для ее обработки. Главная идея состоит в том, чтобы в ходе построения дерева разбора решать задачи последующих этапов компиляции для каждого вновь сформированного узла.
Рис. 5.1 - Схемы компиляции: а - последовательная,
б - интегрированная
Естественно, интеграция приводит к усложнению алгоритмов компиляции. Поэтому выбор подходящей структуры компилятора — непростая задача. Тем не менее, обычно строят компиляторы так, что на выходе синтаксического анализатора получается, как минимум, промежуточная программа в той или иной форме.
5.1.2 СУ-схемы
Интегрированные схемы компиляции базируются на теории перевода языков, ключевыми понятиями которой являются схема синтаксически управляемого перевода (СУ-схема), синтаксически управляемый перевод (СУ-перевод), преобразователь с магазинной памятью (МП - преобразователь). Рассмотрим эти понятия.
Определение. СУ-схемой Т называется пятерка следующих объектов
T={VT, VN, ,R,S), где
VT — конечный входной алфавит, терминалы;
VN — конечное множество нетерминалов;
— конечный выходной алфавит;
R — конечное множество правил вида A ->, где V*,
(VN )*;
S — аксиома (начальный символ) схемы.
Определение. СУ-схема называется простой, если в каждом правиле А-> одноименные нетерминалы встречаются в и в одном и том же порядке. СУ-схема называется постфиксной, если VN * * в каждом правиле {А->) R.
Определение. СУ-переводом , определяемым (генерируемым) СУ-схемой T={VT, VN, ,R,S), называется множество пар
Грамматика GBX = {VT, VN, P,S), где Р = {А -> | (А -> ) R}, называется входной грамматикой СУ-схемы. Грамматика GВЫХ ={,VN, P’,S), где P’ = {А -> | (А -> ) R}, называется выходной грамматикой СУ-схемы.
Пример Рассмотрим СУ-схему Т1 перевода арифметических выражений в обратную польскую запись. В основе этой схемы лежит соответствие правил записи арифметических выражений в обычной (инфиксной) форме и в ПОЛИЗ. Для упрощенных выражений такое соответствие приводится ниже.
Правила инфиксной формы Правила ПОЛИЗ
S->E S->E
E->E+T E->ET+
E->T E->T
T->T*F T->TF*
T->F T->F
F->(E) F->E
F-> имя F->имя
СУ-схема Т1 представляется пятеркой Т1 = {VT, VN, ,R,S), где S — аксиома, VT= {+, *, имя, (,)}; = {+, *, имя}; VN= {S, Е,T, F} и множество R содержит следующие правила:
1)S ->E,E 2)E->E+T,ET+ 3)E->T,T 4)T->T*F,TF* 5)T->F,F 6)F->(E),E 7)F ->имя, имя
Входной грамматикой СУ-схемы Т1 является GВХ = (Vt, Vn, Р, S), где множество правил Р представлено правилами инфиксной формы. GВЫХ= (, Vn, P’ , S) — выходная грамматика СУ-схемы T1, а ее правила Р’ — это правила ОПЗ. Как показывает анализ правил СУ-схемы, Т1 — простая постфиксная СУ-схема. Нетрудно убедиться также, что в ней существует, например, вывод (S, S) =>* (a+b*c, abc*+), порождающий элемент перевода (а+b*с, abc*+) (T1).
5.1.3 МП-преобразователи
МП - преобразователи позволяют формально описать соответствующие действия, связанные не только с распознаванием синтаксических конструкций, но и с построением дерева разбора (вывода) и его преобразованием, а также действия, которые имеют как синтаксический, так и семантический характер.
Определение. МП - преобразователем называют восьмерку вида
Q - конечное множество состояний преобразователя;
- конечный входной алфавит;
Г - конечный магазинный алфавит;
- конечный выходной алфавит;
- отображение множества (Q * (* Г) в множество всех подмножеств множества (Q * Г** *), т.е.
qо - начальное состояние преобразователя, q0 Q;
Zo - начальное содержимое магазина, Zo Г;
F - множество заключительных состояний преобразователя, F Q.
Определение. Конфигурация МП - преобразователя — это четверка (q,w, , у) (Q х * х Г* х *). Начальная конфигурация — (q0 ,w, Zo,), заключительная конфигурация — (q, , , у), где q F. Если одним из значений функции (q, a, Z) является (q’, ,r), то шаг работы преобразователя можно представить в виде отношения на конфигурациях
(q, aw, Za, у) |- (q’,wо, а, уr) для любых w *, Г*, у *.
Строка у будет выходом МП - преобразователя для строки w, если существует путь от начальной до заключительной конфигурации
(qо, w, Zo, ) |-* (q, , , у) для некоторых q F и Г*.
Определение. Переводом (преобразованием) , определяемым МП - преобразователем Р, называется множество
(Р) = {(w,у) | (q0,w, Zo, )|-*(q, , ,у) для q F, Г*.
Определение. МП - преобразователь будет детерминированным, если, как и МП - автомат, он имеет не более одной возможной очередной конфигурации. Расширенный МП - преобразователь отличается от рассмотренного только магазинной функцией
: (Q х () х Г*) -> P(Q х Г* х*).
Теперь обратимся к двум результатам теоретических исследований, имеющим чрезвычайно важное практическое значение. Они состоят в следующем.
Если T={VT, VN, ,R,S) - простая СУ-схема с входной грамматикой LL(k), то СУ-перевод (Т) можно осуществить детерминированным МП - преобразователем.
Если T={VT, VN, ,R,S) - простая постфиксная СУ-схема с входной грамматикой LR(k), то перевод (T) можно выполнить детерминированным МП - преобразователем.
Существуют алгоритмы, позволяющие построить детерминированный МП - преобразователь по заданной СУ-схеме перевода. В их основе лежат алгоритмы построения таблиц разбора.
Простые СУ-переводы образуют важный класс переводов, поскольку для каждого из них можно построить детерминированный МП - преобразователь, отображающий входную строку (цепочку) в выходную строку (цепочку). Такие переводы иногда называют цепочечными.