Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 101
Текст из файла (страница 101)
Но в Р' не должно быль правила 5- 5. Обращаем внимание читателя па то, что Е(6) с:-Е(6,) и, вообще говоря, Е (6,) может содержать цепочки, не принадлежащие Е(6). Теперь опишем алгоритм типа „перенос — свертка" для грамматик операторного прсдшествования. Алгоритм 5.19.
Построение анализатора, использующего операторное предшествовапие. Вход. Грамматика операторного предшествовапия 6 = (Ь(, Х, Р, 5). Выход. Алгоритм разбора 4=(1, д) типа „перенос — свертка" для грамматики 6,, 496 з.и друГИЕ КЛАССЫ Грлммлтик Метод. Пусть 5 обозначает 5 или е. (1) 7(ар, Ь)=--перенос, если а(Ь или а Ь. (2) 1(а(1, Ь) =-свертка, если а) Ь. (3) !'(65, $)=допуск. (4) !'(а, зо)=-ошибка в остальных слччаях.
(5) д(а5ЬТ, 4о) = 4, если (а) р — это 5 или е, (б) а чс Ь, (в) отношение выполняется между последовательными терминальными символами цепочки у, если они существуют, (г) 5 ()ЬТ вЂ” правило с номером 4 грамматики 6,. (6) 8(4с, зо) =ошибка в остальных случаях. ! ) Применение алгоритма 5.!9 к грамматике 6 продемопстри- ровацо на примере 5.46. Для доказательства корректности алго- ритма 5.19 нам понадобятся две леммы. Лемма 5.7. Если и — правовыводимая цепочка операторной грамматики, то а не содержит смежных нетерминалов. Доказательство. Элементарная индукция по длине вывода цепочки а. Г') Лемма 5.8. Если а — правовыводимоя цепочка операторной грамматики, то символ, расположенный непосредственно слева от основа, не может быть нетерминалом.
До к аз ат ел ь ство. Если бы этот символ был нетерминалом, то правовыводнмая цепочка, к которой свертывается и, содержала бы два смежных нстерминала. ! 4 Теорема 5.26. Алгоритм 4=-(Г, д), построенный алгоритмом 5,19, привильно выдает остовные разбора всех цепозмк языка Х. (6). Доказательство. В силу следствия из теоремы 5.25 первое встреченное отношение ) и предыдущее ( правильно выделя4от основу, Лемма 5.7 оправдывает условие, что () может быть только 5 или е (а не любой цепочкой из 5').
Лемма 5.8 объясняет, почему в пункте (5) р включается в основу. ( ) $.4.4. Язык Флойда — Эванса То, чем мы сейчас займемся, не новый алгоритм разбора, а скорее язык, па котором можно описывать детерминированные (безвозвратные) алгоритмы нисходящего н восходящего анализов. Он называется языком Флойда — Эванса. С помощью этого синтаксического метаязыка было реализовано несколько компи- 497 ГЛ. э. одионроходпыя сиитАКсичесКии лиАЛИЗ Иез вОЗВРАтав Э Ч ДРУГИЕ КЛАССЫ ГРАММАтич ляторов. Этот язык не совсем правильно называют еще языкоь1 продукций или правил, так как операторы языка не связаны рамма, написан.
с определенпымн правилами грамматики. Программа, ная на языке Флойда — Эванса, определяет алга итм азб п ннимаю й р щи решения под воздействием управляющего ст ойства с конечной памятью '). Анализатор, записанный на языке Флойда — Эв ставляет соб о "да — ванса, предопе ато т собой список операторов определенного вид . К а. аждыи состоя р р имеет метку, и эти метки можно рассматр м тривать как ран ния управляющего устройства. Предполага я, р аботают раторы не могут иметь одну и ту же метку. Опера над входной цепочкой и магазином и п иво торы строению правого разбора.
Текущее состояние процесса анализа можно представить в виде конфигурации (в, 9Х ...Хю а,...а„й, я) где ( ) и — метка текущего активного оператора; 1 ( ) м...Х,— содержимое магазина, причем Х,— верхний символ (6 — маркер дна магазина); (3) а,... а„— необработанная часть входной цепочки (6 используется такхсе в качестве правого концевого марк.р 4 ркера входной (4) я †готов к данному моменту часть выхода анализатора; ожидается, что полным выходом будет правый разбор входной цепочки для некоторой КС-грамматики. Оператор яаана Флойда — Эванса имеет внд <метка>: сх)а — р) <действие>в <следующая метка> причем метасимволов — и в может не быть.
Допустим, что анализатор находится в конфигурации (с.1, уа, ах, л) и оператор 1.1 имеет вид Ы: сс(а- р) выдача звЕ2 ч ч ного обобщении понятия алгоритма тнпв „перенос — свв н '", сй(д)- . : у у 'рввлиющсс устройство с конечной памятью, в аволннтельную инфо мэпию х у фор, 'раннг в мвгвэиие. Симой общей моделью влгорнтчв в давали '- эсого тнпв следовало бы считать ДМП-п(юабрвэователь. О нвн . 3 4 мы видели, что ДМП-п е ь.
днако в равд. входной пеночки, ел ДМП-преобразователь вовсе не ьобнэвн проводить разбоР д вн свергни в соответствии с грвмматнной, дли внвлиэв рвэд. 5.3 н 5.4. которой он преднвэивчен, иви это делал 1м(й)-влгорнтм и элгар тмы нэ и (19661. Этот оператор говорит о том, что если наверху магазина ожена цепочка я и а — текущий входной символ, то надо заменить а на р, выдать цепочку з, сдвинуть входную головку на один ин символ вправо (на э1о указывает наличие символа и и перейти к следующему оператору 1.2.
Анализатор перейдет, таким образом, в конфигурапию (Е2, уб, х, яэ). Возможно, что и=-е. В этом случае текущий входной символ игнорируется, но о головка сдвинется с него, если есть символ и. Если оператор Е1 нельзя применить из-за того, что и н и е совпадает с верхней частью магазина или а не является теку- входным символом, то делается попытка применить опера- а !. тор, непосредственно следующий в списке операторов за ~ . Обе метки у оператора тоже не обязательны (хотя для того, чт обы обозначать операторы в конфигурациях, предполагается, и» что они имеют имена).
Если отсутствует символ —, то магаз не меняется, и поэтому нет смысла указывать р. Если опущен символ в, то входная головка нс сдвигается. Если опущена <следующая метка>, то после данного оператора применяется следующий в списке. Другие возможные действия — допуск и ошибка. Если место, предназначенное для действия, пусто, то не надо делать ничего, кроме распознавания входного символа и замены в магазине. Первоначально анализатор находится в конфигурации (1., Б, сп$, е), где сл — анализируемая входная цепочка и 1.— выделенный оператор.
Затем последовательно проверяются операторы, пок ока среди них не найдется применимый. После выполнения е всех действий, предписываемых этим оператором, управлени передается оператору, указанному меткой. Анализатор продолжает работать до тех пор, пока не выполнится действие ошибка нли допуск. Выход принимается во внимание только в случае допуска. й(ы покажем, как с помощью языка Флойда — Эванса описываются алгоритмы типа „перенос — свертка", но обращаем внимание читателя на то, что этот язык можно использовать идля реализации нисходящих алгоритмов разбора. Итак, предполагается, что можно писать сс =- а,ссэссв и р = сс,Апв или сс Аа а, если есть гю При этом А — сс,— правило грамматики, а для которой предпринимается разбор, а выход з — номер этого правила.
Язык Флойда †Эван можно модифицировать так, чтобы действиями стали некоторые „семантические процедуры", Тогда вместо того, чтобы выдавать разбор, анализатор будет выполнять синтаксически управляемую трансляцию, вычисляющую перевод нетермииала А в терминах переводов составных частей цепочки ссв. Система такого рода описана Фельдманом гл. з. одноппоходнып синтлксичнскии Анализ нез возвратов Бл. дРугие классы ГРАммАтик Пример 5.47. Запишем на языке Флойда — Эванса анализатор для грамматики 6, с правилами (1) Е- Е+Т (2) Š— Т (3) т Т Р (4) Т-Р (5) Р— (Е) (6) Р— а Символ 4~ играет роль представителя любого символа. Предполагается, что с обеих сторон стрелки он обозначает один и тот же символ. Начальным оператором служит 111.
10: ( ! рР (рр' ! 10 11: а !.де†Рде ! выдача 6 е 12: Тн Р~Е ! Т~ 13: Р,-~ ! выдача 3 1.4 выдача 4 14: т» 15: Е+ Т вЂ”,'б ! Ф=тнФ Е-Ф «10 1 7 выдача 16: Тф- — Еф. )выдача 2 17: Е+ Я вЂ” Е+уР! и 1.0 18: (Е) ! ф- Р т(е )выдача 5 е 12 19: $Е$ ! — )допуск 110: ! ошибка 111: )Ф- рР ! 1О Для входной цепочки (а+а)еа анализатор пройдет такую последовательность конфигурации: [1,1 1, $, (а+а)на$, е)! — [10, $(, а+а)на$, е) ! — [10, $(а, +а) на$, е) ! — [11, $(а, +а)еа$, е) 1 — [12, $(Р'+, а)еа$, 61 )- [ЬЗ, 1 — [Л4, ) — [15, 1 — [16, 1 — [Л7, )- [10„ ! — [1,1, )- [Е2, ) — [ЕЗ, 1 — [1,4, г- [15, ) — [17, $(Р+, а) на$, 61 $(Т+, а)на$, 64) $(Т+, а) еа$, 641 $(Т+, а)еа$, 64) $(Е+, а) еа$, 642) $(Е+а, ) еа$, 6421 $(Е+а, )еа$, 6421 $(Е+Р), еа$, 64261 $ (Е+ Р), е а$, 64261 $(Е+Т), еа$, 64264[ $(Е+Т), на$, 64264) $(Е), еа$, 6426411 [18 $(Е) еа$, 642641) ! [Г2, $Ра, а$, 64264151 [ГЗ $Р», а$, 64264151 [Г4 $Т н а$, 642641541 [ГО $Тна, $, 64264154! [г 1 $Т и а, $, 64264154[ [12 $ТеР$, е, 6426415461 ) — [Г4, $Т$, е, 6426415463! [1,о $Т$', е, 6425415463! [г.б, $Т$, е, 64264154631 [Г 7 $Е$, е, 642641546323 [1,6 $Е$, е, 64264154632) [19 $Е$, е 64264154632! ) — допуск (:) Заметим, что анализатор Флойда — Эванса можно промоделировать на ДМП-преобразователе, Поэтому любой анализатор Флойда — Эванса распознает только детерминированный КС-язык.
Но распознаваемый им язык может не совпадать с языком, определяемым грамматикой, для которой он должен строить разборы, поскольку передача управления операторами может привести к тому, что некоторые свертки не будут реализованы'). Пример 5.48. Пусть 6 состоит нз правил (1) 5- аЯ (2) 3 — 5$ (3) Я- а 1 (6) = (а+ 5)*а. Приведем последовательность операторов, представлягощую собой анализатор, который з соответствии с грамматикой 6 разбирает цепочки из языка 5*а, ио не допускает других цепочек: ЕО: ),т' тг-' % 1.1: а! — Я )выдача 3 14 Е2: Ь! ! 10 ЕЗ: $! ! ошибка Е4: аЬ'! — $ ! выдача 1 14 Е5: 5$ ! — Я ! выдача 2 14 Еб: $3! $ $5$!допуск я.
Е7: ! ошибка ') Обсуждаемая здесь ситуация аналогична той, что рассматривалась п дополнении к равд. 5.1: анализатор Флойда-Эванса А)о, построенный по грамматике С, может быть не адекватен С, т. е. Ь(Мо) Ф Ь(С).— Прим. персе. 501 5ЗЬ ДРУГИЕ КЛАССЫ ГРАММАТИК ГЛ. 5, ОДНОПРОХОДНЫГГ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ Для входной цепочки Ьа анализатор сделает такую последовательность шагош иоииенсмна.сдадоднае ераээмагпннн однаэнан Цепочка Ьа допускается после выполнения оператора Е6. После- довательность шагов для цепочки аа такова: аиаеааируемме пофпойду-Эданау аперагпориоаа реднэеопдадаиаи [ЕО, $, аа$, е11 — [Е1, $а, п$, е1 1 — [Е4, $3, а$, 31 1 — [Е5, $3, а$, 31 ) — [Е6, $3, а$, 31 1 — [!7, $3, а$, 31 ьь Оператор Е7 объявляет об ошибке, хотя ааЕЕ(6). В примере 5.48 ничего мистического нет.
Программа анализа;ора, написанная на языке Флойда — Эванса, пе так тесно свя!Зна с грамматикой, для которой Она производит разбор, как )ругие алгоритмы этой главы со своими грамматиками. [ 1 раааираи ! про даэесгпд одран!амме сиадоа э ' првдагеспдадаиаа В гл. 7 мы дадим алгоритм, механически порождающий ана)изатор, написанный на языке Флойда †Эван, для обратимой рамматнки слабого предшествования. проопгаао преАиеаэгдо данаи '.4Л. Резюме Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
