Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 99
Текст из файла (страница 99)
Так как 6 — грамматика слабого пред|пествования, то, применяя теорему 5.!4 к цепочке убх, находим, что отношение > впервые встречается между 6 и х. Применяя эту теорему к а()ш, находим:- между 1з и ш, а так как ш и у начинаются Одним и тем же символом, то ) оказывается между !) и у. Поэтому !а'р! '"!уб!. Так как дано, что )х!-=!у!, то должно быть а'6=уб и х=-у. Если мы сможем показать, что р=6, то этим докажем, что сс'=-у, Ио из обратимости следует, что А=-В, и, значит, мы получим противоречие с предположением, что уВх~а'Ау. Если (1~ 6, то одна из этих цепочек должна быть суффиксом другой.
Чтобы показать, что (з=-6, исследуем отдельно каждый из возможных случаев. Случай 1: р=..:ЕХ6 для некоторых г и Х. Так как Х вЂ” последний символ цепочки у, то, применяя теорему 5,14 к правовыводимой цепочке уВх, имеем ХЛВ или Х ' В, ЭТО нарушает условие слабого предшествовапия. Случай 2: 6=ЕХр для некоторых В и Х. Этот случай симметричен только что рассмотренному. Итак, р=-6 и б — (1,1)-ОПК-грамматика. [3 Теорема 5.21. Каждая (т, й)-ОПК-грамматика лвллеГися 1-Й(й)- грамматикой.
Доказательство. Пусть 6=()Ч(, Х, Р, В) является (т, и). ОПК-грамматикой, ио пе 1.К((г)-грамматнкой. Тогда по лемме 5.2 4З4 Е. Е ДРУГИЕ КЛАССЫ ГРАММАТИК в пополненной грамматике б' существуют выводы В':=.>'„аАГВ =-.>, сфш 3' =о, 'уВх =з, убх=ару Где !уб!>)а(1! и Е1ЙВТА(у)=Г1КБТ (ш), но уВх~аАу. Если окружить все цепочки символами 5 и положить а'=а, то (Ги, и)- ОПК-условие будет нарушено.
( ) Следствие. Каждая ОПК-грамматика однозначна. Теперь перейдем к построению алгоритма разбора типа „перенос — свертка" для ОПК-грамматик и обсудим эффективную реализацию этого алгоритма. Допустим, что алгоритм указанного типа используется для анализа ОПК-грамматики б и что он находится в конфигурации (а, ГВ, я).
Тогда можно задать множества Яе и в1', которые скажут нам, появилась ли основа право- выводимой цепочки аш наверху магазина (т. е. образует лиона суффикс цепочки а) или же правый конец основы расположен где-то в ш (и тогда надо делать перенос). Если основа в магазине, то эти множества скажут, какова она и какое правило применить для ее свертки. Определение.
Пусть 6 = (1ч, Т., Р, В) — ОПК-грамматика. Для А 6 (ч определим Яо,„(А) как множество таких троек (а, (1, х), что !а!= — т, !х!=п и в пополненной грамматике есть вывод $'"В'5" =>„' у а А ху =>, у арху Множество в)го,„пусть состоит из таких пар (а, х), что (1) либо ! а ! = и +1, где 1 — длина самой длинной правой части правил нз Р, либо !а! < т+1 и а начинается с 5'"; (2) (х!=-и; (3) существует вывод $ В'$" >,'()Ау=э„буу, где ах — надцепочка цепочки руу, расположенная так, что а лежит внутри цепочки ру и не содержит ее последнего сих1вола.
В очевидных случаях мы будем опускать индексы б, т и и в обозначениях Я(А) и ву'. Идея состоит в том, что появление подцепочки арх в ходе просмотра слева направо правовыводимой цепочки должно указывать, что р-- основа н ее надо свернуть к А, если (а, р, х) Е Я (А). Появление такой цепочки ах, что (а, х) ЕЬ", указывает па то, что основа еще не получена, но, возможно, расположена справа от а. Лемма 5.6 подтверждает, что так оно и есть. Лемма 5.6. Грамматика б = ()ч, В, Р, В) является (т, и)-ОПК- грамматикой тогда и только тогда, когда выполняются следующие условия: гл.
в. однопгоходнып синтлксичвскип лнллиз ввз возвглтов вл. детгиз кллссы гелммлтик (!) Пусть А — О и  — 6 — разные правила. Тогда если (а, р, х) ЕЯГ „(А) и (у, 6, х) бЯ~ „(В), то а() — не суффикс цепочки 76, и обратно. (2) Для всех А Е )л( из (а, р, х) Е Я, „(А) следует, что (Оар, к) не содержится в М' „ни для какой цепочки О. Доказательство. Достаточность.
Допустим, что б — не (т, п)-ОПК-грамматика. Тогда в пополненной грамматике б' найдутся выводы 9"5 5" =>„аАис =о,арсв $ 5 $" =о„ТВх=Ф„Тбх= а'ру где а и а' совпадают в последних т позициях, пс и у совпадают в первых п позициях и (х! =(у), но ТВх~а'Ау. Пусть г состоит ,'из последних т символов цепочки а, а г из первых и символов цепочки пс. Тогда (г,й, г) б Яс (А). Если хчиу и !х)~)у(, то должно быть (Оеб, г) ЕД' для некоторой цепочки О, так что условие (2) нарушается. Если х=у, то (ц, 6, г) ЕЯг(В), где с! состоит нз последних т символов цепочки у. Если А — р и В 6— это одно и то жс правило, то при к=у мы вопреки предположению получаем уВх=а'Ау.
Но так как одна из цепочек с!6 и е!3 является суффиксом другой, то, если правила А — б и  — 6 различны, нарушается условие (1). Необходимость. Если нарушается условие (1) или (2), легко доказать, что нарушается (т, п)-ОПК-условие. Эту часть доказательства оставляем в качестве упражнения. Теперь можно перейти к описанию алгоритма разбора типа „перенос — свертка" для ОПК-грамматик. Так как для этого нужно знать множества Ж(А) и Д', займемся сначала их вычислением. Л л г о р и т м 5.
! 6. П о с т р о е н н е м п о ж е с т в Яс „„(А) и вс" Вход. Приведенная грамматика б=. (И, Х, Р, 5). Выход. Множества гс „(А) для А 6Х и вс'",„. Метод. (1) Пусть ! — длина самой длинной правой части правила. Вычислим множество д' таких цепочек Т, что (а) !Т!=-т+п+1или (у! (т+п+! и 7 начинается сб; (б) 7 — подцепочка цепочки а~и, где арсе — правовыводимая цепочка с основой р и и= ВИВТ„(пс); (в) у содержит хотя бы один нетерминал. Здесь можно применить метод, подобный тому, что применялся в первой части алгоритма 5.13. (2) Для А Е Х пусть,Ж (А) содержит каждую тройку (а, р, х) для которой в У найдется цепочка уаАху, в Р— правило А— и (а!=т, (х(=п.
(3) Пусть М' содержит каждую пару (а, х), для которой в У найдется цепочка уВу, в Р†прави  — 6, ах — подцепочка цепочки тбу, а внутри цепочки 76, за исключением ее последнего символа. Требуется также, чтобы (к!-= п и !а ! =.сп +1, где 1 †сам длинная правая часть правила, либо а начинается с $" и !а) (т+1. П Теорема 5.22.
Алгоритм 5.6 правильно вычисляет множества Я(А) и 4'. Доказательств о. Упражнение. ~3 А л г о р и т м 5.17. П о с т р о е н и е а л г о р и т м а т и и а „п е р енос — свертка" для ОПК-г рамматик. Вход. (т, п)-ОПК-грамматика б=-. (Х, Х, Р, 5), пополненная до б'=-(Х', Х, Р, 5'). Выход. Ллгоритм Л = (7', д) типа „перенос — свертка" для грамматики б, Метод. Функции 7 и д зададим так: (1) 7(а, ш)=-. перенос, если (сс, ис) 6 сс",„... (2) 7'(а, ш)- свертка, если а=а,а, и (а„ам пс) ЕЯг,„(А) для некоторого А, но пе верно, что А =-5', а, †-- 3 и ссе =5, (3) 7(5'"5, 5")=допуск, (4) 7(а, ис)=ошибка в остальных случаях, (5) д(а, ис)-- с, если а=.а,сс„(сс„а., ис) ЕЯ~(А) и А — а,— правило с номером (6) у(а, ис) = ошибка в остальных случаях.
с) Теорема 5.23. Алгоритм 5.!7 строит корректный алгоритм разбора типа „перенос- свертки" для грамматсски б. Доказательство. В силу леммы 5.6 при определении функций 7 и д пе возникает недоразумений. По определению множества Яс (А) всякий раз, когда делается свертка, свертываемая цепочка а, служит основой некоторой цепочки (!а,агшг. Если бы она оказалась основой какой-нибудь другой цепочки (!'а,а,свг', то нарушилось бы ОПК-условие.
Единственный трудный момесст— доказательство того, что выполняется условие (3) определения ОПК-грамматики: (х!()у!. Нетрудно показать, что в качестве выводов в ОПК-определении можно взять выводы цепочек (!аса,свг и ()'аса,исг' (в любом порядке), так что условие (3) выполняется. В алгоритме А = (7', у), построенном алгоритмом 5.17, функции 7 и д зависят, очевидно, только от ограниченной части цепочек, которые могут быть их аргументами, хотя в различные моменты приходится рассматривать подцепочки различной длины. Приведем реализацию обеих функций 7 и д в виде дерева реше- 487 вл. дпигие клкссы гРАммвтик ) (а„е) Е )а, е) Окаичеиие певички а Гл.
Б. Одпопроходнып синтАксический АнАлиз Без БОББРАтов ний. Сначала для данных цепочек — и в магазине и х на входе- можно пойти по ветви, соответствующей первым л символам цепочки х. Пегом для каждой такой цепочки из п символов можно начать просматривать я в обратном направлении, на каждом шаге решая, продолжать ли просмотр далыпе или объявить об ошибке, переносе илн свертке. Если объявлена свертка, то у нас достаточно информации, чтобы точно сказать, какое применить правило, так что в дерево решений можно вкл)очить и функцию й.. Для принятия решений можно также использовать обобщенный алгоритм Домелки (см.
упражнения равд. 4.1). Пример 5.43, Рассмотрим грамматику б с правилами (О) 5 5 (1) 5- Ол (2) 5 — 15 (3) А — ОА (4) А — ! Это (1,0)-ОПК-грамматика. Для вычисления множеств Я(А), Я(5) и а))Г нам нужно множество цепочек длины 3 или меньше, которые могут встречаться в активных префиксах правовыводимых цепочек и содержать иетерминал. Это множество состоит из цепочек $5', $5, $0А, $15, ООА, 1!5, 10А и их подцепочек.
Теперь вычисляем У1,е(5') = (($, 5, е)) Яс,а(5) — — — (($, ОА, е), ($, 15, е), (1, ОА, е), (1, 15, е)) .а),е(л) =-((О, Ол, е), (О, 1, е)) Множество,Л' состоит из пар (сс, е), где и — любая из цепочек $, $0, $00, 000, $1, $11, $10, 111, 100 и !1О. Функции 1 и д приведены на рис. 5.17.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
