- •Предисловие
- •Глава 1 введение в проблематику конструирования компиляторов
- •1.1. Понятие компилятора и его структура
- •1.2. Применение компиляторов и задачи их разработки
- •Глава 2 способы задания формальных языков
- •2.1. Математический аппарат теории
- •Формальных языков, перевода и компиляции
- •1) AR*a для всех aÎa;
- •2.2 Цепочки и языки
- •2.3 Грамматики
- •2.4. Распознаватели
- •2.5 Регулярные выражения и синтаксические диаграммы
- •2.6. Автоматы с магазинной памятью (мп - автоматы )
- •2.7. Соответствия между способами описания языков
- •Глава 3 основы теории перевода
- •3.1. Определение перевода
- •3.2. Модели простейших трансляторов
- •3.2.1. Конечные преобразователи
- •3.2.2. Преобразователи с магазинной памятью
- •Глава 4 конструирование сканеров
- •4.1. Общая характеристика процесса сканирования
- •4.2. Описание лексем в языке расширенных регулярных выражений
- •4.3. Построение недетерминированного конечного автомата по расширенному регулярному выражению
- •4.4. Преобразование недетерминированного конечного автомата в детерминированный
- •Замечание. Среди состояний могут оказаться недостижимые состояния . Состояние р называется достижимым , если существует такая цепочка w , что (q0, w) *(p , e ). ¨
- •4.5. Преобразование синтаксической диаграммы в конечный автомат
- •4.6. Представление результатов сканирования
- •4.7. Методики конструирования сканеров
- •Глава 5 конструирование однопроходных нисходящих анализаторов
- •5.1. Определение синтаксического разбора
- •5.2. Нисходящий и восходящий разборы
- •5.3. Ll(k) - грамматики
- •5.4. Предсказывающие алгоритмы разбора
- •5.5. Алгоритмы построения управляющих таблиц для левых анализаторов
- •5.6. Приведение грамматик к ll - форме
- •Глава 6 основы генерации кода
- •6.1. Перевод и генерация кода
- •6.2. Представления промежуточной программы
- •6.3. Преобразование промежуточной программы в ассемблерный код
5.3. Ll(k) - грамматики
Выше анализаторы были определены как недетерминированные МП-преобразователи. Попытка их реализации для широкого класса КС-грамматик приводит к так называемым алгоритмам с “возвратами” которые требуют слишком больших затрат времени. На практике обычно ограничивают классы грамматик таким образом, чтобы сделать процесс разбора полностью детерминированным. Оказывается, что эти ограниченные классы КС-грамматик адекватно отражают все синтаксические черты языков программирования и пригодны для описания проблемно-ориентированных языков. Требованиям детерминированности левых анализаторов наилучшим образом удовлетворяют так называемые LL(k)-грамматики, для которых левый анализатор работает детерминировано, если позволить ему принимать во внимание k входных символов, расположенных справа от текущей входной позиции. Входная цепочка считывается таким анализатором один раз слева направо и в процессе анализа не происходит возвратов к уже прочитанной части цепочки. Такие анализаторы называются однопроходными.
Для определения LL(k)-грамматики введем функцию FIRSTk(a).
Определение. Для КС-грамматики G=(N,S,P,S) определим функцию
FIRSTk(a)={xÎS* | a Þ l* xB и |x|=k или a Þ* x и |x| < k}
Иначе говоря, множество FIRSTk(a) состоит из всех терминальных префиксов длины k (или меньше, если из a выводится терминальная цепочка длины, меньшей k) терминальных цепочек, выводимых из a. ¨
Пример 5.4. Пусть грамматика имеет одно правило S®Sa|b. Определим FIRST3(Sa).
Из Sa можно вывести следующие цепочки: ba, baa, baaa,... и т.д.
Из определения следует:
FIRST3(Sa)={ba, baa}.
Определение. КС-грамматика G=(N, S, Р, S) называется LL(k)-грамматикой для некоторого фиксированного k, если любые два левых вывода
(1) S Þ l*w Aa Þl w ba Þ *w x,
S Þl *w Aa Þl w ga Þ *w y
связаны условием: если FIRSTk(x) = FIRSTk(y), то b=g. ¨
Говоря менее формально, G будет LL(k)-грамматикой, если для данной цепочки w AaÎ(NUE)* и первых k символов (если они есть), выводящихся из Aa, существует не более одного правила, которое можно применить к A, чтобы получить вывод какой-нибудь терминальной цепочки, начинающейся с w и продолжающейся упомянутыми k терминальными символами.
Грамматика называется LL-грамматикой, если она LL(k)-грамматика для некоторого k.
Пример 5.5. Пусть G состоит из правил
S ® aAS,
S ® b,
A ® a,
A ® bSA
и дана цепочка w = abbab, которую нужно вывести. Левый вывод этой цепочки имеет вид
S1 Þ aAS4 Þ abSAS2 Þ abbAS3 Þ abbaS2 Þ abbab
Очевидно, что данная грамматика является LL(1) - грамматикой, так как на каждом шаге вывода для каждой пары (нетерминал, терминал) можно однозначно указать какое правило нужно применить.
Эта грамматика служит примером так называемой простой LL(1)-грамматики (или разделенной грамматики).
Определение. КС-грамматика G=(N,S,Р,S) без e-правил называется простой LL(1)-грамматикой (или разделенной грамматикой), если для каждого AÎ N все его альтернативы начинаются различными терминальными символами. ¨
Условия (признаки), при которых КС-грамматика является LL(k) грамматикой, формулируются в форме следующей теоремы.
Теорема 5.1. КС-грамматика G=(N, å, Р, S) является LL(k) - грамматикой тогда и только тогда, когда для двух различных правил А ® b и А ® g из множества P пересечение
FIRSTk(ba) Ç FIRSTk(ga) = Æ
для всех таких w Aa, что S Þ* w Aa.
Здесь a — произвольная цепочка (a Î (NUå)*) , которая может появиться в выводах справа от А. ¨
Пример 5.6. Дана грамматика G:
S ® aAaa | bAba,
A ® b | e.
Определить, является ли G LL(2) - грамматикой .
Для первой пары правил имеем:
b = aAaa, g = bAba, а роль А играет S, следовательно, a = e и
FIRST2(aAaa) Ç FIRST2 (bAba) = {ab,aa} Ç {bb} = Æ.
Для второй пары имеем:
b = b, g = e, роль А играет А, следовательно, a = {aa, ba},
тогда
FIRST2(baa) Ç FIRST2 (aa) = Æ для a = аа,
FIRST2(bba) Ç FIRST2 (ba) = Æ для a = bа.
Таким образом, условия теоремы выполняются для обеих пар правил грамматики G, следовательно, это LL(2) - грамматика.
Если усилить условия теоремы, то можно сузить класс LL(k)-грамматик и получить класс сильно (или строго) LL(k)-грамматик. Для этого введем множество
FOLLOWk(b) = {w | S Þ*abg и w Î FIRSTk(g)}.
Другими словами, это множество терминальных цепочек длины k, которые могут встречаться в выводимых цепочках непосредственно справа от А.
Определение. КС-грамматика G, в которой для двух различных правил А ® b и А ® g
FIRSTk(bFOLLOWk(A))Ç FIRSTk (g FOLLOWk(A))= Æ,
называется сильно (строго) LL(k)-грамматикой.
Пример 5.7. Дана грамматика G:
S ® aAS | AbSc | e,
A ® cbA | a.
Определить: является ли G сильно LL(2)-грамматикой.
Вначале найдем:
FOLLOW2(S) = {e, c, cc}, FOLLOW2(A)= {e, aa, ac, cb, ab, ba, bc}
Для первой строки правил, согласно определению, имеем:
FIRST2(aASFOLLOW2(S))Ç FIRST2(AbScFOLLOW2(S))Ç
Ç FIRST2(FOLLOW2(S))= FIRST2(aAS, aASc, aAScc) Ç
Ç FIRST2(AbSc, AbScc, AbSccc) Ç FIRST2(c, cc)=
={ac, aa} Ç {cb, ab} Ç {c, cc} = Æ;
для второй строки
FIRST2(cbAFOLLOW2(A))Ç FIRST2(aFOLLOW2(A))=
= {cb} Ç FIRST2(a, aaa, aac, acb, aab, aba, abc} =
{cb} Ç {a, aa, ac, ab} = Æ.
Вывод - это сильно LL(2)-грамматика.
Можно показать, что грамматика G из примера 5.6 не является сильно LL(2)- грамматикой (выполните это в качестве упражнения).
В языках программирования многие синтаксические конструкции описываются LL(1)- грамматиками. Сформируем признаки LL(1)- грамматик, вытекающие из теоремы 5.1.
Грамматика G является LL(1) - грамматикой тогда и только тогда, когда для любых ее правил вида
А ® a1| a2| ... |an
выполняются условия:
1) множества FIRST1(a1), FIRST1(a2), ... , FIRST1(an) попарно не пересекаются;
2) если грамматика содержит e - правила (т. е. ai Þ *e), то FIRST1(aj) Ç FOLLOW1(A) = Æ для 1 £ j £ n, i ¹ j.
Пример 5.8. Проверим, какая из грамматик является LL(1)-грамматикой:
1) S ® A | B,
A ® aA | a,
B ® bB | b.
Здесь нет e-правил, поэтому проверим только условие (1):
FIRST(A)Ç FIRST(B) = {a} Ç {b} = Æ – выполняется;
FIRST(aA)Ç FIRST(a) = {a} Ç {a} ¹ a – не выполняется.
Вывод - это не LL(1)-грамматика.
2) S ® AB,
A ® Ba | c,
B ® Cb | C,
C ® c | e.
Здесь имеется е - правило, поэтому начнем проверку с условия 2. Для второго правила в данной грамматике имеем:
FIRST(Ba) Ç FOLLOW(A) = {a, b, c} Ç {b, c}={b,c} – не выполняется.
Вывод - это не LL(1)-грамматика.
3) S ® aAaB | bAbB,
A ® S | cb,
B ® cB | a.
Здесь нет е-правил, проверяем условие (1):
FIRST(aAab)Ç FIRST(bAbB) = {a} Ç {b} = Æ – выполняется,
FIRST(S)Ç FIRST(cb) = {a, b} Ç {c} = Æ – выполняется,
FIRST(cB)Ç {a} = {c} Ç {a} = Æ – выполняется.
Вывод - это LL(1)-грамматика.