Классическая теория компиляторов

• Название: Классическая теория компиляторов
• Дата: 27.05.2019
• Размер: 1.25 Mb.
• Имя файла: Compiler1.pdf
• Тип: Документы; #79118
• страница: 3 из 6

ПОСТРОЕНИЕ ДКА ПО НКА
Обычно при описании тех или иных объектов наличие дополнительных ограничений снижает общность. Однако большая общность НКА по сравнению с ДКА является кажущейся. Дело в том, что справедливо следующее утверждение:
Для любого НКА можно построить эквивалентный ему конечный
детерминированный автомат.
Для построения детерминированного автомата можно воспользоваться следующей теоремой:
Теорема. Пусть НКА F= (,Q,q
0
,T,P) допускает множество цепочек L.
Определим ДКА F'= (',Q',q
0
',T',P') следующим образом:
1) Множество состояний Q' состоит из всех подмножеств множества Q.
Обозначим элемент множества Q' через [S
1
,S
2
,..,S
l
], где S
1
,S
2
,..,S
l
Q.
2) ' = .
3) Отображение P' определяется как
P'([S
1
,S
2
,..,S
m
],x) = [R
1
,R
2
,..,R
m
], где P({S
1
,S
2
,..,S
m
},x) = { R
1
,R
2
,..,R
m
}, S
i
,R
i
Q, x.
4) Пусть q
0
={S
1
,S
2
,..,S
k
}.
Тогда q
0
'=[S
1
,S
2
,..,S
k
].
5) Пусть множество заключительных состояний T={S
j
, S
k
,.., S
n
}.
Тогда T'=[S
j
, S
k
,.., S
n
].
Или, иначе,
T'={t=[S
a
,S
b
,..,S
c
] |  S
b
: S
b
T}.
Построенный таким образом детерминированный конечный автомат будет эквивалентен в смысле "вход-выход" исходному НКА.
Приведем пример построения
ДКА по
НКА.
Пусть дан недетерминированный автомат

28
S
Z
P
0 1
1,0 1
1 1
Правила переходов: {S1S, S1Z, S0P, P1Z, P0Z, Z1P, Z1S}.
Начальные состояния: {S, P}.
Заключительные состояния: {Z}.
Множество состояний ДКА будет таким: {S, P, Z, PS, SZ, PSZ, PZ}. Их будет ровно 2
n
-1, где n – количество состояний исходного автомата.
Его правила переходов:
{S1SZ, S0P, P1Z, P0Z, Z1PS, PS1SZ, PS0PZ, SZ1PSZ,
PSZ1PSZ, PZ1PSZ}.
Начальное состояние: SP.
Заключительные состояния: {Z, PZ, SZ, PSZ}.
Тогда детерминированный автомат будет выглядеть так:
PZ
Z
PS
0 1,0 1
1
SZ
1
PSZ
1 1
S
1
P
0

29
После упрощения автомата, т.е. удаления вершин, не достижимых из начальной, получим такой автомат:
PZ
PS
0 1
SZ
1
PSZ
1 1
Завершая рассуждения о недетерминированных автоматах, следует отметить еще один момент, связанный с множеством начальных состояний
(н.с.) в НКА. Когда имеется несколько н.с., работа автомата заключается в том, что переход по входному символу осуществляется одновременно из всех
начальных состояний. Именно в этом заключается суть процедуры объединения всех н.с. в одно. Это особенно важно при моделировании НКА, скажем, средствами Пролога.
ОБ УСЛОВИЯХ ЗАВЕРШЕНИЯ РАБОТЫ АВТОМАТА
Как уже говорилось, автомат завершает свою работу при достижении в одно из заключительных состояний. Однако с практической точки зрения бывает иногда целесообразно использовать несколько модифицированный автомат со следующим условием завершения работы:
Автомат нормально завершает работу тогда, когда он попадает в
одно из заключительных состояний и при этом входная последовательность
исчерпана.
Эта ситуация характерна для непрямых лексических анализаторов.
Таким образом, можно рассматривать два вида распознающих автоматов: автоматы для прямых лексических анализаторов (А
ПЛА
) и автоматы для непрямых анализаторов (А
НЛА
).
Рассмотрим в качестве примера некоторый конечный автомат:

30 1
0 0
1 0
0 0
A
B
C
D
1
Начальное состояние q
0
=A, множество терминальных состояний T={D}.
Распишем грамматику, соответствующую этому автомату (или, строже, рассмотрим грамматику, порождающую язык, распознаваемый данным автоматом).
Для начала выпишем правила подстановок, которые получаются явным образом из правил переходов автомата. Ниже слева представлены правила переходов автомата, справа – соответствующие правила грамматики:
№ Правила перехода
Правила грамматики
1
A0A
A0A
2
A1B
A1B
3
B0C
B0C
4
B1A
B1A
5
C0A
C0A
6
C1D
C1D
7
D0D
D0D
8
D1A
D1A
Очевидно, что подобные правила грамматики не смогут породить язык.
Дело в том, что в них отсутствуют терминальные подстановки, т.е. те правила, в правой части которых были бы одни терминальные символы.
В зависимости от условия завершения работы автомата будут разниться и правила соответствующих грамматик.
Для А
ПЛА
, завершающего свою работу при попадании в терминальное состояние, меняется правило №6:
C1D преобразуется в терминальную подстановку C1, т.к. D – терминальное состояние.

31
Формально терминальные правила получаются из правил грамматики путем отбрасывания имен терминальных состояний в правой части. Таких правил у нас два – правила №6 и 7, однако правило № 7, равно как и №8, являются для нашей грамматики лишними (недостижимыми). Это видно из автомата: переходы D0D и D1A в А
ПЛА
не работают.
Для грамматики, соответствующей А
НЛА
, напротив, происходит добавление правил подстановки. Добавляются все терминальные правила, т.е. правила, в правой части которых отбрасываются терминальные состояния.
Таким образом, к имеющимся восьми правилам грамматики добавляются правила C1 (из правила №6) и D0 (из правила №7).
ПРОГРАММИРОВАНИЕ СКАНЕРА
Итак, теперь все готово к тому, чтобы приступить к построению сканера. Напомним, что нам необходимо построить лексический анализатор для выделения из входного потока исходных составляющих языка – лексем или символов. Символами являются:
- разделители или операторы (+,-,*,/,(,) и т.п.);
- служебные слова (что-то вроде begin, end,... и т.п.);
- идентификаторы;
- числа.
Кроме того, необходимо исключать комментарии (как строчные, типа '//', так и многострочные, вида '/*...*/').
Строить сканер мы будем, используя конечный автомат. К автомату предъявляются следующие минимальные требования:
1. Автомат должен формировать поток лексем;
2. Автомат должен заносить полученные лексемы в таблицу символов или имен.
Наш распознающий автомат упрощенно может выглядеть следующим образом:

32
S
int id sla com
R
end
S
D
S
S
error
/
*
*
/
delim
D
L,D
L
S
S
иначе
Здесь под символом D понимается цифра, L означает букву, а delim – разделитель (пробел, табуляцию и т.п.). Состояние int отвечает за распознавание числа, id – за распознавание имени, а sla, com, end и R – за распознавание комментариев. Чтобы не загромождать схему дугами, переходы в основное состояние S обозначены дублированием этой вершины.
При этом следует отметить, что
1. При переходе в начальное состояние S иногда требуется возвращать обратно считываемый символ входной последовательности, т.е. необходимо сместить указатель на одну позицию назад. Иначе мы просто будем терять часть лексем, т.к. автомат – это устройство, последовательно считывающее очередной входной символ на каждом такте работы.
2. Автомат в таком виде бесполезен, он не выполняет никаких полезных процедур.
Следовательно, автомат необходимо дополнить процедурной частью.
Именно процедурная часть отвечает за формирование имен, которые далее будут заноситься в таблицу символов, за возврат считанного символа обратно во входной поток, за инициализацию и т.д. Дополнение автомата этой процедурной частью автомата заключается в том, что когда автомат совершает очередной переход, должна выполняться связанная с этим

33 переходом одна или несколько процедур (или подпрограмм). Это, разумеется, несколько усложняет структуру автомата, однако эту работу выполнять необходимо, т.к. мы занимаемся не только проверкой входной последовательности, но и ее преобразованием в поток лексем.
ОРГАНИЗАЦИЯ ТАБЛИЦ СИМВОЛОВ. ХЕШ-ФУНКЦИИ
При трансляции программы для каждого нового идентификатора в таблицу символов добавляется элемент. Однако поиск элементов ведется всякий раз, когда встречается этот идентификатор. Так как на этот процесс уходит много времени, необходимо выбрать такую организацию таблиц, которая допускала бы прежде всего эффективный поиск.
Простейший способ организации – использовать неупорядоченную таблицу. Новый элемент добавляется в таблицу в порядке поступления.
Среднее время поиска пропорционально n/2 (в среднем приходится делать n/2 сравнений).
Элементы таблицы можно отсортировать. Тогда можно использовать процедуру бинарного поиска, при котором максимальное число сравнений будет равно 1+log
2
n. Однако сортировка – это слишком трудоемкая процедура для того, чтобы ее использовать при организации таблиц.
ХЕШ-АДРЕСАЦИЯ
Идеальный вариант – уметь по имени сразу определить адрес элемента.
В этом смысле "хорошей" процедурой поиска является та, которая сможет определить хотя бы приблизительный адрес элемента. Одним из наиболее эффективных и распространенных методов реализации такой процедуры является хеш-адресация.
Хеш-адресация – это метод преобразования имени в индекс элемента в таблице. Если таблица состоит из N элементов, то им присваиваются номера
0,1,..,N-1. Тогда назовем хеш-функцией некоторое преобразование имени в адрес. Простейший вариант хеш-функции – это использование внутреннего представления первой литеры имени.
Пока для двух различных символов результаты хеширования различны, время поиска совпадает с временем, затраченным на хеширование. Однако, все проблемы начинаются тогда, когда результаты хеширования совпадают для двух и более различных имен. Эта ситуация называется коллизией.
Хорошая хеш-функция распределяет адреса равномерно, так что коллизии возникают не слишком часто. Но прежде, чем говорить о реализации хеш-функций, обратимся к вопросу о том, каким образом разрешаются коллизии.

34
СПОСОБЫ РЕШЕНИЯ ЗАДАЧИ КОЛЛИЗИИ. РЕХЕШИРОВАНИЕ
Пусть хешируется имя S и при этом обнаруживается коллизия.
Обозначим через h значение хеш-функции. Тогда сравниваем S с элементом по адресу (h+p
1
)mod N, где N – длина таблицы (максимальное число элементов в таблице). Если опять возникает коллизия, то выбираем для сравнения элемент с адресом (h+p
2
)mod N и т.д. Это будет продолжаться до тех пор, пока не встретится элемент (h+p i
)mod N, который либо пуст, либо содержит S, либо снова является элементом h (p i
=0, и тогда считается, что таблица полна).
Способы рехеширования заключаются в выборе чисел p
1
,p
2
,..,p n
Рассмотрим наиболее распространенные из них.
Для начала введем параметр, называемый коэффициентом загрузки
таблицы lf: lf = n/N, где n – текущее количество элементов в таблице, N – максимально возможное число элементов.
Линейное рехеширование
p i
= i (т.е. p
1
=1, p
2
=2,..,p n
=n).
Среднее число сравнений E при коэффициенте загрузки lf определяется как
E(lf) = (1-lf/2)/(1-lf).
Это – очень неплохой показатель. В частности, при 10-ти процентной загрузке имеем E, равное 1.06, при 50-ти процентном заполнении E равно всего 1.5, а при 90 процентах загрузки требуется сделать в среднем всего 5.5 сравнений.
Ниже приведен график этой функции:
0 0.2 0.4 0.6 0.8 1
1 10 100

lf
Случайное рехеширование
Пусть максимальное число элементов в таблице кратно степени двойки, т.е. N=2
k
. Вычисление p i
осуществляется по следующему алгоритму:
1) R := 1 2) Вычисляем p i
: a) R := R*5 b) выделяем младшие k+2 разрядов R и помещаем их в R

35 c) p i
:= R>>1 (сдвигаем R вправо на 1 разряд)
3) Перейти к П.2
Среднее число сравнений E при коэффициенте загрузки lf
E = -(1/lf)log
2
(1-lf)
Рехеширование сложением
p i
= i(h+1), где h – исходный хеш-индекс.
Этот метод хорош для N, являющихся простыми числами.
ХЕШ-ФУНКЦИИ
Как уже говорилось, хеш-адресация – это преобразование имени в индекс. Имя представляет множество литер (символов), и для вычисления индекса поступают обычно следующим способом:
1) Берется S', являющееся результатом суммирования литер из исходного символа S (либо простое суммирование, либо поразрядное исключающее
ИЛИ):
S'
S 
^ +
2) Вычисляется окончательный индекс. При этом возможны самые различные варианты. В частности: a) Умножить S' на себя и использовать n средних битов в качестве значения h (для N=2
n
); b) Использовать какую-либо логическую операцию
(например, исключающее ИЛИ) над некоторыми частями S'; c) Если N=2
n
, то разбить S' на n частей и просуммировать их.
Использовать n крайних правых битов результата; d) Разделить S' на длину таблицы, и остаток использовать в качестве хеш- индекса.
Итак, хорошая хеш-функция – это та, которая дает как можно более равномерное и случайное распределение индексов по именам, т.е. для "похожих" или "близких" имен хеш-функция должна выдавать сильно разнящиеся индексы, т.е. не допускает группировки имен в таблице символов.
Приведем пример фрагмента программы, реализующей хеш-адресацию:

36 struct name
//элемент таблицы символов
{ char *string; //имя name *next; //ссылка на следующий элемент double value;
//значение
}; const TBLSIZE = 23; // Количество "ящиков", по которым раскладываем символы name *table[TBLSIZE]; name *findname(char *str, int ins)
// Функция поиска в таблице имени name
// Если ins!=0, то происходит добавление элемента в таблицу
{ int hi = 0;
//Это, фактически, наш хеш-индекс char *pp = str;
// Суммируем по исключающему ИЛИ каждый символ строки.
// Далее сдвигаем для того, чтобы индекс был лучше
// (исключаем использование только одного байта) while (*pp)
{ hi<<=1; // На самом деле здесь лучше применить циклический сдвиг hi^= *pp++;
} if (hi<0) hi = -hi;
//Берем остаток hi %= TBLSIZE;
//Поиск. Мы нашли список, теперь используем
// метод линейного рехеширования for(name *n=table[hi];n;n=n->next) if(strcmp(str,n->string)==0) return n;
//Нашли. Возвращаем адрес
//Ничего не нашли if(ins==0) return NULL; // error("Имя не найдено")
//Добавляем имя name *nn = new name; nn->string = new char[strlen(str)+1]; strcpy(nn->string, str); nn->value = 0; nn->next = table[hi]; table[hi] = nn; return nn;
}
В данном примере таблица символов представляет собой не линейный список, а множество списков, адреса начала которых содержатся в некотором массиве. (Представьте себе аналогию с множеством ящиков, в которых и

37 осуществляется поиск. Тогда хеш-индекс будет представлять собой номер некоторого ящика.)
Условно механизм работы с подобной организацией таблицы символов можно изобразить так:
Table
1 2
3
TBLSIZE
Исходное состояние
Table
1 2
3
TBLSIZE
Процесс добавления нового элемента string next string next
Хеш-индекс string next string next string next
Новый элемент
КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ
Следующей по сложности за регулярной грамматикой следует контекстно-свободная (context-free) грамматика (КСГ).
Естественно, определение КСГ внешне выглядит как и обычное определение грамматики:G
ксг
= (N, , P, S), однако при этом характерным для
КСГ является форма ее правил (продукций)
P: A, где AN,  (N)
+

38
В качестве примера рассмотрим, как мог бы выглядеть некий командный, внешне приближенный к естественному язык:
N = {группа_существ, глагол, прилагательное, существительное,
предлог, фраза}

= {печатать, стереть, зеленый, первый, последний, символ, строка,
страница, в}
S = фраза
P = { Фр

Г, Гс
Гс

Прил, С
Гс

Прил, С, Предлог, Гс
Г

печатать
Г

стереть
Прил

зеленый
Прил

первый
Прил

последний
С

символ
С

строка
С

страница
Предлог

в}
Эта грамматика может порождать фразы вроде "Печатать зеленый
строка", "Стереть первый символ в последний строка в первый страница" и т.п. Синтаксическая проверка подобных предложений может быть осуществлена путем простого перебора возможных подстановок правил грамматики. Например, анализатор предложений такого языка на Прологе может выглядеть так:
/*
АНАЛИЗАТОР КС-ГРАММАТИКИ
Фраза -> Глагол, Группа_сущ
Группа_сущ -> Прилагат, Существ
Группа_сущ -> Прилагат, Существ, Предлог, Группа_сущ
Глагол -> ...
Прилагат -> ...
Существ -> ...
Предлог -> ...
*/ goal
FRAZA = ["печатать","первый","символ","в","последний","строка"], print_list(FRAZA), s(FRAZA). clauses s(A) :- sentence(A), write("\nФРАЗА РАСПОЗНАНА\n").

39 s(_) :- write("\nОШИБКА: ФРАЗА НЕ РАСПОЗНАНА\n").
% СЛУЖЕБНЫЕ И СЕРВИСНЫЕ ПРЕДИКАТЫ append([],L,L). append([H|A],B,[H|C]) :- append(A,B,C). print_list([]). print_list([Head|Tail]) :- write(Head,"."), print_list(Tail).
% СИНТАКСИС sentence(S) :- append(S1,S2,S), glagol(S1),
GS(S2), write("\nГлагол:"), writel(S1), write("\nГс: "), writel(S2).
GS(S) :- append(S1,S2,S), prilagat(S1), noun(S2), write("\n*** Разбор ГС-1:"), write("\nПрилагательное: "),writel(S1), write("\nСуществительное:"),writel(S2).
GS(S) :- append(S1,Stmp1,S), append(S2,Stmp2,Stmp1), append(S3,S4,Stmp2), prilagat(S1), noun(S2), predlog(S3),
GS(S4), write("\n*** Разбор ГС-2:"), write("\nПрилагательное: "), print_list(S1), write("\nСуществительное:"), print_list(S2), write("\nПредлог: "), print_list(S2), write("\nГс: "), print_list(S2).
% СЛОВАРЬ noun(["символ"]). noun(["строка"]). noun(["страница"]). glagol(["печатать"]). glagol(["стереть"]). prilagat(["первый"]). prilagat(["второй"]). prilagat(["последний"]). predlog(["в"]).

40
Но это все – "экзотика". Теперь рассмотрим более осмысленный пример
– грамматику арифметических выражений. Эта грамматика в различных вариантах нам будет встречаться и далее. Пока же рассмотрим наиболее простой случай, содержащий лишь две бинарные операции с разными приоритетами.
G
0
=({E,T,F},{a,+,*,(,)},P,E)
P = { E  E+T|T
T  T*F|F
F  (E)|a}
Анализатор на Прологе будет выглядеть так:
E(L) :- T(L).
E(L) :- a3(L1,["+"],L3,L),
E(L1),
T(L3).
T(L) :- F(L).
T(L) :- a3(L1,["*"],L3,L),
T(L1), F(L3).
F(L) :- L=["a"].
F(L) :- a3(["("],L2,[")"],L),
E(L2).
Здесь предикат a3() разбивает список на три части. Как видно, Пролог- программа повторяет нашу грамматику с точностью до формы записи.