Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 80
Текст из файла (страница 80)
Если Тл ь (и) =- (А — сг, <1'„1'„..., )' >), то найдется в точности одно правило А — а, которое можно применить на первом шаге вывода Ах~А ио для хЕЕ и ОЕТ". Каждое множество )'1 дает всевозможные префиксы длины, не большей й, терминальных цепочек, которые могут следовать за цепочкой, выводимой из ВО когда в выводе вида Ах=!>гах==.>лип, где хЕЕ, применяется правило А — а, где гг=х,В,х,В,х,,В,„х .
По теореме 5.2 6 =(1х(, В, Р, 5) не является (.(. (Ь)-грамматикой тогда и только тогда, когда существует такая цепочка сгЕ(Ы()Х)*, что (!) 5=->; юАа, (2) ГП!5Т»(ргх) !) Г(ВВТ»(усг)~ йу для некоторых Р=Р':у, для которых А — р и А у принадлежат Р. В силу леммы б.! условие (2) можно перефразировать так: (2') если Е=-Г!КВТ»(и), то пересечение Г)ПВТ»ф)»Р»Е и Г1ЦВТ»(у) ИР»Е непусто, 389 гл. е. аднопроходныи синтлксичвскии Анализ ввз ваза~Агав Е.!. Д>.
1А>-ГРАММАТИКИ ~аа) (Ьа) 3 — е аАаа Я вЂ” аАаа л — е ЬАЬа Теперь изложим алгоритм для Е1,(й)-грамматики 6, вычисляющий 1.1. (Ь)-таблицы, необходимые для построения управляющей таблицы. Следует заметить, что если 6 — 1.1,(1)-грамматика, то этот алгоритм может выдать более чем по одной таблице на петерминал. Однако анализаторы, строящиеся алгоритмами 5.1 и 5.2, очень похожи. На входных цепочках, принадлежащих языку, определяемому грамматикой, они, конечна, работают одинаково.
На других входных цепочках после того, как анализатор алгоритма 5.2 обнаружит оп>ибку, анализатор алгоритма 5.1 сделает, возможно, еще несколько шагов. Ал го ритм 5 2. Построен не 11. (Ь)табл и ц. Вход. 1.1. (й)-грамматика 6 =(Х, Х, Р, 5). Выход. Множество Я 1.1. (Ь)-таблиц, необходимых для построения управляющей таблицы для б. Метод. (1) Построить 11,(й)-таблицу Т„соответствующую 5 и (е). (2) Положить вначале "'= (Т,).
(3) Для каждой 1Е(й)-таблицы Т Ежа, содержащей элемент Т(и) =(А- хсВ,х>Ввхв...В„х, <У„У„..., У„)) Следовательно, если 6 — Ы (й)-грамматика и есть вывод 5=ос, и>Аа=р) и>х, то Тлсд(и) будет однозначно определять, какое правило применить к А, если и= Г1П5ТА(х) и 7.=Г)ЮТ„(а). Пример 5.14. Рассмотрим 11.(2)-грамматику 5 — аАаа ) ЬАЬа А- Ь)е Вычислим 1.1.(2)-таблицу Тз 1,>, которую обозначим Т,. Для правила 5 — аАаа найдем Г!ЮТ,(аАаа) 9,(е) =(аа, аЬ). Для 5 — ЬЛЬа вычислим Г!К5Тв (ЬЛЬа) 9, (е) = (ЬЬ). Таким образом, Т„(аа).--(5 — аАаа, У), где У=-Г1м5Тв(аа) 9, (е) =(аа)— локальное множество для А и аа — цепочка, расположенная справа от А в правиле 5 — аАаа.
Продолжая в том же духе, получаем Т, (табл. 5.1). Для каждой цепочки и~(а)-Ь)ев, не показанной в этой таблице, Т,(и) - ошибка. П Табеица б,1 включить в Ю 1-1. (А)-таблицу Твгг.для 1 =.1(т, если Твггр еще не входит в АТ. (4) Повторять шаг (3) до тех пор, пока в й можно включать новые таблицы. Пример 5.15. Построим соответствующее множество 11(2)-табчиц для грамматики Дадим алгоритм, которым можно построить корректную управля>ощую таблицу для 1Д.(/г)-граь>магнии 6 ио соответствующему ей множеству !.1 (й)-таблиц.
Управляемый этой таблицей й-предсказывающий алгоритм будет в качестве магазинных символов употреблять вместо нстерминалов 1.!.(Й)-таблиць>, Таблица б 3 А, >ас> ТА 1,.> Множества Праннло Множества и Правнло А — еЬ А — е Ьи А е ЬЬ А — Ь Алгоритм 5.3. Управляющая таблипа для 11(й)- грамматики. Вход. 1.1.(й)-грамматика 6=(>ц, Х, Р, 5) и соответствующее ей множество ж Щй)-таблиц. Выход. Корректная управляющая таблица М для 6. Метод. М определяется на множестве (,.'Г(>Х П (Я) и Х'" следующим образом: (!) Гели А х,В,х,В,х,...Вжх — правило из Р с номером 1 " >А, даат, то для всех и, для которых Т> > (и)=('! хоВ хаВ х ...Вжх,, (Ут, Ув, ..., У е) '>слагаем М(ТА „, и) =-(хнТвнг,х,Та,,г,х,...Тв,г х, 1).
391 5 — аАаа) ЬАЬа А — Ь>е Начнем с Ь' =(Тз,>а>). Так как Тз и>(аа)=(5 аАаа, (аа)), то в а надо включить ТА, 1,. Аналогично, так как Т, (ЬЬ) -: (5 — ЬАЬа, (Ьа)), то в,Р нужно также включить Тд >е,>. (Элементы 11.(2)-таблиц Тл, 1„> и ТА, >в,>, отличные от значения ошибка, приведены в табл. 5.2.) Сейчас,ыТ =(Тз „>, Тд 1„,>, Т„>вн>), и алгоРитм 5.2 Уже не может включить в ат новых таблиц, так что эти три 1.1.(2)-таблицы образуют множество, соответствующее грамматике 6. ГЛ. Б. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ ВЕЗ ВОЗВРАТОВ (2) М(а, ао) =-выброс для всех РЕХ*'"-".
(3) М(Я, е)=допуск. (4) В остальных случаях М(Х, и) =ошибка. (5) Тв, !.! — начальная таблица. П Лример 5.16. Построим управляющую таблицу для ЬЬ(2)- грамматики (1) 5- аАаа (2) 5 ЬАЬа (3) А — Ь (4) А -- е используя соответству(ощее ей множество ЬЬ(2)-таблиц, найденное в примере 5.15. Алгоритм 5.3 выдаст управляющую таблицу, ев аЬ а бв вв Ь в т, Т1 Ряс. б.б. Управляюц(ая таблица.
изображенную на рис. 5.5, где Т, = Тз (,!, Т, = Тл „,! и Т, =ТА (ы!. Подразумевается, что в пустых ячейках ошибка. Для входной цепочки ЬЬа 2-предсказывающий алгоритм про. делает такую последовательность тактов: (ЬЬа, ТД, е) 1 — (ЬЬа, ЬТ,ЬОЦ, 2) ) — (Ьа, ТеЬО5, 2) )- (Ьа, Ьа$, 24) )- (а, а$, 24) ( — (е, 5, 24) () Теорема 5.5.
Алгоритм 5.3 строит для ЬЬ(й)-грамматики 6 =. (Ь), Х„Р, 5) корректную табли!4у, управляющу!о работой соо1пветствующегп й-предсказв1вающего алгоритма разбора. Д о к а з а т е л ь с т в о. Доказательство аналогично доказательству теоремы 5.4. При построении ЬЬ(й)-таблнц для произ- 5.1. 1.1.
(Й)-ГРАММАТИКИ Вольной КС-грамматики могут возникать конФликты, упомян тые при Определении таблицы Тл с (пункт (3)). Но если ЬЬ(й)-грамматика, то конфликтов ие будет, так как если А р и А у принадлежат Р и 5=;>1 (РАс(, то (Г1КЗТ, (р) Ю А Г(ЮТА (а)) П (ГПЮТА (у) ВР А Г1КЗТ„(сс)) = 8 При построении ЬЬ(к)-таблиц, соответствующих грамматике 6, таблица Тл с вычисляется только тогда, когда 5 =>! (РАи и Ь=Г1Г(ЗТА(и) для некоторой цепочки (х, т. е.
Ь вЂ” локальное множество для А. Поэтому если и~Ь, то существует не более одного правила А — 5, для которого и Е ГИЗТА(5) 9АЬ. Зададим гомоморфизм й на множестве в1 11 Х равенствами й(а)==а для всех абХ и Ь(Т).=А, если Т вЂ” Ь (к)-таблица, соответствующая Л и Ь. Заметим, что у каждой таблицы из ' есть хотя бы один элемент, содержащий правило, и А однозначно определяется таблицей Т.
Теперь докажем, что (5.1.2) 5 „=> хс( тогда и только тогда, когда найдется такая цепочка (х'~(',"1)Х)', что Ь(а')==а и (ху, ТЯ е) )-" (у, с('5, я) для всех у, для которых а=.-'>" у, где Т,— 1 Ь(я)-таблица, соответствующая 5 и (е). Достаточность. Из способа построения управляющей таблицы следует, что когда выдается номер ! правила Л вЂ” 5, алгоритм разбора заменяет таблицу Т, для которой Ь(Т) — -- А, такой цепочкой р', что 11(р')=р. Таким образом, эту часть утверждения (5,1.2) можно доказать прямой индукциеи по числу тактов работы алгоритма разбора. Необходимость. Здесь мы покажем, что (5.1.3) если А .~х, то алгоритм разбора! Нродслает послсдовательность тактов (ху, Т, е) )-' (у, е, н) для л!обой ЬЬ(й)-таблицы Т, соответствующей А и Ь, где Ь =. Г(ЙЗТА(а) для некоторой цепочки с(, для которой 5~! (РАа, н у ЕЕ. Доказательство проведем ипдукцией по длине цепочки и.
Если А 1~а,а,...а„, то (а,а,...а„у, Т, е) ) — (а,...а„у, а,...апс !) посколькуТ (и) — (А — а а,...а„1З)длявсех и~ Г1КЗТ,(а а,...а„) ВАЬ. Тогда (а,...а„у, а,...а„, !) ,'— "(у, е, 1). Теперь предположим, что утверждение (5.!.3) верно для всех левых выводов длины, небольшей1, и пусть А !~х,В,х,В,х,...В,„х„и В, =эу, де (~ )с 1 Тсцда (хух .. у х у Т е)~ (х,у,х,...у ХРТ(х1...Т х, 1), так как Т(и) . (А — х,В,х,,В„х, 393 и.!. 1.1.
!11-ГРАммАтики Таблица Дз М ножес1вв Правнао 1!Равнао Множества 5 —. с 5 — аЬА 5 е 5 аЬА аа аь е аЬ (аа) т, Правнао Множества (аа) (аа( А — Ь А — е 5аа А — а 5аа (аа) аЬ (аа) Ьа т, т! 395 394 ГЛ. 3. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ ВЕЗ ВОЗВРАТОВ <1'О ..., )'ж>) для всех и~Р1НЗТА(Х,В,Х,...Вжх ) ЮАЕ. Каж дая таблица 'Т,— это 1.1.(й)-таблица, соответствующая В, и )л (1(1(т), так что предположение индукции выполняется для каждой последовательности тактов вида (УЗХТ...У х У, Т,, е) ~- '(х,...Ужх У, е, и1) Вставим такты, на которых из магазина выбрасываются х; тогда (х,у,х,у,х,...ужх у, Т, е) 1 — (х,у,х,у,х,...у„х у,ч х,Т,х,Т„х,...Тжхвп 1) ( —.*(УахсУвха...УжхжУ, Т!х!Тех!...Тжх,, 1) (-'(Х!Уаяе...У„Х У, Х,Т,Х,...Т Х„, 1П1) (-е(У, Е, !Пала Пж) Из утверждения (5.1.3), в частности, вытекает, что если Он=->!с, то (1с, Тв$, е), *(е, $, и).
с1 Пример 5.17. Рассмотрим 1.1.(2)-грамматику Ва с правилами (1) 5 е (2)  — аЬА (3) А — Яаа (4) А- Ь Построим сначала соответствующие 1.1(2)-таблицы. Начнем с Т,=ТЗ „! (см. табл. 5.3). Затем по Т, найдем Т, =-Тл,1„1, потом Тв=-ТЗ,„,! и, наконец, Т,=-ТА <„!. По этим 1.1 (2)-таблицам получим управляющую таблицу, показанную на рис. 5.6. 2-предсказывающий алгоритм, управляемый этой таблицей, разберет входную цепочку аЬаа, проделав такую последовательность тактов: (аЬао, Та$, е) )-(аЬаа, аЬТ,$, 2) ) — (Ьаа, ЬТ,$, 2) ~ — (аа, Т,$, 2) ( — (аа, Т,аа$, 23) ( — (аа, аа$, 231) ( — (а, а$, 231) (-(е, $, 231) В заключение этого раздела покажеь1, что й-предсказывающий алгоритм разбирает кажду!о входную цепочку за линейное время. Теорема 5,6, Число шагов, выполняемых й-предсказывающим алгоритл1ом с управляющей таблицей, построенной' алгоритмом 5.3 по 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
