Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 41
Текст из файла (страница 41)
!',) )-р (а„е, ?;...?;) ) — рзь(у„е, е) гДе Уг= 7', тогДа и только тогДа, когДа (д., ~, 2.)) — р (д, е, ?; " У, †,) для д Е Р и Уг...?; , Е Г". Следовательно, Е.,(Р') =-Т,(Р). Справедливо также и обращение леммы 2.22. Лемма 2.23. Пусть Р == (1С, Х, Г, 6, д„7„Я) — МП-автомат. Можно построить такой МП-автомат Р', что й(Р')=Т.,(Р). Д о к а з а т е л ь с т в о. Р' будет моделировать Р, используя в надлежащий момент специальный символ 7' находящийся на дне магазина. В тот момент, когда автомат Р' может прочесть 2', он будет переходить в новое заключительное состоянием .
Формальное построение оставляем в качестве упражнения. 1) а) для мп-аатомата, допуска|ощего язык опустошением магазяна, множество заключительных состояний обычно веретен пустым. Его, очевидно, можно сделать каким угодно. 202 2.$.3, Эквивалентность МП-автоматов и КС-грамматик С помощью полученных результатов можно теперь показать, что языки, определяемые МП-автоматами — это в точности КС- языки. Начнем с построения естественного (недетерминированного) „нисходящего" распознавателя, эквивалентного данной КС-грамматике.
Лемма 2.24, Пустил б = (Х, Х, Р, О) — КС-грамматика. ПО грамматике 6 можно настроить такой МП-автомат гг, ~, (л) = ь (с). До к аз а тел ь ство. Построим )т| так, чтобы ои моделировал все левые выводы в 6. Пусть Й=((|)), Х, ХОю, 6, д, О, |а'), где 6 определяется следующим образом: (1) если А — са принадлежит Р, то 6(д, е, А) содержит И,и); (2) 6 (д, а, а) = ((г?, е)) для всех аЕ Г. Мы хотим показать, что (2.5.2) А.О'ам тогда и только тогда, когда (Ч, и, А) ) — а (д, е, е) для некоторых т, и ь 1 Необходимость условия докажем индукцией пот.
Допустим, что А ~" и. Если т — — 1 и гп — — а,... а„(й ~ 0), то (г), а|...а», А) ) — (а, а,,а„, а,...а») ) †" (а, е, е) Теперь предположим, что А=;"ж для некоторого т>1. Первый шаг этого вывода должен иметь вид А ~Х,Х,,Х», где Х;=О |х| для некоторого и; < т, 1( | (Й, н х,х,...х» —— гп. Тогда Ц, т, А))-(д, гп, Х,Х,...Х„) Если Х,Е Х, то по предположению индукции (|), х„Х,) ) — е (г), е, е) Если Х;=х|б Е, то (|), хо Хг) ~ — (е, е, е) Объединяя вместе эти последовательности тактов, видим, что (Ч, и, А) ь —" (д, е, е).
Для доказательства достаточности покажем нндукцией по и, что если (а, и, А) ) — а(а, е, е), то А =рею. Если и =-1, то и=-е и А — е принадлежит Р, Предположим, что утверждение верно для всех и' (и, Тогда первый такт, 203 ГЛ. К ЭЛВМВНТЫ ТЕОРИИ ЯЗЫКОВ А => Х„...Х, => х,х,.',.Х, сделанный МП-автоматом В, должен иметь вид (д, и, А)) — (д, ю, Х,...Х„) причем (д, хо Х)) — "1(д, е, е) для 1(((й и ю=хх,...хь (лемма 2.20). Тогда А — Х,...ХА — правило из Р, и по предположению индукции Х;=>+х; для Х;ЕЬ). Если Х, б Х, то,=>'х;. Таким образом, =>' х,х,...х„;Х„ =о* Х Х ° ..ХА ХА = и — вывод цепочки и из А в грамматике 6.
Из (2.5.2), в частности, вытекает, что В~~ю тогда и только тогда, когда (4, ю, В) ) — (д, е, е). Следовательно, Е, ((т) = Е(6).П Пример. 2.34. Построим МП-автомат Р, для которого Е, (Р)= = Е (6 ), де 6 — наша обычная грамматика, определяющая Е арифметические выражения. Пусть Р =((4), Х, Г, 5, в„, 8), где й определяется так: (П 5 (у, в, Е) = ((4, Е+ Т), (4, Т)); (2) 5(4, в, Т) = (д, Т*Р), (д, Р)); (3) 5(д, в, Р)= (4, (Е)), (д, и)); (4) 5(ч, Ь, Ь)=1'(д, е)) для всех Ьб(а, +,, (,)). При входе а+а ча для Р возможна среди других последова- тельность тактов (в, а+ава, Е)) — (д, а+аэа, Е+Т) ) — (с, а+аьа, Т+ 7) )--(4, а+ива, Р+Т) ) — (д, а+аэа, и+Т) ) — (д, +ока, +Т) ) — (д, ава, Т) )--Ц, а о, Т*Р) ) — (д, а * а, Р н Р) ) — (д, аРа, аРР) )-(с, ьа, эР) ) — (д,а, Р) )-(д, а, а) ) — (д, с, е) Заметим, что вычисление МП-автомата Р соответствует левому выводу цепочки а+аэа из Е в КС-грамматике 6,, Кб.
АВТОМАТЫ Г МАГАЗИНПОИ ПАМЯТЬЮ Тип синтаксического анализа, проводимого для КС-грамматики МП-автоматом, построенным в лемме 2.24, называется „нисходящим анализом" („ анализом сверху вниз") или „предсказывающим анализом", потому что при этом дерево вывода строится по существу сверку (от корня) вниз, а каждый такт вида (1) можно трактовать как предсказание очередного шага левого вывода. Подробно нисходящий синтаксический анализ будет обсуждаться в гл. 3 — 5.
Можно построить расширенный МП-автомат, который работает „снизу вверх" как „восходящий анализатор", моделируя в обратном порядке правые выводы в КС-грамматике. Рассмотрим цепочку а+ а * а Е Е (6„) и ее правый вывод из Е в грамматике 6,: Е => Е + Т => Е+ Т з Р => Е + Т и о => Е + Р н а =>Е+аэа=>Т+а а.=>Р+аиа=>а+аиа Предположим, что мы записываем этот вывод в обратном порядке. Если считать, что переход от цепочки а +а э а к цепочке Р+ава происходит по правилу Р— а, примененному „в обратном направлении", то можно сказать, что цепочка а+ока „свертывается слева" к цепочке Р+ава.
Более того, это единственно возможная левая свертка. Подобным же способом можно правовыводимую цепочку Р+ава свернуть слева к цепочке Т+оиа с помощью правила Т вЂ” Р и т, д. Определим формально левую свертку. Определение. Пусть 6=(14, Х, Р, В) — КС-грамматика и О' =>, 'аАю.=.>, арт =->', хю — правый вывод в пей. Будем говорить, что правовыводимую цепочку арт можно свернуть слева (или что она левосвертывается) к правовыводимой цепочке аАт с помощью правила А— Указанное вхождение цепочки р в цепочку арф назовем основой цепочки арт. Таким образом, основа правовыводимой цепочки †э ее любая подцепочка, которая является правой частью некоторого правила, причем после замены ее левой частью этого правила тоже получается правовыводимаи цепочка.
Пример 2.35. Рассмотрим грамматику с правиламн  — Ас) Во А — аАЬ! аЬ В аВЬЬ ~ аЬЬ Она порождает язык (а"Ь"с) и-э)) 0 (а"Ь2™мй(п) 1). 205 ГЛ. Я. ЭЛЕМЕНТЫ ТЕОРИИ ЯЗЬПСОВ КБ. АВТОМАТЫ С МАГАЗИННОЯ ПАМЯТЬЮ Рассмотрим правовыводимую цепочку ааЬЬЬЫ. Единственная ее основа — подцепочка аЬЬ, так как аВЬЫ вЂ” правовыводимая цепочка. Заметим, что хотя аЬ вЂ” правая часть правила А — ОЬ, она не будет основой цепочки ааЬЬЬЫ, так как аАЬЬЫ вЂ” не правовыводимая цепочка. 1 ) Основу правовыводимой цепочки можно было бы Определить другим способом, сказав, что основа — это крона самого левого поддерева глубины 1 некоторого дерева вывода этой правовыводимой цепочки, (Дерево глубины 1, состоящее из вершины и ее прямых потомков, которые являются листьями, называют кустом или веером.) 1 ~! ! Рнс.
2,16. Отсечение основ. Дерево вывода цепочки а+аеа в грамматике 6, показано на рнс. 2.16,а. Самый левый куст состоит из самой левой вершины, помеченной Р, которая является его корнем, и кроны а. Если удалить единственный лист самого левого куста, то останется дерево, показанное на рис. 2.16, б. Крона Р+а на этого дерева и есть результат левой свертки цепочки а+аеа, а его основа — крона Р поддерева с корнем, помеченным Г. Опять удалив Основу, получим дерево на рис. 2.16,в. Описанный процесс свертки деревьев назовем отсечением основ. По КС-грамматике 6 можно построить эквивалентный расширенный МП-автомат Р, работа которого заключается в отсечении основ. Здесь удобно представлять себе магазин в виде цепочки, верхним символом которой является самый правый, а не самый левый символ. В силу этого соглашения конфигурации (расширенного) МП-автомата Р = (1Е'„ г', Г, 6, вю 2„ Р) определяются .Точно так же, как раньше, а отношение Г- несколько иначе.
Если 6(в, а, а) содержит (р, 6), то будем писать (в, аш, тсе)) — (р, ш, р(з) для всех шЕХе и уЕ 1". Таким образом, утверждение „6 (в, а, УУ) содержит (р, т'(Р'Х)" имеет разные смыслы в зависимости от того, справа или слева расположена верхняя часть магазина. Если слева, то верхними символами до и после этого такта будут 1' и У, а если справа, то верхними символами будут 2 и Х. Поданному МП-автомату, верхний символ которого расположен слева, можно построить МП-автомат, делающий то же самое, но с верхним символом, расположенным справа, просто записывая в обратном порядке все цепочки из Г*. Например, если было (Р, Р)еЯХ) Е 6(р, а, Р'2), то станет (Р, Х(Р')7) Е6 (д, а, 21').
Разумеется, нужно оговорить тот факт, что верх магазина находится теперь справа. Обратно, МП-автомат с верхним символом, расположенным справа, легко превратить в МП-автомат с верхним символом слева, Мы видим, что обозначение МГ1-автомата в виде семерки можно интерпретировать как два разных МП-автомата в зависимости от того, какой из символов — правый или левый — считается верхним, Нам кажется, что удобство обозначений, создаваемое этими двумя соглашениями, перевешивает возможность путаницы в исходных понятиях. В дальнейшем, если не оговорено противное, будем считать, что у обычного МП-автомата верх магазина расположен слева, а у расширенного †спра. Лемма 2.25.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
