- •Предисловие
- •Глава 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.5. Алгоритмы построения управляющих таблиц для левых анализаторов
Алгоритм А1: построение корректной управляющей таблицы М для заданной LL(1)-грамматики.
Вход А1: заданная LL(1)-грамматика G=(N, S, P, S).
Выход А1: управляющая таблица М.
Описание А1. Будем считать, что $ — маркер дна магазина. Таблица М определяется на множестве (N È S È {$})´(S È {e}) следующим образом:
1) если А®a — правило из P с номером i, то М(А, а) = (a, i) для всех (а¹е)ÎFIRST1(a); если еÎFIRST1(a), то М(А, b) = (a, i) для всех bÎFOLLOW1(A);
2) М(а, а) = «выброс» для всех аÎS;
3) М($, е) = «допуск»;
4) в остальных случаях М(X, а)= «ошибка» для XÎ N È S È {$} и аÎS È {e}.
Пример 5.10. Рассмотрим LL(1)-грамматику G с правилами:
(1) E® T ,
(2) ® +T ,
(3) ® e,
(4) T® F ,
(5) ®*F ,
(6) ® e,
(7) F® (E),
(8) F® a.
Применение пунктов 2 – 4 алгоритма А1 при заполнении элементов таблицы М не вызовет затруднений. Проиллюстрируем применение п.1 при заполнении первых двух строк управляющей таблицы (табл. 5.2.)
Таблица 5.2
|
а |
( |
) |
+ |
* |
e |
E |
T , 1 |
T , 1 |
|
|
|
|
|
|
|
e,3 |
+ T , 2 |
|
e,3 |
T |
F , 4 |
F , 4 |
|
|
|
|
|
|
|
e, 6 |
e, 6 |
*F , 5 |
e, 6 |
F |
a, 8 |
(E), 7 |
|
|
|
|
a |
выброс |
|
|
|
|
|
( |
|
выброс |
|
|
|
|
) |
|
|
выброс |
|
|
|
+ |
|
|
|
выброс |
|
|
* |
|
|
|
|
выброс |
|
$ |
|
|
|
|
|
выброс |
Следуя шагу 1 алгоритма А1, определяем элементы первой строки таблицы М для нетерминала Е в правиле (1). Имеем FIRST1 [ T ] ={ ( , a} , поэтому M [ E , ( ] =[T ,1] и М[E ,a]= =[T ,1], а все остальные элементы этой строки - «ошибки».
Определяем теперь элементы строки для нетерминала . Для правила (2) находим FIRST1 [+T ] = {+} , поэтому М[ ,+]= = [ + T , 2 ] .
Так как имеется е-правило (3) , то еÎFIRST1 (a=e), поэтому вычисляем
FOLLOW1 [ ]={e,)} .
Следовательно, M [ , e] = M[ , )] = [e ,3]. Все остальные элементы строки для - «ошибки» . Продолжая эти рассуждения, заполним все строки таблицы М . Использующий эту таблицу левый анализатор (l - предсказывающий алгоритм разбора ) проанализирует входную цепочку w = (а * а) следующим образом :
[(a*a) , E$ , e ] [(a*a) , T $ , 1] [(a*a) , F $ , 14 ]
[(a*a) , (E) $ ,147] [a*a) ,E) $ ,147]
[a*a) ,T ) $, 1471] [a*a) , F ) $ , 14714]
[a*a) , a ) $ , 147148] [*a) , ) $ , 147148]
[ *a) ,* F ) $ , 1471485 ] [a) , F ) $ , 1471485] [a) , a ) $ , 14714858] [ ) , ) $ , 14714858 ] [ ) , ) $ , 147148586 ] [) , ) $ , 1471485863]
[ e, $ , 1471485863] [ e , $ , 14714858636]
[e,$, 47148586363]
Алгоритм А2 : построение корректной управляющей таблицы М для строгой LL(k) - грамматики .
Вход А 2: заданная строго LL(k) - грамматика G = (N,S,P,S) .
Выход А2 : управляющая таблица М .
Описание А2 . Этот алгоритм почти идентичен алгоритму А1. Небольшое отличие состоит в следующем :
а) входные символы таблицы М , используемой в А1, необходимо заменить аванцепочками х длиной ½х½ £ k ;
б) в пункте 1 алгоритма А1 выражения FIRST1(a) и FOLLOW1(A) заменяются выражениями FIRSTк (a) и FOLLOWк(A) соответственно .
Пример 5.11. Построим управляющую таблицу М для грамматики G из примера 5.7 :
(1) S ® aAS ,
(2) S ® AbSc,
(3) S ® e,
(4) A ® cbA,
(5) A® a.
Выпишем все аванцепочки длиной ½ х½ £ 2 :
aa,ab,ac,ba,bb, bc,ca,cb,cc,a,b,c,e. Вычислим функции FIRST и FOLLOW, необходимые для построения таблицы по п.1 алгоритма А1 . Такими функциями являются :
FIRST2 (aAS) = {aa,ac},
FIRST2 (AbSc) = {ab,cb},
FIRST2 (cbA) = {cb},
FIRST2 (a) = {a},
FOLLOW2 (S) ={e , c , cc}.
Применяя А2, получим управляющую таблицу М (табл.5.3) .
Таблица 5.3
|
aa |
ab |
ac |
ba |
bb |
bc |
ca |
cb |
cc |
a |
b |
c |
e |
S |
aAS,1 |
AbSc,2 |
aAS,1 |
|
|
|
|
AbSc,2 |
e , 3 |
|
|
е ,3 |
е , 3 |
A |
|
|
|
|
|
|
|
cbA,4 |
|
a ,5 |
|
|
|
a |
|
|
|
|
|
|
|
|
|
выбр |
|
|
|
b |
|
|
|
|
|
|
|
|
|
|
выбр |
|
|
c |
|
|
|
|
|
|
|
|
|
|
|
выбр |
|
$ |
|
|
|
|
|
|
|
|
|
|
|
|
допуск |
Левый анализатор (2 - предсказывающий алгоритм разбора), использующий эту таблицу для входной цепочки w=acbacbabaac, выдаст ее левый разбор : 14524153 . Убедитесь в этом самостоятельно .
Мы рассмотрели алгоритмы построения управляющих таблиц левых анализаторов только для строго LL(k) - грамматики. Если грамматика G не является строго LL(k) - грамматикой , то применение алгоритма А2 приведет к построению некорректной таблицы в том смысле , что анализатор на некотором шаге разбора цепочки не сможет однозначно выбрать правило грамматики.
Для класса нестрогих LL(k) - грамматик используются другие алгоритмы, позволяющие построить корректные (не содержащие неоднозначности) управляющие таблицы. Описание этих алгоритмов приведено в монографии А. Ахо и Дж. Ульмана и мы рекомендуем их для самостоятельного изучения.