Главная Промышленная автоматика.

Лемма 5.1. Для любой КС-грамматики G(N,2, Р,5) и любых а, P€(NU2)*

FIRST, (ар) = FIRST? (а) FIRST? (р) Доказательство. Упражнение. □

Определение. Пусть G (N, 2, Р, S) -КС-грамматика. Для каждых /4€N и 12* определим LL {кутаблицу Г,/-. соответствующую А и L, как функцию, значением которой для данной аванцепочки и<* служит либо символ ошибка, либо А-правило и конечный список подмножеств множества 2**, а именно

(1) T.L (и) -ошибка, если в Р нет такого правила А-а, что FlRSt(a)©ftL содержит и;

(2) Tj,a)(A~a, <К„Кз, ...,0),

если

ОС-едип-

L содержит и;

х,€2*, то K,-FIRST,(x,B,,x,,...B,A)©,L локальным множеством для Bf, если m - О, то а. 0));

-у а

ственное правило из Р, для которого FIRST(a)( если

а XqBxBx ... Вх {т > 0)

где B/N и (назовем T,Ui) = {A~

(3) Tji{u) не определено, если в множестве А найдутся два (или более) таких правила А -

и € (FIRST, (а,)L) П (FIRST,(aj)L)

(Эту ситуацию иногда называют конфликтом между правилами А->-а,- и А-.-ау. Если G - LL ()-грамматика, то таких конфликтов не возникает.)

Интуитивно это означает, что если Г. (tt) = ошибка, то в G невозможен вывод вида Ах =Ф uv для xL и у g 2*. Если А,1{и)-{А~а, <Ki, Kg, то найдется в точности одно

правило А-а, которое можно применить на первом шаге вывода Ах= UV для xL и и2*. Каждое множество У,- дает всевозможные префиксы длины, не большей к, терминальных цепочек, которые могут следовать за цепочкой, выводимой из В, когда в выводе вида Ax=iax=>*ии, где xL, применяется правило Л-+а, где а-хВхВх.. .B,„Xf;,.

По теореме 5.2 G -(N, 2, Р, S) не является LL (й)-граммати-кой тогда и только тогда, когда существует такая цепочка a€(Nu2)*, что

(1) S* wAa,

(2) FlRSTft(Pa)nFIRST,(ya) 0 для некоторых ру, для которых Л->р и Л-у принадлежат Р.

В силу леммы 5.1 условие (2) можно перефразировать так:

(2) если L = FlRST(a), то пересечение FIRST,(P)eL и гЩЗТд(у) непусто.

(по числу шагов левого вывода) можно доказать обратное утверждение, а именно: если Sixa, где а - незаконченная часть цепочки ха, и FIRSTi (f/)e FIRST (а), то (л:г/, S$, е) -* ( , а$, я). Из всего этого следует, что (tej, S$, е) j-* (е, $, я) тогда и только тогда, когда S„->tej. Таким образом, - корректный алгоритм разбора для грамматики G, а М - корректная управляющая таблица. □

5.1.5. Разбор для LL }-грамматик

Построим теперь управляющую таблицу для произвольной LL (й)-грамматики G = (N,11, Р, S), где kL Если G - сильно LL ()-грамматика, то можно применить алгоритм 5.1 с аванце-почками, содержащими до k символов. Однако ситуация несколько усложняется, если G не является сильно LL ()-грамматикой. В 1-предсказывающем алгоритме разбора для LL (1)-грамматики в магазин помещались только символы из 2uN и оказывалось, что для однозначного определения очередного применяемого правила достаточно зпать иетерминальпый силшол наверху магазина и текущий входной символ. Но если G не является сильно LL (к)-грамматикой, то нетерминального символа и аванцепочки пе всегда достаточно для однозначного определения очередного правила.

Возьмем, например, LL (2)-грамматику

S --аЛаа ЬАЬа А~Ь\е

из примера 5.8. Если даны нетерминал А и аванцепочка Ьа, то не известно, какое из правил А-*-Ь и А-надо применить.

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

Определение. Пусть 2 - некоторый алфавит. Если я L - подмножества 2*, то положим

Li0ftL2 = {tej для некоторых xL и yL либо w-xy, если \ху\к, либо W состоит из первых к символов цепочки- ху]

Пример 5.13. Пусть = {е, аЬЬ} rL {Ь, ЬаЬ}. ТогдафзL - {Ь,Ьа,аЬ}. □



Таблица 5.1

правило

Множества

аа аЬ bb

S -а Ааа S -> аЛаа S ЬАЬа

{аа\ {аа} {Ьа)

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

Алгоритм 5.2. Построение LL (й)-т а бл и ц.

Вход. LL (/е)-грамматика G = (N, 2, Р, S). Выход. Множество LL (/г)-таблнц, необходимых для построения управляющей таблицы для G. Метод.

(1) Построить LL (/г)-таблнцу Гц, соответствующую 5 и {е}-

(2) Положить вначале ={Т].

(3) Для каждой LL (/г)-таблицы Г, содержащей элемент Т(и) = (А~-х,ВуХфх.,,Вх, <У„ У„ К»

включить в LL (/е)-таблицу Т.у .для lim, если Тв.,у. еще

не входит Б <F.

(4) Повторять шаг (3) до тех пор, пока в можно включать новые таблицы. □

Пример 5.15. Построим соответствующее множество LL(2)-Ta6-лиц для грамматики

S -аАаа ЬАЬа АЬ\е

Начнем с ={Ts,{e)}. Так как Ts, {е) (аа) = {S-аАаа, {аа}), то в надо включить Та, {аа). Аналогично, так как T(bb) (S-ЬАЬа, {Ьа}), то в нужно также включить Та, {Ьа}- (Элементы ЬЬ(2)-таблиа Та, (аа) и Т. {ьщ, отличные от значения ошибка, приведены в табл. 5.2.) Сейчас <-{Ts,{e), Та. {аа), ТА.{Ьа)}, И алгоритм 5.2 уже не может включить в < новых таблиц, так что эти три ЬЬ(2)-таблицы образуют множество, соответствующее грамматике G. П

Дадим алгоритм, которым можно построить корректную управляющую таблицу для ЬГ(/г)-грамматики G но соответствующему ей множеству ЬЬ(/е)-таблиц. Управляемый этой таблицей /е-предсказывающий алгоритм будет в качестве магазинных символов употреблять вместо нетерминалов ЬЬ()-таблицы.

Таблица 5.2

а, {аа)

а, {Ьа)

Правило

Множества и

Правило

Множества

~ Ьа

- bb

Алгоритм 5.3. Управляющая таблица для LL(ft)-грамматики.

Вход. ЬЬ(/е)-грамматика G = (N, 2, Р, S) и соответствующее ей множество ЬЬ()-таблиц.

Выход. Корректная управляющая таблица М для G.

Метод. М определяется на множестве (© U 2 U ($() X 2** следующим образом;

(1) Если Л-XfByXyBx.. .В,„х - правило из Р с номером i a.l€, то для всех а, для которых

TA.l{u) = iAx,B,x,B,x,.. .Вх, <Y„ Y,,

полагаем M{Ta,l, и)-{чГв,,у,х,Тв„у,х,..Тв,ух, О-

Следовательно, если G - LL ()-грамматика и есть вывод 5=$.* wAa} wx, то Ta,l{u) будет однозначно определять, Kaivoe правило применить к Л, если и FIRST (х) и L = FIRST; (а).

Пример 5.14. Рассмотрим ЬЬ(2)-грамматику 5 ->~аАаа\ЪАЬа АЬ\е

Вычислим ЬЬ(2)-таблицу Ts, u), которую обозначим Т, Для правила S~+aAaa найдем FiRST{aAaa) ®{е} = {аа, аЬ]. Для S~bAba вычислим FIRST{ЬAba) l} = Таким обра-

зом, T{aa){SaAaa, Y), тде УFIRST(аа) {е} = {аа} ~ локальное множество для Л и аа-цепочка, расположенная справа от Л в правиле 5->аАаа. Продолжая в том же духе, получаем (табл. 5.1). Для каждой цепочки uE{a-\-b)*, не показанной в этой таблице, 7р (н) ошибка. □



uTioa, 1

аГГаа,]

ЬТгЬа;г.

выброс

выброс

выброс

выброс

выброс

выброс

аопуск

Рис. 5.5. Управляющая таблица.

изображенную на рис. 5.5, где 7 = 75,{е}. ТТллаа) н ТТА,{Ьа}- Подразумевается, что в пустых ячейках ошибка.

Для входной цепочки ЬЬа 2-предсказывающий алгоритм проделает такую последовательность тактов:

(ЬЬа, Т,$, е) h {ЬЬа, ЬТфа$, 2) 1~ {Ьа, ТЬа%, 2) h (Ьа, Ьа%, 24) h {а. а%, 24) 1~ (е, $, 24) □

Теорема 5.5. Алгоритм 5.3 строит для ]Л{к)-грамматики G (N, 2, Р, S) корректную таблицу, управляющую работой соответствующего k-предсказывающего алгоритма разбора.

Доказательство. Доказательство аналогично доказательству теоремы 5.4. При построении ЬЬ(/е)-таблиц для произ-

вольной КС-грамматики могут возникать конфликты, упомянутые при определении таблицы Та, l (пункт (3)). Но если

Q ЬЬ(/е)-грамматика, то конфликтов не будет, так как если

и А->у принадлежат Р и 5=>*и;Ла, то

(FIRST, (р) е, FIRST, (а)) п (FIRST, (у) 0, FIRST, (а)) = 0

При построепин ЬЬ()-таблиц, соответствующих грамматике G, таблица Ta,l вычисляется только тогда, когда S=*iwAa и /,=FlRST,(a) для некоторой цепочки а, т. е. L - локальное множество для А. Поэтому если uL, то существует не более одного правила А~р, для которого а FIRST, (р)

Зададим гомоморфизм h на множестве и 2 равенствами h (а) -а для всех а 2 и h(T) = А, если Т - ЬЬ()-таблица, соответствующая А и L.

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

Теперь докажем, что

(5.1.2) S 31= ха тогда и только тогда, когда найдется такая цепочка а£{u2)*, что h{a)=a и (ху, 7$. ) Ь* (у, п) для всех у, для которых a=>*f/, где Т-

ЬЬ(й)-таблипа, соответствующая S и {е}.

Достаточность. Из способа построения управляющей таблицы следует, что когда выдается номер i правила А-*-6, алгоритм разбора заменяет таблицу Т, для которой h{T) = A, такой цепочкой р, что /i(p)-р. Таким образом, эту часть утверждения

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

Необходимость. Здесь мы покажем, что

(5.1.3) если Ля=?Л, то алгоритм разбора] проделает последовательность тактов (ху, Т, е) -* {у, е, п) для любой ЬЬ()-таблипы Т, соответствующей А и L, где L - FIRST, (а) для некоторой цепочки а, для которой 8=*1 wAa, и yL.

Доказательство проведем индукцией по длине цепочки я. Если А i=aa.. .а, то

(ам.

F, е)\-{а.. .ау, а.

поскольку (а)(Л-.да- • 0) для всех FIRST, (йа.. .а„) ®feL. Тогда {а...ау, а...а„, i)}-"(y, е, 1). Теперь предположим, что утверждение (5.1.3) верно для всех левых выводов длины, не большей /, и пусть А хВхВх.. .В,„х и ВуУ/, где яу</. Тогда {хух.. .уху, Т, e)V-* (хух.. .уху, 11 • • Л. 0. так как Т (и) = (А~х.Вх,...Вх,

(2) М(а, ду) выброс для всех yS***"*.

(3) М{, е)-допуск.

(4) В остальных случаях М{Х, а) = ошибка.

(5) Ts,{e) - начальная таблица. □

Пример 5.16. Построим управляющую таблицу для LL(2)-грамматики

(1) S~aAaa

(2) S-bAba

(3) Ab

(4) Ае

используя соответствующее ей множество ЬЬ(2)-таблиц, найденное в примере 5,15. Алгоритм 5.3 выдаст управляющую таблицу,





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 [64] 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0041