Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 34
Текст из файла (страница 34)
Доказательство непроти- воречнвости этого упорядочения оставляем в качестве упражнения, Надо лишь показать, что либо любые две вершины упорядоченного дерева лежат на одном пути, либо одна из них расположена левее другои. Определение. Кроной дерева вывода назовем цепочку, которая получится, если выписать слева направо метки листьев.
Например, кроны деревьев выводов, показанных на рис. 2.8, таковы: (а) 5, (б) и, (в) аЬаЬ н (г) аЬаЬ. Покажем теперь, что деревья выводов адекватно представляют выводы в том смысле, что для каждого вывода выводимой цепочки и в КС-грамматике 6 можно построить дерево вывода в 6 с кроной а, и обратно. Для этого введем несколько новых понятий. Пусть  — дерево вывода в КС-грамматике 6= =-(М, Л, Р,5).
Определение. Сечением дерева В назовем такое множество С вершин дерева В, что (1) никакие две вершины из С не лежат на одном пути в В, (2) пи одну вершину дерева В нельзя добавить к С, не нарушив свойства (1). Пример 2.20. Множество вершин дерева, состояц1ее из одного корня, является сечением.
Листья тоже образуют сечение. Еще один пример сечения — множество ца рис. 2.9, состоящее из вершин дерева, обведенных кружкамв. С) Определение. Определим крону сечения дерева В как цепочку, которая получается конкатенацией (в порядке слева направо) меток вершин, образующих некоторое сечение. Например, аЬа5Ь5 — крона сечения дерева вывода, показанного на рнс. 2.9, гл, 2, а.чеманты таорин языков Лемма 2.12. Пусть 5=я„я„..., я„— вывод цепочки яв из 5 в КС-грамматике 6=-(1», 2, Р, 5). Тогда в 6 можно постротпь дерево вывода О, для которого яв — крона, а я„я„..., я„4— нвкоторьм из крон сечений. Д о к а з а т е л ь с т в о. Построим такую последовательность деревьев выводов О; (О» 4. и), что я,— крона дерева Оо Пусть Π— дерево, состоящее из единственной вершины, помеченной 5.
О Допустим, что я4=(),Ау; и после прил~енепия правила А- Х,Х, ... Х» к выделенному вхождени1о А получается Яь.,=-рьХ,Х» ... Х»ур Тогда дерево О;„получается из Ог добавлением к листу, помеченному выделенным вхождением А (он является (1р;1-1-1)-и символом кроны дерева О,), й прямых в 3 У~ 42 Л Х ...Д4» в 114» Рнс, 2.10. Построение дсрсвьсв выводов. потомков, которые помечаются Х„Х„..., Х» соответственно. Очевидно, что кроной дерева О;4, будет я„,. Построение О,„ по О, показано на рис. 2.10.
Дерево О„ будет искомым деревом вывода О. ь1 Докажем обращение леммы 2.12, т. е. покажем, что для каж- дого дерева вывода в грамматике 6 существует хотя бы один соответствующи й вывод. Лемма 2.13. Пусть Π— дерево вывода в КС-грал~митинг 6= =(М, г', Р, 5) с кроной я. Тогда 5=>*я. Доказательство. Пусть С„С,, С„...,ф— такая после- довательность сечений дерева О, что (1) С, содержит только корень дерева О, (2) С;„для 0»4 < и получается из С; заменой одной нетер- мнпальной вершины ее прямыми потомками, (3) Св — крона дерева О.
Ясно, что хотя бы одна такая последовательность существует. Если сс; — крона сечения Со то я„я„..., я. — вывод цепочки я„из я, в 6. ьз Среди выводов, которые можно построить по данному дереву, два вывода нас особенно интересуют. 2 4 контекстно своводныи языки Определение.
Если в доказательстве леммы 2.13 сечение С24, получается из С, заменой самой левой нетерминальной вершины в С4 ее прямыми потомками, то соответствующий вывод я„я„..., я„называется левым выводом цепочки я„из я, в грамматике 6. Правый вывод определяется аналогично, надо только в предыдущем предложении читать „самой правой" вместо „самой левой". Заметим, что левый (или правый) вывод определяется по дереву вывода однозначно. Если 5==я„ я„ ...,я„=п4 †лев вывод терминальной цепочки 4в, то каждая цепочка я; (О»! < и) имеет вид х»Афн ~ !~ г Г ! ! а Рис. 2.11. Пример дерева.
где х4Е2", А,Е)»1 и ~»Е(Я()Е)4. Каждая следующая цепочка я;.„левого вывода получается из предыдущей я; зал4еной самого левого нетерминала А; правой частью некоторого правила. В правом выводе заменяется самый правый нетерминал. Пример 2.21. Рассмотрим КС-грамматику 6, с правилами Е- Е+Т) Т Т- Тир1с Р— (Е) )а Дерево вывода, показанное на рнс.
2.!1, служит представлением десяти эквивалентных выводов цепочки а+а. Ее левый вывод— Е ~ Е+Т =в> Т (- Т =Ф г + Т =~ а г Т => а+ Г =~ а+ а а правый вывод— Е ~Е+Т- Е ( у=2>Е+а=г>Т+аг>с+а=~а+а П Определение. Цепочку я будем называть лгвовыводимои (в грамматике 6), если существует левый вывод 5=я„я„..., я„=я, и писать 5=>о,Я (или 5=4>;Я„, когда Ясно, какаЯ гРамматика 6 имеется в виду). Аналогично я будем называть правовыводимой, если существует правый вывод 5=я„я„..., я„=я, и писать 5:-.ьо, Я (или 5=>,Я).
Одни шаг левого вывода обозначим через =>,, а шаг правого вывода — через =>„. 167 Гл. 2. элсменты ТЕОРНН языков Леммы 2.12 я 2.13 можно объединить в одну теоРемУ: Теорема 21!. 77 ус|па б =(Х, Х, Р, 5) — КСграл|л|атика. 5='»*а тогда и только тогда, когда в б суи(ествует дерево вывода с кроной а. Доказательство. Это непосредственно следует из лемм 2.12 и 2.13, П Заметим, что мы остерегались говорить, что если дап вывод 5 =,«'а в КС-грамматике, то можно найтн единственное дерево вывода в 6 с кроной а. Причина этого заключается в том, что есть КС-грамматики, у которых может быть несколько различных деревьев выводов с одной и той же кроной Такова грамматика из примера 2.19.
На рис. 2.8 показаны разные деревья выводов (в) и (г) с одной и той же кроной. Определение. КС-грамматику 6 называют неоднозначной, если существует хотя бы одна цепочка и|ЕЕ(6), которая является кроной двух или более различных деревьев выводов в б. Это равносильно тому, что некоторая цепочка шЕ Е(6) имеет два или более разных левых (правых) Вывода (упр. 2.4.4). В противном случае КС-грамматика б называется Однозначной, Неоднозначность будет подробнее рассмотрена в равд. 2,6.8.
2.4.2. Преобразования КС-грамматик Данную грамматику часто требуется модифицировать так, чтобы порождаемый ею язык приобрел нужную структуру, Рассмотрим, например, язык Е(6,). Этот язык может порождаться грамматикой 6 с правилами Š— Е+ Е ! Е ь Е || (Е) ( а Но грамматика б имеет два недостатка Прежде всего она неоднозначна из-за наличия в ней правил Е- Е+Е(Е«Е. Эту неоднозначность можно устранить, взяв вместо 6 грамматику 6, с правилами Š— Е+Т(Е«Т(Т Т вЂ” (Е))а Другой недостаток грамматики 6, которым обладает также и б„заключается в том, что операции + и ь имеют один и тот же приоритет. Иначе говоря, структура выражений а+ива и а«а+а, которую придает им грамматика б„подразумевает тот же порядок выполнения операций, что и в выражениях (а+а)ьа и (а«а)+а соответственно.
2лс КОНТЕКСть!О-своволныа ЯзЫКН Чтобы получить обычный приоритет операций -1- и « котоРо" ': предшествУет + и выражение а+а»а понимается как а+(аьа), надо перейти к грамматике б„. Общего алгоритмического метода, который придавал бы данному языку произвольную структуру, не существует. Но с помощью ряда преобразований можно видоизменить грамматику, не испортив порождаемого ею языка. В танноы аз еле 2.4.3 — 2.4.3 мы укажем несколько преобразован!!й такого рода. Начнем с очевидных, но важных преобразований.
В некоторых случаях КС-грамматика может содержать бесполезные символы н правила. Например, в грамматике 6=((5, А),(а, Ь), Р, 5), где Р = (5 †« а, А †« Ь), нетерминал А и терминал Ь не могут появиться ни в какой выводимой цепочке. Таким об аз,, символы не имеют Отношения к языку Е(6), и их можно устранить из определения грамматики 6, не затронув языка Е (6). Определение. Назовем символ Х б Х () Х бесполезным в КС-грамматике 6=(Х, Х, Р, 5), если в ней пст вывода вида 5=>" вХу ==;>»шху, где п1, х, у принадлежат Х'. р, ал, построим Чтобы установить, бесполезен ли пете"мпнал А, п сначала алгоритм, выясняющий, может ли нетсрминал порождать какие-нибудь терминальные цепочки, т.
е. решающий проблему пустоты множества (щ~ Л =>*ш, шб Х«|. Из существования такого алгоритма следует разрешимость проблемы пустоты для КС- матнк. т ля -грам- А л г о р и т м 2.7. Н е п у с т л и я з ы к Е (6)2 Вход. КС-грамматика 6=(Х, Х, Р, 5). Выход.,ДА", если Е(6)~йу, „НЕТ" в противном случае. Метод. Строим множества Х„Х„...
Рекурсивно: ( ) Положить Х,— 8' н ! — 1. (2) Положить Х;=-(А (А — аЕ Р и с|Е(Х|,() Х)*) (1 Х ( ) . ',-.»'=1~, „положить |=-!'+1 и перейти к шагу (2). Ю Если Х--Х 1-! 1-1 противном случае положить Х, -- Х . сли Е Х, выда|ь выход „ДА, в противноь! Случае |', то алгоритм 2.7должен остановиться самое Так как Х ~Х, ольшее после и-';! повторений шага (2), если Х содержит п нетерминалов, докажем корректность алгоритма 2.7. т а .. ««оказапростое и послужит в качестве модели для нескольких аналогичных доказательств, Теорема 2.12.
Алгоритм 2.7 говорит „ДА" тогда и только тогда, ковда 5~»ш для некоторой 2(еио!ки и|ЕХ". !69 Гл. а. элементы теОРии языков В.4. контекстно-СВОБОдные языки До к а з а т ел ь с т в о. Сначала докажем индукцией по 4, что (2.4.!) если АЕ)л(и то А=р*ш для некоторой цепочки плЕЕ'. Базис, 4=0, не нуждается в доказательстве, так как уча~о. Предположим, что утверждение (2.4.1) истинно для 4, н возьмем АЕМ444. Если А принадлежит также и 1л)и то шаг индукции тривиален. Если А Е 744+4 — )л)О то существует правило А — Х,, Х, где каждый символ Х, принадлежит либо 5, либо г(а Такйм образом, для каждого Х, можно найти такую цепочку шу, что Ху-ращу: если Х ЕЕ, то Илу=-Хм в противном случае существование пл следует из (2.4.1).
Легко видеть, что А =-> Х, ... Х, =р' ш,Х,... Х, =р'... =ь' ш,... ша Случай А=О (т. е. правило А- е) не составляет исключения. Шаг индукции окончен. Определение множеств Ж, гарантирует, что если (ч(4=1)4 лч то Ж,.=1ч)4„„=.... Мы должны показать, что еслн А~аж для некоторой цепочки плЕХ*, то АЕМл, В силу сделанного выше замечания все, что нужно показать, это что АЕ(л), для некоторого Е Индукцией по и докажем, что (2А.2) если А:=>аш, то АЕХ; для некоторого Е Базис, п=!, тривиален — в этом случае 4'=1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
