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

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

Работа с таблицами
Таблица имен представляет собой структуру, подобную следующей:
Номер элемента
Идентификатор
Дополнительная информация
(тип, размер и т.п.)
1
A идент., тип = "строка"
…
…
…
N
3.1415 константа, число
Механизм работы с таблицами должен обеспечивать:
- быстрое добавление новых идентификаторов и сведений о них;
- быстрый поиск информации.
К работе с таблицами мы еще вернемся, когда будем рассматривать
хеш-функции.
Синтаксический и семантический анализ
Синтаксический анализ – это процесс, в котором исследуется цепочка лексем и устанавливается, удовлетворяет ли она структурным условиям, явно сформулированным в определении синтаксиса языка. Это – самая сложная часть компилятора.
Синтаксический анализатор расчленяет исходную программу на составные части, формирует ее внутреннее представление, заносит информацию в таблицу символов и другие таблицы. При этом производится полный синтаксический и, по возможности, семантический контроль программы. Фактически, это – синтаксически управляемая программа. При этом обычно стремятся отделить синтаксис от семантики насколько это возможно – когда синтаксический анализатор распознает конструкцию исходного языка, он вызывает семантическую процедуру, которая контролирует эту конструкцию, заносит информацию куда надо, проверяет на дублирование описания переменных, проверяет соответствие типов и т.п.
Предложения исходной программы обычно записываются в инфиксной форме. Однако эта привычная форма, в которой оператор записывается между операндами, является совершенно не пригодной для автоматического вычисления. Дело в том, что необходимо постоянно помнить о приоритетах операторов, "забегая" при анализе выражения "вперед". К тому же очень усложняют жизнь применяемые скобки, определяющие очередность вычислений. Альтернативой инфиксной форме является польская форма записи (в честь польского математика Лукасевича): постфиксная и

13
префиксная. Обычно под польской формой понимают именно постфиксную форму записи. Кроме того, используются и такие внутренние формы представления исходной программы, как дерево (синтаксическое) и
тетрады.
Дерево. Пусть имеется входная цепочка i=(a+b)*c. Тогда дерево будет выглядеть так:
=
i *
+
c a
b
У каждого элемента дерева может быть только один “предок”. Дерево
“читается” снизу вверх и слева направо. Дерево – это прежде всего удобная математическая абстракция. На практике дерево можно реализовать в виде списковой структуры.
Польская форма записи. Существуют три вида записи выражений:
 инфиксная форма, в которой оператор расположен между операндами
(например, "а+b");
 постфиксная форма, в которой оператор расположен после операндов (то же выражение выглядит как "а b + ");
 префиксная форма, в которой оператор расположен перед операндами ("+ а b").
Постфиксная и префиксная формы образуют т.н. польскую форму записи. Польская форма удобна прежде всего тем, что в ней отсутствуют скобки. На практике наиболее часто используется постфиксная форма.
Поэтому под польской обычно понимают именно постфиксную форму записи.
В этой форме записи выражение i=(a+b)*c выглядит так: " iab+c*=". Это выражение удобно расписывается по дереву: с нижней строки записываются
“a” и “b”, далее “+” и “с”, выше – “i” и “*” и в вершине дерева “=”.

14
Тетрада- это четверка, состоящая из кода операции, приемника и двух операндов. Если требуется не два, а менее операторов, то в этом случае тетрада называется вырожденной. Например:
Исходное выражение
Код Приемник
Операнд1
Операнд2 a+bT1
+
Т1 а b
T1+cT2
*
T2
T1 c i=T2
=
I
T2
(вырожденная тетрада)
Польская форма записи и тетрады удобны своей однозначностью.
Фактически в обеих этих формах мы раскладываем исходное выражение на элементарные составляющие.
Пусть на вход синтаксического анализатора подаются выражения "<ид1>=(<ид2>+<ид3>)*<ид4>" и "A = B+C*D"
На выходе будем иметь:
1) Дерево для выражения
Дерево для выражения "<ид1>=(<ид2>+<ид3>)*<ид4>"
"A = B+C*D"
=
=
<ид1>
A
*
+
+
*
B
C
D
<ид2>
<ид3>
<ид4>
2) Тетрады для "<ид1> = (<ид2>+<ид3>)*<ид4>"
+, <ид2>, <ид3>, T1
*, T1, <ид4>, T2
=, T2, <ид1>
Тетрады для "A = B+C*D"
*, C, D, T1
+, B, T1, T2
=, T2, A
(T1, T2 – временные переменные, созданные компилятором)
3) Польская форма для "<ид1> = (<ид2>+<ид3>)*<ид4>":
<ид1> <ид2> <ид3> + <ид4> * =

15
Польская форма для "A=B+C*D" будет выглядеть как "ABCD*+=".
Обратите внимание на то, что порядок следования операндов в польской форме записи такой же, как и в исходном инфиксном выражении (записи "abc*=" и "bc*a=" – это вовсе не одно и то же).
Алгоритм вычисления польской формы записи очень прост:
Просматриваем последовательно символы входной цепочки. Если очередной символ является операндом (идентификатором или константой), то читаем дальше. Если символ является бинарным оператором, то извлекаем из цепочки два предыдущих операнда вместе с оператором, производим операцию и помещаем результат обратно в цепочку символов.
Более подробно этот алгоритм будет рассмотрен ниже. Оставшиеся стадии компиляции, связанные с подготовкой к генерации команд, распределением памяти, оптимизацией программы и собственно с генерацией команд и генерацией объектного кода, безусловно важны, однако сейчас на них останавливаться мы не будем.
ТЕОРИЯ ФОРМАЛЬНЫХ ЯЗЫКОВ. ГРАММАТИКИ
ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ
Общение на каком-либо языке – искусственном или естественном- заключается в обмене предложениями или, точнее, фразами. Фраза – это конечная последовательность слов языка. Фразы необходимо уметь строить и распознавать.
Если существует механизм построения фраз и механизм признания их корректности и понимания (механизм распознавания), то мы говорим о существовании некоторой теории рассматриваемого языка.
Определение: Язык L – это множество цепочек конечной длины в алфавите .
Возникает вопрос – каким образом можно задать язык? Во-первых, язык можно задать полным его перечислением. С точки зрения математики это вовсе не является полной бессмысленностью. А во-вторых, можно иметь некоторое конечное описание языка.
Одним из наиболее эффективных способов описания языка является грамматика. Строго говоря, грамматика – это математическая система,
определяющая язык. Как мы убедимся далее, грамматика пригодна не только для задания (или генерации) языка, но и для его распознавания.
Далее нам потребуются некоторые термины и обозначения. Начнем с определения замыкания множества.

16
Если  – множество (алфавит или словарь), то 
*
– замыкание множества , или, иначе, свободный моноид, порожденный , т.е. множество всех конечных последовательностей, составленных из элементов множества , включая и пустую последовательность.
Например, пусть A = {a, b, c}. Тогда A*={e, a, b, c, aa, ab, ac, bb, bc, cc,
…}. Здесь e – это пустая последовательность.
Символом 
+
мы будем обозначать положительное замыкание множества  (или, иначе, свободную полугруппу, порожденную множеством ). В отличие от свободного моноида в положительное замыкание не входит пустая последовательность.
Теперь все готово к тому, чтобы дать основное определение.
Определение. Грамматика – это четверка G = (N, ,P,S), где
N – конечное множество нетерминальных символов (синтаксические переменные или синтаксические категории);
 – конечное множество терминальных символов (слов) (N=);
P – конечное подмножество множества
(N)
*
N(N)
*
 (N)
*
Элемент (,) множества P называется правилом или продукцией и записывается в виде ;
S – выделенный символ из N (SN), называемый начальным символом
(эта особая переменная называется также "начальной переменной" или "исходным символом").
Пример:
G = ({A,S},{0,1},P,S),
P = (S0A1, 0A00A1, Ae)
Определение. Язык, порождаемый грамматикой G (обозначим его через L(G)) – это множество терминальных цепочек, порожденных грамматикой G.
Или, иначе, язык L, порождаемый (распознаваемый) грамматикой, есть множество последовательностей (слов), которые
- состоят лишь из терминальных символов;
- можно породить, начиная с символа S.
И опять нам требуются определения и обозначения:
Определение: Пусть G = (N, , P, S). Отношение 
G
на множестве
(N)
*
называется
непосредственной выводимостью

G

( непосредственно выводима из ), если  – цепочка из (N)
*
и  – правило из P, то 
G
.
Транзитивное замыкание отношения 
G
обозначим через 
+
G

17
Запись 
+
G
 означает:  выводима из  нетривиальным образом.
Рефлексивное и транзитивное замыкание отношения 
G
обозначим через 
*
G
. Запись 
*
G
 означает:  выводима из . (Если 
*
– это рефлексивное и транзитивное замыкание отношения
, то последовательность 
1

2
, 
2

3
,.., 
m-1

m
, где 
i
(N)
*
, записывается так: 
1

*

m
.)
При этом предполагалось наличие следующих определений:
Определение A. k-я степень отношения R на множестве A (R
k
):
(1) aR
1
b тогда и только тогда, когда aRb (или R
1
R);
(2) aR
i b для i>1 тогда и только тогда, когда  cA: aRc и cR
i-1
b.
Определение B. Транзитивное замыкание отношения R на множестве A (R
+
): aR
+
b тогда и только тогда, когда aR
i b для некоторого i>0.
Определение C. Рефлексивное и транзитивное замыкание отношения R на множестве A (R
*
):
(1) aR
*
a для  aA;
(2) aR
*
b, если aR
+
b
Таким образом, получаем формальное определение языка L:
L(G)={| 
*
, S
*
}
Нормальная форма Бэкуса-Наура. Нормальная форма Бэкуса-Наура
(НФБ или БНФ) служит для описания правил грамматики. Она была впервые применена Науром при описании синтаксиса языка Фортран. По сути БНФ является альтернативной, более упрощенной, менее строгой и потому более распространенной формой записи грамматики. Далее мы будем пользоваться ею наравне с формальными определениями в силу ее большей наглядности.
Пример:
<число> ::= <чс>
<чс> ::= <чс><цифра>|<цифра>
<цифра> ::= 0|1|...|9
ИЕРАРХИЯ ХОМСКОГО
Вернемся к определению грамматики как четверки вида G = (N, , P,
S), где нас интересует вид правил P, под которыми понимается конечное подмножество множества
(N)
*
N(N)
*
 (N)
*
В зависимости от конкретики реализаций правил P существует следующая классификация грамматик (в порядке убывания общности вида правил):

18
Грамматика типа 0: Правила этой грамматики определяются в самом общем виде.
P: xUyz
Для распознавания языков, порожденных этими грамматиками, используются т.н. машины Тьюринга – очень мощные (на практике практически неприменимые) математические модели.
Грамматика типа 1: Контекстно-зависимые (чувствительные к контексту)
P: xUyxuy
Грамматика типа 2: Контекстно-свободные. Распознаются стековыми автоматами (автоматами с магазинной памятью)
P: Uu
Грамматика
типа
3:
Регулярные грамматики.
Распознаются конечными автоматами
P: Ua или UaA
При этом приняты следующие обозначения: u  (N)
+
x, y, z  (N)
*
A,U  N a  
Условно иерархию Хомского можно изобразить так:
Грамматика типа 0
Грамматика типа 1
Грамматика типа 2
Грамматика типа 3
Итак, иерархия Хомского необходима для классификации грамматик по степени их общности. При этом, как видно,
 Грамматика типа 0 – самая сложная, никаких ограничений на вид правил в ней не накладывается.
 Грамматика типа 1 – контекстно-зависимая; в ней возможность замены цепочки символов может определяться ее (т.е. цепочки) контекстом.

19
 Грамматика типа 2 – контекстно-свободная; в левой части нетерминалы меняются на что угодно.
 Грамматика типа 3 – регулярная грамматика, самая ограниченная, самая простая.
РЕГУЛЯРНЫЕ ГРАММАТИКИ
Начнем изучение грамматик с самого простого и самого ограниченного их типа – регулярных грамматик. Вот некоторые примеры:
1. Идентификатор (в форме БНФ)
<идент> ::= <бкв>
<идент> ::= <идент><бкв>
<идент> ::= <идент><цфр>
<бкв> ::= a|b|...|z
<цфр> ::= 0|1|...|9 2. Арифметическое выражение (без скобок)
G = (N, ,P,S)
N={S,E,op,i}
={<число>, <идент>,+,-,*,/}
P={Si
SiE
Eop S op+ op- op* op/ i<число> i<идент>}
Ту же грамматику бесскобочных выражений можно изобразить в виде
БНФ (это не совсем строго, зато весьма наглядно):
::= <число>|<идент>
::=
::= +|-|*|/
<число> ::= <цфр>
<число> ::= <число><цфр>
3. Еще один пример:
Z ::= U0 | V1
U ::= Z1 | 1
V ::= Z0 | 0

20
Порождаемый этой грамматикой язык состоит из последовательностей, образуемых парами 01 или 10, т.е. L(G) = { B
n
| n > 0}, где B = { 01, 10}.
Стоит, однако, рассмотреть чуть более сложный объект (например, арифметические выражения со скобками), как регулярные грамматики оказываются слишком ограниченными:
4. Арифметическое выражение (со скобками)
G
0
=({E,T,F},{a,+,*,(,),#},P,E)
P = { E  E+T|T
T  T*F|F
F  (E)|a}
Это, разумеется, уже не регулярная, а контекстно-свободная грамматика.
Тем не менее, регулярные грамматики играют очень важную роль в теории компиляторов. По крайней мере, их достаточно для того, чтобы реализовать первую часть компилятора – сканер. Ведь сканер имеет дело именно с такими простыми объектами, как идентификаторы и константы.
Итак, будем считать, что мы как минимум умеем порождать фразы регулярных языков. Однако все-таки нашей основной задачей является не порождение, а распознавание фраз. Поэтому далее рассмотрим один из наиболее эффективных распознающих механизмов – конечный автомат.
КОНЕЧНЫЕ АВТОМАТЫ
ФОРМАЛЬНОЕ ОПРЕДЕЛЕНИЕ
Как уже говорилось выше, грамматика – это порождающая система.
Автомат – это формальная воспринимающая система (или акцептор). Правила автомата определяют принадлежность входной формы данному языку, т.е. автомат – это система, которая распознает принадлежность фразы к тому или иному языку.
Говорят, что автомат эквивалентен данной грамматике, если он воспринимает весь порождаемый ею язык и только этот язык. Как и грамматики, автоматы определяются конечными алфавитами и правилами переписывания.
Определение. Конечный автомат (КА) – это пятерка КА = (,Q,q
0
,T,P), где
  – входной алфавит (конечное множество, называемое также входным словарем);
 Q – конечное множество состояний;
 q
0
– начальное состояние (q
0
Q);

21
 T – множество терминальных (заключительных) состояний, TQ;
 P – подмножество отображения вида QQ, называемое функцией переходов. Элементы этого отображения называются правилами и обозначаются как q
i a
k
q j
, где q i
и q j
– состояния, a k
– входной символ: q i
, q j
 Q, a k
.
КА можно рассматривать как машину, которая в каждый момент времени находится в некотором состоянии qQ и читает поэлементно последовательность  символов из , записанную на конечной слева ленте.
При этом читающая головка машины двигается в одном направлении (слева направо), либо лента перемещается (справа налево). Если автомат в состоянии q i
читает символ a k
и правило q i
a k
q j
принадлежит P, то автомат воспринимает этот символ и переходит в состояние q j
для обработки следующего символа:
Входная лента: входные символы a i

a
1
a n
a
2
a k
Конечное управляющее устройство
(состояние q i
)
Операция чтения
Движение ленты
Таким образом, суть работы автомата сводится к тому, чтобы прочитать очередной входной символ и, используя соответствующее правило перехода, перейти в другое состояние.
Связь между конечными автоматами и регулярными грамматиками самая непосредственная, что следует из утверждения:
Каждой
грамматике
можно
поставить
в
соответствие
эквивалентный ей автомат, и каждому автомату соответствует
эквивалентная ему грамматика.
Итак, мы установили взаимосвязи между грамматиками, языками и автоматами:

22
G
L(G)
грамматика язык
A автомат
ДЕТЕРМИНИРОВАННЫЕ И НЕДЕТЕРМИНИРОВАННЫЕ КА
Конфигурация конечного автомата – это элемент множества Q
*
, т.е. последовательность вида q, где q – состояние из Q,  – элемент из 
*
Если к любой конфигурации q i
 применимо не более одного правила, то такой автомат называется детерминированным конечным автоматом
(ДКА). В противном случае мы имеем дело с недетерминированным конечным автоматом (НКА).
Итак, недетерминированные конечные автоматы отличаются от ДКА
- неоднозначностью переходов;
- наличием, в общем случае, более чем одного начальных состояний.
КА удобно представлять в виде диаграммы состояний (переходов), представляющей собой ориентированный граф.
Пример 1. Пусть задан следующий НКА
КА = (,Q,q
0
,T,P)
 = {0,1},
Q = {S, A, B, Z}, q
0
= S,
T = {Z},
P = {S0Z, S0A, A1B, B0Z, B0A}
Диаграмма его переходов будет выглядеть так:

23
S
Z
A
B
0 0
0 0
1
Пример 2. Рассмотрим понятие идентификатора, представленное в НФБ и в виде ДКА:
<идент> ::= <бкв>
<идент> ::= <идент><бкв>
<идент> ::= <идент><цфр>
<бкв> ::= a|b|...|z
<цфр> ::= 0|1|...|9
S
1
Err
4
A
2
T
3
<бкв>
<бкв>|<цфр> иначе конец иначе
Изобразим множество P в виде матрицы (т.н. матрицы переходов)
P:
1 2
3
<бкв>
2 2
-
<цфр>
4 2
-
<конец>
4 3
-
<иначе>
4
-
-

24
Строки матрицы – входные символы, столбцы – состояния автомата.
Некоторые элементы этой матрицы – явно лишние. В частности, 3-й столбец вовсе не нужен. Эти "лишние" состояния могут служить для диагностики ошибок.
Обобщенный алгоритм работы этого автомата может быть реализован на языке С следующим образом:
char c;
//текущий исходный символ int q;
//номер состояния int a;
//входной текущий символ для автомата q=0;
//начальное состояние автомата while(1)
//бесконечный цикл
{ c = readchar();
//считывание входного символа a = gettype(c);
//распознавание входного символа –
//отнесение его к одной из известных автомату
//категорий - <бкв>, <цфр>, <конец> или <иначе>
//Выполнение перехода q = P[a, q];
//Обработка if (q==3) return 1;
//нормальный выход из программы if (q==4) return 0;
//выход по ошибке
}
Обратите внимание на то, что входной алфавит – это то, что автомат умеет воспринимать. При этом он не обязан различать между собой, скажем, буквы и цифры.
Пример 3. Арифметическое выражение (без скобок)
::= <число>|<идент>
::=
::= +|-|*|/
<число> ::= <цфр>
<число> ::= <число><цфр>

25
S
1
Err
4
A
2
T
3
<число>|<идент>
иначе конец иначе
(На самом деле грамматкика, соответствующаяэтому автомату несколько иная, однако сути дела это не меняет.)
Рассмотрим анализатор языка, распознаваемый КА, структура которого приведена ниже:
S
B
A
0 0
1 0
1 1
Автомат этот недетерминированный и его реализация с помощью процедурных языков программирования может вызвать определенные сложности. Обратимся поэтому к языку Пролог:
/*
АНАЛИЗАТОР РЕГУЛЯРНОЙ ГРАММАТИКИ - 1
S->1S
S->1B
S->0A
A->0A
A->0B
B->1S
Начальное состояние S
Конечное состояние B
*/ goal
Recognize([1,1,1,1,1,0,0,0,0,0,0,1,1,0,0,0,0]).

26 clauses
Recognize(L) :- s(L), write("ФРАЗА РАСПОЗНАНА").
Recognize(_) :- write("*** ОШИБКА ! ФРАЗА НЕ РАСПОЗНАНА"). append([],L,L). append([H|T],B,[H|C]) :- append(T,B,C).
S(L) :- append(L1,L2,L), L1=[1], S(L2).
S(L) :- append(L1,L2,L), L1=[1], B(L2).
S(L) :- append(L1,L2,L), L1=[0], A(L2).
A(L) :- append(L1,L2,L), L1=[0], A(L2).
A(L) :- append(L1,L2,L), L1=[0], B(L2).
B(L) :- append(L1,L2,L), L1=[1], S(L2).
B([]).
Более эффективным и простым будет следующий вариант программы, в которой нет необходимости использовать процедуру деления списка на две части:
/* АНАЛИЗАТОР РЕГУЛЯРНОЙ ГРАММАТИКИ – 2 . Вариант без предиката append */ goal
Recognize([1,1,1,1,1,0,0,0,0,0,0,1,1,0,0,0,0]). clauses
Recognize(L) :- s(L), write("ФРАЗА РАСПОЗНАНА").
Recognize(_) :- write("*** ОШИБКА ! ФРАЗА НЕ РАСПОЗНАНА").
S([1|L]) :- S(L).
S([1|L]) :- B(L).
S([0|L]) :- A(L).
A([0|L]) :- A(L).
A([0|L]) :- B(L).
B([1|L]) :- S(L).
B([]).
Вернемся к вопросу о конечных состояниях. Смысл конечного состояния заключается в определении условия завершения работы автомата.
Работа автомата может быть завершена при попадании его в одно из заключительных состояний (такие состояния назовем поглощающими), и тогда мы имеем дело с ПЛА. Однако условие завершения может быть более сложным: работа автомата заканчивается тогда, когда входная последовательность исчерпана и при этом автомат находится в одном из терминальных состояний. Эта ситуация характерна для НЛА.
Реализовать недетерминированный автомат на Прологе достаточно просто. А сделать то же самое на процедурном языке – задача весьма нетривиальная. На практике поэтому предпочтительнее работать с "нормальным", детерминированным автоматом, не допускающим неоднозначностей.

27