Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 84
Текст из файла (страница 84)
а~ьЬ, то оиа называется псевдораздсленной. Для псевдоразделенной грамматики 6 = ([А[, Х, Р, 5) определим состветстврюа]ай пРостой МП-Распознаватель Мо:=:(Х, Х, 6, 5), у которого Х И (5) — входной алфавит ($(Х), ]х] — магазинный алфавит, 5 — начальный символ магазина и 6 — функция, отображающая (Х [) (5))м Ь( в ]А[*К(0, 1) (она описывает один такт его работы). Функция 6 задается равенствами (1) 6 (а, Л) =- (я, !) тогда и только тогда, когда правило А--ая принадлежит Р; (2) 6(Ь, А) =-(е, О) тогда н только тогда, когда А — е принадлежит Р и в Р нет правила вида Л 66. В парах (я, 1) и (е, О) вторая компонента указывает соответственно на наличие сдвига входной головки и его отсутствие.
Для всех гсаХ* и у Е Ь]* почожим (агс5, Лу) [ — (гс$, яу) в случае (!) и (Ьге$, Лу) ) — (Ьгс5, у) в случае (2). Кроме того, если в равенстве (2) Ь =-$, положим (5, Ау)] — (6, у). Языком 1. (М ), распознаваемым Мо, назовем множество (гав Х'](гол, 5)] — *(5, е)). Заметим, что если гс»-'7. (Мо), то длЯ цепочки гс вычисление Мо соответствует ее левому выводу в 6 и гвЕВ(6), т. е.
х.(МО) ~:-7. (6). Но пе обязательно В(МО) --Е(6). Пример !. Пусть 6,— псевдоразделенная грамматика с правилами 5 — а5А) е А- а(Ь 409 ГЛ. Б. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ ВЕЗ ВОЗВРАТОВ дополнение Тогда Ма =((а, Ь), (Я„А), 6, 5), где 6(а, Я) =-(ЯА, 1) 6(Ь, В) =(е, О) 6 (8, 5) =(е, 0) 6 (а, А ) =- (е, ! ) 6 (Ь, А) =-(е, 1) Легко убедиться, что Е (6) = (а"х1н) О, х Е (а, Ь)", ( х ( = а) н Е (Мо) = (е) 1..1 (а "Ьу ( п ) 1, у б (а, Ь)', ( у / = и — Ц.
Для цепочки аа5 распознаватель Мо сделает последовательность тактов ,'(аа3, 5) )- (ай, ЯА) ',— (3, ВА А) ( — (3, АА) Сравним эту последовательность с левым выводом цепочки аа в грамматике 6: 5,>, аЯА ~, аА =О, аа Если Е(МО) — --Е(6), то распознаватель Мо распознает в точности язык Е(6), т. е. он, так сказать, адекватен грамматике 6 и, если снабдить его выходом, станет анализатором для 6, будет строить левые выводы всех цепочек из 7.
(6). гз Определение. Псевдоразделенная грамматика 6 называется слаборазделенной, если Е(6) =Е(М,) для соответствующего простого МП-распознавателя Мо. Пример 2. Грамматика 6, с правилами 5 — а5А (е А — 61е слаборазделенная и Х,(6,)=(а"ЬА10(й(п). Г) Упр. 1. Для произвольной КС-грамматики 6 постройте эквивалентную ей грамматику 6' в слабой нормальной форме Грейбах. Упр. 2. Для простого МП-распознавателя Мо, соответствующего псевдоразделенной грамматике 6, постройте такой ДМП-автомат М, что Е, (М) =-Е(МО) $. **Упр. 3.
Докажите, что ие существует алгоритма, распознающего по произвольной КС-'грамматике, является ли она слабо- разделенной. Определение. 1-слаборазделенной грамматикой называется псевдоразделенная грамматика 6 = (К, Х, Р, Я), для которой выполняется следующее условие: если Р содержит правила А —" е и А — аа, то не существует такого ВЕ Ь( (в том числе и В=А) что Р содержит правило В ар, 5=>,*1ИАуВ6 и у~*е. Если В=А допускается, грамматика 6 называется 2-слаборазделенной.
410 упр. 4. Покажите, что 2-слаборазделенная грамматика является слаборазделенной. упр. 5. Покажите, что 1-слаборазделенная грамматика является ЕЕ (1)-грамматикой. упр, 8. Покажите, что для каждой Ы. (1)-грамматики можно построить эквивалентную ей 1-слаборазделенную грамматику. упр, 7. Покажите, что существует 2-слаборазделенная грамматика„которая ие является 1-слаборазделенной. Указание, Рассмотрите грамматику 6, из примера 2. Упр. 8. Постройте алгоритмы, проверяющие, является ли КС-грамматика 6 (а) !-слаборазделенной, (б) 2-слаборазделенной.
"*Упр. 9. Покажите, что (а) существует детерминированный язык, который не является слаборазделенным, (б) существует слаборазделенный язык, который не является 2-слаборазделенным, (в) существует 2-слаборазделенный язык, который не является 1-слаборазделенным (т. е. ЕЕ (1)-языком в силу упр. 5 н 6). В работах Вельбицкого и Ющенко [19701 и Вельбнцкого 11973) определены два метаязыка, предназначенные для описания детерминированных распознавателей, использующих один или несколько магазинов (онн названы соответственно СМ- и К-метаязыком, причем второй язык является некоторым уточнением и развитием первого).
Ограничиваясь случаем одного магазина, мы определим здесь метаязык (назовем его СМК-метаязыком), охватывающий основные черты этих формализмов. Программа распознавателя, записанная на СМК-метаязыке, состоит из команд, роль которых аналогична роли команд ДМП-автомата (если 6 (о, а, 2) = (а'„у) интерпретировать как команду) или операторов метаязыка Флойда — Эванса (равд. 5.4.4). Задаются конечный алфавит состояний К (он же будет магазинным алфавитом), входной, или терминальный, алфавит Х, и каждая команда записывается в виде ж;ин й-а — + Х где й ЕК, арХ 11(е), у ~ К*, ХЕ К О (р) (причем РАК) и В';— обозначение операции, Выполняемой командой над копфигураиней распознавателя.
Конфигурация имеет вид (Ь, ю$, а), где. Е К вЂ состоян распознавателя, ю Е 2* †необработанн часть 411 гл. 5. ОднОНРоходнып синтхксическип Анхлиз зез вОзвРАтов ДОПОЛНЕНИЕ входной цепочки, аЕК' — цепочка в магазине (будем считать, что верхний символ расположен слева), $ — правый концево;( маркер ($ ~ Х 0 К), Существует два типа операций, обозначаемых )Р( и )Р„и соответственно два типа команд. Команда первого типа в случае Х=-й' а К применима к конфигурации (й, ац)ч, а); в результате она дает конфигурацию (Й', ц)9, уа), т. е. к содержимому магазина приписывается у (или ничего, если у=-е) и, если аЕХ, сдвигается входная головка. В случае Х=р, она применима к конфигурации (Й, ап)К, Й'с(), если у=.е, и (й, ац)ь, а), если у-;й"у', Для первой конфигурации опа дает (й', и)З, а), т.
е. нз магазина извлекается очередное состояние. Для второй конфигурации она дает (Й", ц)$, у'а), т. е. Очередным состоянием становится первый символ цепочки у, а остальная ее часть помещается в магазин. Команда второго типа имеет вид Ме (е) Й а — >й' где гЕ К и й' ЕК.
Она применила к конфигурации (й, ац)ч, га) и дает (Й', И,, а), т. е. она применима, если г — верхнии символ магазина, и в этом случае она удаляет его из магазина. Заметим, что применимость команды второго типа зависит от содержимого магазина, а первого типа †н. Символ, стоящий слева от знака †, образует левую часть команды. Команду с левой частью й назовем й-командой.
Последовательность й-команд (Те) я' (т*) )Р. (т ) будем называть й-комплектом, если из агЕХ и (<у следует, м.(т) что а(ЕХ. Будем записывать его в виде й а, — '-> Х,)...) а„— > Хео Заметим, что команды й-комплекта упорядочены так, чтобы команды с а(Е Х предшествовалн командам с а;=е. Определение. СМК-распознавателем назовем пятерку М = =(К, Х, )г, Й„(), где К вЂ” алфавит состояний (он же магазинный алфавит), Х вЂ” входной, или терминальный, алфавит, не пересекающийся с К, )() — конечное множество й-комплектов (пе более одного для каждого й), Йе Е К вЂ” начальное состояние, ) Е К— заключительное состояние. Если первая из команд Й-комплекта распознавателя М, при" менимая к конфигурации (й, ц)З, у)„дает (й', 'и)'Ъ, у'), будем писать (Й, ю$, у) ) —,и(й', а)'Ь', у').
Языком, определяемым распознавателем М, назовем множество 1 (М) =((оЕХ*)(й„, ыФ, ))(-м(1, Э, в)) Пример 3. Рассмотрим СМК-распознаватель М = ((й„ й„ 1), (а Ь), Д, Йее 1), в котоРом й) состоит из комплектов и, (А,) (Р,(е) й,-а — >й,) в — ->р и, (е) ж, (е) й, Ь вЂ” >р)е — >р для входной цепочки ааЬ$ распознаватель М сделает такую последовательность тактов: (Й„чаЬ$, 1) « — (й„аЬй, й)1) (Йе, ЬЭ, й,й,)') «-(й",, Ь$', й',1) «- (й,', й, '~) ' «-(1, $, е) Определение. СМК-распознаватель назовем слабым, если все его команды первого типа.
Для слабого СМК-распознавателя М.=(К, Х, )х, Й„Г) определим соответствующую КС-грамматику 6м-=(г), Х, Р, Ь), пои, (т) ложнв г)=-К, л' —.Й„ндля каждой команды из)() вида Й-а — >-й' )Р, (т) включив в Р правило й — ай'), а для команды вида й а — — >р— правило й — ау. Пример 4. Распознаватель М из примера 3 слабый и ему соответствует КС-грамматика й, — ай,й, ~)в й,— Ь) е Она получается из грамматики примера 2 очевидным переименованием нетерминалов. сз Легко видеть, что если ц)Е1. (М), то каждый шаг слабого СМК-распознавателя М соответствует шагу левого вывода цепочки и) в грамматике 6 о на котором применяется соответствующее правило. Следовательно, Е(М) =Й(6м).
Но не обязательно ь(М) ==.Й(6„). Слабый СМЙ-распознаватель М назовем адекватным, если Л(М) =Й(6м), Упр. 1О, Покажите, что если в каждом й-комплекте слабого СМЙ-распознавателя М отбросить для каждого аЕ ХО(с) все (Р, (т) правила вида й-а — >Х, кроме первого, то получится распознаватель М', эквивалентный М; Упр 11. Покажите, что если у слабого СМ)х-распознават еля М команды вида й-в — +Х удовлетворяют условиям у=в ж~ (7) нХ=Р,„ 413 ГЛ. 5. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ ВЕЗ ВОЗВРАТОВ ДОПОЛНЕНИЕ 414 Рис. Д.с, КС-диаграмма. (а) соответствующая КС-грамматика 65, псевдоразделенная, (б) М эквивалентен простому МП-распозпавателю М' = Мо АС' соответствующему грамматике 6м, и, значит, М адекватен тогда и только тогда, когда 65,— слаборазделенная грамматика. Вгка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
