- •Содержание
- •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 Формирование ат-грамматики
- •Решение
5.3.3 Формирование ат-грамматики
Теперь покажем, как по конкретной входной КС-грамматике можно построить АТ-грамматику и определить ее класс.
Задача Дана КС-грамматика G = (VT, Vn, P, S) описания вещественных переменных, где VT- {real, имя, ,}, VN = {DCL, LIST), S = DCL и P - множество правил:
1)DCL -> real имя LIST
2)LIST ->, имя LIST
3)LIST->ε
Требуется сформировать АТ-грамматику описания переменных и распределения памяти под значения этих переменных в некотором блоке памяти. Адрес должен быть помещен в запись таблицы имен для соответствующей переменной. Для определенности положим, что переменной отводится одна нумерованная ячейка памяти.
Решение
1. Определим класс входной грамматики G. Следуя методике, изложенной в разделе LL(k)-грамматики, устанавливаем, что грамматика G обладает свойствами LL(1)-грамматик.
2. Преобразуем входную грамматику в Т-грамматику. Адрес должен быть назначен переменной сразу после чтения во входной строке символа имя. Поэтому операционный символ, который обозначим [ALLOC], располагается в Т-грамматике после каждого терминала имя:
DCL -> real имя [ALLOC] LIST
LIST-*, имя [ALLOC]LIST
3)LIST->ε
3. Определим атрибуты символов Т-грамматики. Атрибут символа имя - указатель на строку таблицы имен. Атрибуты символа DCL:
указатель на начальную ячейку блока памяти для переменных - наследуемый;
указатель на свободную ячейку после обработки всего описания - синтезируемый (от символа LIST в правой части правила).
Атрибуты символа LIST:
указатель на очередную свободную ячейку блока памяти - наследуемый (из левой части правила);
указатель на свободную ячейку после обработки всего описания — синтезируемый (от символа в левой или правой части правила).
Атрибуты символа [ALLOC]:
указатель на строку таблицы имен — наследуемый (от левого символа имя);
адрес ячейки памяти для значения переменной — наследуемый (от символа в левой части правила).
4. Выберем обозначения для атрибутов символов правила, положив i=0,1, ...:
pi — указатель на строку таблицы имен;
bi — указатель на свободную ячейку блока памяти;
ai — адрес, назначенный переменной.
5. Запишем грамматику, приписав символам атрибуты, а за тем пополнив ее комментариями для атрибутов и правилами вычисления их значений. В результате этих действий получим АТ-грамматику:
/*** DCLx1,x2 - наследуемый x1, синтезируемый х2; ***/
/*** LISTy1,y2 - наследуемый y1, синтезируемый у2; ***/
/*** [ALLOC]z1,z2 - наследуемые z1 и z2. ***********/
1) DCLb0,b1 -> real имяр0[АLLОС]p1,a0LISTb2,b3
p1 = p0, a0 = b0,b2 = b0+1, b1 = b3
2) LISTb0,b1 ->, имяр0[АLLОС]p1,a0LISTb2,b3
p1 = p0, a0 = b0,b2 = b0+1, b1 = b3
3) LISTboM -> ε
b1 = b0
Поясним отдельные формулы для вычисления значений атрибутов. Предварительно еще раз уточним функцию операционного символа [ALLOC]. По своей сути это подпрограмма, которая по указателю р1 на элемент таблицы имен для информации о переменной, предшествующей [ALLOC], помещает в определенное поле этого элемента адрес a0 ячейки для значения переменной. Носителем указателя является терминал имя, отсюда формула р1 = р0. Носителем адреса является первый атрибут нетерминала в левой части правила, отсюда формула a0 = b0. Информация о текущей свободной ячейке передается к другим правилам посредством атрибута b2 нетерминала LIST в правой части правила. Номер свободной ячейки на 1 больше последней занятой (формула b2 = b0 + 1). Атрибут b0 символа LIST в правиле 3 будет содержать адрес свободной ячейки после назначения адресов всем элементам списка переменных. Поэтому второй атрибут в этом правиле должен получить значение первого (формула b1 = b0). Формула b1 = b3 позволяет передать это значение атрибуту b1 нетерминала DCL.
6. Определим класс АТ-грамматики.
Для этого проверим выполнение условий для атрибутов из определения L-AT-грамматики. Все эти условия выполняются. Значит, полученная грамматика есть L-AT-грамматика с входной LL(1)-грамматикой.
Порядок вычисления значений атрибутов хорошо иллюстрируется с помощью дерева разбора активной атрибутной цепочки.
Пример Для входной строки real имя5, имя4 и L-AT-грамматики из предыдущей задачи дерево разбора соответствующей активной атрибутной цепочки показано на рис. 5.5. В этом примере начальный адрес в блоке принят равным нулю.
Рисунок 5.5 Дерево разбора активной атрибутной цепочки
real имя5 [ALLOC]5 имя4 [ALLOC]4
После построения безатрибутного дерева оно заполнялось значениями атрибутов. Вычисление наследуемых атрибутов выполнялось раньше синтезируемых и велось в направлении от корня дерева к его листьям. Синтезируемые атрибуты, напротив, вычислялись при движении от листьев к корню. Интересно проследить, как пришедшая сверху информация (номер 2 очередной свободной ячейки) направляется снова вверх после применения правила 3 грамматики. Заметим также, что свойство L-атрибутной грамматики обеспечивает вычисление атрибутов в порядке, пригодном для нисходящей обработки входной строки.
Атрибутную трансляцию, описанную формально АТ - грамматикой, можно выполнить с помощью атрибутного МП - преобразователя, который называют также атрибутным МП - процессором или атрибутной МП - машиной. Выполнение атрибутной трансляции предполагает следующие действия МП - преобразователя:
- последовательное чтение входных символов вместе с их атрибутами;
- проверку принадлежности входной строки языку, определенному входной грамматикой;
- выдачу последовательности атрибутных операционных символов, соответствующей входной строке, из активной атрибутной цепочки.
Атрибутный МП - преобразователь представляет собой обычный МП- преобразователь, у которого состояния, входные, выходные и магазинные символы имеют атрибуты. На каждом шаге работы преобразователя значения атрибутов нового состояния, нового верхнего символа магазина (если этот шаг — не выталкивание из магазина) и выходных символов вычисляются как функции атрибутов старого состояния, верхнего символа магазина и входного символа (если это не пустой шаг). Вопросы построения атрибутных МП - преобразователей здесь рассматривать не будем.