- •Университет наяновой
- •М. А. Шамашов основные структуры данных и алгоритмы компиляции
- •Предисловие
- •Введение
- •1. Краткий обзор процесса компиляции
- •2. Лексический анализ
- •0123...9 Пробел
- •3. Организация таблиц компилятора
- •3.1. Общий вид таблиц
- •3.2. Прямой доступ к таблице или метод индексов
- •3.3. Неупорядоченная таблица или метод линейного списка
- •3.4. Упорядоченная таблица. Бинарный, двоичный или логарифмический поиск
- •3.5. Сбалансированные деревья
- •3.6. Деревья оптимального поиска
- •3.7.1. Рехеширование
- •3.7.3. Метод цепочек или гроздей
- •4. Общие методы синтаксического анализа
- •4.1. Нисходящий разбор с возвратами
- •4.2. Восходящий разбор с возвратами
- •4.3. Символьный препроцессор на основе бэктрекинга
- •4.3.1. Фаза анализа и перевода грамматики во внутреннее представление
- •4.3.2. Лексичекий анализ в сп
- •4.3.3. Синтаксический анализ в сп
- •4.3.4. Выполнение семантических действий
- •5. Однопроходный синтаксический анализ без возвратов
- •5.1. Ll(k) языки и грамматики
- •5.1.1. Предсказывающие алгоритмы разбора и разбор для ll(1)-грамматик
- •5.1.2. Рекурсивный спуск
- •5.2. Языки и грамматики простого предшествования
- •Xy, если u xy
- •X y, если u xU1) (y l(u1))
- •X y, если (u u1y) (X r(u1)) or
- •5.2.1. Алгоритм Вирта–Вебера для анализа языков простого предшествования
- •5.2.2. Функции предшествования.
- •5.2.3. Проблемы построения грамматик предшествования
- •5.3. Операторная грамматика предшествования
- •6. Введение в семантику
- •6.1. Внутренние формы исходной программы
- •6.1.1. Польская инверсная запись
- •If выр then инстр 1 else инстр 2
- •6.1.2. Интерпретация полиЗа
- •6.1.3. Генерирование команд по полиЗу
- •6.1.4. Тетрады и триады
- •6.2. Семантические подпрограммы перевода инфиксной записи в полиз и аспекты их реализации
- •6.3. Семантические подпрограммы для перевода в тетрады
- •6.4. Метод замельсона–бауэра для перевода в полиз и тетрады
- •6.5. Нейтрализация ошибок
- •6.5.1. Исправления орфографических ошибок
- •6.5.2. Нейтрализация семантических ошибок
- •6.5.3. Нейтрализация синтаксических ошибок
- •7. Машинно-независимая оптимизация программ
- •7.1. Исключение общих подвыражений
- •7.2. Вычисления во время компиляции
- •7.3. Оптимизация булевых выражений
- •7.4. Вынесение инвариантных вычислений за цикл
- •8. Машинно-зависимые фазы компиляции
- •8.1. Распределение памяти
- •8.2. Генерация кода и сборка
- •8.3. Трансляция с языка ассемблера
- •Заключение
- •Список литературы
- •Содержание
- •1. Краткий обзор процесса компиляции 5
- •2. Лексический анализ 10
- •3. Организация таблиц компилятора 16
- •4. Общие методы синтаксического анализа 28
- •5. Однопроходный синтаксический анализ без возвратов 52
- •6. Введение в семантику 78
- •7. Машинно-независимая оптимизация программ 102
- •8. Машинно-зависимые фазы компиляции 109
Xy, если u xy
То есть xy , если они стоят рядом в правой части какой-либо продукции именно в отмеченном порядке (x, а сразу следом за ним y).
X y, если u xU1) (y l(u1))
Если в правой части продукции стоит символ x (терминал или нетерминал), а следом за ним нетерминал U1, то x будет всех левых U1 (L(U1)).
X y, если (u u1y) (X r(u1)) or
(U U1U2) (x R(U1)) (y L(U2))
Если в правой части какой–либо продукции указан нетерминал U1, а следом за ним терминал x (напомним, что разбор канонический), то все правые символы U1 (R(U1)) будут x. И далее, если в правой части продукции два нетерминала U1 и U2 стоят рядом, то все самые правые символы U1 (R(U1)) будут левых символов U2 (L(U2)).
# b
( a
a ) b #
# b
( M
a )
b #
# b
(
L
b #
# b
M b
#
# S
#
Рис. 5.10
Для любой сентенциальной формы x1. . .x n основой является самая левая подцепочка x j . . . x i , такая что x j – 1 x j , x jx j + 1, ..., x i -1 x i , x i x i + 1 .
Пример 5.10. На рис. 5.10 представлены шаги свертки цепочки b(aa)b к начальному символу грамматики S. Основы, получаемые на каждом шаге свертки, выделены здесь курсивом и подчеркнуты. Для осуществления последней свертки к цепочке добавляется ограничитель слева и справа (x0 и x n). В качестве символа ограничителя здесь взят символ # и предполагается, что # x и x # для любого x из G.
Контекстно–свободная грамматика G называется грамматикой простого предшествования, или грамматикой (1,1) предшествования или грамматикой предшествования Вирта если:
-
грамматика G однозначно обратима, то есть никакие два правила грамматики не имеют одинаковых правых частей;
-
между любыми двумя символами грамматики существует не более одного отношения предшествования.
5.2.1. Алгоритм Вирта–Вебера для анализа языков простого предшествования
При практическом применении отношений предшествования для распознавания предложений языка потребуется способ компактного представления отношений. Обычно этой цели служит матрица P, элементы которой принимают значения:
P[i,j] = 0, если x i и x j несравнимы (x iy j);
P[i,j] = 1, если x i x j ;
P[i,j] = 2, если x ix j ;
P[i,j] = 3, если x i x j .
Для грамматики предшествования такое представление возможно, так как известно что между любыми двумя символами грамматики определено не более одного отношения. Таким образом, под каждый элемент матрицы можно отвести всего два разряда, но для того чтобы не выполнять лишних действий на выделение разрядов следует, видимо, использовать байтовый массив.
Сами правила грамматики должны располагаться в таблице, имеющей такую структуру, которая позволяет по полученной основе найти правило, содержащее данную основу в качестве правой части продукции, а затем указать соответствующую левую часть.
Неформально работу алгоритма Вирта–Вебера, а именно Н. Виртом и Х. Вебером были определены отношения простого предшествования и данный алгоритм в 1966 году, можно представить следующим образом. Символы входной цепочки просматриваются слева направо и заносятся в магазин (стек) до тех пор, пока не окажется, что верхний символ стека находится в отношении к следующему входному символу. Это означает, что верхний символ стека является хвостом основы и, следовательно, вся основа уже в стеке. Затем полученную основу находят в списке правил грамматики и заменяют тем нетерминалом, из которого она выводится. Процесс повторяется до тех пор, пока в стеке не окажется символ S (начальный символ грамматики) и следующим входным символом станет ограничитель цепочки (в нашем случае – #).
На рис. 5.11 представлена функциональная схема данного алгоритма. Здесь C – стек, Т – входная цепочка, i – номер (позиция) верхнего символа в стеке, k – текущая позиция входной цепочки. Ограничимся небольшими комментариями к отдельным блокам или их группе, используя номера блоков из схемы:
1). В стек заносится ограничитель цепочки – # и индексам по стеку и входной строке присваиваются начальные (0–ые) значения.
2) – 3). Если между символом из вершины стека – C[i] и очередным входным символом – T[k] отношения не определены, то сообщить об ошибке и завершить работу. В противном случае перейти к блоку 4.
4) – 5). Ищется хвост основы. До тех пор, пока между C[i] и T[k] не обнаружится отношения , текущий входной символ помещается в стек, извлекается следующий входной символ и осуществляется переход к блоку 2. Если хвост основы найден (C[i] T[k]), то переходим к блоку 6.
6) – 8). Осуществляется поиск головы основы в стеке. На нее будет указывать индекс j.
9). Найденная основа ищется среди правых частей продукций заданной грамматики. Если поиск успешен, то осуществляется переход к блоку 10, иначе – к блоку 12.
10) – 11). Основа в стеке заменяется нетерминалом U – левой частью правила, обнаруженного в блоке 9. Затем выполняется семантическая подпрограмма, связанная с данным правилом грамматики и осуществляется переход к блоку 2.
12)–14). Сюда мы попадаем, когда обнаруженная основа ни к чему не приводится. Это может случиться тогда, когда в стеке кроме левого ограничителя цепочки записан начальный символ грамматики и очередной входной символ – правый ограничитель. В этом случае вся цепочка была свернута к начальному символу грамматики, исходная цепочка принадлежит рассматриваемому языку и алгоритм завершает работу сообщив об успешном окончании. В противном случае, для найденной основы просто не обнаружено соответствующего правила грамматики, и алгоритм также завершит работу, сообщив об ошибке.
Пример 5.11. На рис. 5.12 разобрана по шагам работа изложенного алгоритма для правильной цепочки b(aa)b языка из примера 5.8 с матрицей предшествования с рис. 5.9 б.
Шаги |
С0 |
С1 |
С2 |
С3 |
С4 |
С5 |
Отношение |
Т k |
|
|
|
|
|
|
0 |
# |
|
|
|
|
|
|
b |
( |
a |
a |
) |
b |
# |
1 |
# |
b |
|
|
|
|
|
( |
a |
a |
) |
b |
# |
|
2 |
# |
b |
( |
|
|
|
|
a |
a |
) |
b |
# |
|
|
3 |
# |
b |
( |
a |
|
|
|
a |
) |
b |
# |
|
|
|
4 |
# |
b |
( |
M |
|
|
|
a |
) |
b |
# |
|
|
|
5 |
# |
b |
( |
M |
a |
|
|
) |
b |
# |
|
|
|
|
6 |
# |
b |
( |
M |
a |
) |
|
b |
# |
|
|
|
|
|
7 |
# |
b |
( |
L |
|
|
|
b |
# |
|
|
|
|
|
8 |
# |
b |
M |
|
|
|
|
b |
# |
|
|
|
|
|
9 |
# |
b |
M |
b |
|
|
|
# |
|
|
|
|
|
|
10 |
# |
S |
|
|
|
|
|
# |
|
|
|
|
|
|
Рис. 5.12
На рис. 5.13 а представлен пример разбора ошибочной цепочки babb, где причиной ошибки является отсутствие отношений между символами b и b, а на рис. 5.13 б показан пример цепочки ba , где ошибка возникает из–за отсутствия обнаруженной основы bM среди правых частей правил грамматики.
Завершая обсуждение алгоритма Вирта–Вебера, заметим, что в нем и других подобных распознавателях есть одно очень привлекательное свойство: нет необходимости хранить в памяти одновременно всю цепочку входных символов (если только грамматика не из ряда вон выходящая). Символы считываются с входного носителя по одному и заносятся в стек, но после редукции основы те символы, что входили в нее исчезают. Всю цепочку приходится хранить в памяти только в том случае, когда основа находится в правом конце цепочки, но грамматики языков программирования никогда не строятся подобным образом.