Алфавиты, цепочки и языки

Алфавит, или словарь - это конечное множество символов. Для обозначения символов мы будем пользоваться цифрами, латинскими буквами и специальными литерами типа #, $.

Пусть V - алфавит. Цепочка в алфавите V - это любая строка конечной длины, составленная из символов алфавита V . Синонимом цепочки являются предложение, строка и слово. Пустая цепочка (обозначается e) - это цепочка, в которую не входит ни один

символ.

Конкатенацией цепочек x и y называется цепочка xy. Заметим, что xe = ex = x для любой цепочки x.

Пусть x, y, z - произвольные цепочки в некотором алфавите. Цепочка y называется подцепочкой цепочки xyz. Цепочки x и y называются, соответственно, префиксом и суффиксом цепочки xy. Заметим, что любой префикс или суффикс цепочки является подцепочкой этой цепочки. Кроме того, пустая цепочка является префиксом, суффиксом и подцепочкой для любой цепочки.

Пример2.1. Для цепочки abbba префиксом является любая цепочка

из множества L1 = {e, a, ab, abb, abbb, abbba}, суффиксом является любая цепочка из множества L2 = {e, a, ba, bba, bbba, abbba}, подцепочкой является любая цепочка из множества L1

L2.

Длиной цепочки w (обозначается |w|) называется число символов в ней. Например, |abababa| = 7, а |e| = 0.

Язык в алфавите V - это некоторое множество цепочек в алфавите V .

Пример 2.2. Пусть дан алфавит V = {a, b}. Вот некоторые языки в алфавите V :

L1 =

- пустой язык;

L2 = {e} - язык, содержащий только пустую цепочку

(заметим, что L1 и L2 - различные языки);

L3 = {e, a, b, aa, ab, ba, bb} - язык,

содержащий цепочки из a и b, длина которых не превосходит 2;

L4 - язык, включающий всевозможные цепочки из a и b, содержащие четное число a и четное число b;

L5 = {an2

|n > 0} - язык цепочек из a, длины которых представляют собой квадраты натуральных чисел.

Два последних языка содержат бесконечное число цепочек.

Введем обозначение V *

для множества всех цепочек в алфавите V , включая пустую цепочку. Каждый язык в алфавите V является подмножеством V *.
Для обозначения множества всех цепочек в алфавите V , кроме пустой цепочки, будем

использовать V +.

Пример 2.3. Пусть V = {0, 1}. Тогда V * = {e, 0, 1, 00, 01, 10, 11, 000, ...}, V + = {0, 1, 00, 01, 10, 11, 000, ...}.

Введем некоторые операции над языками.

Пусть L1 и L2

- языки в алфавите V . Конкатенацией языков L1 и L2

называется язык L1L2 = {xy|x

L1, y L2}.

Пусть L - язык в алфавите V . Итерацией языка L называется язык L*, определяемый следующим образом:

L0 = {e};

Ln = LLn-1, n 1;

L* =

n=0Ln.

Пример 2.4. Пусть L1 = {aa, bb} и L2 = {e, a, bb}. Тогда

L1L2 = {aa, bb, aaa, bba, aabb, bbbb}, и

L1* = {e, aa, bb, aaaa, aabb, bbaa, bbbb, aaaaaa, ...}.

Большинство языков, представляющих интерес, содержат бесконечное число цепочек. При этом возникают три важных вопроса.

Во-первых, как представить язык (т.е. специфицировать входящие в него цепочки)? Если язык содержит только конечное множество цепочек, ответ прост. Можно просто перечислить его цепочки. Если язык бесконечен, необходимо найти для него конечное представление. Это конечное представление, в свою очередь, будет строкой символов над некоторым алфавитом вместе с

некоторой интерпретацией, связывающей это представление с языком.

Во-вторых, для любого ли языка существует конечное представление? Можно предположить, что ответ отрицателен. Мы увидим, что множество всех цепочек над алфавитом счетно. Язык - это любое подмножество цепочек. Из теории множеств известно, что множество всех подмножеств счетного множества несчетно. Хотя мы и не дали строгого определения того, что является конечным представлением, интуитивно ясно, что любое разумное

определение конечного представления ведет только к счетному множеству конечных представлений, поскольку нужно иметь возможность записать такое конечное представление в виде строки символов конечной длины. Поэтому языков значительно больше, чем конечных представлений.

В-третьих, можно спросить, какова структура тех классов языков, для которых существует конечное представление?

Алгоритм разбора сверху-вниз

Пусть дана КС-грамматика G = (N, T, P, S). Рассмотрим предсказывающий разбор (или разбор сверху-вниз) для грамматики G.

Основная задача предсказывающего разбора - определение правила вывода, которое нужно применить к нетерминалу. Процесс предсказывающего разбора с точки зрения построения дерева разбора проиллюстрирован на рис.4.1.

Рис. 4.1:

Фрагменты недостроенного дерева соответствуют сентенциальным формам. Вначале дерево состоит только из одной вершины, соответствующей аксиоме S. В этот момент по первому символу входной цепочки предсказывающий анализатор должен определить правило S

X1X2... , которое должно быть применено к S. Затем необходимо определить правило, которое должно быть применено к X1, и т.д., до тех пор, пока в процессе такого построения сентенциальной формы, соответствующей левому выводу,

не будет применено правило Y

a... . Этот процесс затем применяется для следующего самого левого нетерминального символа сентенциальной формы.

На рис. 4.2 приведена структура предсказывающего анализатора, который определяет очередное правило с помощью таблицы. Такую таблицу можно построить непосредственно по грамматике.

Рис. 4.2:

Таблично-управляемый предсказывающий анализатор имеет входную ленту, управляющее устройство (программу), таблицу анализа, магазин (стек) и выходную ленту.

Входная лента содержит анализируемую строку, заканчивающуюся символом $ - маркером конца строки. Выходная лента содержит последовательность примененных правил вывода.

Таблица анализа - это двумерный массив M[A, a], где A - нетерминал, и a - терминал или символ $. Значением M[A, a] может быть некоторое правило грамматики

или элемент «ошибка».

Магазин может содержать последовательность символов грамматики с $ на дне. В начальный момент магазин содержит только начальный символ грамматики на верхушке и $ на дне.

Анализатор работает следующим образом. Вначале анализатор находится в конфигурации, в которой магазин содержит S$, на входной ленте w$ (w - анализируемая цепочка), выходная лента пуста.
На каждом такте анализатор рассматривает X - символ на верхушке магазина и a - текущий входной символ. Эти

два символа определяют действия анализатора. Имеются следующие возможности.

1. Если X = a = $, анализатор останавливается, сообщает об успешном окончании разбора и выдает содержимое выходной ленты.

2. Если X = a

$, анализатор удаляет X из магазина и продвигает указатель входа на следующий входной символ.

3. Если X - терминал, и Xa, то анализатор останавливается и сообщает о том, что входная цепочка не принадлежит языку.

4. Если X - нетерминал, анализатор заглядывает в таблицу M[X, a]. Возможны два случая:

Значением M[X, a] является правило для X. В этом случае анализатор заменяет X на верхушке магазина на правую часть данного правила, а само правило помещает на выходную ленту. Указатель входа не передвигается.

Значением M[X, a] является «ошибка». В этом случае анализатор останавливается и сообщает о том, что входная цепочка не принадлежит языку.

Работа анализатора может быть задана следующей программой:

do      {X=верхний символ магазина;       if (X - терминал  X=="$")           if (X==InSym)               {удалить X из магазина;                InSym=очередной символ;               }           else error();       else /*X - нетерминал*/           if (M[X,InSym]=="X->Y1Y2...Yk")               {удалить X из магазина;                поместить Yk,Yk-1,...Y1 в магазин                   (Y1 на верхушку);                вывести правило X->Y1Y2...Yk;               }           else error(); /*вход таблицы M пуст*/      }   while (X!=$) /*магазин пуст*/

<


Пример 4.3. Рассмотрим грамматику арифметических выражений G = ({E, E', T, T', F}, {id, +, *, (, )}, P, E) с правилами:

 

	E TE'		T' *FT'
	E' +TE'		T' e
	E' e		F (E)
	T FT'		F id

 

Таблица предсказывающего анализатора для этой грамматики приведена на рис. 4.3. Пустые клетки таблицы соответствуют

элементу «ошибка».

Рис. 4.3:

При разборе входной цепочки id + id * id$ анализатор совершает последовательность шагов, изображенную на рис. 4.4. Заметим, что анализатор осуществляет в точности левый вывод. Если за уже просмотренными входными символами поместить символы грамматики в магазине, то можно получить в точности левые сентенциальные формы вывода. Дерево разбора для этой цепочки приведено на рис. 4.5.

Рис. 4.4:

Рис. 4.5:

Атрибутная схема для алгоритма сопоставления образцов

Алгоритмы 9.1 и 9.2 являются «универсальными» в том смысле, что конкретные грамматики выражений и образцов являются, по-существу, параметрами этих алгоритмов. В то же время, для каждой

конкретной грамматики можно написать свой алгоритм поиска образцов. Например, в случае нашей грамматики выражений и приведенных на рис. 9.16 образцов алгоритм 9.2 может быть представлен атрибутной грамматикой, приведенной ниже.

Наследуемый атрибут Match содержит упорядоченный список (вектор) образцов для сопоставления в поддереве данной вершины. Каждый из образцов имеет вид либо <op op-list> (op - операция в данной вершине, а op-list - список ее операндов), либо представляет

собой нетерминал N. В первом случае op-list «распределяется» по потомкам вершины для дальнейшего сопоставления. Во втором случае сопоставление считается успешным, если есть правило N

op {Pati}, где w состоит из образцов, успешно сопоставленных потомкам данной вершины. В этом случае по потомкам в качестве образцов распределяются элементы правой части правила. Эти два множества образцов могут пересекаться. Синтезируемый атрибут Pattern - вектор логических значений, дает результат

сопоставления по вектору-образцу Match.

Таким образом, при сопоставлении образцов могут встретиться два случая:

Вектор образцов содержит образец <op {Pati}>, где op - операция, примененная в данной вершине. Тогда распределяем образцы Pati по потомкам и сопоставление по данному образцу считаем успешным (истинным), если успешны сопоставления элементов этого образца по всем потомкам.

Образцом является нетерминал N. Тогда рассматриваем все правила вида N

op {Pati}. Вновь распределяем образцы Pati по потомкам и сопоставление считаем успешным

(истинным), если успешны сопоставления по всем потомкам. В общем случае успешным может быть сопоставление по нескольким образцам.

Отметим, что в общем случае в потомки одновременно передается несколько образцов для сопоставления.

В приведенной ниже атрибутной схеме не рассматриваются правила выбора покрытия наименьшей стоимости (см.
предыдущий раздел). Выбор оптимального покрытия может быть сделан еще одним проходом по дереву, аналогично тому, как это было сделано

выше. Например, в правиле с '+' имеется несколько образцов для Reg, но реального выбора одного из них не осуществляется. Кроме того, не уточнены некоторые детали реализации. В частности, конкретный способ формирования векторов Match и Pattern. В тексте употребляется термин «добавить», что означает добавление к вектору образцов очередного элемента. Векторы образцов записаны в угловых скобках.

RULE   Stat ::= '=' Reg Reg     SEMANTICS   Match=;   Match=;   Pattern[1]=Pattern[1]&Pattern[1].

Этому правилу соответствует один образец 2. Поэтому в качестве образцов потомков через их атрибуты Match передаются, соответственно, и .

RULE   Reg ::= '+' Reg Reg     SEMANTICS   if (Match содержит Reg в позиции i)       {Match=;        Match=>;       }   if (Match содержит образец  в позиции j)       {добавить Reg к Match в некоторой позиции k;       добавить Const к Match в некоторой позиции k;       }   if (Match содержит образец  в позиции j)   Pattern[j]=Pattern[k]&Pattern[k];   if (Match[0] содержит Reg в i-й позиции)   Pattern[i]=(Pattern[1]&Pattern[1])                 |(Pattern[2]&Pattern[2])                 |(Pattern[3]&Pattern[3]).

Образцы, соответствующие этому правилу, следующие:

(4) Reg '+' Reg Const,



(5) Reg '+' Reg Reg,

(6) Reg '+' Reg '@' '+' Reg Const.

Атрибутам Match второго и третьего символов в качестве образцов при сопоставлении могут быть переданы векторы и >, соответственно. Из анализа других

правил можно заключить, что при сопоставлении образцов предков левой части данного правила атрибуту Match символа левой части может быть передан образец

(из образцов 2, 3, 6) или образец Reg.

RULE   Reg ::= '@' Reg     SEMANTICS   if (Match содержит Reg в i-й позиции)       Match=,Reg>;   if (Match содержит  в j-й позиции)       добавить к Match  в k позиции;   if (Match содержит Reg в i-й позиции)       Pattern[i]=Pattern[1]|Pattern[2];   if (Match содержит  в j-й позиции)       Pattern[j]=Pattern[k].

Рис. 9.19:

Образцы, соответствующие этому правилу, следующие:

(3) Reg '@' '+' Reg Const,

(7) Reg '@' Reg.

Соответственно, атрибуту Match второго символа в качестве образцов при сопоставлении могут быть переданы (образец 3) или

(образец 7). Из анализа других правил можно заключить, что при сопоставлении образцов предков

левой части данного правила атрибуту Match могут быть переданы образцы

(из образца 6) и Reg.

RULE   Reg ::= Const     SEMANTICS   if (Pattern содержит Const в j-й позиции)   Pattern[j]=true;   if (Pattern содержит Reg в i-й позиции)   Pattern[i]=true.

Для дерева рис. 9.15 получим значения атрибутов, приведенные на рис. 9.19. Здесь M обозначает Match, P - Pattern, C - Const, R - Reg.

Атрибутные грамматики

Среди всех формальных методов описания языков программирования атрибутные грамматики (введенные Кнутом[6]) получили, по-видимому, наибольшую известность и распространение. Причиной этого является то, что формализм атрибутных грамматик основывается на дереве разбора программы в КС-грамматике, что сближает его с хорошо разработанной теорией и практикой построения трансляторов.

Динамическая организация памяти

Динамическая организация памяти - это организация памяти периода исполнения программы. Оперативная память программы обычно состоит из нескольких основных разделов: стек (магазин), куча, область статических

данных (инициализированных и неинициализированных). Наиболее сложной является работа со стеком. Вообще говоря, стек периода исполнения необходим для программ не на всех языках программирования. Например, в ранних версиях Фортрана нет рекурсии, так что программа может исполняться без стека. С другой стороны, исполнение программы с рекурсией может быть реализовано и без стека (того же эффекта можно достичь, например, и с помощью списковых структур). Однако, для

эффективной реализации пользуются стеком, который, как правило, поддерживается на уровне машинных команд.

Рассмотрим схему организации магазина периода выполнения для простейшего случая (как, например, в языке Паскаль), когда все переменные в магазине (фактические параметры и локальные переменные) имеют известные при трансляции смещения. Магазин служит для хранения локальных переменных (и параметров) и обращения к ним в языках, допускающих рекурсивные вызовы

процедур. Еще одной задачей, которую необходимо решать при трансляции языков с блочной структурой - обеспечение реализации механизмов статической вложенности. Пусть имеется следующий фрагмент программы на Паскале:

procedure P1;         var V1;         procedure P2;           var V2;         begin           ...           P2;           V1:=...           V2:=...           ...         end;       begin         ...         P2;         ...       end;

<
В процессе выполнения этой программы, находясь в процедуре P2, мы должны иметь доступ к последнему экземпляру значений переменных процедуры P2 и к экземпляру значений переменных процедуры P1, из которой была вызвана P2. Кроме того, необходимо обеспечить восстановление

состояния программы при завершении выполнения процедуры.

Мы рассмотрим две возможные схемы динамической организации памяти: схему со статической цепочкой и с дисплеем в памяти. В первом случае все статические контексты связаны в список, который называется статической цепочкой; в каждой записи для процедуры в магазине хранится указатель на запись статически охватывающей процедуры (помимо, конечно, указателя динамической цепочки - указателя на «базу» динамически

предыдущей процедуры). Во втором случае для хранения ссылок на статические контексты используется массив, называемый дисплеем. Использование той или иной схемы определяется, помимо прочих условий, прежде всего числом адресных регистров.

Формальное определение грамматики

Для нас наибольший интерес представляет одна из систем генерации языков - грамматики. Понятие грамматики изначально было формализовано лингвистами при изучении естественных языков. Предполагалось, что это может помочь при их автоматической трансляции. Однако, наилучшие результаты в этом направлении достигнуты при описании не естественных языков, а языков программирования. Примером может служить способ описания синтаксиса языков

программирования при помощи БНФ - формы Бэкуса-Наура.

Определение. Грамматика - это четверка G = (N, T, P, S), где

N - алфавит нетерминальных символов;

T - алфавит терминальных символов, N

T = ;

P - конечное множество правил вида

, где (N T)*N(N T)*,

(N

T)*;

S

N - начальный символ (или аксиома) грамматики.

Мы будем использовать большие латинские буквы для обозначения нетерминальных символов, малые латинские буквы из начала алфавита для

обозначения терминальных символов, малые латинские буквы из конца алфавита для обозначения цепочек из T* и, наконец, малые греческие буквы для обозначения цепочек из (N

T)*.

Будем использовать также сокращенную запись A

1|2|...|n для обозначения группы правил A 1, A 2, ..., A n.

Определим на множестве (N

T)* бинарное отношение выводимости следующим образом: если P, то

для всех

, (N T)*. Если 1 2, то говорят, что цепочка 2

непосредственно выводима из

1.

Мы будем использовать также рефлексивно-транзитивное и транзитивное замыкания

отношения

, а также его степень k 0 (обозначаемые соответственно *, + и k). Если 1 *2 (1 +2, 1 k2), то говорят, что цепочка 2 выводима (нетривиально выводима, выводима за k шагов) из 1.

Если

k (k 0), то существует последовательность шагов

где = 0 и = k. Последовательность цепочек 0, 1, 2, ..., k в этом случае называют выводом

из

.

Сентенциальной формой грамматики G называется цепочка, выводимая из ее начального символа.

Языком, порождаемым грамматикой G (обозначается L(G)), называется множество всех ее терминальных сентенциальных форм, т.е.

Грамматики G1

и G2 называются эквивалентными, если они порождают один и тот же язык, т.е.
L(G1) = L(G2).

Пример2.5. Грамматика G = ({S, B, C}, {a, b, c}, P, S), где

P = {S

aSBC, S aBC, CB BC, aB ab, bB bb, bC bc, cC cc}, порождает язык L(G) = {anbncn|n > 0}.

Действительно, применяем n- 1 раз правило 1 и получаем an-1S(BC)n-1, затем один раз правило 2 и получаем an(BC)n, затем n(n- 1)/2 раз правило 3 и

получаем anBnCn.

Затем используем правило 4 и получаем anbBn-1Cn. Затем применяем n- 1 раз правило 5 и получаем anbnCn. Затем применяем правило 6 и n - 1 раз правило 7 и получаем anbncn. Можно показать, что язык L(G) состоит из цепочек только такого вида.

Пример 2.6. Рассмотрим грамматику G = ({S}, {0, 1}, {S 0S1, S 01}, S). Легко видеть, что цепочка 000111 L(G), так как существует вывод



Нетрудно показать, что грамматика порождает язык L(G) = {0n1n|n > 0}.

Пример 2.7. Рассмотрим грамматику G = ({S, A}, {0, 1}, {S 0S,

S 0A, A 1A, A 1}, S). Нетрудно показать, что грамматика порождает язык L(G) = {0n1m|n, m > 0}.

Функции FIRST и FOLLOW

При построении таблицы предсказывающего анализатора нам потребуются две функции - FIRST и FOLLOW.

Пусть G = (N, T, P, S) - КС-грамматика. Для

- произвольной цепочки, состоящей из символов грамматики, определим FIRST() как множество терминалов, с которых начинаются строки, выводимые из . Если *e, то e также принадлежит FIRST().

Определим FOLLOW(A) для нетерминала A как множество терминалов a, которые могут появиться непосредственно справа от A в

некоторой сентенциальной форме грамматики, т.е. множество терминалов a таких, что существует вывод вида S

*Aa для некоторых , (N T)*. Заметим, что между A и a в процессе вывода могут находиться нетерминальные символы, из которых выводится e. Если A может быть самым правым символом некоторой сентенциальной формы, то $ также принадлежит FOLLOW(A).

Рассмотрим алгоритмы вычисления функции FIRST.

 

Алгоритм 4.3. Вычисление FIRST для символов грамматики.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Множество FIRST(X) для каждого символа X

(N T).

Метод. Выполнить шаги 1-3:

Если X - терминал, то положить FIRST(X) = {X}; если X - нетерминал, положить FIRST(X) =

.

Если в P имеется правило X

e, то добавить e к FIRST(X).

Пока ни к какому множеству FIRST(X) нельзя уже будет добавить новые элементы, выполнять:

если X - нетерминал и имеется правило вывода X

Y 1Y 2...Y k, то включить a в FIRST(X), если a FIRST(Y i) для некоторого i, 1 i k, и e принадлежит всем FIRST(Y 1), ..., FIRST(Y i-1), то есть Y 1...Y i-1 *e. Если e принадлежит FIRST(Y j) для всех j = 1, 2, ..., k, то добавить e к FIRST(X).

 

Алгоритм 4.4. Вычисление FIRST для цепочки.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Множество FIRST(X1X2...Xn), Xi

(N T).

Метод. Выполнить шаги 1-3:

При помощи предыдущего алгоритма вычислить FIRST(X) для каждого X

(N T).

Положить FIRST(X1X2...Xn) =

.

Добавить к FIRST(X1X2...Xn) все не e-элементы из FIRST(X1). Добавить к нему также все не e-элементы из FIRST(X2), если e

FIRST(X1), не e-элементы из FIRST(X3), если e принадлежит как FIRST(X1), так и FIRST(X2), и т.д.
Наконец, добавить цепочку e к FIRST(X1X2...Xn), если e FIRST(Xi) для всех i.

 

Рассмотрим алгоритм вычисления функции FOLLOW.

 

Алгоритм 4.5. Вычисление FOLLOW для

нетерминалов грамматики.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Множество FOLLOW(X) для каждого символа X N.

Метод. Выполнить шаги 1-4:

Положить FOLLOW(X) = для каждого символа X

N.

Добавить $ к FOLLOW(S).

Если в P eсть правило вывода A B, где , (NT)* то все элементы из FIRST(), за исключением e, добавить к FOLLOW(B).

Пока ничего нельзя будет добавить ни к какому множеству FOLLOW(X), выполнять:

если в P есть правило A

B или A B, , (NT)*, где FIRST() содержит e (т.е. *e), то все элементы из FOLLOW(A) добавить к FOLLOW(B).

Пример 4.4. Рассмотрим грамматику из примера 4.3. Для нее

 

	FIRST(E) = FIRST(T) = FIRST(F) = {(, id}
	FIRST(E') = {+, e}
	FIRST(T') = {*, e}
	FOLLOW(E) = FOLLOW(E') = { ), $}
	FOLLOW(T) = FOLLOW(T') = {+, ), $}
	FOLLOW(F) = {+, *, ), $}

 

Например, id и левая скобка добавляются к FIRST(F) на шаге 3 при i = 1, поскольку FIRST(id) = {id} и FIRST(”(”) = {”(”} в соответствии с шагом 1. На шаге 3 при i = 1, в соответствии с правилом вывода T FT' к FIRST(T) добавляются также id и левая скобка. На шаге 2 в FIRST(E') включается e.

При вычислении множеств FOLLOW на шаге 2 в FOLLOW(E) включается $. На шаге 3, на основании правила F (E), к FOLLOW(E) добавляется также правая скобка. На шаге 4, примененном к правилу E TE', в FOLLOW(E') включаются $ и правая

скобка. Поскольку E'*e, они также попадают и во множество FOLLOW(T). В соответствии с правилом вывода E TE', на шаге 3 в FOLLOW(T) включаются и все элементы из FIRST(E'), отличные от e.

Функции расстановки

Много внимания исследователями было уделено тому, какой должна быть (первичная) функция расстановки. Основные требования к ней очевидны: она должна легко

вычисляться и распределять равномерно. Один из возможных подходов здесь заключается в следующем.

1. По символам строки s определяем положительное целое H. Преобразование одиночных символов в целые обычно можно сделать средствами языка реализации. В Паскале для этого служит функция ord, в Си при выполнении арифметических операций символьные значения трактуются как целые.

2. Преобразуем H, вычисленное выше, в номер элемента, т.е. целое между 0 и N - 1, где N - размер таблицы

расстановки, например, взятием остатка при делении H на N.

Функции расстановки, учитывающие все символы строки, распределяют лучше, чем функции, учитывающие только несколько символов, например, в конце или середине строки. Но такие функции требуют больше вычислений.

Простейший способ вычисления H - сложение кодов символов. Перед сложением с очередным символом можно умножить старое значение H на константу q. Т.е. полагаем H0 = 0, Hi = q*Hi-1 + ci для 1

i k, k - длина строки. При

q = 1 получаем простое сложение символов. Вместо сложения можно выполнять сложение ci и q*Hj-1 по модулю 2. Переполнение при выполнении арифметических операций можно игнорировать.

Функция Hashpjw, приведенная ниже [10], вычисляется, начиная с H  =  0 (предполагается, что используются 32-битовые целые). Для каждого символа c сдвигаем биты H на 4 позиции влево и добавляем очередной символ. Если какой-нибудь из четырех старших бит H равен 1, сдвигаем эти 4 бита на 24 разряда вправо, затем складываем

по модулю 2 с H и устанавливаем в 0 каждый из четырех старших бит, равных 1.

#define PRIME 211   #define EOS '\0'   int Hashpjw(char *s)   {char *p;    unsigned H=0, g;    for (p=s; *p!=EOS; p=p+1)      {H=(H     if (g=H&0xf0000000)           {H=H^(g>>24);            H=H^g;      }    }    return H%PRIME;   }

Генерация кода

Задача генератора кода - построение для программы на входном языке эквивалентной машинной программы. Обычно в качестве входа для генератора кода служит некоторое промежуточное представление программы.

Генерация кода включает ряд специфических, относительно независимых подзадач: распределение памяти (в частности, распределение регистров), выбор команд, генерацию объектного (или загрузочного) модуля. Конечно, независимость этих подзадач

относительна: например, при выборе команд нельзя не учитывать схему распределения памяти, и, наоборот, схема распределения памяти (регистров, в частности) ведет к генерации той или иной последовательности команд. Однако удобно и практично эти задачи все же разделять, обращая при этом внимание на их взаимодействие.

В какой-то мере схема генератора кода зависит от формы промежуточного представления. Ясно, что генерация кода из дерева отличается от генерации кода из

троек, а генерация кода из префиксной записи отличается от генерации кода из ориентированного графа. В то же время все генераторы кода имеют много общего, и основные применяемые алгоритмы отличаются, как правило, только в деталях, связанных с используемым промежуточным представлением.

В дальнейшем в качестве промежуточного представления мы будем использовать префиксную нотацию. А именно, алгоритмы генерации кода будем излагать в виде атрибутных схем со входным языком Лидер.

Элементы теории перевода

До сих пор мы рассматривали процесс синтаксического анализа только как процесс анализа допустимости входной цепочки. Однако, в компиляторе синтаксический анализ служит основой еще одного важного шага - построения дерева синтаксического анализа. В примерах 4.3 и 4.8 предыдущей главы в процессе синтаксического анализа в качестве выхода выдавалась последовательность примененных правил, на основе которой и может быть построено дерево. Построение

дерева синтаксического анализа является простейшим частным случаем перевода - процесса преобразования некоторой входной цепочки в некоторую выходную.

Определение. Пусть T - входной алфавит, а

- выходной алфавит. Переводом (или трансляцией) с языка L1

T*

на язык L2

*

называется отображение

: L1 L2. Если y = (x), то цепочка y называется выходом для цепочки x.

Мы рассмотрим несколько формализмов для определения переводов: преобразователи с магазинной памятью, схемы синтаксически

управляемого перевода и атрибутные грамматики.

Классы атрибутных грамматик и их реализация

В общем виде реализация вычислителей для атрибутных грамматик вызывает значительные трудности. Это связано с тем, что множество значений атрибутов,

связанных с данным деревом, приходится вычислять в соответствии с зависимостями атрибутов, которые образуют ориентированный ациклический граф. На практике стараются осуществлять процесс вычисления атрибутов, привязывая его к тому или иному способу обхода дерева. Рассматривают многовизитные, многопроходные и другие атрибутные вычислители. Это, как правило, ведет к ограничению допустимых зависимостей между атрибутами, поддерживаемых вычислителем.

Простейшими подклассами атрибутных грамматик, вычисления

всех атрибутов для которых может быть осуществлено одновременно с синтаксическим анализом, являются S-атрибутные и L-атрибутные грамматики.

Определение. Атрибутная грамматика называется S-атрибутной, если она содержит только синтезируемые атрибуты.

Нетрудно видеть, что для S-атрибутной грамматики на любом дереве разбора все атрибуты могут быть вычислены за один обход дерева снизу вверх. Таким образом, вычисление атрибутов можно делать параллельно

с восходящим синтаксическим анализом, например, LR(1)-анализом.

Пример5.8. Рассмотрим S-атрибутную грамматику для перевода арифметических выражений в ПОЛИЗ. Здесь атрибут v имеет строковый тип,  - обозначает операцию конкатенации. Правила вывода и семантические правила определяются следующим образом

 

E1 E2 + T	v(E1) = v(E2) v(T) ' + '
E T	v(E) = v(T)
T T * F	v(T1) = v(T2) v(F) '*'
T F	v(T) = v(F)
F id	v(F) = v(id)
F (E)	v(F) = v(E)

  Определение. Атрибутная грамматика называется L-атрибутной, если любой наследуемый атрибут

любого символа Xj

из правой части каждого правила X0

X1X2...Xn

грамматики зависит только от

атрибутов символов X1, X2, ..., Xj-1, находящихся в правиле слева от Xj, и

наследуемых атрибутов символа X0.

Заметим, что каждая S-атрибутная грамматика является L-атрибутной. Все атрибуты на любом дереве для L-атрибутной грамматики могут быть вычислены за один обход дерева сверху-вниз слева-направо.

Конечные автоматы

Регулярные выражения, введенные ранее, служат для описания регулярных множеств. Для распознавания регулярных множеств служат конечные автоматы.

Недетерминированный конечный автомат (НКА) - это пятерка M = (Q, T, D, q0, F), где

Q - конечное множество состояний;

T - конечное множество допустимых входных символов (входной алфавит);

D - функция переходов (отображающая множество QЧ(T

{e}) во множество подмножеств множества Q), определяющая поведение управляющего устройства;

q0

Q - начальное состояние управляющего устройства;

F

Q - множество заключительных состояний.

Работа конечного автомата представляет собой некоторую последовательность шагов, или тактов. Такт

определяется текущим состоянием управляющего устройства и входным символом, обозреваемым в данный момент входной головкой. Сам шаг состоит из изменения состояния и, возможно, сдвига входной головки на одну ячейку вправо (рис.3.2).

Рис. 3.2:

Недетерминизм автомата заключается в том, что, во-первых, находясь в некотором состоянии и обозревая текущий символ, автомат может перейти в одно из, вообще говоря, нескольких возможных состояний, и во-вторых, автомат может делать переходы по e.

Пусть M = (Q, T, D, q0, F) - НКА. Конфигурацией автомата M называется пара (q, w)

QЧT*, где q - текущее состояние управляющего устройства, а w - цепочка символов на входной ленте, состоящая из символа под головкой и всех символов

справа от него. Конфигурация (q0, w) называется начальной, а конфигурация (q, e), где q

F - заключительной (или допускающей).

Пусть M = (Q, T, D, q0, F) - НКА. Тактом автомата M называется бинарное отношение

, определенное на конфигурациях M следующим образом: если p D(q, a), где a T {e}, то (q, aw) (p, w) для всех w T*.

Будем обозначать символом

+ (*) транзитивное (рефлексивно- транзитивное) замыкание отношения .

Говорят, что автомат M допускает цепочку w, если (q0, w)

*(q, e) для некоторого q F. Языком, допускаемым (распознаваемым, определяемым) автоматом M, (обозначается L(M)), называется множество

входных цепочек, допускаемых автоматом M. Т.е.



Важным частным случаем недетерминированного конечного автомата является детерминированный конечный автомат, который на каждом такте работы имеет возможность перейти не более чем в одно состояние и не может делать переходы по e.

Пусть M = (Q, T, D, q0, F) - НКА. Будем называть M детерминированным конечным автоматом (ДКА), если

выполнены следующие два условия:

D(q, e) = для любого q Q, и

D(q, a) содержит не более одного элемента для любых q Q и a T.

Так как функция переходов ДКА содержит не более одного элемента для любой пары аргументов, для ДКА мы будем пользоваться записью D(q, a) = p вместо D(q, a) = {p}.

Конечный автомат может быть изображен графически в виде диаграммы, представляющей собой ориентированный граф, в котором каждому состоянию соответствует вершина,

а дуга, помеченная символом a T {e}, соединяет две вершины p и q, если p D(q, a). На диаграмме выделяются начальное и заключительные состояния (в примерах ниже, соответственно, входящей стрелкой и двойным контуром).

Пример 3.3. Пусть L = L(r), где r = (a|b)*a(a|b)(a|b).

Недетерминированный конечный автомат M, допускающий язык L:

	M = {{1, 2, 3, 4}, {a, b}, D, 1, {4}},

где функция переходов D определяется так:

	D(1, a) = {1, 2},	D(3, a) = {4},
	D(2, a) = {3},	D(3, b) = {4},
	D(2, b) = {3}.

Диаграмма автомата приведена на рис. 3.3, а.

Детерминированный конечный автомат M, допускающий язык L:

	M = {{1, 2, 3, 4, 5, 6, 7, 8}, {a, b}, D, 1, {3, 5, 6, 8}},

где функция переходов D определяется так:

	D(1, a) = 2,	D(5, a) = 8,
	D(1, b) = 1,	D(5, b) = 6,
	D(2, a) = 4,	D(6, a) = 2,
	D(2, b) = 7,	D(6, b) = 1,
	D(3, a) = 3,	D(7, a) = 8,
	D(3, b) = 5,	D(7, b) = 6,
	D(4, a) = 3,	D(8, a) = 4,
	D(4, b) = 5,	D(8, b) = 7.

Диаграмма автомата приведена на рис. 3.3, б.

Рис. 3.3:

Пример 3.4. Диаграмма ДКА, допускающего множество чисел в десятичной записи, приведена на рис. 3.4.

Рис. 3.4:

Пример 3.5. Анализ цепочек.



При анализе цепочки w = ababa автомат из примера 3.3, а, может сделать следующую последовательность тактов:

(1, ababa) (1, baba) (1, aba) (2, ba) (3, a) (4, e).

Состояние 4 является заключительным, следовательно, цепочка w допускается этим автоматом.

При анализе цепочки w = ababab автомат из примера 3.3, б, должен сделать следующую последовательность тактов:

(1, ababab) (2, babab) (7, abab) (8, bab) (7, ab) (8, b) (7, e).

Так как состояние 7 не является заключительным, цепочка w не допускается этим автоматом.

Конструирование LR(1)-таблицы

Рассмотрим теперь алгоритм конструирования таблицы, управляющей LR(1)-анализатором.

Пусть G = (N, T, P, S) - КС-грамматика. Пополненной грамматикой для данной грамматики G называется КС-грамматика

т.е. эквивалентная грамматика, в которой введен новый начальный символ S' и новое правило вывода S' S.

Это дополнительное правило вводится для того, чтобы определить, когда анализатор должен остановить разбор и зафиксировать допуск входа. Таким образом, допуск имеет место тогда и

только тогда, когда анализатор готов осуществить свертку по правилу S'

S.

LR(1)-ситуацией называется пара [A

., a], где A - правило грамматики, a - терминал или правый концевой маркер $. Вторая компонента ситуации называется аванцепочкой.

Будем говорить, что LR(1)-ситуация [A

., a] допустима для активного префикса , если существует вывод S r*Aw rw, где = и либо a - первый символ w, либо w = e и a = $.

Будем говорить, что ситуация допустима, если она допустима для какого-либо активного префикса.

Пример4.9. Рассмотрим

грамматику G = ({S, B}, {a, b}, P, S) с правилами

	S BB
	B aB | b

Существует правосторонний вывод S

r*aaBab

raaaBab. Легко видеть, что ситуация [B

a.B, a] допустима для активного префикса = aaa, если в определении выше положить = aa, A = B, w = ab, = a, = B. Существует также правосторонний вывод S r*BaB

rBaaB. Поэтому для активного префикса Baa допустима ситуация [B

a.B, $].

Центральная идея метода заключается в том, что по грамматике строится детерминированный конечный автомат, распознающий активные префиксы. Для этого ситуации группируются во множества, которые и образуют состояния автомата.

Ситуации можно рассматривать как состояния недетерминированного конечного автомата, распознающего активные префиксы, а их группировка на самом деле есть процесс построения детерминированного конечного автомата из недетерминированного.

Анализатор, работающий слева-направо по типу сдвиг-свертка, должен уметь распознавать основы на верхушке магазина. Состояние автомата после прочтения содержимого магазина и текущий входной символ определяют очередное действие автомата.
Функцией переходов этого конечного

автомата является функция переходов LR-анализатора. Чтобы не просматривать магазин на каждом шаге анализа, на верхушке магазина всегда хранится то состояние, в котором должен оказаться этот конечный автомат после того, как он прочитал символы грамматики в магазине от дна к верхушке.

Рассмотрим ситуацию вида [A

.B, a] из множества ситуаций, допустимых для некоторого активного префикса z. Тогда существует правосторонний вывод S r*yAax ryBax, где z = y. Предположим, что из ax выводится

терминальная строка bw. Тогда для некоторого правила вывода вида B q имеется вывод S r*zBbw rzqbw. Таким образом [B .q, b] также допустима для z и ситуация [A B., a] допустима для активного префикса zB. Здесь либо b может быть первым терминалом, выводимым из , либо из

выводится e в выводе ax r*bw и тогда b равно a. Т.е. b принадлежит FIRST(ax). Построение всех таких ситуаций для данного множества ситуаций, т.е. его замыкание, делает приведенная ниже функция closure.

Система множеств допустимых LR(1)-ситуаций для всевозможных активных

префиксов пополненной грамматики называется канонической системой множеств допустимых LR(1)-ситуаций. Алгоритм построения канонической системы множеств приведен ниже.

 

Алгоритм 4.9. Конструирование канонической системы множеств допустимых LR(1)-ситуаций.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Каноническая система C множеств допустимых LR(1)-ситуаций для грамматики G.

Метод. Заключается в выполнении для пополненной грамматики G' процедуры items, которая использует функции closure и goto.

 

function closure(I){ /* I - множество ситуаций */

do{

for (каждой ситуации [A .B, a] из I,

каждого правила вывода B

из G',

каждого терминала b из FIRST(a),

такого, что [B ., b] нет в I)

добавить [B ., b] к I;

}

while (к I можно добавить новую ситуацию);

return I;

}

 

function goto(I,X){ /* I - множество ситуаций;

X - символ грамматики */

Пусть J = {[A X., a] | [A .X, a] I};

return closure(J);



}

 

procedure items(G'){ /* G' - пополненная грамматика */

I0 = closure({[S' .S, $]});

C = {I0};

do{

for (каждого множества ситуаций I из системы C,

каждого символа грамматики X такого,

что goto(I, X) не пусто и не принадлежит C)

добавить goto(I, X) к системе C;

}

while (к C можно добавить новое множество ситуаций);

 

Если I - множество ситуаций, допустимых для некоторого активного префикса , то goto(I, X) - множество ситуаций, допустимых для активного префикса X.

Работа алгоритма построения системы C множеств допустимых

LR(1)-ситуаций начинается с того, что в C помещается начальное множество ситуаций I0 = closure({[S' .S, $]}). Затем с помощью функции goto вычисляются новые множества ситуаций и включаются в C. По-существу, goto(I, X) - переход конечного автомата из состояния I по символу X.

Рассмотрим теперь, как по системе множеств LR(1)-ситуаций строится LR(1)-таблица, т.е. функции действий и переходов LR(1)-анализатора.

 

Алгоритм 4.10. Построение LR(1)-таблицы.

Вход. Каноническая система C = {I0, I1, ..., In} множеств допустимых LR(1)-ситуаций для грамматики G.

Выход. Функции Action и Goto, составляющие LR(1)-таблицу для грамматики G.

Метод. Для каждого состояния i функции Action[i, a] и Goto[i, X] строятся по множеству ситуаций Ii:

Значения функции действия (Action) для состояния i определяются следующим образом:

если [A .a, b] Ii (a - терминал) и goto(Ii, a) = Ij, то полагаем Action[i, a] = shift j;

если [A ., a] Ii, причем AS', то полагаем Action[i, a] = reduce A ;

если [S' S., $] Ii, то полагаем Action[i, $] = accept.

Значения функции переходов для

состояния i определяются следующим образом: если goto(Ii, A) = Ij, то Goto[i, A] = j (здесь A - нетерминал).

Все входы в Action и Goto, не определенные шагами 2 и 3, полагаем равными error.

Начальное состояние анализатора строится из множества, содержащего ситуацию [S' .S, $].

Таблица на основе функций Action и Goto, полученных в результате работы алгоритма 4.10, называется канонической LR(1)-таблицей.


LR(1)-анализатор, работающий с этой таблицей, называется каноническим LR(1)-анализатором.

Пример 4.10. Рассмотрим следующую грамматику, являющуюся пополненной для грамматики из примера 4.8:

 

	(0) E' E
	(1) E E + T
	(2) E T
	(3) T T * F
	(4) T F
	(5) F id

 

Множества ситуаций и переходы по goto для этой грамматики приведены на рис. 4.11. LR(1)-таблица для этой грамматики приведена на рис. 4.9.

Рис. 4.11:

Конструирование таблицы предсказывающего анализатора

Для конструирования таблицы предсказывающего анализатора по грамматике G может быть использован алгоритм, основанный на следующей идее. Предположим, что A

- правило вывода грамматики и a FIRST(). Тогда анализатор делает развертку A по , если входным символом является a. Трудность

возникает, когда

= e или *e. В этом случае нужно развернуть A в , если текущий входной символ принадлежит FOLLOW(A) или если достигнут $ и $ FOLLOW(A).

Алгоритм 4.6. Построение таблицы предсказывающего анализатора.

Вход. КС-грамматика G = (N, T, P, S).

Выход. Таблица M[A, a] предсказывающего анализатора, A

N, a T {$}.

Метод. Для каждого правила вывода A

грамматики выполнить шаги 1 и 2. После этого выполнить шаг 3.

Для каждого терминала a из FIRST(

) добавить A к M[A, a].

Если e

FIRST(), добавить A к M[A, b] для каждого

терминала b из FOLLOW(A). Кроме того, если e

FIRST() и $ FOLLOW(A), добавить A к M[A, $].

Положить все неопределенные входы равными «ошибка».

Пример 4.5. Применим алгоритм 4.6 к грамматике из примера 4.3. Поскольку FIRST(TE') = FIRST(T) = {(, id }, в соответствии с правилом вывода E

TE' входы M[E, ( ] и M[E, id ] становятся равными E TE'.

В соответствии с правилом вывода E'

+TE' значение M[E', +] равно E' +TE'. В соответствии с правилом вывода E' e значения M[E', )] и M[E', $] равны E' e, поскольку FOLLOW(E') = { ), $}.

Таблица анализа, построенная алгоритмом 4.6 для этой грамматики, приведена на рис. 4.3.

Конструктор лексических анализаторов LEX

Для автоматизации разработки лексических анализаторов было разработано довольно много средств. Как правило, входным языком для них служат либо праволинейные грамматики, либо язык регулярных выражений. Одной из наиболее распространенных систем является LEX, работающий с расширенными регулярными выражениями. LEX-программа состоит из трех частей:

Объявления     %%     Правила трансляции     %%     Вспомогательные подпрограммы

Секция объявлений включает объявления переменных, констант и определения регулярных выражений. При определении регулярных выражений могут использоваться следующие конструкции:

[abc]	- либо a, либо b, либо c;
[a-z]	- диапазон символов;
R*	- 0 или более повторений регулярного выражения R;
R+	- 1 или более повторений регулярного выражения R;
R1/R2	- R1, если за ним следует R2;
R1|R2	- либо R1, либо R2;
R?	- если есть R, выбрать его;
R$	- выбрать R, если оно последнее в строке;
^R	- выбрать R, если оно первое в строке;
[^R]	- дополнение к R;
R{n,m}	- повторение R от n до m раз;
{имя}	- именованное регулярное выражение;
(R)	- группировка.

 

Правила

трансляции LEX программ имеют вид

p_1 { действие_1 }   p_2 { действие_2 }   ................   p_n { действие_n }

где каждое p_i - регулярное выражение, а каждое действие_i - фрагмент программы, описывающий, какое действие должен сделать лексический анализатор, когда образец p_i сопоставляется лексеме. В LEX действия записываются на Си.

Третья секция содержит вспомогательные процедуры, необходимые для действий. Эти процедуры могут транслироваться раздельно и загружаться с лексическим анализатором.

Лексический анализатор, сгенерированный

LEX, взаимодействует с синтаксическим анализатором следующим образом. При вызове его синтаксическим анализатором лексический анализатор посимвольно читает остаток входа, пока не находит самый длинный префикс, который может быть сопоставлен одному из регулярных выражений p_i.
Затем он выполняет действие_i. Как правило, действие_i возвращает управление синтаксическому анализатору. Если это не так, т.е. в соответствующем действии нет возврата, то лексический анализатор продолжает поиск лексем до тех, пока действие не вернет управление

синтаксическому анализатору. Повторный поиск лексем вплоть до явной передачи управления позволяет лексическому анализатору правильно обрабатывать пробелы и комментарии. Синтаксическому анализатору лексический анализатор возвращает единственное значение - тип лексемы. Для передачи информации о типе лексемы используется глобальная переменная yylval. Текстовое представление выделенной лексемы хранится в переменной yytext, а ее длина в переменной yylen.

Пример 3.11. LEX-программа для ЛА, обрабатывающего идентификаторы, числа, ключевые

слова if, then, else и знаки логических операций.

%{ /*определения констант LT,LE,EQ,NE,GT,             GE,IF,THEN,ELSE,ID,NUMBER,RELOP, например,             через DEFINE или скалярный тип*/ %}            /*регулярные определения*/            delim    [ \t\n]            ws       {delim}+            letter   [A-Za-z]            digit    [0-9]            id       {letter}({letter}|{digit})*            number   {digit}+(\.{digit}+)?(E[+\-]?{digit}+)?            %%            {ws}     {/* действий и возврата нет */}            if       {return(IF);}            then     {return(THEN);}            else     {return(ELSE);}            {id}     {yylval=install_id(); return(ID);}            {number} {yylval=install_num(); return(NUMBER);}            "         "         "="      {yylval=EQ; return(RELOP);}            "<>"     {yylval=NE; return(RELOP);}            ">"      {yylval=GT; return(RELOP);}            ">="     {yylval=GE; return(RELOP);}            %%            install_id()            {/*подпрограмма, которая помещает лексему,                   на первый символ которой указывает yytext,                   длина которой равна yylen, в таблицу                   символов и возвращает указатель на нее*/            }            install_num()            {/*аналогичная подпрограмма для размещения                            лексемы числа*/            }

<


В разделе объявлений, заключенном в скобки %{ и %}, перечислены константы, используемые правилами трансляции. Все, что заключено в

эти скобки, непосредственно копируется в программу лексического анализатора lex.yy.c и не рассматривается как часть регулярных определений или правил трансляции. То же касается и вспомогательных подпрограмм третьей секции. В данном примере это подпрограммы install_id и install_num.

В секцию определений входят также некоторые регулярные определения. Каждое такое определение состоит из имени и регулярного выражения, обозначаемого этим именем. Например, первое определенное имя - это delim. Оно обозначает класс символов { \t\n\}, т.е. любой из трех символов: пробел, табуляция или новая строка.

Второе определение - разделитель, обозначаемый именем ws. Разделитель - это любая последовательность одного или более символов-разделителей. Слово delim должно быть заключено в скобки, чтобы отличить его от образца, состоящего из пяти символов delim.

В определении letter используется класс символов. Сокращение [A-Za-z] означает любую из прописных букв от A до Z или строчных букв от a до z. В пятом определении для id для группировки используются скобки, являющиеся метасимволами LEX. Аналогично, вертикальная черта - метасимвол LEX, обозначающий объединение.

В последнем регулярном определении number символ «+»

используется как метасимвол «одно или более вхождений», символ «?» как метасимвол «ноль или одно вхождение». Обратная черта используется для того, чтобы придать обычный смысл символу, использующемуся в LEX как метасимвол. В частности, десятичная точка в определении number обозначается как «\.», поскольку точка сама по себе представляет класс, состоящий из всех символов, за исключением символа новой строки. В классe символов [+\] обратная черта перед минусом стоит потому, что знак минус используется как символ диапазона, как в [A-Z].

Если символ имеет смысл метасимвола,

то придать ему обычный смысл можно и по-другому, заключив его в кавычки.


Так, в секции правил трансляции шесть операций отношения заключены в кавычки.

Рассмотрим правила трансляции, следующие за первым %%. Согласно первому правилу, если обнаружено ws, т.е. максимальная последовательность пробелов, табуляций и новых строк, никаких действий не производится. В частности, не осуществляется возврат в синтаксический анализатор.

Согласно второму правилу, если обнаружена последовательность букв «if», нужно вернуть значение IF, которое определено как целая константа, понимаемая синтаксическим

анализатором как лексема «if». Аналогично обрабатываются ключевые слова «then» и «else» в двух следущих правилах.

В действии, связанном с правилом для id, два оператора. Переменной yylval присваивается значение, возвращаемое процедурой install_id. Переменная yylval определена в программе lex.yy.c, выходе LEX, и она доступна синтаксическому анализатору. yylval хранит возвращаемое лексическое значение, поскольку второй оператор в действии, return(ID), может только возвратить код класса лексем. Функция install_id заносит идентификаторы в таблицу символов.

Аналогично обрабатываются числа в следующем правиле. В последних шести

правилах yylval используется для возврата кода операции отношения, возвращаемое же функцией значение - это код лексемы relop.

Если, например, в текущий момент лексический анализатор обрабатывает лексему «if», то этой лексеме соответствуют два образца: «if» и {id} и более длинной строки, соответствующей образцу, нет. Поскольку образец «if» предшествует образцу для идентификатора, конфликт разрешается в пользу ключевого слова. Такая стратегия разрешения конфликтов позволяет легко резервировать ключевые слова.

Если на входе встречается «

КС-грамматики и МП-автоматы

Пусть G = (N, T, P, S) - контекстно-свободная грамматика. Введем несколько важных понятий и определений.

Вывод, в котором в любой сентенциальной форме на каждом шаге делается подстановка самого левого нетерминала, называется левосторонним. Если S

*u в процессе левостороннего вывода, то u - левая сентенциальная форма. Аналогично определяется правосторонний вывод. Будем обозначать шаги левого (правого) вывода посредством l (r).

Упорядоченным

графом называется пара (V, E), где V есть множество вершин, а E - множество линейно упорядоченных списков дуг, каждый элемент которого имеет вид ((v, v1), (v, v2), ..., (v, vn)). Этот элемент указывает, что из вершины v выходят n дуг, причем первой из них считается дуга, входящая в вершину v1, второй - дуга, входящая в вершину v2, и т.д.

Упорядоченным помеченным деревом называется упорядоченный граф (V, E), основой которого является дерево и для которого определена функция f : V

F (функция

разметки) для некоторого множества F.

Упорядоченное помеченное дерево D называется деревом вывода (или деревом разбора) цепочки w в КС-грамматике G = (N, T, P, S), если выполнены следующие условия:

корень дерева D помечен S;

каждый лист помечен либо a

T, либо e;

каждая внутренняя вершина помечена нетерминалом A

N;

если X - нетерминал, которым помечена внутренняя вершина и X1, ..., Xn - метки ее прямых потомков в указанном порядке, то

X

X1...Xk - правило из множества P;

Цепочка, составленная из выписанных слева направо меток листьев, равна w.

Грамматика G называется неоднозначной, если существует цепочка w, для которой имеется два или более различных деревьев вывода в G.

Грамматика G называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод A

+A для некоторой цепочки .

Автомат с магазинной памятью (МП-автомат) - это семерка M = (Q, T,

, D, q0, Z0, F), где

Q - конечное множество состояний,

представляющих всевозможные состояния управляющего устройства;

T - конечный входной алфавит;

- конечный алфавит магазинных символов;

D - отображение множества QЧ(T{e})Ч в множество конечных подмножеств QЧ*, называемое функцией переходов;

q0 Q - начальное состояние управляющего устройства;

Z0 - символ, находящийся в магазине в начальный момент (начальный символ магазина);

F Q - множество заключительных состояний.

Конфигурацией МП-автомата называется

тройка (q, w, u), где

q Q - текущее состояние управляющего устройства;

w T* - непрочитанная часть входной цепочки; первый символ цепочки w находится под входной головкой; если w = e, то считается, что вся входная лента прочитана;

u * - содержимое магазина; самый левый символ цепочки u считается верхним символом магазина; если u = e, то магазин считается пустым.

Такт работы МП-автомата M будем представлять в виде бинарного отношения , определенного на конфигурациях. Будем писать

если множество D(q, a, Z) содержит (p, v), где q, p Q, a T {e}, w T*, Z и u, v *.

Начальной конфигурацией МП-автомата M называется конфигурация вида (q0, w, Z0), где w T*, т.е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно проанализировать, а в магазине находится только начальный символ Z0.

Заключительная конфигурация - это конфигурация вида (q, e, u), где q F, u *, т.е. управляющее устройство находится

в одном из заключительных состояний, а входная цепочка целиком прочитана.

Введем транзитивное и рефлексивно-транзитивное замыкание отношения , а также его степень k 0 (обозначаемые +, * и k соответственно).

Говорят, что цепочка w допускается МП-автоматом M, если (q0, w, Z0) *(q, e, u) для некоторых q F и u *.

Язык, допускаемый (распознаваемый, определяемый) автоматомM (обозначается L(M)) - это множество всех цепочек, допускаемых автоматом M.

Пример 4.1. Рассмотрим МП-автомат



у которого функция переходов D содержит следующие элементы:

 

D(q0, a, Z) = {(q0, aZ)},

D(q0, b, Z) = {(q0, bZ)},

D(q0, a, a) = {(q0, aa), {q1, e)},

D(q0, a, b) = {(q0, ab)},

D(q0, b, a) = {(q0, ba)},

D(q0, b, b) = {(q0, bb), (q1, e)},



D(q1, a, a) = {(q1, e)},

D(q1, b, b) = {(q1, e)},

D(q1, e, Z) = {(q2, e)}.

 

Нетрудно показать, что L(M) = {wwR|w {a, b}+}, где wR

обозначает обращение («переворачивание») цепочки w.

Иногда допустимость определяют несколько иначе: цепочка w допускается МП-автоматом M, если (q0, w, Z0) *(q, e, e) для некоторого q Q. В таком случае говорят, что автомат допускает цепочку опустошением магазина. Эти определения эквивалентны, ибо справедлива

Теорема 4.1. Язык допускается магазинным автоматом тогда и только тогда, когда он допускается (некоторым другим автоматом) опустошением магазина.

Доказательство. Пусть L = L(M) для некоторого МП-автомата M = (Q, T, , D, q0, Z0, F). Построим новый МП-автомат M', допускающий тот же язык опустошением магазина.

Пусть M' = (Q{q0', qe}, T, {Z0'}, D', q0', Z0', ), где функция переходов D' определена следующим образом:

Если (r, u) D(q, a, Z), то (r, u) D'(q, a, Z) для всех q Q, a T {e} и Z ;

D'(q0', e, Z0') = {(q0, Z0Z0')};

Для всех q

F и Z {Z0'} множество D'(q, e, Z) содержит (qe, e);

D'(qe, e, Z) = {(qe, e)} для всех Z {Z0'}.

Автомат сначала переходит в конфигурацию (q0, w, Z0Z0') в соответствии с определением D' в п.2, затем в (q, e, Y 1...Y kZ0'), q F в соответствии с п.1, затем в (qe, e, Y 1...Y kZ0'), q F в соответствии с п.3, затем в (qe, e, e) в соответствии с п.4. Нетрудно показать по индукции, что (q0, w, Z0) +(q, e, u) (где q F) выполняется для автомата M тогда и только тогда, когда (q0', w, Z0') +(qe, e, e) выполняется для автомата M'. Поэтому L(M) = L', где L' - язык, допускаемый автоматом M' опустошением магазина.

 

Обратно, пусть M = (Q, T, , D, q0, Z0, ) - МП-автомат, допускающий опустошением магазина язык L.

Построим автомат M', допускающий тот же язык по заключительному состоянию.

Пусть M' = (Q{q0', qf}, T, {Z0}, D', q0', Z0', {qf}), где D' определяется следующим образом:

D'(q0', e, Z0') = {(q0, Z0Z0')} - переход в «режим M»;

Для каждого q Q, a T{e}, и Z определим D'(q, a, Z) = D(q, a, Z) - работа в «режиме M»;



Для всех q

Q, (qf, e) D'(q, e, Z0') - переход в заключительное состояние.

Нетрудно показать по индукции, что L = L(M'). __

Одним из важнейших результатов теории контекстно-свободных языков является доказательство эквивалентности

МП-автоматов и КС-грамматик.

Теорема 4.2. Язык является контекстно-свободным тогда и только тогда, когда он допускается магазинным автоматом.

Доказательство. Пусть G = (N, T, P, S) - КС-грамматика. Построим МП-автомат M, допускающий язык L(G) опустошением магазина.

Пусть M = ({q}, T, N T, D, q, S, ), где D определяется следующим образом:

Если A u P, то (q, u) D(q, e, A);

D(q, a, a) = {(q, e)} для всех a T.

Фактически, этот МП-автомат в точности моделирует все возможные выводы в грамматике

G. Нетрудно показать по индукции, что для любой цепочки w T*

вывод S +w в грамматике G существует тогда и только тогда, когда существует последовательность тактов (q, w, S) +(q, e, e) автомата M.

 

Обратно, пусть M = (Q, T, , D, q0, Z0, ) - МП-автомат, допускающий опустошением магазина язык L. Построим грамматику G, порождающую язык L.

Пусть G = ({ [qZr] | q, r Q, Z }{S}, T, P, S), где P состоит из правил следующего вида:

Если (r, X1...Xk) D(q, a, Z), k 1, то

для любого набора s1, s2, ..., sk состояний из Q;

Если (r, e) D(q, a, Z), то [qZr] a P, a T {e};

S [q0Z0q] P для всех q Q.

Нетерминалы и правила вывода грамматики определены так, что работе автомата M при обработке цепочки w соответствует левосторонний вывод w в грамматике G.

Индукцией по числу шагов вывода в G или числу тактов M нетрудно показать, что (q, w, A) +(p, e, e) тогда и только тогда, когда [qAp] +w.

Тогда, если w L(G), то S [q0Z0q] +w для некоторого q Q. Следовательно, (q0, w, Z0) +(q, e, e) и поэтому

w L. Аналогично, если w L, то (q0, w, Z0) +(q, e, e). Значит, S [q0Z0q] +w, и поэтому w L(G). __

МП-автомат M = (Q, T, , D, q0, Z0, F) называется детерминированным (ДМП-автоматом), если выполнены следующие два условия:

Множество D(q, a, Z) содержит не более одного элемента для любых q Q, a T {e}, Z ;



Если D(q, e, Z), то D(q, a, Z) = для всех a T.

Язык, допускаемый ДМП-автоматом, называется детерминированным КС-языком.

Так как функция переходов ДМП- автомата содержит не более одного элемента для любой тройки

аргументов, мы будем пользоваться записью D(q, a, Z) = (p, u) для обозначения D(q, a, Z) = {(p, u)}.

Пример 4.2. Рассмотрим ДМП-автомат



у которого функция переходов определяется следующим образом:

 

D(q0, X, Y ) = (q0, XY ), X {a, b}, Y {Z, a, b},

D(q0, c, Y ) = (q1, Y ), Y {a, b},

D(q1, X, X) = (q1, e), X {a, b},

D(q1, e, Z) = (q2, e).

 

Нетрудно показать, что этот детерминированный МП-автомат допускает язык L = {wcwR|w {a, b}+}.

К сожалению, ДМП-автоматы имеют меньшую распознавательную способность, чем МП-автоматы. Доказано, в частности, что

существуют КС-языки, не являющиеся детерминированными КС-языками (таковым, например, является язык из примера 4.1).

Рассмотрим еще одну важную разновидность МП-автомата.

Расширенным автоматом с магазинной памятью назовем семерку M = (Q, T, , D, q0, Z0, F), где смысл всех символов тот же, что и для обычного МП-автомата, кроме D, представляющего собой отображение конечного подмножества множества QЧ(T {e})Ч*

во множество конечных подмножеств множества QЧ*. Все остальные определения (конфигурации, такта, допустимости) для расширенного

МП-автомата остаются такими же, как для обычного.

Теорема 4.3. Пусть M = (Q, T, , D, q0, Z0, F) - расширенный МП-автомат. Тогда существует такой МП-автомат M', что L(M') = L(M).

Расширенный МП-автомат M = (Q, T, , D, q0, Z0, F) называется детерминированным, если выполнены следующие условия:

Множество D(q, a, u) содержит не более одного элемента для любых q Q, a T {e}, Z *;

Если D(q, a, u), D(q, a, v) и uv, то не существует цепочки x такой, что u = vx или v = ux;

Если D(q, a, u), D(q, e, v), то не существует цепочки x такой, что u = vx или v = ux.

Теорема 4.4. Пусть M = (Q, T, , D, q0, Z0, F) - расширенный ДМП-автомат. Тогда существует такой ДМП-автомат M', что L(M') = L(M).

ДМП-автомат и расширенный ДМП-автомат лежат в основе рассматриваемых далее в этой главе, соответственно, LL и LR-анализаторов.

Лексический анализ

Основная задача лексического анализа - разбить входной текст, состоящий из последовательности одиночных символов, на последовательность слов, или лексем, т.е. выделить эти слова из непрерывной последовательности символов. Все символы входной последовательности с этой точки зрения разделяются на символы, принадлежащие каким-либо лексемам, и символы, разделяющие лексемы (разделители). В некоторых случаях между лексемами может и не быть разделителей. С другой стороны, в некоторых языках

лексемы могут содержать незначащие символы (например, символ пробела в Фортране). В Си разделительное значение символов-разделителей может блокироваться («\» в конце строки внутри "...").

Обычно все лексемы делятся на классы. Примерами таких классов являются числа (целые, восьмеричные, шестнадцатиричные, действительные и т.д.), идентификаторы, строки. Отдельно выделяются ключевые слова и символы пунктуации (иногда их называют символы-ограничители). Как правило, ключевые слова - это некоторое конечное

подмножество идентификаторов. В некоторых языках (например, ПЛ/1) смысл лексемы может зависеть от ее контекста и невозможно провести лексический анализ в отрыве от синтаксического.

С точки зрения дальнейших фаз анализа лексический анализатор выдает информацию двух сортов: для синтаксического анализатора, работающего вслед за лексическим, существенна информация о последовательности классов лексем, ограничителей и ключевых слов, а для контекстного анализа, работающего вслед за синтаксическим, важна информация

о конкретных значениях отдельных лексем (идентификаторов, чисел и т.д.).

Таким образом, общая схема работы лексического анализатора такова. Сначала выделяется отдельная лексема (возможно, используя символы-разделители). Ключевые слова распознаются либо явным выделением непосредственно из текста, либо сначала выделяется идентификатор, а затем делается проверка на принадлежность его множеству ключевых слов.

Если выделенная лексема является ограничителем, то он (точнее, некоторый его признак) выдается как

результат лексического анализа. Если выделенная лексема является ключевым словом, то выдается признак соответствующего ключевого слова. Если выделенная лексема является идентификатором - выдается признак идентификатора, а сам идентификатор сохраняется отдельно. Наконец, если выделенная лексема принадлежит какому-либо из других классов лексем (например, лексема представляет собой число, строку и т.д.), то выдается признак соответствующего класса, а значение лексемы сохраняется отдельно.

Лексический

анализатор может быть как самостоятельной фазой трансляции, так и подпрограммой, работающей по принципу «дай лексему». В первом случае (рис.3.1, а) выходом анализатора является файл лексем, во втором (рис. 3.1, б) лексема выдается при каждом обращении к анализатору (при этом, как правило, признак класса лексемы возвращается как результат функции «лексический анализатор», а значение лексемы передается через глобальную переменную). С точки зрения обработки значений лексем, анализатор

может либо просто выдавать значение каждой лексемы, и в этом случае построение таблиц объектов (идентификаторов, строк, чисел и т.д.) переносится на более поздние фазы, либо он может самостоятельно строить таблицы объектов. В этом случае в качестве значения лексемы выдается указатель на вход в соответствующую таблицу.

Рис. 3.1:

Работа лексического анализатора задается некоторым конечным автоматом. Однако, непосредственное описание конечного автомата неудобно с практической точки зрения. Поэтому для задания лексического анализатора, как правило, используется либо регулярное выражение, либо праволинейная грамматика. Все три формализма (конечных автоматов, регулярных выражений и праволинейных грамматик) имеют одинаковую выразительную мощность. В частности, по регулярному выражению или праволинейной грамматике

можно сконструировать конечный автомат, распознающий тот же язык.

Левая факторизация

Oсновная идея левой факторизации в том, что в том случае, когда неясно, какую из двух альтернатив надо использовать для развертки нетерминала A, нужно изменить A-правила так, чтобы отложить решение до

тех пор, пока не будет достаточно информации для принятия правильного решения.

Если A

1 | 2 - два A-правила и входная цепочка начинается с непустой строки, выводимой из , мы не знаем, разворачивать ли по первому правилу или по второму. Можно отложить решение, развернув A A'. Тогда после анализа того, что выводимо из , можно развернуть по A' 1 или по A' 2. Левофакторизованные правила принимают вид

Алгоритм 4.8. Левая факторизация грамматики.

Вход. КС-грамматика G.

Выход. Левофакторизованная КС-грамматика G', эквивалентная G.

Метод. Для каждого нетерминала A ищем самый длинный префикс

, общий для двух или более его альтернатив. Если e, т.е. существует нетривиальный общий префикс, заменяем все A-правила

где z обозначает все альтернативы, не начинающиеся с , на

где A' - новый нетерминал. Повторно применяем это преобразование, пока никакие две альтернативы не будут иметь общего префикса.

Пример 4.7. Рассмотрим вновь грамматику условных

операторов из примера 4.6:

	S if E then S | if E then S else S | a
	E b

После левой факторизации грамматика принимает вид

	S if E then SS'| a
	S' else S | e
	E b

К сожалению, грамматика остается неоднозначной, а значит, и не LL(1).

Линеаризованные представления

В качестве промежуточных представлений весьма распространены линеаризованные представления деревьев. Линеаризованное представление позволяет относительно легко хранить промежуточное представление во внешней памяти и обрабатывать его. Наиболее распространенной формой линеаризованного представления является польская запись - префиксная (прямая) или постфиксная (обратная).

Постфиксная запись - это список вершин дерева, в котором каждая вершина

следует (при обходе снизу-вверх слева-направо) непосредственно за своими потомками. Дерево на рис.8.1, а, в постфиксной записи может быть представлено следующим образом:

В постфиксной записи вершины синтаксического дерева явно не присутствуют. Они могут быть восстановлены из порядка, в котором следуют вершины и из числа операндов соответствующих операций. Восстановление вершин

аналогично вычислению выражения в постфиксной записи с использованием стека.

В префиксной записи сначала указывается операция, а затем ее операнды. Например, для приведенного выше выражения имеем

Рассмотрим детальнее одну из реализаций префиксного представления - Лидер [9]. Лидер - это аббревиатура от «ЛИнеаризованное ДЕРево». Это машинно-независимая префиксная запись. В Лидере

сохраняются все объявления и каждому из них присваивается свой уникальный номер, который используется для ссылки на объявление. Рассмотрим пример.

module M;         var X,Y,Z: integer;         procedure DIF(A,B:integer):integer;            var R:integer;            begin R:=A-B;                  return(R);            end DIF;         begin Z:=DIF(X,Y);         end M.

<
Этот фрагмент имеет следующий образ в Лидере.

program 'M'        var int        var int        var int        procbody proc int int end int           var int           begin assign var 1 7 end                        int int mi par 1 5 end par 1 6 end                 result 0 int var 1 7 end                 return           end        begin assign var 0 3 end int              icall 0 4 int var 0 1 end              int var 0 2 end end        end

Рассмотрим его более детально:

program 'M'		Имя модуля нужно для редактора связей.
var int		Это образ переменных X, Y, Z;
var int		переменным X, Y, Z присваиваются номера
var int		1, 2, 3 на уровне 0.
procbody proc		Объявление процедуры с двумя
int int end		целыми параметрами, возвращающей целое.
int		Процедура получает номер 4 на уровне 0 и
		параметры имеют номера 5, 6 на уровне 1.
var int		Переменная R имеет номер 7 на уровне 1.
begin		Начало тела процедуры.
assign		Оператор присваивания.
var 1 7 end		Левая часть присваивания (R).
int		Тип присваиваемого значения.
int mi		Целое вычитание.
par 1 5 end		Уменьшаемое (A).
par 1 6 end		Вычитаемое (B).
result 0		Результат процедуры уровня 0.
int		Результат имеет целый тип.
var 1 7 end		Результат - переменная R.
return		Оператор возврата.
end		Конец тела процедуры.
begin		Начало тела модуля.
assign		Оператор присваивания.
var 0 3 end		Левая часть - переменная Z.
int		Тип присваиваемого значения.
icall 0 4		Вызов локальной процедуры DIF.
int var 0 1 end		Фактические параметры X
int var 0 2 end		и Y.
end		Конец вызова.
end		Конец тела модуля.

Литература

[1]   Адельсон-Вельский Г.М., Ландис Е.М. Один алгоритм организации информации. ДАН СССР. 1962. Т.146. N 2. С. 263-266.

[2]   Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции, в 2-х т. М.: Мир, 1978.

[3]   Бездушный А.Н., Лютый В.Г., Серебряков В.А. Разработка компиляторов в системе СУПЕР. М.: ВЦ АН СССР, 1991.

[4]   Грис Д. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975.

[5]   Кнут Д. Искусство программирования для ЭВМ. Т.1. Основные алгоритмы. М.: Мир, 1976.

[6]   Кнут Д. Семантика контекстно-свободных языков. В сб.: Семантика языков программирования. М.: Мир, 1980.

[7]   Курочкин В.М. Алгоритм распределения регистров для выражений за один обход дерева вывода. 2 Всес. конф «Автоматизация производства ППП и

трансляторов». 1983. С. 104-105.

[8]   Лавров С.С., Гончарова Л.И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971.

[9]   Надежин Д.Ю., Серебряков В.А., Ходукин В.М. Промежуточный язык Лидер (предварительное сообщение). Обработка символьной информации. М.: ВЦ АН СССР, 1987. С. 50-63.

[10]   Aho A., Sethi R., Ullman J. Compilers: principles, techniques and tools. N.Y.: Addison-Wesley, 1986.

[11]   Aho A.U., Ganapathi M., Tjiang S.W. Code generation using tree matching and dynamic programing. ACM Trans. Program. Languages and Systems. 1989. V.11.N 4.

[12]   Bezdushny A., Serebriakov V. The use of the parsing method for

optimal code generation and common subexpression elimination. Techn. et Sci. Inform. 1993. V.12. N.1. P.69-92.

[13]   Emmelman H., Schroer F.W., Landweher R. BEG - a generator for efficient back-ends. ACM SIGPLAN. 1989. V.11. N 4.p.227-237

[14]   Fraser C.W., Hanson D.R. A Retargetable compiler for ANSI C. SIGPLAN Notices. 1991. V 26.

[15]   Graham S.L., Harrison M.A., Ruzzo W.L. An improved context-free recognizer. ACM Trans. Program. Languages and Systems. 1980. N.2.

[16]   Harrison M.A. Introduction to formal language theory. Reading, Mass.: Addison-Wesley, 1978.

LL(1)-грамматики

Алгоритм 4.6 для построения таблицы предсказывающего анализатора может быть применен к любой КС-грамматике. Однако для некоторых грамматик построенная таблица может иметь неоднозначно определенные входы. Нетрудно доказать, например, что если грамматика леворекурсивна или неоднозначна, таблица будет иметь по крайней мере один неоднозначно определенный вход.

Грамматики, для которых таблица предсказывающего анализатора не имеет неоднозначно определенных входов, называются LL(1)-грамматиками.

Предсказывающий анализатор, построенный для LL(1)-грамматики, называется LL(1)-анализатором. Первая буква L в названии связано с тем, что входная цепочка читается слева направо, вторая L означает, что строится левый вывод входной цепочки, 1 - что на каждом шаге для принятия решения используется один символ непрочитанной части входной цепочки.

Доказано, что алгоритм 4.6 для каждой LL(1)-грамматики G строит таблицу предсказывающего анализатора, распознающего все цепочки из L(G) и только эти цепочки.

Нетрудно доказать также, что если G - LL(1)-грамматика, то L(G) - детерминированный КС-язык.

Справедлив также следующий критерий LL(1)-грамматики. Грамматика G = (N, T, P, S) является LL(1)-грамматикой тогда и только тогда, когда для каждой пары правил A

, A из P (т.е. правил с одинаковой левой частью) выполняются следующие 2 условия:

FIRST(

) FIRST() = ;

Если e

FIRST(), то FIRST() FOLLOW(A) = .

Язык, для которого существует порождающая его LL(1)-грамматика, называют LL(1)-языком. Доказано,

что проблема определения того, порождает ли грамматика LL-язык, является алгоритмически неразрешимой.

Пример 4.6. Неоднозначная грамматика не является LL(1). Примером может служить следующая грамматика G = ({S, E}, {if, then, else, a, b}, P, S) с правилами:

	S if E then S | if E then S else S | a
	E b

Эта грамматика является неоднозначной, что иллюстрируется на рис. 4.6.

Рис. 4.6:

LR(1)-анализаторы

В названии LR(1) символ L указывает на то, что входная цепочка читается слева-направо, R - на то, что строится правый вывод, наконец, 1 указывает на то, что анализатор видит один символ непрочитанной части входной цепочки.

LR(1)-анализ привлекателен по нескольким причинам:

LR(1)-анализ -

наиболее мощный метод анализа без возвратов типа сдвиг-свертка;

LR(1)-анализ может быть реализован довольно эффективно;

LR(1)-анализаторы могут быть построены для практически всех конструкций языков программирования;

класс грамматик, которые могут быть проанализированы LR(1)-методом, строго включает класс грамматик, которые могут быть проанализированы предсказывающими анализаторами (сверху-вниз типа LL(1)).

Схематически структура LR(1)-анализатора изображена на рис. 4.8. Анализатор состоит из входной ленты, выходной ленты, магазина,

управляющей программы и таблицы анализа (LR(1)-таблицы), которая имеет две части - функцию действий (Action) и функцию переходов (Goto). Управляющая программа одна и та же для всех LR(1)-анализаторов, разные анализаторы отличаются только таблицами анализа.

Программа анализатора читает символы на входной ленте по одному за шаг. В процессе анализа используется магазин, в котором хранятся строки вида S0X1S1X2S2...XmSm (Sm - верхушка магазина). Каждый Xi

- символ грамматики (терминальный или

нетерминальный), а Si - символ состояния.

Заметим, что символы грамматики (либо символы состояний) не обязательно должны размещаться в магазине. Однако, их использование облегчает понимание поведения LR-анализатора.

Рис. 4.8:

Элемент функции действий Action[Sm, ai] для символа состояния Sm и входа ai

T {$}, может иметь одно из четырех значений:

shift S (сдвиг), где S - символ состояния,

reduce A

(свертка по правилу грамматики A ),

accept (допуск),

error (ошибка).

Элемент функции переходов Goto[Sm, A] для символа состояния Sm и входа A

N, может иметь одно из двух значений:

S, где S - символ состояния,

error (ошибка).

Конфигурацией LR(1)-анализатора называется пара, первая компонента которой - содержимое магазина, а вторая - непросмотренный вход:

Эта конфигурация соответствует правой сентенциальной форме



Префиксы правых сентенциальных форм, которые могут появиться в магазине

анализатора, называются активными префиксами. Основа сентенциальной формы всегда располагается на верхушке магазина. Таким образом, активный префикс - это такой префикс правой сентенциальной формы, который не переходит правую границу основы этой формы.

В начале работы анализатора в магазине находится только символ начального состояния S0, на входной ленте - анализируемая цепочка с маркером конца.

Очередной шаг анализатора определяется текущим входным

символом ai

и символом состояния на верхушке магазина Sm

следующим образом.

Пусть LR(1)-анализатор находится в конфигурации



Анализатор может проделать один из следующих шагов:

Если Action[Sm, ai] = shift S, то анализатор выполняет сдвиг, переходя в конфигурацию



Таким образом, в магазин помещаются входной символ ai и символ состояния S, определяемый Action[Sm, ai]. Текущим входным символом становится ai+1.

Если Action[Sm, ai] = reduce A , то анализатор выполняет свертку, переходя в конфигурацию

где S = Goto[Sm-r, A] и r - длина , правой части правила вывода.

Анализатор сначала удаляет из магазина 2r символов (r символов состояния и r символов грамматики), так что на верхушке оказывается состояние Sm-r. Затем анализатор

помещает в магазин A - левую часть правила вывода, и S - символ состояния, определяемый Goto[Sm-r, A]. На шаге свертки текущий входной символ не меняется. Для LR(1)-анализаторов Xm-r+1...Xm - последовательность символов грамматики, удаляемых из магазина, всегда соответствует - правой части правила вывода, по которому делается свертка.

После осуществления шага свертки генерируется выход LR(1)-анализатора, т.е. исполняются семантические действия, связанные с правилом, по которому делается свертка, например, печатаются номера правил, по которым делается свертка.

Заметим, что функция Goto таблицы анализа, построенная

по грамматике G, фактически представляет собой функцию переходов детерминированного конечного автомата, распознающего активные префиксы G.



Если Action[Sm, ai] = accept, то разбор успешно завершен.

Если Action[Sm, ai] = error, то анализатор обнаружил ошибку, и выполняются действия по диагностике и восстановлению.

Пример 4.8. Рассмотрим грамматику арифметических выражений G = ({E, T, F}, {id, +, *}, P, E) с правилами:

 

	(1) E E + T
	(2) E T
	(3) T T * F
	(4) T F
	(5) F id

 

На рис. 4.9 изображены функции Action и Goto, образующие LR(1)-таблицу для этой

грамматики. Для Элемент Si функции Action означает сдвиг и помещение в магазин состояния с номером i, Rj - свертку по правилу номер j, acc - допуск, пустая клетка - ошибку. Для функции Goto символ i означает помещение в магазин состояния с номером i, пустая клетка - ошибку.

На входе id + id * id последовательность состояний магазина и входной ленты показаны на рис. 4.10. Например, в первой строке LR-анализатор находится в нулевом состоянии и «видит» первый входной символ id. Действие S6 в нулевой строке и столбце id в поле Action (рис. 4.9) означает

сдвиг и помещение символа состояния 6 на верхушку магазина. Это и изображено во второй строке: первый символ id и символ состояния 6 помещаются в магазин, а id удаляется со входной ленты.

Рис. 4.9:

Рис. 4.10:

Текущим входным символом становится +, и действием в состоянии 6 на вход + является свертка по F id. Из магазина удаляются два символа (один символ состояния и один символ грамматики). Затем анализируется нулевое состояние. Поскольку Goto в нулевом состоянии по символу F - это 3, F и 3 помещаются в магазин. Теперь имеем конфигурацию, соответствующую третьей строке. Остальные шаги определяются аналогично.

LR(1)-грамматики

Если для КС-грамматики G функция Action, полученная в результате работы алгоритма 4.10, не содержит неоднозначно определенных входов, то грамматика называется LR(1)-грамматикой.

Язык L называется LR(1)-языком, если он может быть порожден некоторой LR(1)-грамматикой.

Иногда используется другое определение LR(1)-грамматики. Грамматика называется LR(1), если из условий

1. S'

r*uAw ruvw,

2. S'

r*zBx ruvy,

3. FIRST(w) = FIRST(y)

следует, что uAy = zBx (т.е. u = z, A = B и x = y).

Согласно этому

определению, если uvw и uvy - правовыводимые цепочки пополненной грамматики, у которых FIRST(w) = FIRST(y) и A

v - последнее правило, использованное в правом выводе цепочки uvw, то правило A v должно применяться и в правом разборе при свертке uvy к uAy. Так как A дает v независимо от w, то LR(1)-условие означает, что в FIRST(w) содержится информация, достаточная для определения того, что uv за один шаг выводится из uA. Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку

пополненной грамматики.

Можно доказать, что эти два определения эквивалентны.

Если грамматика не является LR(1), то анализатор типа сдвиг-свертка при анализе некоторой цепочки может достигнуть конфигурации, в которой он, зная содержимое магазина и следующий входной символ, не может решить, делать ли сдвиг или свертку (конфликт сдвиг/свертка), или не может решить, какую из нескольких сверток применить (конфликт свертка/свертка).

В частности, неоднозначная грамматика

не может быть LR(1). Для доказательства рассмотрим два различных правых вывода

(1) S

ru1 r... run rw, и

(2) S

rv1 r... rvm rw.

Нетрудно заметить, что LR(1)-условие (согласно второму определению LR(1)-грамматики) нарушается для наименьшего из чисел i, для которых un-i

vm-i.

Пример 4.11. Рассмотрим вновь грамматику условных операторов:

 

	S if E then S | if E then S else S | a
	E b

 

Если анализатор типа сдвиг-свертка находится в конфигурации, такой что необработанная часть входной цепочки имеет вид else...$, а в магазине

находится ...if E then S, то нельзя определить, является ли if E then S основой, вне зависимости от того, что лежит в магазине ниже. Это конфликт сдвиг/свертка. В зависимости от того, что следует на входе за else, правильной может быть свертка по S if E then S или сдвиг else, а затем разбор другого S и завершение основы if E then S else S. Таким образом нельзя сказать, нужно ли в этом случае делать сдвиг или свертку, так что грамматика не является LR(1).

Эта грамматика может быть преобразована к LR(1)-виду следующим образом:

 

	S M | U
	M if E then M else M | a
	U if E then S | if E then M else U
	E b

Основная разница между LL(1)- и LR(1)-грамматиками заключается в следующем. Чтобы грамматика была LR(1), необходимо распознавать вхождение правой части правила вывода, просмотрев все, что выведено из этой правой части и текущий символ входной цепочки. Это требование существенно менее строгое, чем требование для LL(1)-грамматики, когда необходимо определить применимое правило, видя только первый символ,

выводимый из его правой части. Таким образом, класс LL(1)-грамматик является собственным подклассом класса LR(1)-грамматик.

Справедливы также следующие утверждения [2].

Теорема 4.5. Каждый LR(1)-язык является детерминированным КС-языком.

Теорема 4.6. Если L - детерминированный КС-язык, то существует LR(1)-грамматика, порождающая L.

Место компилятора в программном обеспечении

Компиляторы составляют существенную часть программного обеспечения ЭВМ. Это связано с тем, что языки высокого уровня стали основным средством разработки программ. Только очень незначительная часть программного обеспечения, требующая особой эффективности, программируется с помощью ассемблеров. В настоящее время распространено довольно много языков программирования. Наряду с традиционными языками, такими, как Фортран, широкое

распространение получили так называемые «универсальные» языки (Паскаль, Си, Модула-2, Ада и другие), а также некоторые специализированные (например, язык обработки списочных структур Лисп). Кроме того, большое распространение получили языки, связанные с узкими предметными областями, такие, как входные языки пакетов прикладных программ.

Для некоторых языков имеется довольно много реализаций. Например, реализаций Паскаля, Модулы-2 или Си для ЭВМ типа IBM PC на рынке десятки.

С другой стороны, постоянно растущая потребность в новых компиляторах связана с бурным развитием архитектур ЭВМ. Это развитие идет по различным направлениям. Совершенствуются старые архитектуры как в концептуальном отношении, так и по отдельным, конкретным линиям. Это можно проиллюстрировать на примере микропроцессора Intel-80X86. Последовательные версии этого микропроцессора 8086, 80186, 80286, 80386, 80486, 80586 отличаются не только техническими характеристиками, но и, что более важно, новыми возможностями и, значит, изменением (расширением) системы

команд. Естественно, это требует новых компиляторов (или модификации старых). То же можно сказать о микропроцессорах Motorola 68010, 68020, 68030, 68040.

В рамках традиционных последовательных машин возникает большое число различных направлений архитектур. Примерами могут служить архитектуры CISC, RISC. Такие ведущие фирмы, как Intel, Motorola, Sun, начинают переходить на выпуск машин с RISC-архитектурами. Естественно, для каждой новой системы команд требуется полный набор новых компиляторов с распространенных языков.

Наконец,

бурно развиваются различные параллельные архитектуры. Среди них отметим векторные, многопроцессорные, с широким командным словом (вариантом которых являются суперскалярные ЭВМ). На рынке уже имеются десятки типов ЭВМ с параллельной архитектурой, начиная от супер-ЭВМ (Cray, CDC и другие), через рабочие станции (например, IBM RS/6000) и кончая персональными (например, на основе микропроцессора I-860). Естественно, для каждой из машин создаются новые компиляторы для многих языков программирования. Здесь необходимо также

отметить, что новые архитектуры требуют разработки совершенно новых подходов к созданию компиляторов, так что наряду с собственно разработкой компиляторов ведется и большая научная работа по созданию новых методов трансляции.

Модель машины

При изложении алгоритмов генерации кода мы будем следовать некоторой модели машины, в основу которой положена система команд микропроцессора Motorola MC68020. В микропроцессоре имеется регистр - счетчик команд PC, 8 регистров данных и 8 адресных регистров.

В системе команд используются следующие способы адресации:

ABS - абсолютная: исполнительным адресом является значение адресного выражения.

IMM - непосредственный операнд: операндом команды

является константа, заданная в адресном выражении.

D - прямая адресация через регистр данных, записывается как Хn, операнд находится в регистре Хn.

А - прямая адресация через адресный регистр, записывается как An, операнд находится в регистре An.

INDIRECT - записывается как (An), адрес операнда находится в адресном регистре An.

POST - пост-инкрементная адресация, записывается как (Аn)+, исполнительный адрес есть значение адресного регистра An и после исполнения команды значение

этого регистра увеличивается на длину операнда.

PRE - пре-инкрементная адресация, записывается как -(Аn): перед исполнением операции содержимое адресного регистра An уменьшается на длину операнда, исполнительный адрес равен новому содержимому адресного регистра.

INDISP - косвенная адресация со смещением, записывается как (bd,An), исполнительный адрес вычисляется как (An)+d - содержимое An плюс d.

INDEX - косвенная адресация с индексом, записывается как (bd,An,Xn*sc), исполнительный адрес вычисляется как (An)+bd+(Xn)*sc - содержимое адресного

регистра + адресное смещение + содержимое индексного регистра, умноженное на sc.

INDIRPC - косвенная через PC (счетчик команд), записывается как (bd,PC), исполнительный адрес определяется выражением (PC)+bd.

INDEXPC - косвенная через PC со смещением, записывается как (bd,PC,Xn*sc), исполнительный адрес определяется выражением (PC)+bd+(Xn)*sc.

INDPRE - пре-косвенная через память, записывается как ([bd,An,sc*Xn],od) (схема вычисления адресов для этого и трех последующих способов адресации приведена ниже).

INDPOST - пост-косвенная через

память: ([bd,An],sc*Xn,od).

INDPREPC - пре-косвенная через PC: ([bd,PC,sc*Xn],od).

INDPOSTPC - пост-косвенная через PC: ([bd,PC],Xn,od).

Здесь bd - это 16- или 32- битная константа, называемая смещением, od - 16- или 32-битная литеральная константа, называемая внешним смещением. Эти способы адресации могут использоваться в упрощенных формах без смещений bd и/или od и без регистров An или Xn. Следующие примеры иллюстрируют косвенную постиндексную адресацию:

MOVE D0, ([A0])     MOVE D0, ([4,A0])     MOVE D0, ([A0],6)     MOVE D0, ([A0],D3)     MOVE D0, ([A0],D4,12)     MOVE D0, ([$12345678,A0],D4,$FF000000)

Индексный регистр Xn может масштабироваться (умножаться) на 2,4,8, что записывается как sc*Xn. Например, в исполнительном адресе ([24,A0,4*D0]) содержимое квадратных скобок вычисляется как [A0] + 4 * [D0] + 24.

Эти способы адресации работают следующим образом. Каждый исполнительный адрес содержит пару квадратных скобок [...] внутри пары круглых скобок, т.е. ([...], ... ). Сначала вычисляется содержимое квадратных

скобок, в результате чего получается 32-битный указатель. Например, если используется постиндексная форма [20,A2], то исполнительный адрес - это 20 + [A2]. Аналогично, для преиндексной формы [12,A4,D5] исполнительный адрес - это 12 + [A4] + [D5].

Указатель, сформированный содержимым квадратных скобок, используется для доступа в память, чтобы получить новый указатель (отсюда термин косвенная адресация через память). К этому новому указателю добавляется содержимое внешних круглых

скобок и таким образом формируется исполнительный адрес операнда.

В дальнейшем изложении будут использованы следующие команды (в частности, рассматриваются только арифметические команды с целыми операндами, но не с плавающими):

MOVEA ИА, А - загрузить содержимое по исполнительному адресу ИА на адресный регистр А.



MOVE ИА1, ИА2 - содержимое по исполнительному адресу ИА1 переписать по исполнительному адресу ИА2.

MOVEM список_регистров, ИА - сохранить указанные регистры в памяти, начиная с адреса ИА (регистры указываются

маской в самой команде).

MOVEM ИА, список_регистров - восстановить указанные регистры из памяти, начиная с адреса ИА (регистры указываются маской в самой команде).

LEA ИА, А - загрузить исполнительный адрес ИА на адресный регистр А.

MUL ИА, D - умножить содержимое по исполнительному адресу ИА на содержимое регистра данных D и результат разместить в D (на самом деле в системе команд имеются две различные команды MULS и MULU для чисел со знаком и чисел без знака соответственно; для упрощения

мы не будем принимать во внимание это различие).

DIV ИА, D - разделить содержимое регистра данных D на содержимое по исполнительному адресу ИА и результат разместить в D.

ADD ИА, D - сложить содержимое по исполнительному адресу ИА с содержимым регистра данных D и результат разместить в D.

SUB ИА, D - вычесть содержимое по исполнительному адресу ИА из содержимого регистра данных D и результат разместить в D.

Команды CMP и TST формируют разряды регистра состояний. Всего имеется 4 разряда: Z

- признак нулевого результата, N - признак отрицательного результата, V - признак переполнения, C - признак переноса.

CMP ИА, D - из содержимого регистра данных D вычитается содержимое по исполнительному адресу ИА, при этом формируется все разряды регистра состояний, но содержимое регистра D не меняется.

TST ИА - выработать разряд Z регистра состояний по значению, находящемуся по исполнительному адресу ИА.

BNE ИА - условный переход по признаку Z = 1 (не равно) по исполнительному адресу ИА.

BEQ ИА - условный переход по признаку

Z = 0 (равно) по исполнительному адресу ИА.

BLE ИА - условный переход по признаку N or Z (меньше или равно) по исполнительному адресу ИА.

BGT ИА - условный переход по признаку not N (больше) по исполнительному адресу ИА.

BLT ИА - условный переход по признаку N (меньше) по исполнительному адресу ИА.

BRA ИА - безусловный переход по адресу ИА.

JMP ИА - безусловный переход по исполнительному адресу.

RTD размер_локальных - возврат из подпрограммы с указанием размера локальных.

LINK A, размер_локальных - в стеке сохраняется значение регистра А,

в регистр А заносится указатель на это место в стеке и указатель стека продвигается на размер локальных.

UNLK A - стек сокращается на размер локальных и регистр А восстанавливается из стека.

Набор команд виртуальной машины

Виртуальная Java-машина имеет следующие команды:

помещение констант на стек,

помещение локальных переменных на стек,

запоминание значений из стека в локальных

переменных,

обработка массивов,

управление стеком,

арифметические команды,

логические команды,

преобразования типов,

передача управления,

возврат из функции,

табличный переход,

обработка полей объектов,

вызов метода,

обработка исключительных ситуаций,

прочие операции над объектами,

мониторы,

отладка.

 

Рассмотрим некоторые команды подробнее.

Назначение адресов

Назначение адресов переменным, параметрам и полям записей происходит при обработке соответствующих объявлений. В однопроходном трансляторе это может производиться вместе с построением основной таблицы символов и соответствующие адреса (или смещения) могут храниться в этой же таблице. В промежуточном представлении Лидер объявления сохранены, что делает это промежуточное представление машинно-независимым.

Напомним, что в Лидер-представлении каждому описанию соответствует некоторый номер. В процессе работы генератора кодов поддерживается таблица Table, в которой по этому номеру (входу) содержится следующая информация:

- для типа: его размер;

- для переменной: смещение в области процедуры (или глобальной области);

- для поля записи: смещение внутри записи;

- для процедуры: размер локальных параметров;

- для массива: размер массива, размер

элемента, значение левой и правой границы.

Функция IncTab вырабатывает указатель (вход) на новый элемент таблицы, проверяя при этом наличие свободной памяти.

Для вычисления адресов определим для каждого объявления два синтезируемых атрибута: DISP будет обозначать смещение внутри области процедуры (или единицы компиляции), а SIZE - размер. Тогда семантика правила для списка объявлений принимает вид

RULE DeclPart ::= ( Decl )   SEMANTICS       Disp=0;   1A: Disp=Disp+Size;       Size=Disp.

Все объявления, кроме объявлений переменных, имеют нулевой размер. Размер объявления переменной определяется следующим правилом:

RULE   Decl ::= 'VAR' TypeDes   SEMANTICS   Tablentry Entry;   0: Entry=IncTab;      Size=((Table[VAL]+1) / 2)*2;      // Выравнивание на границу слова      Table[Entry]=Disp+Size.

В качестве примера трансляции определения типа рассмотрим обработку описания записи:

RULE   TypeDes ::= 'REC' ( TypeDes ) 'END'   SEMANTICS   int Disp;   Tablentry Temp;   0: Entry=IncTab;      Disp=0;   2A: {Temp=IncTab;        Table[Temp]=Disp;        Disp=Disp+Table[Entry]+1) / 2)*2;        // Выравнивание на границу слова        }   Table[Entry]=Disp.

Обобщенные схемы синтаксически управляемого перевода

Расширим определение СУ-схемы, с тем чтобы выполнять

более широкий класс переводов. Во-первых, позволим иметь в каждой вершине дерева разбора несколько переводов. Как и в обычной СУ-схеме, каждый перевод зависит от прямых потомков соответствующей вершины дерева. Во-вторых, позволим элементам перевода быть произвольными цепочками выходных символов и символов, представляющих переводы в потомках. Таким образом, символы перевода могут повторяться или вообще отсутствовать.

Определение. Обобщенной схемой синтаксически управляемого перевода (или трансляции, сокращенно: OСУ-схемой) называется шестерка Tr = (N, T,

, , R, S), где все символы имеют тот же смысл, что и для СУ-схемы, за исключением того, что

- конечное множество символов перевода вида Ai, где A N и i - целое число;

R - конечное множество правил перевода вида

A

u, A1 = v1, ..., Am = vm,

удовлетворяющих следующим условиям:

Aj

для 1 j m,

каждый символ, входящий в v1, ..., vm, либо принадлежит

, либо является Bk , где B входит в u,

если u имеет более одного вхождения символа B, то каждый символ Bk

во всех v соотнесен (верхним индексом) с конкретным вхождением B.

A

u называют входным правилом вывода, Ai - переводом нетерминала A, Ai = vi - элементом перевода, связанным с этим правилом перевода. Если в ОСУ-схеме нет двух правил перевода с одинаковым входным правилом вывода, то ее называют семантически однозначной.

Выход ОСУ-схемы определим снизу вверх. С каждой внутренней вершиной n дерева разбора (во входной грамматике), помеченной A, свяжем одну цепочку для каждого Ai. Эта цепочка называется значением (или переводом) символа Ai

в вершине n. Каждое значение вычисляется подстановкой значений символов перевода данного элемента перевода Ai = vi, определенных в прямых потомках вершины n.

Переводом

(Tr), определяемым ОСУ-схемой Tr, назовем множество {(x, y) | x имеет дерево разбора во входной

грамматике для Tr и y - значение выделенного символа перевода Sk в корне этого дерева}.

Пример 5.4.
Рассмотрим формальное дифференцирование выражений, включающих константы 0 и 1, переменную x, функции sin и cos , а также операции * и +. Такие выражения порождает грамматика

 

	E E + T | T
	T T * F | F
	F (E) | sin (E) | cos (E) | x | 0 | 1

 

Свяжем с каждым из E, T и F два перевода, обозначенных индексом 1 и 2. Индекс 1 указывает на то, что выражение не дифференцировано, 2 - что выражение продифференцировано. Формальная производная - это E2. Законы дифференцирования таковы:

d(f(x) + g(x)) = df(x) + dg(x)

d(f(x) * g(x)) = f(x) * dg(x) + g(x) * df(x)

d sin (f(x)) = cos (f(x)) * df(x)

d cos (f(x)) = - sin (f(x))df(x)

dx = 1

d0 = 0

d1 = 0

Эти законы можно реализовать следующей ОСУ-схемой:

 

E E + T	E1 = E1 + T1
	E2 = E2 + T2
E T	E1 = T1
	E2 = T2
T T * F	T1 = T1 * F1
	T2 = T1 * F2 + T2 * F1
T F	T1 = F1
	T2 = F2
F (E)	F1 = (E1)
	F2 = (E2)
F sin (E)	F1 = sin (E1)
	F2 = cos (E1) * (E2)
F cos (E)	F1 = cos (E1)
	F2 = - sin (E1) * (E2)
F x	F1 = x
	F2 = 1
F 0	F1 = 0
	F2 = 0
F 1	F1 = 1
	F2 = 0

 

Дерево вывода для sin(cos (x))+x приведено на рис. 5.1.

Рис. 5.1:

Обработка исключительных ситуаций

Команда athrow - возбудить исключительную ситуацию.

С каждым методом связан список

операторов catch. Каждый оператор catch описывает диапазон инструкций, для которых он активен, тип исключения, который он обрабатывает. Кроме того, с оператором связан набор инструкций, которые его реализуют. При возникновении исключительной ситуации просматривается список операторов catch, чтобы установить соответствие. Исключительная ситуация соответствует оператору catch, если инструкция, вызвавшая исключительную ситуацию, находится в соответствующем диапазоне и исключительная ситуация принадлежит подтипу

типа ситуации, которые обрабатывает оператор catch. Если соответствующий оператор catch найден, управление передается обработчику. Если нет, текущий стек-фрейм удаляется, и исключительная ситуация возбуждается вновь.

Порядок операторов catch в списке важен. Интерпретатор передает управление первому подходящему оператору catch.

Описание областей видимости и блочной структуры

Задачей контекстного анализа является установление свойств объектов и их использования. Наиболее часто решаемой задачей является определение существования объекта и соответствия его использования контексту, что осуществляется с помощью анализа типа объекта. Под контекстом здесь понимается вся совокупность свойств текущей точки программы,

например множество доступных объектов, тип выражения и т.д.

Таким образом, необходимо хранить объекты и их типы, уметь находить эти объекты и определять их типы, определять характеристики контекста. Совокупность доступных в данной точке объектов будем называть средой. Обычно среда программы состоит из частично упорядоченного набора компонент

Каждая компонента - это множество объявлений, представляющих собой пары (имя, тип):

где под типом будем подразумевать полное описание свойств объекта (объектом, в частности, может быть само описание типа).

Рис.6.1:

Компоненты образуют дерево, соответствующее этому частичному порядку. Частичный порядок между компонентами обычно определяется статической вложенностью компонент в программе. Эта вложенность может соответствовать блокам, процедурам или классам программы (рис. 6.1). Компоненты среды могут быть именованы. Поиск в среде обычно ведется с учетом упорядоченности компонент. Среда может включать в себя как компоненты, полученные при

трансляции «текущего» текста программы, так и «внешние» (например, раздельно компилированные) компоненты.

Для обозначения участков программы, в которых доступны те или иные описания, используются понятия области действия и области видимости. Областью действия описания является процедура (блок), содержащая описание, со всеми входящими в нее (подчиненными по дереву) процедурами (блоками). Областью видимости описания называется часть области действия,

из которой исключены те подобласти, в которых по тем или иным причинам описание недоступно, например, оно перекрыто другим описанием. В разных языках понятия области действия и области видимости уточняются по-разному.

Обычными операциями при работе со средой являются:

- включить объект в компоненту среды;

- найти объект в среде и получить доступ к его описанию;

- образовать в среде новую компоненту, определенным образом связанную с остальными;

- удалить компоненту из среды.

Среда состоит из отдельных объектов, реализуемых как записи (в дальнейшем описании мы будем использовать имя TElement для имени типа этой записи). Состав полей записи, вообще говоря, зависит от описываемого объекта (тип, переменная и т.д.), но есть поля, входящие в запись для любого объекта:

TObject Object - категория объекта (тип, переменная, процедура и т.д.);

TMode Mode - вид объекта: целый, массив, запись и т.д.;

TName Name - имя объекта;

TType Type - указатель на описание типа.

Определение атрибутных грамматик

Атрибутной грамматикой называется четверка AG = (G, AS, AI, R), где

G = (N, T, P, S) - приведенная КС-грамматика;

AS - конечное множество синтезируемых атрибутов;

AI - конечное множество наследуемых атрибутов, AS

AI = ;

R - конечное множество семантических правил.

Атрибутная грамматика AG сопоставляет каждому символу X из N 

 T множество AS(X) синтезируемых атрибутов и множество AI(X) наследуемых атрибутов. Множество всех синтезируемых

атрибутов всех символов из N 

 T обозначается AS, наследуемых - AI. Атрибуты разных символов являются различными атрибутами. Будем обозначать атрибут a символа X как a(X). Значения атрибутов могут быть произвольных типов, например, представлять собой числа, строки, адреса памяти и т.д.

Пусть правило p из P имеет вид X0

X1X2...Xn. Атрибутная грамматика AG сопоставляет каждому правилу p из P конечное множество R(p) семантических правил вида

где 0

j, k, ..., m n, причем 1 i n, если a(Xi) AI(Xi) (т.е. a(Xi) - наследуемый атрибут), и i = 0, если a(Xi) AS(Xi) (т.е. a(Xi) - синтезируемый атрибут).

Таким образом, семантическое правило определяет значение атрибута a символа Xi

на основе значений атрибутов b, c, ..., d символов Xj, Xk, ..., Xm

соответственно.

В частном случае длина n правой части правила может быть равна нулю, тогда будем говорить, что атрибут a символа Xi

«получает в качестве значения константу».

В дальнейшем

будем считать, что атрибутная грамматика не содержит семантических правил для вычисления атрибутов терминальных символов. Предполагается, что атрибуты терминальных символов - либо предопределенные константы, либо доступны как результат работы лексического анализатора.

Пример 5.5. Рассмотрим атрибутную грамматику, позволяющую вычислить значение вещественного числа, представленного в десятичной записи. Здесь N = {Num, Int, Frac}, T = {digit, .}, S = Num, а правила вывода и семантические правила определяются следующим образом (верхние

индексы используются для ссылки на разные вхождения одного и того же нетерминала):

 

Num Int . Frac	v(Num) = v(Int) + v(Frac)
	p(Frac) = 1
Int e	v(Int) = 0
	p(Int) = 0
Int1 digit Int2	v(Int1) = v(digit) * 10p(Int2) + v(Int2)
	p(Int1) = p(Int2) + 1
Frac e	v(Frac) = 0
Frac1 digit Frac2	v(Frac1) = v(digit) * 10-p(Frac1) + v(Frac2)
	p(Frac2) = p(Frac1) + 1

 

Для этой грамматики

 

AS(Num) = {v},	AI(Num) = ,
AS(Int) = {v, p},	AI(Int) = ,
AS(Frac) = {v},	AI(Frac) = {p}.

Пусть дана атрибутная грамматика AG и цепочка, принадлежащая языку, определяемому соответствующей G = (N, T, P, S). Сопоставим этой цепочке «значение» следующим образом. Построим дерево

разбора T этой цепочки в грамматике G. Каждый внутренний узел этого дерева помечается нетерминалом X0, соответствующим применению p-го правила грамматики; таким образом, у этого узла будет n непосредственных потомков (рис. 5.2).

Рис. 5.2:

Пусть теперь X - метка некоторого узла дерева и пусть a - атрибут символа X. Если a - синтезируемый атрибут, то X = X0 для некоторого p P; если же a - наследуемый атрибут, то X = Xj для некоторых p P и 1 j n. В обоих случаях дерево «в районе» этого узла имеет вид, приведенный на рис. 5.2. По определению, атрибут a имеет в этом узле значение v, если в соответствующем семантическом правиле

все атрибуты b, c, ..., d уже определены и имеют в узлах с метками Xj, Xk, ..., Xm

значения vj, vk, ..., vm

соответственно, а v = f(v1, v2, ..., vm). Процесс вычисления атрибутов на дереве продолжается до тех пор, пока нельзя будет вычислить больше ни одного атрибута. Вычисленные в результате атрибуты корня дерева представляют собой «значение», соответствующее данному дереву вывода.

Заметим, что значение синтезируемого атрибута символа в узле синтаксического дерева вычисляется по атрибутам

символов в потомках этого узла; значение наследуемого атрибута вычисляется по атрибутам «родителя' и «соседей».

Атрибуты, сопоставленные вхождениям символов в дерево разбора, будем называть вхождениями атрибутов в дерево разбора, а дерево с сопоставленными каждой вершине атрибутами - атрибутированным деревом разбора.



Пример 5.6. Атрибутированное дерево для грамматики из предыдущего примера и цепочки w = 12.34 показано на рис. 5.3.

Рис. 5.3:

Будем говорить, что семантические правила заданы корректно, если они позволяют вычислить все атрибуты произвольного узла в любом дереве вывода.

Между вхождениями атрибутов в дерево разбора существуют зависимости, определяемые семантическими правилами, соответствующими примененным синтаксическим правилам. Эти зависимости могут быть представлены в виде ориентированного графа следующим образом.

Пусть T - дерево разбора. Сопоставим

этому дереву ориентированный граф D(T), узлами которого являются пары (n, a), где n - узел дерева T, a - атрибут символа, служащего меткой узла n. Граф содержит дугу из (n1, a1) в (n2, a2) тогда и только тогда, когда семантическое правило, вычисляющее атрибут a2, непосредственно использует значение атрибута a1. Таким образом, узлами графа D(T) являются атрибуты, которые нужно вычислить, а дуги определяют зависимости, подразумевающие, какие атрибуты вычисляются раньше,

а какие позже.

Пример 5.7. Граф зависимостей атрибутов для дерева разбора из предыдущего примера показан на рис. 5.4.

Рис. 5.4:

Можно показать, что семантические правила являются корректными тогда и только тогда, когда для любого дерева вывода T соответствующий граф D(T) не содержит циклов (т.е. является ориентированным ациклическим графом).

Организация информации в генераторе кода

Синтаксическое дерево в чистом виде несет только информацию о структуре

программы. На самом деле в процессе генерации кода требуется также информация о переменных (например, их адреса), процедурах (также адреса, уровни), метках и т.д. Для представления этой информации возможны различные решения. Наиболее распространены два:

информация хранится в таблицах генератора кода;

информация хранится в соответствующих вершинах дерева.

Рассмотрим, например, структуру таблиц,

которые могут быть использованы в сочетании с Лидер-представлением. Поскольку Лидер-представление не содержит информации об адресах переменных, значит, эту информацию нужно формировать в процессе обработки объявлений и хранить в таблицах. Это касается и описаний массивов, записей и т.д. Кроме того, в таблицах также должна содержаться информация о процедурах (адреса, уровни, модули, в которых процедуры описаны, и т.д.).

При входе в процедуру в таблице уровней процедур заводится

новый вход - указатель на таблицу описаний. При выходе указатель восстанавливается на старое значение. Если промежуточное представление - дерево, то информация может храниться в вершинах самого дерева.

Организация магазина с дисплеем

Рассмотрим теперь организацию магазина с дисплеем. Дисплей - это массив (DISPLAY) , i-й элемент которого представляет собой указатель

на область активации последней вызванной подпрограммы i-го статического уровня. Доступ к переменным самой внутренней подпрограммы осуществляется через регистр BP. Дисплей может быть реализован либо через регистры (если их достаточно), либо через массив в памяти.

При вызове процедуры следующего (по отношению к вызывающей) уровня в дисплее отводится очередной элемент. Если вызывающая процедура имеет статический уровень i, то при вызове процедуры уровня j

i элементы

дисплея j, ..., i должны быть скопированы (обычно в стек вызывающей процедуры), текущим уровнем становится j и в DISPLAY[j] заносится указатель на область активации вызываемой процедуры. По окончании работы вызываемой процедуры содержимое дисплея восстанавливается из стека.

Иногда используется комбинированная схема - дисплей в магазине. Дисплей хранится в области активации каждой процедуры. Формирование дисплея для процедуры осуществляется в соответствии с правилами, описанными выше.

Отдельного

рассмотрения требует вопрос о технике передачи фактических параметров. Конечно, в случае простых параметров (например, чисел) проблем не возникает. Однако передача массивов по значению - операция довольно дорогая, поэтому с точки зрения экономии памяти целесообразнее сначала в подпрограмму передать адрес массива, а затем уже из подпрограммы по адресу передать в магазин сам массив. В связи с передачей параметров следует упомянуть еще одно

обстоятельство.

Рассмотренная схема организации магазина допустима только для языков со статически известными размерами фактических параметров. Однако, например, в языке Модула-2 по значению может быть передан гибкий массив, и в этом случае нельзя статически распределить память для параметров. Обычно в таких случаях заводят так называемый «паспорт» массива, в котором хранится вся необходимая информация, а сам массив размещается в магазине в рабочей области

выше сохраненных регистров.

Организация магазина со статической цепочкой

Итак, в случае статической цепочки магазин организован, как это изображено на рис.9.1.

Рис. 9.1:

Таким образом, на запись текущей процедуры в магазине указывает регистр BP (Base Pointer), с которого начинается динамическая цепочка. На статическую цепочку указывает регистр LP (Link Pointer). В качестве регистров BP и LP в различных системах команд могут использоваться универсальные, адресные или специальные регистры. Локальные переменные отсчитываются от регистра BP вверх, фактические параметры - вниз с учетом памяти, занятой точкой возврата и самим сохраненным регистром

BP.

Вызов подпрограмм различного статического уровня производится несколько по-разному. При вызове подпрограммы того же статического уровня, что и вызывающая подпрограмма (например, рекурсивный вызов той же самой подпрограммы), выполняются следующие команды:

Занесение фактических параметров в магазин      JSR A

Команда JSR A продвигает указатель SP, заносит PC на верхушку магазина и осуществляет переход по адресу A. После выполнения этих команд состояние магазина становится таким, как это изображено на рис. 9.2. Занесение BP, отведение локальных, сохранение регистров делает вызываемая подпрограмма (см. ниже).

Рис. 9.2:

При вызове локальной подпрограммы необходимо установить указатель статического уровня на текущую подпрограмму, а при выходе - восстановить его на старое значение (охватывающей текущую). Для этого исполняются следующие команды:

Занесение фактических параметров в магазин      MOVE BP, LP      SUB Delta, LP      JSR A

Здесь Delta - размер локальных вызывающей подпрограммы плюс двойная длина слова. Магазин после этого принимает состояние, изображенное на рис. 9.3. Предполагается, что регистр LP уже сохранен среди сохраняемых регистров, причем самым первым (сразу после локальных переменных).

После выхода из подпрограммы в вызывающей подпрограмме выполняется команда

MOVE (LP), LP

которая восстанавливает старое значение статической цепочки. Если выход осуществлялся из подпрограммы 1-го уровня, эту команду выполнять не надо, поскольку для 1-го уровня нет статической цепочки.

Рис. 9.3:

При вызове подпрограммы меньшего, чем вызывающая, уровня выполняются следующие команды:

Занесение фактических параметров в магазин      MOVE (LP), LP /* столько раз, какова разность                       уровней вызывающей и вызываемой ПП */      JSR A

Тем самым устанавливается статический уровень вызываемой подпрограммы. После выхода из подпрограммы выполняется команда

MOVE  -Delta(BP), LP

восстанавливающая статический уровень вызывающей подпрограммы.

Тело подпрограммы начинается со следующих команд:

LINK BP , -размер_локальных      MOVEM -(SP)

Команда LINK BP, размер_локальных эквивалентна трем командам:

MOVE BP, -(SP)      MOVE SP, BP      ADD -размер_локальных, SP

Команда MOVEM сохраняет в магазине регистры.

В результате выполнения этих команд магазин приобретает вид, изображенный на рис. 9.1.

Выход из подпрограммы осуществляется следующей последовательностью команд:

MOVEM (SP)+      UNLK BP      RTD размер_фактических

Команда MOVEM восстанавливает регистры из магазина. Команда UNLK BP эквивалентна такой последовательности команд:

MOVE BP,SP      MOVE (SP),BP      ADD #4, SP  /* 4 - размер слова */

Команда RTD размер_фактических, в свою очередь, эквивалентна последовательности

ADD размер_фактических+4, SP      JMP -размер_фактических-4(SP)

После ее выполнения магазин восстанавливается до состояния, которое было до вызова.

В зависимости от наличия локальных переменных, фактических параметров и необходимости сохранения регистров каждая из этих команд может отсутствовать.

Организация памяти

Машина имеет следующие регистры:

pc - счетчик команд;

optop - указатель вершины стека операций;

frame - указатель на стек-фрейм исполняемого метода;

vars - указатель на 0-ю переменную исполняемого метода.

Все регистры 32-разрядные. Стек-фрейм имеет три компоненты: локальные переменные, среду исполнения, стек

операндов. Локальные переменные отсчитываются от адреса в регистре vars. Среда исполнения служит для поддержания самого стека. Она включает указатель на предыдущий фрейм, указатель на собственные локальные переменные, на базу стека операций и на верхушку стека. Кроме того, здесь же хранится некоторая дополнительная информация, например, для отладчика.

Куча сборки мусора содержит экземпляры объектов, которые создаются и уничтожаются автоматически. Область методов

содержит коды, таблицы символов и т.д.

С каждым классом связана область констант. Она содержит имена полей, методов и другую подобную информацию, которая используется методами.

Организация таблиц символов

В процессе работы компилятор хранит информацию об объектах программы в специальных таблицах символов. Как правило, информация о каждом объекте состоит из двух основных элементов: имени объекта и описания объекта. Информация об объектах программы должна быть организована таким образом, чтобы поиск ее был по возможности быстрее, а требуемая память по возможности меньше.

Кроме того, со стороны языка программирования

могут быть дополнительные требования к организации информации. Имена могут иметь определенную область видимости. Например, поле записи должно быть уникально в пределах структуры (или уровня структуры), но может совпадать с именем объекта вне записи (или другого уровня записи). В то же время имя поля может открываться оператором присоединения, и тогда может возникнуть конфликт имен (или неоднозначность в трактовке имени). Если язык имеет блочную структуру, то необходимо обеспечить

такой способ хранения информации, чтобы, во-первых, поддерживать блочный механизм видимости, а во-вторых - эффективно освобождать память при выходе из блока. В некоторых языках (например, Аде) одновременно (в одном блоке) могут быть видимы несколько объектов с одним именем, в других такая ситуация недопустима.

Мы рассмотрим некоторые основные способы организации таблиц символов в компиляторе: таблицы идентификаторов, таблицы расстановки, двоичные

деревья и реализацию блочной структуры.

Основа

В процессе разбора снизу-вверх типа сдвиг-свертка строится дерево разбора входной цепочки, начиная с листьев (снизу) к корню (вверх). Этот

процесс можно рассматривать как «свертку» цепочки w к начальному символу грамматики. На каждом шаге свертки подцепочка, которую можно сопоставить правой части некоторого правила вывода, заменяется символом левой части этого правила вывода, и если на каждом шаге выбирается правильная подцепочка, то в обратном порядке прослеживается правосторонний вывод (рис.4.7). Здесь ко входной цепочке, так же как и при анализе LL(1)-грамматик, приписан концевой маркер $.

Рис. 4.7:

Подцепочка сентенциальной формы, которая может быть сопоставлена правой части некоторого правила вывода, свертка по которому к левой части правила соответствует одному шагу в обращении правостороннего вывода, называется основой цепочки. Самая левая подцепочка, которая сопоставляется правой части некоторого правила вывода A

, не обязательно является основой, поскольку свертка по правилу A

может дать цепочку, которая не может быть сведена к аксиоме.

Формально, основа

правой сентенциальной формы z - это правило вывода A

и позиция в z, в которой может быть найдена цепочка

такие, что в результате замены

на A получается предыдущая сентенциальная форма в правостороннем выводе z. Таким образом, если S r*A r, то A

в позиции, следующей за

, это основа цепочки . Подцепочка справа от основы содержит только терминальные символы.

Вообще говоря, грамматика может быть неоднозначной, поэтому не единственным может быть правосторонний вывод

и не единственной может быть

основа. Если грамматика однозначна, то каждая правая сентенциальная форма грамматики имеет в точности одну основу. Замена основы в сентенциальной форме на нетерминал левой части называется отсечением основы. Обращение правостороннего вывода может быть получено с помощью повторного применения отсечения основы, начиная с исходной цепочки w. Если w - слово в рассматриваемой грамматике, то w =

n, где n - n-я правая сентенциальная форма еще неизвестного правого вывода S = 0 r1 r... rn-1 rn = w.

Чтобы

восстановить этот вывод в обратном порядке, выделяем основу n в n и заменяем n на левую часть некоторого правила вывода An n, получая (n - 1)-ю правую сентенциальную форму n-1. Затем повторяем этот процесс, т.е. выделяем основу n-1 в n-1 и сворачиваем эту основу, получая правую сентенциальную форму n-2. Если, повторяя этот процесс, мы получаем правую сентенциальную форму, состоящую только из начального символа S, то останавливаемся и сообщаем об успешном завершении разбора. Обращение последовательности правил, использованных в свертках, есть правый

вывод входной строки.

Таким образом, главная задача анализатора типа сдвиг-свертка - это выделение и отсечение основы.

---

---