1 Часть II. Глава 2. LL(k)-ГРАММАТИКИ И ТРАНСЛЯЦИИ Теория формальных языков и трансляций. - презентация

1 1 Часть II. Глава 2. LL(k)-ГРАММАТИКИ И ТРАНСЛЯЦИИ Теория формальных языков и трансляций

2 2 § 2.1. Введение в LL(k)-грамматики Неформальное описание. В гл. II.1 было показано, что произвольная простая синтаксиче- ски управляемая трансляция ( sdt ) всегда может быть реализована при помощи недетерми- нированного магазинного преобразователя (npdt). Если же, кроме того, схема ( sdts ), посредством которой задается эта трансляция, является семантически однозначной, то выход трансляции можно получить по левостороннему анализу входной цепочки при помощи детерминиро- ванного магазинного преобразователя (dpdt). Часть II: Глава 2

3 3 Следовательно, если найти такие классы входных грамматик, в которых левосторонний анализ может быть реализован детерминирован- ным образом, то мы имели бы полностью детерминированную реализацию простых семан- тически однозначных трансляций. Одним из таких подклассов КС-грамматик являются так называемые LL(k)-грамматики. Это наибольший естественный класс левоанализи- руемых грамматик. Часть II: Введение в LL(k)-грамматики

4 4 Определение 2.1. Пусть G = (V N, V T, P, S) однозначная cfg, w = a 1 a 2 …a n, n > 0, где a l V T (l = 1, 2, …, n), и w L(G). Тогда существует единственная последова- тельность левосентенциальных форм …, m, такая, что = S, i i+1 для 0 i < m и m = w. Последовательность номеров правил грам- матики G p 0, p 1,…, p m–1 называется лево- сторонним анализом цепочки w.

5 5 Теперь предположим, что мы хотим найти этот левосторонний анализ, просматривая w слева направо один раз. Мы могли бы попытаться сделать это путём построения последовательности левосентенциальных форм …, m. Начальная сентенциальная форма = S уже известна. Остается определить способ построения следующей сентенциальной формы по последней из уже построенных. Часть II: Введение в LL(k)-грамматики

6 6 Пусть i = a 1 a 2...a j A последняя из построенных сентенциальных форм. Сравнивая закрытую часть этой сентен- циальной формы a 1 a 2...a j с цепочкой w = a 1 a 2 … a j a j+1 …a n, мы можем определить её окончание a j+1 …a n, вывод которого ещё предстоит построить. Часть II: Введение в LL(k)-грамматики

7 7 Было бы желательно, чтобы i + 1 можно было найти, зная только (1) a 1 a 2... a j часть входной цепочки, которую мы уже просмотрели к этому моменту, (2) несколько следующих входных симво- лов a j+1 … a j+k для некоторого фиксиро- ванного k, называемой аванцепочкой, и (3) A V N. Часть II: Введение в LL(k)-грамматики

8 8 Если эти три величины однозначно определяют, какое правило должно исполь- зоваться для раскрытия A, то мы смогли бы точно определить i+1 по i. Говорят, что грамматика, в которой каждый левосторонний вывод имеет это свойство, есть LL(k)-грамматика. Будет показано, что для каждой LL(k)- грамматики можно построить детерминиро- ванный левосторонний анализатор, кото- рый действует за линейное время. Часть II: Введение в LL(k)-грамматики

9 Формальное определение Определение 2.2. Пусть G = (V N, V T, P, S) cfg. Определим функцию {w V T * w, w < k, либо wx, w = k, x V T * }. Здесь k целое, (V N V T ) *. Ret 21

10 10 Отметим, что эта функция определена, в частности, и для терминальной цепочки, и тогда, когда она пуста. При этом верхний индекс грамматики G функции не существен, так как никакие правила для вывода терминаль- ной цепочки при = не требуются. Часть II: Введение в LL(k)-грамматики

11 11 Определение 2.3. Пусть G = (V N, V T, P, S) cfg. Говорят, что G есть LL(k)-грамматика для некоторого фиксированного k 0, если для любых двух левосторонних выводов вида 1) S wA w wx, 2) S wA w wy, в которых имеет место равенство =. Часть II: Формальное определение LL(k)-грамматики Ret 12Ret 16 Ret 23 Ret 33 Ret 19 Ret 59

12 12 Часть II: Формальное определение LL(k)-грамматики Определение 2.4. Говорят, что cfg G есть LL-грамматика, если она LL(k) для некоторого k. Пример 2.2. LL(1)-грамматика. Пусть G = ({S, B}, {a, b}, P, S), где P = {S aBS b, B a bSB}. Рассмотрим два левосторонних вывода вида (1) и (2) (см. определение 2.3), в кото- рых роль нетерминала A играет символ S.2.3 Ret 80

13 13 Имеем (1) S aBS и (2) S b. Тогда w = =, = aBS, = b. Ясно, что любая цепочка x, выводимая из = aBS, начинается на a, а цепочка y, выводимая из = b, равна b. Поэтому если первый символ цепочки, следующей за закрытой частью сентенциаль- ной формы (w = ), есть a, то для замены нетерминала S следует использовать первую альтернативу. Если она начинается на b, то вторую. Пример 2.2.

14 14 Пример 2.2. Рассмотрим два левосторонних вывода, в которых роль нетерминала A играет символ B: (1) S aBS aaS и (2) S aBS abSBS. Тогда w = a, = S, = a, = bSB. Ясно, что любая цепочка x, выводимая из = aS, начинается на a, а цепочка y, выводимая из = bSBS, начинается на b.

15 15 Поэтому если первый символ цепочки, следующей за закрытой частью сентенциаль- ной формы, есть a, то для замены нетер- минала B следует использовать первую альтернативу (т. е. правило B a). Если она начинается на b, то вторую (т. е. правило B bSB). Пример 2.2.

16 16 В обоих случаях LL(1)-условие выполнено: по первому символу цепочки, следующей за закрытой частью сентенциальной формы, однозначно определяется то правило, которое следует применить к соответствую- щему нетерминалу, чтобы в конце концов получить анализируемую цепочку. Очевидно, что любые два левосторонних вывода в данной грамматике, подпадающие под образец (см. определение 2.3), удовлет- воряют LL(k)-условию при k = Пример 2.2.

17 17 Грамматика примера 2.2 служит примером простой LL(1)-грамматики. Определение 2.5. Говорят, что cfg G является простой LL(1)-грамматикой, если в ней нет -правил, и все альтернативы для каждого нетерминала начинаются с терминалов, и притом различных. Таким образом, в простой LL(1)- грамматике для данной пары (A, a), где A V N и a V T, существует, самое большее, одна альтернатива вида A a, V *. Часть II: Формальное определение LL(k)-грамматики

18 18 § 2.2. Свойства LL(k)-грамматик Теорема 2.1. Чтобы cfg G = (V N, V T, P, S) была LL(k)-грамматикой, необходимо и достаточно, чтобы для всех,,, таких, что существуют правила вида A, A P,, и существует вывод вида S wA. Ret 169Ret 126Ret 49

19 19 Доказательство. Будем предполагать, что грамматика G не содержит бесполезных нетерминалов, то есть G приведённая КС- грамматика. Это предположение не умаляет общности рассуждений, так как бесполезные нетерми- налы не влияют на LL(k)-условие, фигури- рующее в определении 2.3 LL(k)-грамматик.2.3 Обе части доказательства проведём методом от противного. Свойства LL(k)-грамматик

20 20 Свойства LL(k)-грамматик I.Необходимость. Пусть G LL(k)-грам- матика, но условие не выполнено, т. е. нашлись такие цепочки,,, что существуют правила (1) A, (2) A P,, и существует вывод S wA, для которых

21 21 Пусть некоторая цепочка Следовательно, существуют выводы для некоторых u, v V T *, причём если z < k, то u = v = (см. определение 2.2), которые всегда можно перестроить в левосторонние.2.2 Необходимое условие LL(k) (3) zu и (4) zv,

22 22 Необходимое условие LL(k) Мы можем продолжить имеющийся вывод S wA, используя правила (1) A, (2) A и выводы (3) zu и (4) zv, двумя разными способами :

23 23 1) S wA w wzu, 2) S wA w wzv Остается сопоставить эти два лево- сторонних вывода с теми, которые участву- ют в определении 2.3 LL(k)-грамматик. Здесь в роли цепочки x используется zu, а в роли цепочки y zv.2.3 Очевидно, но, что противоречит предположению о том, что G LL(k)-грамматика. Необходимое условие LL(k) x y

24 24 В частности, если z < k и u = v =, то мы имеем два разных левосторонних вывода одной и той же терминальной цепочки wz. Это означает, что G не однозначная грамматика и, естественно, не LL(k) ни при каком k. Необходимость доказана. Необходимое условие LL(k)

25 25 II. Достаточность. Пусть условие теоремы выполнено, но G не LL(k)-грамматика. Это значит, что существуют два левосторонних вывода: 1) S wA w wx, 2) S wA w wy, в которых но. Достаточное условие LL(k)

26 26 Достаточное условие LL(k) Имеем x и y, и пусть Согласно определению функции из существования этих двух выводов заклю- чаем, что и, следовательно, что входит в противоречие с первоначаль- ным предположением о том, что условие теоремы выполняется. Достаточность доказана, а вместе с ней и вся теорема.

27 27 Свойства LL(k)-грамматик Определение 2.6. Пусть G = (V N, V T, P, S) cfg, и. Определим функцию = {w S и }. Здесь k целое.

28 28 Необходимое и достаточное условие LL(1) Теорема 2.2. Чтобы cfg G = (V N, V T, P, S) была LL(1)-грамматикой, необходимо и достаточно, чтобы для всех A V N,, (V N V T ) *, таких, что существуют правила A, A P, где. Ret 169Ret 46

29 29 Доказательство. Требуется пояснить, что в формулировке условия теоремы аргумент функции не цепочка, как было определено ранее, а множество цепочек. Расширение области определения этой функции на множества цепочек про- изводится естественным образом: Необходимое и достаточное условие LL(1)

30 30 Необходимое условие LL(1) Обе части теоремы доказываются методом от противного. Как и ранее, не нарушая общности рассуждений, будем считать грамматику G приведённой. I. Необходимость. Пусть G LL(1)-грам- матика, но условие не выполнено, т. е. существуют правила A, A P при, и существует c (V T { }), такие, что и

31 31 Необходимое условие LL(1) Это означает, что существуют такие, что и и согласно определению функции существуют выводы: a cu и b cv, при некоторых u,v, если c V T, или a и b, если c =, и в этом случае a = b =. Ret 35 Ret 38 Ret 39 Ret 42

32 32 Необходимое условие LL(1) Случай 1: c V T, a cu a = cu, cu, u V T * ; b cv b = cv, cv, v V T *. Так как грамматика G приведённая, то существует вывод, в частности лево- сторонний, который порождает сентенциаль- ную форму, содержащую A: S wA, который может быть продолжен двумя способами:

33 33 Необходимое условие LL(1) 1) S wA w wcu wcu z, 2) S wA w wcv wcv z, где вывод z c z V T * существует также в силу приведённости грамматики G. Итак, имеем два левосторонних вывода 1) и 2), фигурирующие в определении 2.3 LL(k)-грамматик, в которых в роли цепочки x используется cu z, в роли цепочки y cv z, причём2.3 x y

34 34 Необходимое условие LL(1) но. Следовательно, грамматика G не LL(1), что противоречит первоначальному пред- положению.

35 35 Необходимое условие LL(1) Случай 2: c V T,, (см. 31)31 b cv b, cv, v V T *. То, что означает, что существует вывод, в частности левосторон- ний, вида S wA, такой, что или, что то же самое, существует вывод сz при некотором z V T *.

36 36 Необходимое условие LL(1) Продолжим левосторонним образом вывод S wA двумя способами: 1) S wA w w wсz, 2) S wA w wсv wсv сz. x y Получили два вывода 1) и 2), фигурирующие в определении LL(k)- грамматик (при k = 1), с cz в роли цепочки x и cv cz в роли цепочки y.

37 37 Необходимое условие LL(1) Имеем: но. Следовательно, грамматика G не LL(1), что противоречит первоначальному пред- положению. т. е.

38 38 Необходимое условие LL(1) Случай 3: c V T, a cu a, cu, u V T * ;, Он разбирается аналогично случаю 2. (см. 31).31

39 39 Необходимое условие LL(1) Случай 4: c V T,,, a = b = c, То, что означает суще- ствование вывода вида S wA, такого, что или, что то же самое, cz при некотором z V T *. (см. 31).31

40 40 Необходимое условие LL(1) Теперь вывод S wA перестроим в лево- сторонний и продолжим двумя способами: 1) S wA w w wсz, 2) S wA w w wсz, Мы получили два левосторонних вывода 1) и 2), фигурирующих в определении LL(k)- грамматик (при k = 1), в которых в роли цепочек x и y используются одинаковые терминальные цепочки сz: притом что. x y

41 41 Следовательно, грамматика G не LL(1), что противоречит первоначальному пред- положению. Противоречие можно видеть и в том, что существуют два разных левосторонних вывода для одной и той же терминальной цепочки wcz. То есть грамматика G неоднозначна и не может быть LL- грамматикой по самому замыслу этого класса КС-грамматик. Необходимое условие LL(1)

42 42 Необходимое условие LL(1) Случай 5: c =,,, a = b =, Как и в случае 4, означает существование вывода S wA, такого, что. Его можно перестроить в левосторонний и продолжить двумя способами: 1) S wA w w w, 2) S wA w w w.

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

44 44 Достаточное условие LL(1) II. Достаточность. Пусть условие теоремы выполнено, но грамматика G не LL(1). Тогда существуют два левосторонних вывода вида 1) S wA w wx, 2) S wA w wy, в которых но. Поскольку x и y, то

45 45 Достаточное условие LL(1) Пусть Тогда а это противоречит первоначальному пред- положению о том, что условие теоремы выполнено, то есть что Достаточность доказана и вместе с ней и вся теорема.

46 46 Необходимое и достаточное условие LL(1) Следствие 2.1. Теорему 2.2 можно переформулировать следующим образом: КС-грамматика G является LL(1)-грам- матикой тогда и только тогда, когда для каждого множества A-правил A 1 2 … n выполняются следующие условия (ср. 28) :28 1) при i j, 1 i, j n; 2) если i, то для всех j: 1 j n, j i.

47 47 Необходимое и достаточное условие LL(1) Определение 2.7. Контекстно-свободная грамматика G = (V N, V T, P, S) называется сильной LL(k)-грамматикой, если она удовлетворяет условию теоремы 2.2: для всех A V N,, (V N V T ) *, таких, что существуют правила A, A P,. Ret 113

48 48 Следствие 2.2. Каждая LL(1)-грамматика является сильной. Однако следующий пример показывает, что для k > 1 не всякая LL(k)-грамматика является сильной. Необходимое и достаточное условие LL(1)

49 49 Пример 2.3. Несильная LL(2)-грамматика. Рассмотрим cfg G = ({S, A}, {a, b}, P, S), где P = {S aAaa bAba, A b }. Используя теорему 2.1, проверим, что грамматика G LL(2).2.1 I. Проведём тестирование относительно нетерминала S: (aAaa ) = {aa, ab}, (bAba ) = {bb} независимо от, (aAaa ) (bAba ) = = {aa, ab} {bb} =. Ret 122Ret 125 Фактически, единственное возможное =.

50 50 II. Проведём тестирование относительно нетерминала A. При этом следует учесть, что S aAaa и S bAba, так что {aa, ba}. Тогда при = aa: (baa) = {ba}, ( aa) = {aa}, (baa) ( aa) = {ba} {aa} = ; при = ba: (bba) = {bb}, ( ba) = {ba}, (bba) ( ba) = {bb} {ba} =. Так что G действительно LL(2)-грам- матика. Пример не сильной LL(2)-грамматики

51 51 Пример не сильной LL(2)-грамматики Но поскольку, очевидно, что то, учитывая существование выводов S aAaa и S bAba, заключаем, что Проверка условия сильной LL(2)-грам- матики показывает, что

52 52 Пример не сильной LL(2)-грамматики Ret 120 для S: а для A: (b{aa, ba}) ( {aa, ba}) = = {ba, bb} {aa, ba} = {ba}. Таким образом, грамматика G LL(2), но не сильная LL(2)-грамматика. (aAaa{ }) (bAba{ }) = {aa, ab} {bb} =,

53 53 Теорема 2.3. Если G = (V N, V T, P, S) cfg, и G леворекурсивна, то G не LL(k)- грамматика ни при каком k. Доказательство будем проводить в предположении приведённости грамматики G, поскольку, как отмечалось ранее, бесполезные нетерминалы не влияют на выполнение LL(k)-критерия. Ret 165 Ret 167

54 54 Так как грамматика G леворекурсивна, то существует вывод вида A A, где, хотя и не исключается, что. Напомним, что A A означает, что существует вывод вида A A. Отметим, что независимо от того, = A или A, должно существовать ещё какое-то правило для A, скажем, A ( ), ибо в противном случае ничего, кроме A A i, где i 0, вывести из нетерминала A было бы невозможно, что противоречило бы приведённости G. Леворекурсивная грамматика не LL(k) при любом k

55 55 Леворекурсивная грамматика не LL(k) при любом k Итак, вывод вида A A в общем случае состоит из шагов вида A A 1 1 A A m–1 m– A m m... 1 = A, где A m = A, = m m– Очевидно, что в этом выводе были использованы правила A A 1 1, A 1 A 2 2,…, A m–1 A m m, где A m = A.

56 56 Хотя бы одно из этих правил должно иметь альтернативу, не начинающуюся ни на один из нетерминалов A 1, A 2, …, A m (иначе грамматика G была бы неприве- дённой). Пусть, например, существует A j A j+1 j+1 |, где A j+1 j+1. Леворекурсивная грамматика не LL(k) при любом k

57 57 Леворекурсивная грамматика не LL(k) при любом k Так как грамматика G приведённая, существует сентенциальная форма, в частности, левостороннего вывода, в которой участвует нетерминал A, например в выводе S wA, который может быть продолжен следующим образом: S wA wA i wA 1 1 i … … wA j j … 1 i. Далее этот вывод можно продолжить двумя способами:

58 58 Леворекурсивная грамматика не LL(k) при любом k 1) wA j+1 j+1 j … 1 i wA m m … 1 i = = wA i+1 wA j j … 1 i+1 w j … 1 i+1 wzx j …x 1 r i+1 t, 2) w j … 1 i wzx j … x 1 r i t, y x предполагая, что ввиду приведённости грамматики, существуют выводы z, j x j, …, 1 x 1, r, t, где w, z, x j, …, x 1, r, t V T *.

59 59 Леворекурсивная грамматика не LL(k) при любом k Эти два вывода можно сопоставить с теми, которые фигурируют в определении 2.3 LL(k)-грамматик, учитывая, что 2.3 x = zx j …x 1 r i+1 t, а y = zx j …x 1 r i t. Если r, то каким бы большим ни было k, всегда путем выбора i можно добиться, чтобы при том, что в точке, где эти два вывода разошлись, были применены различные аль- тернативы для раскрытия нетерминала A j : A j A j+1 j+1 |, A j+1 j+1.

60 60 Если r =, то имеем два разных левосторонних вывода одной и той же терминальной цепочки wzx j … x 1 t. То и другое означает, что грамматика G не LL(k) ни при каком k. Леворекурсивная грамматика не LL(k) при любом k Следствие 2.3. Итак, мы имеем два достаточных признака для того, чтобы считать КС-грамматику не LL-грамматикой. Это неоднозначность и леворекурсив- ность.

61 61 § 2.3. k-Предсказывающие алгоритмы анализа Для класса LL(k)-грамматик существует адекватный класс анализаторов, называе- мых k-предсказывающими алгоритмами анализа Неформальное описание. Это устройство (рис. 2.1) имеет разбитые на ячейки входную, выходную ленты и ленту магазина. Дно магазина маркируется специальным символом, например $, который постоянно находится на магазин- ной ленте.2.1

62 62 … … u… x * ; u * k ; x * Управляющая таблица M(X, u) МагазинМагазин Вход: Выход: $ X0X0 Рис. 2.1a. k-Предсказывающий алгоритм анализа. Начальная конфигурация x X 0 x

63 63 В начальный момент на входе находится вся анализируемая цепочка (x * ), читаю- щая головка сканирует начало входной ленты, в магазине начальный символ магазина (X 0 ) и маркер его дна ($), на выходе пусто (см. рис. 2.1а).2.1а k-Предсказывающие алгоритмы анализа

64 64 Конечное устройство управления руко- водствуется управляющей таблицей (M), создаваемой по грамматике, в которой производится синтаксический анализ. Она определяет действия в зависимости от: аванцепочки (u * k ) k символов, ска- нируемых единовременно читающей голов- кой входной ленты, начиная с текущего символа, причём при x = u k; верхнего символа магазина (X ). k-Предсказывающие алгоритмы анализа

65 65 Этими параметрами определяются движения следующих двух типов: 1. Замещение верхнего символа магазина (X), представляющего левую часть некоторого правила грамматики (A ), цепочкой магазинных символов правой частью этого правила или цепочкой, производной от неё, и присоединение к концу выходной цепочки номера этого правила (i). При этом продвижения по входной цепочке не происходит, а выходная головка продвигается к следующей свободной ячейке (см. рис. 2.1 б).2.1 б k-Предсказывающие алгоритмы анализа

66 66 i u Управляющая таблица M(X, u) = (, i) МагазинМагазин Вход: Выход: wy $ Рис. 2.1б. k-Предсказывающий алгоритм анализа. Движение типа 1. X x * ; u * k ; y * X * * ; i Ret 70 u k, если y =

67 67 2. Сброс верхнего символа магазина и продвижение к следующей ячейке входной ленты. На выходную ленту ничего не пишется. Такие движения происходят только тогда, когда первый символ аванцепочки такой же, как верхний символ магазина (см. рис. 2.1в). 2.1в k-Предсказывающие алгоритмы анализа

68 68 a aa… Управляющая таблица M(X, u) = pop МагазинМагазин Вход: Выход: w x * $ Рис. 2.1в. k-Предсказывающий алгоритм анализа. Движение типа 2. a ; x + a * * Ret 68

69 69 На каждом такте работы алгоритм адресуется к своей управляющей таблице. Управляющий элемент, если он определён, диктует одно из упомянутых выше движений, которое и выполняется. Этот цикл повторяется до тех пор, пока управляющий элемент не просигнализирует о приёме входной цепочки, и в этом случае на выходе образуется её левосторонний анализ, или управляющий элемент диагностирует ошибку на входе, и тогда алгоритм останавливается, не принимая входной цепочки. k-Предсказывающие алгоритмы анализа

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

71 71 На рис. 2.1б входная цепочка представлена как wx, причем w обозначает просмотренную, а x не просмотренную её часть, которая начинается с аванцепочки u и заканчивается цепочкой y. Магазинная цепочка представлена в виде X $, где X обозначает верхний символ магазина, символы магазина, располагающиеся ниже его вершины, а $ маркер дна. Выходная цепочка представлена как i, где обозначает часть выходной цепочки, образованной перед последним движением алгоритма, а i последнюю произведённую запись на выходную лентурис. 2.1б k-Предсказывающие алгоритмы анализа

72 72 k-Предсказывающие алгоритмы анализа Формальное определение. Определение 2.8. k-Предсказывающим алго- ритмом анализа называется формальная система = (,,, M, X 0, $), где входной алфавит, магазинный алфавит, $ маркер дна магазина, выходной алфавит, X 0 начальный символ магазина, M: ( {$}) * k {(, i), pop, accept, error} управляющая таблица, *, i (номер правила грамматики).

73 73 k-Предсказывающие алгоритмы анализа Работу k-предсказывающего алгоритма анализа проще всего описать в терминах отношения на множестве конфигураций. Определение 2.9. Под конфигурацией k- предсказывающего алгоритма анализа будем подразумевать тройку (x,, ), где x * непросмотренная часть входной цепочки, причём u (x) * k аванцепочка, * {$} всё содержимое магазина, * выходная цепочка.

74 74 Начальная конфигурация есть (w, X 0 $, ), где w * вся входная цепочка. Пусть (x, X, ) текущая конфигурация, где x * непросмотренная часть входной цепочки, X { } верхний символ ма- газина или пустая цепочка, * {$} остальная часть магазинной цепочки, * выходная цепочка, образованная к этому моменту. k-Предсказывающие алгоритмы анализа

75 75 k-Предсказывающие алгоритмы анализа Определим следующую конфигурацию в зависимости от значения элемента управ- ляющей таблицы M(X, u). 1. Если M(X, u) = (, i), то (x, X, ) (x,, i). 2. Если M(X, u) = pop, и в этом случае всегда X = a, a, x = ax, x *, то (x, X, ) = (ax, a, ) (x,, ).

76 76 3. Если M(X, u) = accept, что бывает только по достижении конечной или принимающей конфигурации (, $, ), то анализатор оста- навливается, принимая входную цепочку. 4. Если M(X, u) = error, то анализатор сообщает об ошибке на входе и останавливается, не принимая входной цепочки. k-Предсказывающие алгоритмы анализа

77 77 k-Предсказывающие алгоритмы анализа Как обычно, определяется степень ( ), транзитивное замыкание ( ) и рефлексивно- транзитивное замыкание ( ) этого отношения на конфигурациях. Если (w, X 0 $, ) (, $, ), то мы пишем (w) = и называем выходом для входа w. Если алгоритм из начальной конфигу- рации не достигает принимающей конфигу- рации, то говорят, что значение (w) не определено.

78 78 k-Предсказывающие алгоритмы анализа Трансляция, определяемая k-предсказыва- ющим алгоритмом анализа, есть ( ) = {(w, ) (w) = }. Говорят, что есть правильный k-пред- сказывающий алгоритм анализа для cfg G, если (1) L(G) = {w (w) определено} и (2) если (w) =, то S w.

79 79 k-Предсказывающие алгоритмы анализа Если k-предсказывающий алгоритм анализа, использующий управляющую таблицу M, является правильным для cfg G, то говорят, что M правильная управляющая таблица для грамматики G.

80 80 Пример 1-предсказывающего алгоритма анализа Пример 2.4. Построим 1-предсказыва- ющий алгоритм анализа для простой LL(1)- грамматики, приведённой в примере II-2.2.II-2.2 Пронумеруем её правила: 1) S aBS, 2) S b, 3) B a, 4) B bSB. С учётом свойств этой грамматики, выявленных в этом примере это простая LL(1)-грамматика, нетрудно построить управляющую таблицу анализатора:

81 81 Пример 1-предсказывающего алгоритма анализа А в а н ц е п о ч к и ab SaBS, 1b, 2error Ba, 3bSB, 4error apoperror b poperror $ accept X Табл. 2.1

82 82 Используя эту таблицу, алгоритм анали- зировал бы входную цепочку abbab следующим образом: (abbab, S$, ) (abbab, aBS$, 1) (bbab, BS$, 1) (bbab, bSBS$,14) (bab, SBS$,14) (bab, bBS$, 142) (ab, BS$, 142) (ab, aS$, 1423) (b, S$, 1423) (b, b$, 14232) (, $, 14232). Пример 1-предсказывающего алгоритма анализа

83 83 Пример 1-предсказывающего алгоритма анализа Итак, (abbab) = Нетрудно проверить, что действительно левый анализ abbab: достаточно лишь произвести левосторонний вывод с использованием правил в указанной последовательности: S aBS abSBS abbBS abbaS abbab. Следовательно, правильный 1- предсказывающий алгоритм анализа для грамматики G.

84 84 Пример 2.5. Построим детерминирован- ный магазинный преобразователь, модели- рующий k-предсказывающий алгоритм анализа предыдущего примера. Поскольку грамматика является простой, то нетрудно заметить, что за движением типа 1 сразу же следует pop-движение, продвигающее анализатор к следующему символу входной цепочки и стирающее верхний символ магазина, который всегда оказывается равным входному. Пример 2.5. dpdt, моделирующий анализатор

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

86 86 Кроме того, конец входной цепочки будет маркирован, чтобы контролировать его достижение. Принимая во внимание сказанное, положим P = ({q 0, q, accept}, {a, b, $}, {S, B, a, b, $}, {1, 2, 3, 4},, q 0, $, {accept}), где Пример 2.5. dpdt, моделирующий анализатор

87 87 1) (q 0,, $) = (q, S$, ) воспроизводит начальную конфигурацию; 2) (q, a, S) = (q, BS, 1) воспроизводит движения M(S, a) = (aBS, 1); M(a, a) = pop; 3) (q, b, S) = (q,, 2) воспроизводит движения M(S, b) = (b, 2); M(b, b) = pop; 4) (q, a, B) = (q,, 3) воспроизводит движения M(B, a) = (a, 3); M(a, a) = pop; 5) (q, b, B) = (q, SB, 4) воспроизводит движения M(B, b)= (bSB,4); M(b, b) = pop; 6) (q, $, $) = (accept,, ) сигнализирует о приёме. Пример 2.5. dpdt, моделирующий анализатор

88 88 Пример 2.5. dpdt, моделирующий анализатор Легко проверить, что (w$, ) e (P) = (P) тогда и только тогда, когда (w) =. Посмотрим, как действует этот преобразо- ватель на той же входной цепочке abbab: (q 0, abbab$, $, ) (q, abbab$, S$, ) (q, bbab$, BS$, 1)(q, bab$, SBS$,14) (q, ab$, BS$, 142)(q, b$, S$, 1423) (q, $, $, 14232) (accept,,, 14232). Как видим, (abbab$, 14232) e (P) = (P).

89 89 § 2.4. Построение 1-предсказывающего алгоритма анализа по LL(1)-грамматике Алгоритм 2.1: построение LL(1)- анализатора. Вход: G = (V N, V T, P, S) LL(1)-грамматика. Выход: правильный 1-предсказываю- щий алгоритм анализа для грамматики G. Метод. Положим = (,,, M, X 0, $), где = V T, = V N V T, = {1, 2, …, #P}, X 0 = S. Ret 169Ret 259 Ret 97Ret 124

90 90 Управляющая таблица M на множестве ( {$}) ( { }) определяется следую- щим образом: 1) Если A является i-м правилом во множестве правил P, то M(A, a) = (, i) для всех a a. Кроме того, если то M(A, b) = (, i) для всех Алгоритм 2.1: построение LL(1)-анализатора Ret 97 Ret 100

91 91 2) M (a, a) = pop для всех a V T ; 3) M ($, ) = accept; 4) M (X, a) = error на всех парах (X, a) ( {$}) ( { }), для которых значения элементов, остались не определёнными по пп. 1–3. Алгоритм 2.1: построение LL(1)-анализатора Ret 94

92 92 Пример 2.6: LL(1)-анализатор арифметических выражений Пример 2.6. Посредством алгоритма 2.1 построим LL(1)-анализатор для LL(1)-грамматики G = ({E, E, T, T, F}, {a, +, *, (, )}, P, E), где P = {(1) E TE, (2) E +TE, (3) E, (4) T FT, (5) T *FT, (6) T, (7) F (E), (8) F a}. Положим = ({a, +, *, (, )}, {E, E, T, T, F, a, +, *, (, )}, {1, 2, 3, 4, 5, 6, 7, 8}, M, E, $), где M дана в виде табл В ней пустые клетки соответствуют значениям error. Ret 128Ret 179

93 93 Таб Маг-ные символы А в а н ц е п о ч к и a+*() ETE, 1 E+TE, 2, 3 TFT, 4 T, 6 *FT, 5, 6 Fa, 8(E), 7 apop + * ( ) $ accept Ret 260 Ret 128

94 94 Пример 2.6: LL(1)-анализатор арифметических выражений 1-Предсказывающий алгоритм анализа, исполь- зующий эту управляющую таблицу, проанализи- ровал бы входную цепочку (a + a), совершив сле- дующую последовательность движений: ( (a + a), E$, ) ( (a + a), TE $, 1 ) ( ( a + a), FT E $, 14 ) ( (a + a), (E) T E $, 147 ) ( a + a), E) T E $, 147 ) ( a + a), TE ) T E $, 1471 ) ( a + a), F T E ) T E $, )

95 95 ( a + a), a T E ) T E $, ) ( +a), T E ) T E $, ) ( +a), _E ) T E $, ) ( +a), +TE ) T E $, ) ( a), TE ) T E $, ) ( a), F T E ) T E $, ) ( a), a T E ) T E $, ) ( ), T E )T E $, ) ( ), _E ) T E $, ) ( ), _) T E $, ) Пример 2.6: LL(1)-анализатор арифметических выражений

96 96 Пример 2.6: LL(1)-анализатор арифметических выражений (, T E $, ) (, _E $, ) (, _$, ). Итак, ((a + a)) = Нетрудно проверить, что E (a + a), где =

97 97 Теорема 2.4. Алгоритм 2.1 производит правильный 1-предсказывающий алгоритм анализа для любой LL(1)-грамматики. Доказательство. Пусть G = (V N, V T, P, S) LL(1)-грамматика, и 1-предсказы- вающий алгоритм анализа для грамматики G, построенный согласно алгоритму Требуется доказать, что S x тогда и только тогда, когда (x, S$, ) (, $, ). Ret

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

99 99 Если S x, то (xy, S$, ) (y, $, ) I. Докажем сначала, что если S x, где x * закрытая часть, а (V N V T ) * открытая часть данной сентенциальной формы x, то для любой цепочки y *, такой, что анализатор совершает переход (xy, S$, ) (y, $, ). Индукция по l =.

100 100 Если S x, то (xy, S$, ) (y, $, ) База. Пусть l = 1, т. е. = i, где i номер некоторого правила грамматики. Пусть S x и y * такая цепочка, что На единственном шаге этого вывода применялось правило вида S x, имею- щее номер i. Для всех согласно алгоритму M(S, a) = (x, i).

101 101 Если S x, то (xy, S$, ) (y, $, ) Посмотрим, как будет действовать ана- лизатор, начиная с конфигурации (xy, S$, ). Очевидно, что аванцепочка и, следовательно, M(S, u) = (x, i). Поэтому (xy, S$, ) (xy, x $, i) (y, $, i), причём последний переход реализуется посредством pop-движений. База доказана.

102 102 Если S x, то (xy, S$, ) (y, $, ) Индукционная гипотеза. Предположим, что утверждение выполняется для всех l n (n 1). Индукционный переход. Докажем утверж- дение для l = n + 1. Пусть имеется левосторонний вывод длиной n + 1: S x = x A x = x. Здесь = i, = A, = z, где z V T *, x = x z, A V N,, V *.

103 103 Если S x, то (xy, S$, ) (y, $, ) На последнем шаге вывода применялось правило A i-е правило из множества правил P. Согласно алгоритму 2.1 M(A, a) = (, i) (2.1) для всех Посмотрим, как будет действовать анализатор из своей начальной конфигура- ции (xy, S$, ) = (x zy, S$, ) = (x y, S$, ), где y = zy.

104 Применим к имеющемуся выводу S x индукционную гипотезу с цепочкой y, поскольку Как следствие получаем (xy, S$, ) = (xzy, S$, ) = = (xy, S$, ) (y,$,) = (zy, A $,). 104 Если S x, то (xy, S$, ) (y, $, )

105 105 Если S x, то (xy, S$, ) (y, $, ) Вычислим аванцепочку от zy: а для таких аванцепочек, как показывает равенство (2.1), M(A, u) = (, i). Поэтому следующее движение и завершающие pop-движения продолжают процесс таким образом: (zy, A $, ) (zy, $, i) = = (zy, z $, i) (y, $, ). Утверждение (I) доказано.

106 106 Если (xy, S$, ) (y, $, ), то S x II. Докажем теперь, что если анализатор совершает переход вида (xy, S$, ) (y, $, ) для любой цепочки y *, такой, что то S x, где x закрытая часть, а открытая часть данной сентенциальной формы x. Индукция по l =.

107 107 Если (xy, S$, ) (y, $, ), то S x База. Пусть l = 1, т. е. = i. Имеем (xy, S$, ) (y, $, i). Анализатор пишет на выходную ленту номер правила только при движении типа 1, а оно совершается только при наличии нетерми- нала на вершине магазина. Следовательно, это первое движение, и только оно, пишет номер i на выход.

108 108 Если (xy, S$, ) (y, $, ), то S x Поэтому фактически имеем (xy, S$, ) (xy, $, i) = = (xy, x $, i) (y, $, i), причём все остальные движения это pop- движения. Очевидно, что только при = x достижима последняя конфигурация. Первое движение обеспечивается элементом таблицы M(S, u) = (, i), где а это подразумевает существование правила S = x под номером i. А тогда S x.

109 109 Если (xy, S$, ) (y, $, ), то S x Индукционная гипотеза. Предположим, что утверждение выполняется для всех l n (n 1). Индукционный переход. Докажем утверж- дение для l = n + 1. Пусть (xy, S$, ) = (x y, S$, ) (y, $, ) = (y, A $, ) (y, $, i) = (zy, z $, ) (y, $, ), где = i, = n, xy = x y, = A.

110 110 Если (xy, S$, ) (y, $, ), то S x Здесь первый переход включает n движений типа 1, а второй сам является движением типа 1. Завершающие pop-движения показывают, что y = zy, = z ; т. к. xy = x y = x zy, то x = x z. Последнее движение типа 1 было выпол- нено благодаря элементу M(A, u ) = (, i) для что предполагает суще- ствование правила A под номером i.

111 111 Если (xy, S$, ) (y, $, ), то S x Одновременно можно воспользоваться индукционной гипотезой в применении к переходу (x y, S$, ) (y, $, ), поскольку и получить как следствие S x = x A x = x z = x. Утверждение II доказано.

112 112 Если (xy, S$, ) (y, $, ), то S x Из утверждений I и II при y = = заключаем, что S x тогда и только тогда, когда (x, S$, ) (, $, ). А это и означает, что 1-предсказывающий алгоритм анализа, построенный согласно алгоритму 2.1, является правильным для LL(1)-грамматики G. Теорема доказана.

113 113 Замечание 2.1. Алгоритм 2.1 пригоден для построения анализаторов для LL(k)- грамматик и при k > 1, если только они сильные. При его применении к сильным LL(k)-грамматикам всюду, где используется параметр 1, следует использовать значение k. сильные Прежде, чем перейти к обсуждению LL- анализа при k > 1, введём в рассмотрение ещё одну полезную операцию над языками.

114 114 Определение Пусть некоторый алфавит, и L 1, L 2 подмножества *. Положим Операция k подобна инфиксной опера- ции Пример 2.7. Пусть L 1 = {, abb} и L 2 = {b, bab}. Тогда L 1 2 L 2 = {b, ba, ab}. Операция

115 115 Лемма 2.1. Для любой cfg G = (V N, V T, P, S) и любых цепочек V * имеет место тож- дество Доказательство. I. Пусть Докажем, что тогда Обозначим Из того, что следует, что существуют выводы u, v, такие что Ret 175 Ret 217 Ret 219

116 116 Последние два вывода означают, что Учитывая определение операции k, заключаем, что Остается убедиться в том, что (*)(*)

117 117 Так как а то u = xu и v = yv при некоторых u, v V T *, причём если x < k, то u =, и если y < k, то v =. Итак, имеем uv = xuyv. Если x = k, то Если x < k, то u = и (I.1)

118 118 причём, если y < k, то v = и тогда если же y = k, то Итак, в любом случае из (I.1), (I.2), (I.3) с учётом ( * ) следует (I.2) (I.3)

119 119 II. Пусть Докажем, что тогда Согласно определению операции k суще- ствуют цепочки Кроме того, согласно определению функции имеем xu, yv при некоторых u, v V T * и

120 120 Остается убедиться в том, что Если x = k, то Если x < k, то u = и причём, если y k, то v = и а при y = k от v ничего не зависит и (II.1) (II.2) (II.3)

121 121 Следовательно, учитывая (II.1), (II.2), (II.3), заключаем, что Из рассуждений I и II следует утверждение леммы. Что и требовалось.

122 122 § 2.5. Анализ в LL(k)-грамматиках В общем случае анализа в LL(k)- грамматиках непосредственно по нетерми- налу и аванцепочке невозможно однозначно определить правило для построения очередной сентенциальной формы. Рассмотрим, например, несильную LL(2)- грамматику из примера 2.3 :2.3 S aAaa bAba; A b.

123 123 Анализ в LL(k)-грамматиках Согласно алгоритму 2.1 для замены нетерминала A в выводе S wA wx следует применять правило A, если аванцепочка принадлежит множеству Очевидно, что в нашем примере

124 124 Анализ в LL(k)-грамматиках Получается так, что следует применять правило A b, если аванцепочка из или правило A, если аванцепочка из множества Если аванцепочка равна ba, то существует неопределённость в выборе правила для замены нетерминала A.

125 125 Анализ в LL(k)-грамматиках Её можно разрешить, если для опреде- ления правила, по которому следует раскрывать нетерминал, помимо нетерми- нала и аванцепочки, использовать ещё один параметр: T A, L так называемую LL(k)-таблицу, ассоциированную с двумя индексами: A V N и, где множество L вычисляется с учётом следующих соображений.

126 126 Анализ в LL(k)-грамматиках Пусть имеется вывод S wA в некоторой LL(k)-грамматике. Вспоминая теорему 2.1, нетрудно сообразить, что критерием выбора правила A для продолжения этого вывода может служить факт принадлеж- ности текущей аванцепочки множеству2.1 где

127 127 Это множество L и есть тот второй индекс таблицы T A, L, о котором идёт речь. По аванцепочке таблица T A, L выдаёт пра- вило, которое следует использовать для замены нетерминала A в текущей лево- сентенциальной форме. Ясно, что для любой cfg число таких LL(k)- таблиц конечно, и все таблицы, необходимые для анализа любой цепочки в данной грамматике, могут быть построены заблаговременно. Анализ в LL(k)-грамматиках

128 128 Они используются k-предсказывающим алгоритмом анализа в магазинных цепочках взамен нетерминалов (см. Пример 2.8 далее).Пример 2.8 Теперь дадим определение LL(k)-таблиц и способ построения множества LL(k)-таблиц, необходимых и достаточных для анализа в данной LL(k)-грамматике (см. алгоритм 2.2 далее).2.2 Анализ в LL(k)-грамматиках

129 Определение Пусть G = (V N, V T, P, S) cfg. Для каждого A V N и определим T A, L LL(k)-таблицу, ассоциированную с A и L, как функцию, которая по данной аван- цепочке выдает: 1) либо значение error, 2) либо A-правило и конечный список под- множеств цепочек из, 3) либо значение undefied. 129 Анализ в LL(k)-грамматиках

130 130 LL(k)-таблицы 1) T A, L (u) = error, если не существует ни одного правила вида A P, такого, что 2) T A, L (u) = (A, Y 1, Y 2,…, Y m ), если A единственное правило из P, такое, что при этом, если = x 0 B 1 x 1 B 2 … B m x m, B i V N, x j V T *, то i = 1, 2, …, m; j = 0, 1, …, m; m 0;

131 131 LL(k)-таблицы Множество терминальных цепочек Y i называется множеством локальных правых контекстов для B i. В частности, если m = 0, то T A, L (u) = (A, ). 3) T A, L (u) = undefined, если существует два или более A-правил: A 1 | 2 | … | n, таких, что для 1 i n, n 2. Случай 3 для LL(k)-грамматик не актуален.

132 132 LL(k)-таблицы Пусть мы имеем левосторонний вывод в LL(k)-грамматике: S wA wx. Как было сказано в начале этого пара- графа, именно таблица T A, L, где сообщает, что следующую за wA сентен- циальную форму следует получать при по- мощи правила A, если для окажется, что T A, L (u) = (A, Y 1,Y 2,…, Y m ).

133 133 Если = x 0 B 1 x 1 B 2 …B m x m, то следующая за wA сентенциальная форма будет w = wx 0 B 1 x 1 B 2 … B m x m, и в свое время раскрытием B 1 будет руководить LL(k)-таблица T B 1,Y 1, раскрытием B 2 будет руководить LL(k)-таблица T B 2,Y 2, …, а раскрытием B m LL(k)-таблица T B m,Y m. LL(k)-таблицы S wA w wx, T A, L (u) = (A, Y 1,Y 2,…, Y m ), = x 0 B 1 x 1 B 2 …B m x m, *)

134 134 Пример 2.8. Рассмотрим уже не раз обсуждавшуюся несильную LL(2)-грамматику с правилами S aAaa bAba; A b и построим все LL(2)-таблицы, необходимые для анализа в этой грамматике. Начнем с таблицы T S,{ }. Именно она диктует выбор первого правила для раскрытия нетерминала S. LL(k)-таблицы

135 135 Используя правило S aAaa, вычисляем Используя правило S bAba, вычисляем Соответственно определяем LL(2)-таблицу: T 0 = T S,{ } (табл. 2.3). Пример 2.8

136 136 Элементы LL(2)-таблиц ПравилоМн-во лок. контекстов aa S aAaa {aa} ab S aAaa {aa} bb S bAba {ba} ba A b aa A bb A b ba A u Таблица 2.3 Пример 2.8 Ret 146 T 0 = T S,{ } T 1 = T A,{aa} T 2 = T A,{ba} LL(2)-табл.

137 137 Глядя на T 0, легко определить, что потребуются ещё таблицы T 1 = T A,{aa} и T 2 = T A,{ba}. Таблица T 1 получается с учётом того, что для правила A b получаем а для правила A Пример 2.8

138 138 Таблица T 2 получается с учетом того, что для правила A b имеем а для правила A В правых частях правил для нетерминала A нет ни одного нетерминала. Поэтому в двух последних таблицах множества локальных правых контекстов пусты. Пример 2.8

139 139 При построении этих LL(2)-таблиц мы придерживались простой дисциплины: начинали с построения начальной таблицы T S,{ }, а затем в каждой из уже построенных LL(2)-таблиц использовали значения эле- ментов, чтобы определить пары индексов других необходимых таблиц каждое вхождение нетерминала в правую часть правила сочеталось с соответствующим локальным множеством. Пример 2.8

140 140 LL(k)-таблицы Этот порядок построения LL(k)-таблиц фиксируется в следующем описании алгоритма. Алгоритм 2.2: построение множества LL(k)- таблиц, необходимых и достаточных для анализа цепочек в данной LL(k)-грамматике. Вход: G = (V N, V T, P, S) LL(k)-грамматика. Выход: множество LL(k)-таблиц, необ- ходимых и достаточных для анализа цепочек в грамматике G.

141 141 LL(k)-таблицы Метод. 1. Построить T 0 = T S,{ } и = {T 0 }. 2. Если T A, L, и для имеет место T A, L (u) = (A x 0 B 1 x 1 B 2 …B m x m, Y 1,Y 2,…, Y m ), то к множеству таблиц добавить те таб- лицы из множества {T B i,Y i | i = 1, 2, …, m}, которых ещё нет в.

142 142 LL(k)-таблицы 3. Так как для любой данной cfg G существует только конечное число таких таблиц (число нетерминалов конечно, число подмножеств тоже конечно), то процесс пополнения множества закончит- ся за конечное время. Фактически же для анализа требуются не все возможные LL(k)-таблицы, которые можно построить для грамматики G, а только те, которые определяются описанным алго- ритмом.

143 143 Построение k-предсказывающего алгоритма анализа Алгоритм 2.3: построение k-предсказываю- щего алгоритма анализа. Вход: G = (V N, V T, P, S) LL(k)-грамматика. Выход: правильный k-предсказыва- ющий алгоритм анализа для G. Метод. 1. Построим множество необходимых LL(k)-таблиц для грамматики G. 2. Положим = (, {$},, M, T 0, $), где = V T, = V T, = {1, 2, …, #P}, T 0 = T S,{ }. Ret 148 Ret 155 Ret 169

144 Управляющую таблицу M определим на множестве ( {$}) * k так: 3.1. M (T A, L, u) = (x 0 T B 1,Y 1 x 1 …T B m,Y m x m, i), если T A, L (u) = (A x 0 B 1 x 1 …B m x m, Y 1,…, Y m ) и A x 0 B 1 x 1 …B m x m является i-м правилом M (a, av) = pop для всех a, v * k– M ($, ) = accept M (X, u) = error для всех пар (X, u) ( {$}) * k, для которых значения элементов остались не определёнными по пп. 3.1–3.3. Построение k-предсказывающего алгоритма анализа Ret 152Ret 155

145 145 Пример 2.9. Рассмотрим ещё раз LL(2)- грамматику, обсуждавшуюся в примере 2.3, с правилами 1) S aAaa, 2) S bAba, 3) A b, 4) A. Используя уже построенные для неё LL(2)-таблицы легко собрать управляющую таблицу для этой грамматики см. табл LL(2)-таблицы Ret 251 Построение k-предсказывающего алгоритма анализа

146 146 Маг. сим. А в а н ц е п о ч к и aaabbabbab T0T0 aT 1 aa,1 bT 2 ba, 2 T1T1, 4 b, 3 T2T2, 4 b, 3 apop b $ accept Таблица 2.4 Пример 2.9 Ret 253 Ret 136

147 147 Пример 2.9 Например, на входной цепочке bba этот 2- предсказывающий алгоритм анализа проходит следующие конфигурации: (bba, T 0 $, ) (bba, bT 2 ba$, 2) (ba, T 2 ba$, 2) (ba, ba$, 24) (a, a$, 24) (, $, 24). В то же время, посредством правил 2 и 4, получаем S bAba bba. pop

148 148 Теорема 2.5. Алгоритм 2.3 производит правильный k-предсказывающий алгоритм анализа для любой LL(k)-грамматики. Доказательство аналогично доказатель- ству предыдущей теоремы Пусть G = (V N, V T, P, S) LL(k)-грам- матика и k-предсказывающий алгоритм анализа для грамматики G, построенный посредством алгоритма Требуется доказать, что S x тогда и только тогда, когда (x,T 0 $, ) (, $, ). Ret 167

149 149 По индукции докажем вспомогательное утверждение: анализатор в своем магазине воспроизводит последовательность образов открытых частей сентенциальных форм левостороннего вывода входной цепочки, если они выводимы в данной грамматике G, причём если последовательность номеров правил, участвующих в их выводе, то образуется на выходе анализатора. Если S x, то (xy, T 0 $, ) (y, $, )

150 150 Область определения h легко расширить до *, и мы будем в дальнейшем пред- полагать, что это сделано. Связь между открытыми частями сентенциальных форм и их образами в магазине LL(k)-анализатора описывается следующим гомоморфизмом: если Если S x, то (xy, T 0 $, ) (y, $, )

151 I. Докажем сначала, что если S x, где x закрытая, а открытая часть данной сентенциальной формы x, то для любой цепочки y *, такой, что анализатор совершает переход Попросту говоря, если в заменить LL(k)-таблицы на нетерминалы, с которыми они ассоциированы, то получится. где 151 Если S x, то (xy, T 0 $, ) (y, $, )

152 152 Индукция по l =. База. Пусть l = 1, т. е. = i, где i номер некоторого правила грамматики. Пусть S x и y *, такая, что На единственном шаге этого вывода при- меняется правило вида S x, имеющее номер i. Согласно п. 3.1 алгоритма для всех Напомним, что T 0 = T S,{ }. Если S x, то (xy, T 0 $, ) (y, $, )

153 153 Посмотрим, как будет действовать LL(k)- анализатор, начиная с конфигурации (xy, T 0 $, ). Очевидно, что аванцепочка и, следовательно, Поэтому причём последний переход происходит посредством pop-движений. База доказана. Если S x, то (xy, T 0 $, ) (y, $, )

154 154 Индукционная гипотеза. Предположим, что утверждение выполняется для всех l n (n 1). Индукционный переход. Докажем утверж- дение для l = n + 1. Пусть имеется левосторонний вывод длиной n + 1: S x = xA x = x. Здесь =i, = A, = z, где z V T *, x = xz, A V N,, V *. На последнем шаге вывода применялось i-е правило A из множества P. Если S x, то (xy, T 0 $, ) (y, $, )

155 155 Согласно п. 3.1 алгоритма для всех где Посмотрим, как будет действовать ана- лизатор из своей начальной конфигурации (xy, T 0 $, ) = (xzy, T 0 $, ) = (xy, T 0 $, ), где y = zy. Применим к имеющемуся выводу S x индукционную гипотезу с цепочкой y = zy, поскольку (I.1) Если S x, то (xy, T 0 $, ) (y, $, )

156 156 Как следствие получаем (xy, T 0 $, ) = (xy, T 0 $, ) (y, $,) = (zy, T A, L $,). Вычислим аванцепочку (I.2) а для таких аванцепочек, как показывает (I.1), Если S x, то (xy, T 0 $, ) (y, $, )

157 157 Поэтому следующее движение типа 1 и завершающие pop-движения продолжают процесс (I.2) следующим образом: (zy, T A, L $,) (zy, $,i) = = (zy, z $,i) (y, $, ). Утверждение I доказано. Если S x, то (xy, T 0 $, ) (y, $, )

158 158 II. Докажем теперь, что если LL(k)-анализатор совершает переход вида (xy, T 0 $, ) (y, $, ) для любой цепочки y *, такой, что где то S x, где x закрытая, а открытая часть данной сентенциальной формы. Если (xy, T 0 $, ) (y, $, ), то S x

159 159 Индукция по l =. База. Пусть l = 1, т. е. = i, и (xy, T 0 $, ) (y, $, i). Анализатор пишет на выходную ленту номер правила только, если на вершине магазина LL(k)-таблица. Следовательно, в рассматриваемой исходной конфигурации это первое движение, и только оно пишет номер i на выход. Поэтому фактически имеем (xy, T 0 $, ) (xy, $, i) (y, $, i), причём все остальные движения это pop- движения. Если (xy, T 0 $, ) (y, $, ), то S x

160 160 Очевидно, что завершающая конфигура- ция достижима только посредством одних только pop-движений, если = x. Первое движение обеспечивалось эле- ментом таблицы M(T 0, u) = (, i), где а это подразумевает суще- ствование правила S P, в котором = x, под номером i. Тогда S x, и база доказана. Если (xy, T 0 $, ) (y, $, ), то S x

161 161 Индукционная гипотеза. Предположим, что утверждение выполняется для всех l n (n 1). Индукционный переход. Докажем утверж- дение для l = n + 1. Пусть (xy, T 0 $, ) = (xy, T 0 $, ) (y, $,) = = (y, T A, L $,) (y, $,i) (y, $, ), где =i, = n. Завершающие pop-движения предполагают, что y = zy, = z. Если (xy, T 0 $, ) (y, $, ), то S x

162 162 Кроме того, мы имеем xy = xy = xzy, откуда x = xz. Так как = T A, L, то последнее движе- ние типа 1 было выполнено благодаря эле- менту M (T A, L, u) = (, i) для что предполагает существование правила A под номером i. Если (xy, T 0 $, ) (y, $, ), то S x

163 163 Воспользовавшись индукционной гипоте- зой в применении к переходу (xy, T 0 $, ) (y, $,), поскольку получаем как следствие S x = xA x = xz = x. Здесь,,, гомоморфные образы соответственно. Утверждение II доказано. Если (xy, T 0 $, ) (y, $, ), то S x

164 164 Из рассуждений I и II при y = = заключаем, что S x тогда и только тогда, когда (x, T 0 $, ) (, $, ). А это и означает, что k-предсказывающий алгоритм анализа, построенный согласно алгоритму 2.3, явля- ется правильным для LL(k)-грамматики G. Что и требовалось доказать. Если (xy, T 0 $, ) (y, $, ), то S x

165 Теорема 2.6. Число шагов, выполняемых k-предсказывающим алгоритмом анализа, линейно зависит от длины анализируемой цепочки. Доказательство. Поскольку k-предсказыва- ющий алгоритм анализа применим только к LL(k)-грамматикам, а они не могут быть леворекурсивными (теорема 2.3), то макси- мальное число шагов в любом левосторон- нем выводе вида меньше, чем неко- торая константа c, зависящая от грамматики.теорема Линейное время алгоритма анализа

166 166 Линейное время алгоритма анализа Во всяком случае, если бы существовал вывод такого вида, длина которого была бы больше числа нетерминалов грамматики то какие-то два нетерминала (B i и B j при i j) неизбежно оказались бы одинаковыми. Другими словами, мы имели бы вывод вида что означало бы леворекурсивность грам- матики. при

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

168 168 Пусть цепочка x L(G), где G LL(k)- грамматика и n = x. Разбирая цепочку x, k-предсказывающий алгоритм анализа, построенный для грамматики G, совершает ровно n pop- движений и не более c движений типа 1 перед каждым из них. Следовательно, общее число движений N n + c n = O(n). Что и требовалось доказать. Линейное время алгоритма анализа

169 169 § 2.6. Тестирование LL(k)-грамматик Пусть имеется cfg G. Алгоритмы построения управляющих таблиц LL(k)- анализаторов 2.1 и 2.3 достигают успеха только если G LL(k)-грамматика Поэтому естественно поинтересоваться, является ли данная грамматика G LL(k)- грамматикой для данного значения k. Для ответа на этот вопрос можно восполь- зоваться теоремой 2.1, а для k = 1 и силь- ных LL(k)-грамматик также и теоремой 2.2 при данном значении k.теоремой 2.1теоремой 2.2

170 170 Напомним, что в общем случае cfg G = (V N, V T, P, S) не является LL(k)-грам- матикой тогда и только тогда, когда существуют левосторонний вывод вида S wA и пара различных A-правил A и A P ( ), для которых где Тестирование LL(k)-грамматик

171 171 Тестирование LL(k)-грамматик Для описания алгоритма, разрешающего этот вопрос, введем вспомогательную функцию. Определение Пусть G = (V N, V T, P, S) cfg и A V N. Определим Одно L множество локальных правых контекстов в одном выводе, в котором встречается A. А таких выводов может быть несколько и каждый даёт своё L. Так что есть множество множеств терминальных цепочек не длиннее k.

172 172 Алгоритм 2.4: тестирование LL(k)-грамматик. Вход: G = (V N, V T, P, S) контекстно- свободная грамматика. Выход: да, если G LL(k)-грамматика; нет в противном случае. Метод. 1. Для каждого нетерминала A, для которого существуют две или более альтернативы, вычисляется (A). Тестирование LL(k)-грамматик

173 173 Тестирование LL(k)-грамматик 2. Пусть A и A P ( ) два различных A-правила. Для каждого L (A) вычисляется Если f (L), то алгоритм завершается с результатом нет. Если f (L) = для всех L (A), то шаг 2 повторяется для всех остальных пар A- правил.

174 174 Тестирование LL(k)-грамматик 3. Повторять шаги 1 и 2 для всех нетерминалов из множества V N. 4. Завершить алгоритм с результатом да. Этот шаг выполняется, если были рассмотрены все нетерминалы и алгоритм не завершился на шаге 2. Поскольку здесь используется функция то необходим алгоритм её вычисления.

175 175 § 2.7. Вычисление функции Алгоритм 2.5: вычисление Вход: G = (V N, V T, P, S) cfg и = X 1 X 2 … X n, X i V (i =1, 2,…, n; n 0). Выход: Метод. Согласно лемме 2.1лемме 2.1 так что задача сводится к вычислению для X V. Ret 177Ret 180 Ret 184

176 176 Вычисление функции Если X V T { }, то Остается найти способ вычисления Мы будем использовать метод последовательных приближений и строить последовательности множеств F i (X) для всех X V N V T, i = 0, 1, 2,.... для X V N.

177 F i (a) = {a} для всех a V T и i F 0 (A) = {x A x P, V, где x = k, либо x < k и = }. 3. Предположим, что F 0 (A), F 1 (A), …, F i – 1 (A) уже построены для всех A V N. Тогда F i (A) = F i – 1 (A) {x A Y 1 Y 2 …Y m P, x F i – 1 (Y 1 ) k F i – 1 (Y 2 ) k … k F i – 1 (Y m )}. Ret 180 Ret 186 Ret 188 Ret 192 Ret 195 Вычисление функции

178 Так как F i–1 (A) F i (A) для всех A V N и i > 0, то шаг 3 требуется повторять до тех пор, пока при некотором i = j не окажется F j (A) = F j+1 (A) для всех A V N. Очевидно, что тогда F j (A) = F j+1 (A) = F j+2 (A) = …. 5. Остается только положить Вычисление функции

179 179 Пример Рассмотрим ещё раз LL(1)- грамматику из примера 2.6:2.6 G = ({E, E, T, T, F}, {a, +, *, (, )}, P, E), где P = {(1) E TE, (2) E +TE, (3) E, (4) T FT, (5) T *FT, (6) T, (7) F (E), (8) F a}, и построим функцию для всех A {E, E, T, T, F}. Пример вычисления функции

180 180 Прежде всего согласно шагу 2 алгоритма 2.5 получаем2.5 F 0 (E) = F 0 (T) =, F 0 (E ) = {+, }, F 0 (T ) = {*, }, F 0 (F) = {(, a}. Далее шаг 3 даёт F 1 (E) = F 0 (T) 1 F 0 (E ) F 0 (E) = = 1 {+, } = = F 0 (E); F 1 (E )=F 0 (+) 1 F 0 (T) 1 F 0 (E ) F 0 (E )= = {+} 1 1 {+, } { } {+, } = = { } {+, } = {+, } = F 0 (E ); Пример вычисления функции

181 181 F 1 (T) = F 0 (F) 1 F 0 (T ) F 0 (T) = = {(, a} 1 {*, } = {(, a} F 0 (T); F 1 (T )=F 0 (*) 1 F 0 (F) 1 F 0 (T ) F 0 { } F 0 (T )= = {*} 1 {(, a} 1 {*, } { } {*, } = = {*} { } {*, } = {*, } = F 0 (T ); F 1 (F) = F 0 (() 1 F 0 (E) 1 F 0 ( )) F 0 (F) = = {(} 1 1 {)} {(, a} = {(, a} = F 0 (F). Пример вычисления функции

182 182 Поскольку процесс не сошелся для всех нетерминалов, необходимо повторить шаг 3, что дает F 2 (E) = F 1 (T) 1 F 1 (E ) F 1 (E) = = {(, a} 1 {+, } = {(, a} F 1 (E); F 2 (E )=F 1 (+) 1 F 1 (T) 1 F 1 (E ) F 1 ( ) F 1 (E ) = = {+} 1 {(, a} 1 {+, } { } {+, } = ={+} { } {+, } = {+, } = F 1 (E ); F 2 (T) = F 1 (F) 1 F 1 (T ) F 1 (T) = = {(, a} 1 {*, } {(, a} = = {(, a} {(, a} = {(, a} = F 1 (T); Пример вычисления функции

183 183 F 2 (T )=F 1 (*) 1 F 1 (F) 1 F 1 (T ) F 1 ( ) F 1 (T ) = = {*} 1 {(, a} 1 {*, } { } {*, } = = {*} { } {*, } = {*, } = F 1 (T ); F 2 (F) = F 1 ( ( ) 1 F 1 (E) 1 F 1 ( ) ) F 1 (F) = = {(} 1 {(, a} 1 {)} {(, a} = = {(} {(, a} = {(, a} = F 1 (F). Так как F 2 (E) F 1 (E) придется ещё раз проделать шаг 3, что даёт, наконец, Пример вычисления функции

184 184 Пример вычисления функции F 3 (E) = {(, a}= F 2 (E); F 3 (E )= {+, }= F 2 (E ); F 3 (T) = {(, a}= F 2 (T); F 3 (T ) = {*, }= F 2 (T ); F 3 (F) = {(, a}= F 2 (F). Таким образом, окончательно получаем:

185 185 Теорема 2.7. Пусть G = (V N, V T, P, S) cfg. Алгоритм 2.5 правильно вычисляет функцию для любой цепочки и k Доказательство. Фактически достаточно показать, что если F i (A) = F j (A) при i > j для всех A V N. Не нарушая общности рассуждений, будем предполагать, что G приведённая грамматика.

186 186 I. Покажем сначала, что Пусть x F l (A) при l j. Индукцией по l покажем, что тогда База. Пусть l = 0 и x F 0 (A). Тогда согласно шагу 2 алгоритма 2.5 существует правило вида A x P, где x и либо x = k, либо x < k и =.2 Следовательно, A x xy, где x = k и y, либо x < k и y =. Согласно определению функции, заключаем, что База доказана.

187 187 Индукционная гипотеза. Предположим, что аналогичное утверждение выполняется для всех l n (0 n j).

188 188 Индукционный переход. Докажем, что тогда аналогичное утверждение верно для l = n + 1. Пусть x F n+1 (A). Согласно алгоритму 2.5 (см. шаг 3)3 либо x F n (A) и тогда в соответствии с индук- ционным предположением либо существует правило вида A Y 1 Y 2 …Y m P и x F n (Y 1 ) k F n (Y 2 ) k … k F n (Y m ).

189 189 Если Y p V N (1 p m), то в соответствии с индукционной гипотезой Если же Y p V T (1 p m), то согласно определению множеств F n и функции заключаем, что Итак, в любом случае справедливо вложение для Y p V N V T (1 p m).

190 190 Тогда поскольку A Y 1 Y 2 …Y m P. Утверждение I доказано.

191 191 II. Покажем теперь, что Пусть По определению этой функции существует вывод A xy, где x = k и y V T *, либо x < k и y =. Индукцией по длине вывода l покажем, что если благодаря существованию такого вывода, то x F j (A).

192 192 База. Пусть l = 1. Имеем A xy, где x = k и y V T *, либо x < k и y =. Тогда существует правило A xy P и согласно шагу 2 алгоритма 2.52 x F 0 (A) F j (A). База доказана. Индукционная гипотеза. Предположим, что аналогичное утверждение выполняется для всех l n (n 1).

193 193 Индукционный переход. Докажем, что тогда аналогичное утверждение верно для l = n + 1. Пусть A Y 1 Y 2 …Y m y 1 y 2 …y m вывод длиной n + 1, где Y p y p, Y p V, y p, n p n, p = 1, 2, …, m, и по определению функции заключаем, что

194 194 Последнее вложение множеств имеет место в соответствии со следствием из индукционной гипотезы, применённой к выводам Y p y p, n p n, p = 1, 2, …, m, с учётом того, что при n p = 0 имеем Y p = y p. Итак,

195 195 Итак, существует правило A Y 1 Y 2 …Y m P и x F n (Y 1 ) k F n (Y 2 ) k … k F n (Y m ). Согласно шагу 3 алгоритма 2.5 заключаем, что x F n+1 (A) F j (A).3 Утверждение II доказано. Из рассуждений I и II следует равенство что равносильно утверждению теоремы.

196 196 § 2.8. Вычисление функции (A) Обратимся теперь к описанию алгоритма вычисления функции (A). Алгоритм 2.6: вычисление (A) для A V N. Вход: G = (V N, V T, P, S) cfg. Выход: (A) для всех A V N. Метод. По определению и Ret 214

197 197 Введём в рассмотрение ещё одну вспомо- гательную функцию, определяемую для пары нетерминалов следующим образом: (A, B) = {L V T *k A wB, w V T * и Очевидно, что (A) = (S, A). Таким образом, достаточно дать алгоритм вычисления функции (A, B) для любых A, B V N. Вычисление функции (A) Ret 215Ret 219 Ret 222

198 198 Мы будем вычислять (A, B) методом по- следовательных приближений, параллельно выстраивая последовательности множеств i (A, B) для всех возможных пар (A, B) V N V N следующим образом: Вычисление функции (A)

199 199 Вычисление функции (A) 2. Пусть вычислены для всех пар нетерминалов. Положим Ret 217 Ret 220 Ret 224 Ret 215

200 200 Вычисление функции (A) 3. Повторять шаг 2 до тех пор, пока при некотором i = j не окажется, что j+1 (A, B) = j (A, B) для всех (A, B) V N V N. Такое j существует, потому что 0 (A, B) 1 (A, B) … 4. Полагаем (A, B) = j (A, B). 5. Наконец, (A) = (S, A). Если окажется, в частности, что { } (S, S), то (S) = (S, S) {{ }}.

201 201 Пример Пусть G = ({S, A}, {a, b}, P, S), где P = {S AS, S, A aA, A b}. Вычислим функции (S) и (A) при k = 1. Сначала получаем Затем построим последовательности i (X, Y), где (X, Y) V N V N (табл. 2.5). За два шага получаем (S) = {{ }}, (A) = {{, a, b}}. и

202 202 Таблица 2.5 i i = 0i = 1 (S, S) {{ }} (S, A) {{, a, b}} (A, S) (A, A) {{ }}

203 203 Поясним построение этих последова- тельностей. Шаг 1. Построение 0 (S, S): имеем правило для S AS, в котором нетерминал S встречается слева и справа. Вычисляется поскольку правый контекст для S в правой части этого правила есть. Другого правила для S, в котором справа встречается нетерминал S, не существует. Поэтому 0 (S, S) = {{ }}. Пример 2.1: вычисление функции при k = 1

204 204 Построение 0 (S, A): существует только одно правило с нетерминалом S в левой части и нетерминалом A в правой. Это правило S AS. Вычисляется от правого контекста A, т. е. Соответственно 0 (S, A) = {{, a, b}}. Построение 0 (A, S): не существует ни одного правила с нетерминалом A в левой части и нетерминалом S в правой. Поэтому 0 (A, S) =. Пример 2.1: вычисление функции при k = 1

205 205 Построение 0 (A, A): имеется только одно продуктивное правило A aA, дающее по пустому правому контексту A значение 0 (A, A) = {{ }}. Пример 2.1: вычисление функции при k = 1

206 206 Шаг 2. Построение 1 (S, S): имеем правило для S AS, в котором справа два нетерминала два источника для попол- нения множества 0 (S, S) новыми членами. Именно: можно вычислить новый член по первому вхождению нетерминала в правую часть этого правила это A и по второму вхождению нетерминала это S:, где L 0 (A, S) =. Ясно, что из этого источника никакого пополнения не получается. Пример 2.1: вычисление функции при k = 1

207 207 Пример 2.1: вычисление функции при k = 1 Попробуем воспользоваться другим источником для получения нового члена множества 1 (S, S):, где L 0 (S,S) = {{ }}. Существует единственное множество L = { }, с помощью которого вычисляется новый член но такое множество уже есть в 1 (S, S) понаследству от 0 (S, S).

208 208 Рис Пример 2.1: вычисление функции при k = 1 S AS L 0 (A, S) L 0 (S, S) На рис. 2.2 представлена схема соответствия параметров, используемых при вычислении множества 1 (S, S). Отправная точка A Отправная точка S Общая цель S

209 209 Пример 2.1: вычисление функции при k = 1 Аналогичным образом пополняются множества 0 (S, A), 0 (A, S) и 0 (A, A). Однако добавить к этим множествам новые члены, как нетрудно проверить, не удаётся.

210 210 Пример 2.1: вычисление функции при k = 1 Теперь все готово для тестирования данной cfg G на предмет её принадлежности к классу LL(1)-грамматик. Имеем два альтернативных правила для нетерминала S: S AS, S. Требуется вычислить где L (S) = {{ }}.

211 211 Пример 2.1: вычисление функции при k = 1 Получаем и тогда (I)

212 212 Имеем также два альтернативных правила для нетерминала A: A aA, A b. Требуется вычислить где L (A) = {{, a, b}}. Получаем и тогда Пример 2.1: вычисление функции при k = 1 (II)

213 213 Так как оба пересечения (I) и (II) пусты, то данная грамматика G действительно LL(1)-грамматика. Пример 2.1: вычисление функции при k = 1

214 214 Теорема 2.8. Пусть G = (V N, V T, P, S) cfg. Алгоритм 2.6 правильно вычисляет функцию (A) для любого нетерминала A V N и k Доказательство. Достаточно показать, что при i > j для всех A, B V N. Не нарушая общности рассуждений, будем предполагать, что G приведённая грамматика. если

215 215 I. Покажем сначала, что Индукцией по i покажем, что для любого i 0. База. Пусть i = 0, т. е. Согласно шагу 1 алгоритма 2.6 существует правило1 A B P, где, V *, Поскольку грамматика G приведённая, то существует вывод, в частности левосторон- ний, вида A wB. Следовательно, по определениюопределению База доказана. (A, B)

216 216 Индукционная гипотеза. Предположим, что аналогичное утверждение выполняется для всех i n (0 n j).

217 217 Индукционный переход. Докажем, что тогда аналогичное утверждение верно для i = n + 1. Пусть Согласно шагу 2 алгоритма 2.6:2 либо и тогда в соответствии с индукционной гипотезой либо существуют правило A X 1 X 2 …X m P, где и такие что (I.1)

218 218 Согласно индукционной гипотезе, при- ненной к, можем утверждать, что и, в следствии (I.2), существует вывод вида X p w p B, и Тогда можно построить левосторонний вывод: A X 1 X 2 … X p–1 X p X p+1 … X m w 1 w 2 …w p–1 X p X p+1 … X m w 1 w 2 …w p–1 w p B X p+1 …X m. (I.3) (I.2)

219 219 Согласно определению функциифункции Кроме того, по лемме Итак, Что и требовалось. (cм. I.1 4). (I.4)

220 220 II. Покажем теперь, что Пусть Это значит, что суще- ствует левосторонний вывод A wB, w V T * и Индукцией по длине вывода l покажем, что База. Пусть l = 1, т. е. A wB, w V T * и Тогда существует правило A wB и согласно шагу 1 алгоритма 2.61 База доказана.

221 221 Индукционная гипотеза. Предположим, что аналогичное утверждение выполняется для всех l n (n 1). Индукционный переход. Докажем, что тогда аналогичное утверждение верно для l = n + 1.

222 222 Пусть L (A, B) благодаря тому, что (см. определение (A, B)):определение A X 1 X 2 … X p–1 X p X p+1 … X m w 1 w 2 …w p–1 X p X p+1 … X m w 1 w 2 …w p–1 w p B X p+1 … X m = wB вывод длинны n + 1, где w = w 1 w 2 …w p, X p w p B P, = X p+1 … X m, и где

223 223 Одновременно согласно шагу 2 алгорит- ма 2.6 из существования вывода2 X p w p B, l p n, следует по определению функции, что а по индукционному предположению, что и, следовательно,

224 224 Кроме того, имеется правило A X 1 X 2 … X p X p+1 … X m P. Согласно шагу 2 алгоритма 2.62 где есть элемент Но Итак, Из рассуждений I и II следует равенство и утверждение теоремы.

225 225 § 2.9. Алгоритм вычисления функции Сопоставляя определения функций и где A V N, нетрудно сообразить, что

226 226 Это равенство ключ к модификации алгоритма вычисления (A), дающей алго- ритм вычисления Алгоритм вычисления функции

227 227 Алгоритм 2.7: вычисление Вход: G = (V N, V T, P, S) cfg. Выход: для всех A V N. Метод. Определим вспомогательную функ- цию где A, B V N. Очевидно, что Ret 259 Алгоритм вычисления функции Ret 232Ret 235

228 228 Остается определить алгоритм для вычисления функции Вычисление значения производит- ся методом последовательных приближений по шагам 1-3: 1. Алгоритм вычисления функции Ret 237Ret 242

229 Пусть значения уже построены для всех (A, B) V N V N. Тогда Алгоритм вычисления функции Ret 239 Ret 244 Ret 246

230 Шаг 2 повторяется до тех пор, пока при некотором i = j не окажется j+1 (A, B) = j (A, B) для всех (A, B) V N V N. Такое j существует, ибо 0 (A, B) 1 (A, B) … V T * k, и множество V T * k конечное. И тогда (A, B) = j (A, B). Алгоритм вычисления функции

231 231 Алгоритм вычисления функции 4. Наконец, полагаем для всех A V N и так как всегда но может оказаться, что

232 232 Пример вычисления функции Пример Пусть G = ({S, A}, {a, b}, P, S), где P = {S aAaa, S bAba, A b, A }. Построим множества и используя описанный алгоритм (см. табл. 2.6). Получаем поскольку

233 233 N 0 1 (S, S) (S, A){aa, ba} (A, S) (A, A) Таблица 2.6 Пример вычисления функции

234 234 Покажем теперь, что алгоритм 2.7 действительно вычисляет функцию2.7 для любого нетерминала A. Алгоритм вычисления функции

235 235 j (A, B) (A,B) Теорема 2.9. Пусть G = (V N, V T, P, S) cfg. Алгоритм 2.7 правильно вычисляет функцию для любого A V N и k Доказательство. Фактически достаточно показать, что если при i > j для всех (A, B) V N V N. Ret 230

236 236 j (A, B) (A, B) I. Покажем сначала, что или, что то же самое, если при l j, то используя индукцию по l.

237 237 j (A, B) (A, B) База. Пусть l = 0. Имеем Согласно шагу 1 алгоритма 2.7 существует правило A B P,, V *, и1 Это правило позволяет построить вывод A B, причём любая цепочка также является элементом множества таково определение этой функции, т. е. База доказана.

238 238 j (A, B) (A, B) Индукционная гипотеза. Предположим, что аналогичное утверждение выполняется для всех l n (0 n j).

239 239 j (A, B) (A, B) Индукционный переход. Докажем, что тогда аналогичное утверждение верно для l = n + 1. Итак, пусть Согласно шагу 2 алгоритма 2.72 либо и тогда согласно индукцион- ной гипотезе либо существует правило A X 1 X 2 … X p X p+1 … X m P и где X p V N, 1 p m.

240 240 j (A, B) (A, B) Иначе говоря, по определению операции k существуют и w (w 1 w 2 ). В соответствии с индукционным предпо- ложением из того, что следует, что По самому определению функции (A, B) последнее вхождение w 1 означает, что суще- ствует вывод X p B и w 1 ( ).

241 241 j (A, B) (A, B) Кроме того, w (w 1 w 2 ) = = (w 1 ) k (w 2 ) ( ) k (X p+1 … X m ) = = ( X p+1 … X m ) и при этом существует вывод A X 1 X 2 … X p X p+1 … X m X 1 X 2 … B X p+1 … X m. Следовательно,

242 242 (A, B) j (A, B). II. Покажем теперь, что (A, B) j (A, B). Пусть w (A, B) благодаря тому, что су- ществует вывод A B и w ( ). Индукцией по длине вывода l покажем, что w j (A, B). База. Пусть l = 1. Имеем A B и w ( ). Тогда существует правило A B P и согласно шагу 1 алгоритма 2.71 w 0 (A, B) j (A, B). База доказана.

243 243 Индукционная гипотеза. Предположим, что аналогичное утверждение выполняется для всех l n (n 1). (A, B) j (A, B).

244 Индукционный переход. Докажем, что тогда аналогичное утверждение верно для l = n + 1. Пусть w (A, B) благодаря тому, что су- ществует вывод длиной n + 1 вида A X 1 X 2 … X p–1 X p X p+1 …X m X p B = B, в котором X 1 X 2 … X p–1 ; X p+1 … X m ; X p B ; X p V N, =, = ;,,, V. 244 (A, B) j (A, B).

245 245 (A, B) j (A, B). w ( ) = ( ) = = ( ) k ( ) (X p, B) k (X p+1 … X m ) j (X p, B) k (X p+1 … X m ) j+1 (A, B) = j (A, B), поскольку ( ) (X p, B) j (X p, B). Предпоследнее вложение следует в соот- ветствии с индукционной гипотезой из существования вывода X p B длиной не больше n.

246 246 Здесь использовано существование правила A X 1 X 2 … X p X p+1 … X m P, благодаря которому, учитывая шаг 2 алгоритма 2.7, мы заключили, что2 w j+1 (A, B). Утверждение II доказано. Из рассуждений I и II следует равенство j (A, B) = (A, B) и утверждение теоремы. (A, B) j (A, B).

247 247 § k-Предсказывающий алгоритм трансляции Ранее была доказана теорема 1.3 о том, что выходную цепочку простой семантически одно- значной трансляции можно сгенерировать по левостороннему анализу входной цепочки посредством детерминированного магазинного преобразователя.1.3 Если входная грамматика схемы синтаксически управляемой трансляции принадлежит классу LL(k), то мы имеем детерминированный механизм, правда, не преобразователь, а k-предсказывающий алгоритм анализа, который выдаёт левосторонний анализ входной цепочки трансляции, задаваемой такой схемой.

248 248 Использованный в лемме 1.1 приём можно применить для модификации k-предсказывающего алгоритма анализа в k-предсказывающий алгоритм трансляции, реализующий трансляцию, специфи- цируемую простой семантически однозначной sdts с входной грамматикой класса LL(k).1.1 Это устройство отличается от LL(k)-анализатора лишь тем, что имеет ещё один тип движений (pass), состоящий в том, чтобы перенести верхний символ магазина, являющийся гомоморфным образом выходного символа, на выходную ленту, превратив его в оригинал выходного символа (как в лемме 1.1). Детали прояснятся из описания алгоритма k-Предсказывающий алгоритм трансляции

249 249 Алгоритм 2.8: построение k-предсказываю- щего алгоритма трансляции. Вход: T = (N,,, R, S) простая семанти- чески однозначная sdts с входной грам- матикой G i класса LL(k). Выход: k-предсказывающий алгоритм трансляции, реализующий трансляцию (T). Алгоритм построения k-предсказывающего алгоритма трансляции Ret 245Ret 266 Ret 254 Ret 259

250 250 Алгоритм построения k-предсказывающего алгоритма трансляции Метод. Предполагая, что множество LL(k)-таблиц, необходимых и достаточных для анализа в грамматике G i, уже построено, положим = (, {$},, M, X 0, $), где и такие же, как в схеме T; = ; ={b b = h(b), b }; = ; X 0 =T 0 =T S,{ } начальный символ магазина; $ маркер дна магазина;

251 M(T A,L, u) = x 0 y 0 T A 1,Y 1 x 1 y 1 …T A m,Y m x m y m, если T A, L (u) = (A x 0 A 1 x 1 … A m x m, Y 1, …, Y m ), и A x 0 A 1 x 1 … A m x m, y 0 A 1 y 1 … A m y m R i-е правило схемы. Здесь u, а y i = h(y i ), i = 0, 1, 2, …, m. Алгоритм построения k-предсказывающего алгоритма трансляции M: ( {$}) * {pop, pass, accept, error} управляющая таблица, которая строится по следующим шагам:

252 252 Алгоритм построения k-предсказывающего алгоритма трансляции 2. M (a, u) = pop, если a, u = av, v. 3. M (b, u) = pass для всех b, u. Такой управляющий элемент определяет переход между конфигурациями: (x, b $, y) (x, $, yb). 4. M ($, ) = accept. 5. M (X, u) = error для всех (X, u) ( {$}), для которых элементы M не определены по пп. 1–4.

253 253 Пример Пусть T = ({S, A}, {a, b}, {a, b, e, }, R, S) sdts, где R = {(1) S aAaa, aAaa; (2) S bAba, a; (3) A b, b; (4) A, e}. Входная грамматика этой схемы не сильная LL(2)-грамматика. В примере 2.9 для неё был построен 2-предсказывающий алгоритм анализа.2.9 Пример построения 2-предсказывающего алгоритма трансляции

254 254 Пример построения 2-предсказывающего алгоритма трансляции Применяя алгоритм 2.8 к данной схеме, получаем следующий 2-предсказывающий алгоритм трансляции, реализующий опреде- ляемую ею трансляцию:2.8 = ({a, b}, {T 0, T 1, T 2, a, b, a, b, e,, $}, {a, b, e, }, M, T 0, $), где M представляется управляющей табл

255 255 Маг. cим. А в а н ц е п о ч к и aaabbabbab T0T0 aaT 1 aaaa b a T1T1 ebb T2T2 e apop b a b e < > $accept Таблица 2.7 p a s s Ret 145

256 256 Пример построения 2-предсказывающего алгоритма трансляции Для иллюстрации работы только что построенного 2-предсказывающего алгорит- ма трансляции рассмотрим обработку вход- ной цепочки bba: (bba, T 0 $, ) (bba, b a$, ) (ba, a$, ) (ba, T 2 ba>a$, a$, a$, a$, a$,

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

258 258 Пример Пусть T = ({E, E, T, T, F}, {a, +, *, (, )}, {a, +, *}, R, E) sdts, где R = {(1) E TE, TE ; (2) E +TE, T+E ; (3) E, ; (4) (5) (6) (7) F (E), E; (8) F a, a}. Пример 1-предсказывающего алгоритма трансляции E T E FT E (E) T E (TE ) T E E TE FT E FT

259 259 Очевидно, что T простая семантически однозначная sdts с входной грамматикой LL(1). Используя модификацию алгоритма 2.8 с учётом леммы 1.1, алгоритмов 2.1 и 2.7 получаем следующий 1-предсказывающий алгоритм трансляции: = ({a, +, *, (, )}, {E, E, T, T, F, a, +, *, (, ), a, +, *, $}, {a, +, *}, M, E, $), где M представлена в табл Пример 1-предсказывающего алгоритма трансляции

260 260 Маг. сим. А в а н ц е п о ч к и a+*() ETE E+T+E TFT T *F* T Faa(E)(E) Таблица 2.8 Пример 1-предсказывающего алгоритма трансляции (Ср. с анализатором для входной грамматики примера 2.6).примера 2.6

261 261 Маг. сим. А в а н ц е п о ч к и a+*() apop + * ( ) Таблица 2.8 (прод.) Пример 1-предсказывающего алгоритма трансляции

262 262 Маг. сим. А в а н ц е п о ч к и a+*() a p a s s + * $accept Таблица 2.8 (прод.1) Пример 1-предсказывающего алгоритма трансляции *) Пустые клетки соответствуют значениям error.

263 263 Пример 1-предсказывающего алгоритма трансляции Посмотрим, как будет действовать построенный нами 1-предсказывающий алгоритм трансляции на входной цепочке (a + a). 1. ( (a+a), E$, ) 2. ( (a+a), TE $, ) 3. ( (a+a), FT E $, ) 4. ( (a+a), (E) T E $, ) 5. ( a+a), E) T E $, )

264 264 Пример 1-предсказывающего алгоритма трансляции 6.( a+a), TE ) T E $, ) 7.( a+a), F T E ) T E $, ) 8.( a+a), aa T E ) T E $, ) 9.( +a), a T E )T E $, ) 10.( +a), T E ) T E $, a ) 11.( +a), E ) T E $, a ) 12.( +a), +T+ E ) T E $, a ) 13.( a), T+ E ) T E $, a ) 14.( a), FT + E )T E $, a ) 15.( a), aa T + E ) T E $, a )

265 265 Пример 1-предсказывающего алгоритма трансляции 16.( ), a T + E ) T E $, a ) 17.( ), T + E ) T E $, aa ) 18.( ), + E ) T E $, aa ) 19.( ), E ) T E $, aa+ ) 20.( ), )T E $, aa+ ) 21.(, T E $, aa+ ) 22.(, E $, aa+ ) 23.(, $, aa+) accept. Итак, ((a + a)) = a a +. Не трудно проверить, что (E, E) ((a + a), a a +).

266 266 (T)= ( ) Теорема Пусть T = (N,,, R, S) простая семантически однозначная схема синтаксически управляемой трансляции с входной грамматикой G i класса LL(k), и = (, {$},, M, T 0, $) k-предсказывающий алгоритм трансля- ции, построенный посредством алгоритма 2.8, применённого к данной схеме трансляции T. 2.8 Тогда (T) = ( ). Ret 273

267 267 Доказательство. Справедливость данного утверждения следует из того факта, что LL(k)-анализатор, построенный по входной грамматике данной схемы, является правильным. (T)= ( )

268 268 Модификация, превращающая LL(k)- анализатор в LL(k)-транслятор, фактически состоит в том, что когда анализатор, моделируя шаг левостороннего вывода, замещает некоторую LL(k)-таблицу T A,L на вершине магазина образом правой части правила вида x 0 T A 1,L 1 x 1 T A 2,L 2 …T A m,L m x m, транслятор подмешивает к этой магазинной цепочке образы выходных символов из семантической цепочки соответствующего правила схемы. (T)= ( )

269 269 Таким образом, что полученная смесь x 0 y 0 T A 1,L 1 x 1 y 1 T A 2,L 2 …T A m,L m x m y m в магазине обеспечивает точное воспроизведение движений анализатора и синхронизирован- ную с ними генерацию соответствующей цепочки на выходной ленте. (T)= ( )

270 270 Действительно, выполнив pop-движения и продвинувшись по фрагменту x i входной цепочки, который является также и фрагментом правила входной грамматики A x 0 A 1 x 1 A 2...A m x m, транслятор тут же выдает на выход соответствующий фрагмент y i выходной цепочки, который также является и фрагментом семантиче- ской цепочки соответствующего правила схемы A x 0 A 1 x 1 A 2 … A m x m, y 0 A 1 y 1 A 2 … A m y m. Что и требовалось доказать. (T)= ( )

271 271 Теорема Пусть T = (N,,, R, S) простая семантически однозначная схема синтаксически управляемой трансляции с входной грамматикой G i класса LL(k). Существует детерминированный мага- зинный преобразователь P, такой, что e (P) = {(x$, y) (x, y) (T)}. dpdt P: e (P) = {(x$, y) (x, y) (T)}

272 272 Доказательство. Заметим, что входная цепочка трансляции, реализуемой магазин- ным преобразователем, всегда имеет маркер конца, тогда как схема порождает трансляцию с входами без такого маркера. Маркер необходим, чтобы гарантировать детерминизм магазинного преобразователя. dpdt P: e (P) = {(x$, y) (x, y) (T)}

273 273 dpdt P: e (P) = {(x$, y) (x, y) (T)} Доказательство основано на построении dpdt, моделирующего движения k-пред- сказывающего алгоритма трансляции, адекватного данной схеме, который согласно теореме 2.10 существует. теореме 2.10 Итак, пусть построен k-предсказы- вающий алгоритм трансляции = (, {$},, M, T 0, $).

274 274 dpdt P: e (P) = {(x$, y) (x, y) (T)} Положим dpdt P = (Q, {$}, {$},,, q 0, $, ), где, и те же, что и в ; Q = {q 0 } {[u] u * k } {[v$] v * k–1 }.

275 (q 0,, $) = ([ ], T 0 $, ) моделирует начальную конфигурацию. 2. ([v], a, T) = ([va], T, ), v * k–1, a, T реализует накопление полной аванцепочки. 3. ([v], $, T) = ([v$], T, ), v * k–1, T совершает накопление короткой аванцепочки. dpdt P: e (P) = {(x$, y) (x, y) (T)}

276 ([u],, T) = ([u],, ), u k, T, M(T, u) = моделирование движения типа 1 при полной аванцепочке. 5. ([v$],, T) = ([v$],, ), v * k–1, T, M(T, v) = моделирование движения типа 1 при короткой аванцепочке. dpdt P: e (P) = {(x$, y) (x, y) (T)}

277 ([av],, a) = ([v],, ), a, v k–1 моделирование pop-движения при полной аванцепочке. 7. ([av$],, a) = ([v$],, ), a, v * k–2 моделирование pop-движения при короткой аванцепочке. dpdt P: e (P) = {(x$, y) (x, y) (T)}

278 ([u],, b ) = ([u],, b), b, u k моделирование pass-движения при полной аванцепочке. 9. ([v$],, b ) = ([v$],, b), b, v * k–1 моделирование pass-движения при короткой аванцепочке. 10. ([$],, $) = ([ ],, ) моделирование перехода в принимающую конфигурацию. dpdt P: e (P) = {(x$, y) (x, y) (T)}

279 279 То, что построенный dpdt P действи- тельно точно моделирует k-предсказы- вающий алгоритм трансляции, нетрудно доказать индукцией по числу движений типа 1 того и другого устройств. dpdt P: e (P) = {(x$, y) (x, y) (T)}

280 Непростые LL(k)-трансляции и магазинные процессоры Пусть T = (N,,, R, S) непростая семантически однозначная sdts с входной грамматикой G i класса LL(k). Для реализации такой трансляции можно ввести ещё одну модификацию k- предсказывающего алгоритма анализа, называемую магазинным процессором.

281 281 Магазинный процессор ведёт анализ входной цепочки во входной грамматике и генерирует дерево вывода выходной цепочки в выходной грамматике. Другими словами, он моделирует вывод элемента трансляции, используя магазин для манипуляции над синтаксическими цепочками трансляционных форм, а семантические цепочки этих форм представляет в виде дерева вывода в выходной грамматике, разрастающегося в ходе вывода. Непростые LL(k)-трансляции и магазинные процессоры

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

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

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

285 285 Проще всего проиллюстрировать работу магазинного процессора схематически см. рис. 2.3). Непростые LL(k)-трансляции и магазинные процессоры

286 286 Рис. 2.3 (a). Магазинный процессор. На рис. 2.3(a) представлена началь- ная конфигурация магазинного про- цессора. В магазине, кроме маркера дна магазина, находится только начальная LL(k)-таблица T 0 с указателем p 0 на корень строящегося дерева вывода в выходной грамматике результата трансляции входной цепочки. Этот указатель запоминается также в отдельной переменной (Root), чтобы через него получить доступ к дереву после его построения. $ T 0, p 0 МагазинМагазин Root S Непростые LL(k)-трансляции и магазинные процессоры

287 287 Рис. 2.3 (б, в). Магазинный процессор. $ T A,L, p МагазинМагазин (б)(б) A 1 B 1, 2 B 2 А S Root A (в)(в) 2 2 S B $ T B,Y, q 1 1 МагазинМагазин Root На рис. 2.3 (б) представлена промежуточная конфигурация мага- зинного процессора, когда часть дерева вывода построена. Среди его листьев находится вер- шина, помеченная нетерминалом A. В рассматриваемый момент на вершине магазина находится LL(k)- таблица T A,L с указателем p на упомя- нутую вершину дерева вывода, поме- ченную нетерминалом A, к которой будет пристроено поддерево, пред- ставляющее семантический элемент правила A 1 B 1, 2 B 2, используемого на этом шаге модели- рования вывода. В этом правиле явно выделена пара связанных вхождений одного нетерминала (B).

288 288 Рис. 2.3 (в) иллюстрирует результат этого шага: в магазине вместо таблицы T A,L поме- щён образ синтаксической цепочки 1 B 1, а к узлу A пристроен древовидный образ семантической цепочки 2 B 2. Показана связь одного символа T B,Y образа нетерминала B в синтаксической цепочке, заместившей в магазине T A,L, с узлом B из множества вновь образованных узлов, составляющих образ семантической цепочки 2 B 2. Непростые LL(k)-трансляции и магазинные процессоры

289 289 Указатель q при T B, Y определяет ту верши- ну, к которой будет подвешиваться древо- видный образ семантической цепочки некоторого правила схемы, определяющего нетерминал B, когда магазинный символ T B,Y будет замещаться синтаксической цепочкой этого же правила. Опишем теперь неформально алгоритм построения магазинного процессора по данной схеме, обладающей указанными свойствами. Непростые LL(k)-трансляции и магазинные процессоры

290 290 Алгоритм 2.9: построение магазинного процессора по непростой семантически однозначной sdts с входной грамматикой класса LL(k). Вход: T = (N,,, R, S) непростая семантически однозначная sdts с входной грамматикой G i класса LL(k). Выход: магазинный процессор, такой, что ( ) = (T). Алгоритм построения магазинного процессора

291 291 Метод. Магазинный процессор в своем магазине будет повторять действия LL(k)- анализатора, построенного по входной грамматике схемы T, используя вместо выходной ленты устройство памяти прямого доступа, в котором он строит дерево вывода результата трансляции в выходной грамматике схемы. Алгоритм построения магазинного процессора

292 292 Алгоритм построения магазинного процессора 1.Первоначально имеет запись (S, p r ) на вершине магазина, где p r указатель на корневой узел n r дерева результата трансляции. Этот же указатель дубли- руется переменной Root. В случае использования LL(k)-таблиц вместо начального нетерминала S будет использоваться начальная LL(k)-таблица T 0 = T S,{ }.

293 293 Алгоритм построения магазинного процессора 2. Если имеет терминал входной грам- матики на вершине магазина и текущий входной символ (первый символ аван- цепочки) такой же терминал, то планируется pop-движение процессора, аналогичное движению анализатора.

294 294 Алгоритм построения магазинного процессора 3. Если раскрывает нетерминал A (или замещает LL(k)-таблицу, ассоциированную с A) посредством правила A X 1 X 2 …X m с семантическим элементом y 0 B 1 y 1 …B m y m в схеме, и при этом рядом с этим нетерминалом A (или заменяющей его LL(k)- таблицы) на вершине магазина процессора находится указатель на узел n, то планируются следующие действия процес- сора:

295 295 a) создание узлов прямых потомков для n, помеченных слева направо символами цепочки y 0 B 1 y 1 …B m y m ; б) замена на вершине магазина нетерминала A (или соответствующей ему LL(k)-таблицы) и указателя при нём (ней) на цепочку X 1 X 2 … X m (или её образ) с указателями при каждом нетерминале (или заменяющей его LL(k)-таблицы). Алгоритм построения магазинного процессора

296 296 Алгоритм построения магазинного процессора Если X j нетерминал (или заменяющая его LL(k)-таблица), то указатель при нем (ней) должен указывать на узел, созданный для B i, при условии, что X j и B i связаны в правиле схемы A X 1 X 2 … X j … X m, y 0 B 1 y 1 …B i y i … B m y m.

297 297 Алгоритм построения магазинного процессора 4. Планируется, что завершает работу, когда в его магазине только маркер дна магазина, а аванцепочка пуста. Результат трансляции, задаваемый дан- ной схемой, получается посредством выпи- сывания меток листьев построенного дерева с корнем Root при его левостороннем обходе.

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

299 299 Теорема Алгоритм 2.9 строит правильный магазинный процессор, выдающий в качестве выхода дерево, метки листьев которого, выписанные слева направо, представляют результат трансляции входной цепочки. Доказательство следует из предыдущих рассуждений. Алгоритм построения магазинного процессора