Теория синтаксического анализа, перевода и компиляции - Том 1 (Теория синтаксического анализа, перевода и компиляции), страница 12

0.$.4. Упорядоченные графы Упорядоченным графом называется пара (А, )т), где А обозна. чает„как и раньше, множество вершин, а л' — множество линейно упорядоченных списков дуг, каждый элемент которого имеет вид ((а, Ь,), (а, Ье), ..., (а, Ь„)). Этот элемент указывает, что нз вершины а выходят л дуг, причем первой из них считается дуга, входящая в вершину Ь„, Второй — дуга, входжцая в вершину Ь„ и т.

д. Пример 0.23. На рис. 0.10 изображен упорядоченный граф. Линейное упорядочение дуг, выходящих из вершины, указывается Рис. 0.10. Уиорядоччиимй граф. в помощью нумерации их числами 1, 2, ..., л, где л — степень яо выходу этой вершины. формально упорядоченный граф на рис. ОЛО определяется как пара (А, )е), где А — (а, Ь, с) и )е =- (((а, с), (а, Ь), (а, Ь), (а, а)), ((Ь, с))). И 3аметим, что упорядоченный граф на рис.

0.10 не является Ориентиров рованиым в смысле нашего определения, так как в нем из вершины а в вершину Ь ведут две дуги. (Напомним, что во ,;множес естве дуг графа каждый элемент встречается только адин раз.) Как и для неупорядоченных графов, определим понятия р аз- *;метки и равенства помеченных графов. Определение. Разметкой упорядоченного графа б = (А, )т) назовем такую пару функций )"' и я, что (1)); А — 3 для некоторого множества5 (1 помечает вершины); (2) д отображает )т в последовательности символов из неко- торого'мнажсства Т так, что образом списка ((ап Ь,), ..., (а, Ь„)) является последовательность из л символов (д помечает дуги).

Помеченные графы б,=-(А„)т',) и бе=(АР, Р,) с разметками Дм д,) и (~„й,) соответственно назовем Раеньсии, если сУществует такое биективиос отображение й: А, — А„что (1) Р, содержит ((а, Ь,), ..., (а, Ь„)) тогда и только тогда, когда )(, содержит ((й (а), й (Ь,)), ..., (й(а), й(Ь„)); (2) 1', (а)=1е(й(а)) для всех аь А,; Щ д, (((а, Ь,),..., (а, Ь„))) — д, (((й (а), й (Ь,)),..., (й (а), й (Ь ))).

Неформально можно сказать, что два помеченных упорядо- ,' Ченных графа равны, если существует взаимно однозначное со- .ответствие между их вершинами, сохраняющее метки вершин и дуг. Если множества значений обеих разметок состоят из един- 'ственного элемента, то граф по существу не помечен, и надо :;Проверять только условие (1). Аналогично, если одним элемен- .фм помечены талька все вершины или только все дуги, то ,йоатветственно становится тривиальным условие (2) или (3). Для каждого упорядоченного графа (А, )т) существует неупо- ,'гйядоченный граф (А, )т') (называемый его основой), дугамн ко- ::.З(»рого служат дуги графа (А, )т) без учета порядка и без повто- . й, т.

е. )т' состоит из пар (а, Ь), для которых существует сок ((а, Ь,), ..., (а, Ь„)) ~ )с и Ь = Ь, для некоторого 1, 1: 1~л. :ч) Упорядоченный а»(иклический граф — эта упорядоченный граф, :»11сновой которого является ациклический граф, Улорядоченнсе дерево — это упорядоченный граф (А, Й), основой которого является дерево, и если Ка, Ь,),, (а, „))ч)1, а Ь то Ь»чь Ь для (~е 1. 57 тл Ря . с.

О.1!. Два дер тэ Рпс. 0.12. Упорядочепиое дерево. гл. о.1геедвлт1тельные млтемдт 1ЛЧЕС1СНЕ ГВ ЕДЕ ННЯ Если ие оговорено противное, то ое, то предполагается ч о а нога ациклическог мые пото ки е шины в е а право. 1 ы всегда линейно упорядочены слева иа- Когда рассматривается воп ос о а опро~ Раве1'стве дву Р фов ет. „изображенные на рис. О. 1, случае. неупорядоченные, и различны ы в противном О.а.а. ИН дукция по ациклическому ому графу Многие теоремы об р ях можно доказыват евь р б ациклическнх г а вать инд кцией р фах и особенно о дват у ", но часто бывает не дет у вести иид 'к ию.

ясно, даются доказательств ам такого со та, у цию. Теоремы, которые дений о том, что иечт р, часто имеют вид утве поднек тве оторого подмножества что истинно для всех ва вершин. Таким об а, ь вершин дерева или дл утвержве ши у рждение о вершинах дерева и т еб етс р зом, нужно доказать Р у ся ка"Ой то параметр В качестве таких па жио применять х па р глуби~у ершины, х параметров можно б ать длину пути) от базовой дерева ог корня) до р вьян состоит в том, б Ппдд Д ИНДУКЦИИ ПО КОНЕ Н ч ым упорядоченным еве ш образом Упорядочить т, чтобы каким-то депоследовательности.

О цию по пози и пишем ва а ц и вершины в получе рядочения. д распространенных способа упо иной Определение. Пусть Т вЂ конечн по я ь †конечн упорядоченное дерево. Пря, .. .) ... й осле- шага 1, начиная с корня. ре урсивиым применением 5В О В, НЕКОТОРЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ Шаг 1: Пусть данное применение шага 1 относится к вершине а. Если а — лист, включить вершину а в список. Если а не лист и ее прямые потомки — вершины а„а„..., а„, включить а в список и затем применить шаг 1 к вершинам а„а„..., а„в этом порядке. Обратный порядок вершин дерева Т получится, если заклю":".' чительную часть последнего предложения в описании шага 1 ~;; заменить на „применить шаг 1 к вершинам а„а„..., аа в этом порядке, а затем включить в список вершину а".

Пример 0.24. Рассмотрим упорядоченное дерево на рис. 0.12. Прямой порядок вершин: 123466789; обратный порядок: 342789661. Иногда можно пронести индукцию по месту, которое занимает вершина в том или ином упорядочении. 0.$.6. Вложение частичного порядка е линейный Если задан частичный порядок 1с на множестве А, часто бывает нужен линейный порядок, содержащий этот частичный порядок. Зга проблема вложения частичного порядка в линейный называется топологической сортировкой. Интуитивно топологическая сортировка заключается в том, что надо взять ациклический граф, который в сущности и является заданным частичным порядком, и расположить его вершины в столбец так, чтобы все дуги были направлены вниз.

Линейный порядок задается положением вершин в этом столбце. Например, при такал деформации граф, изображенный на рис. 0.8, может превратиться в столбец, показанный на рис. 0.13. Формально можно сказать, что частичный порядок лл на множестве А вложен в линейный порядок 1с', если )7' — линейный порядок и лт с=)А1', т.

е. а)ЛЬ влечет а)с'Ь для всех а и 6 из А. гл. о. пнедвАРительпые млтемлтическ! скин сведения Для данного частичного порядка р сущ в е. т т много линейных порядков, в которые его можно вложить (упр. О.б.б). Следующий алгоритм находит один из таких линейных порядков: Алгоритм 0.1. Топологическая со тировка. сор- Вход.

Час тичный порядок В на конечном множестве А. Выход. Линейный порядок К на А ля которого В = Я'. на , для Метод. сд. Так как А — конечное множество, линейный по я ок йпорядок)! на А можно представить последовательность элементов строится с помощью следующих шагов: (1) Положить !'=-1, А =А и В =-В. ( ) "сли А! пусто, остановиться и выда ать „ ..., аг, в качестве искомого линейно- го порядка. В противном случае выбрать в луненнмй на ацнк- А! такой элемент а,, что а!г а ложно лннеского !рафа на а Е А О Рно о 3. (3) Положить А! .. = А! — (а,.) и ницу и повторить шаг 2. г! Если частичный порядок представлен в ви е а графа, то алгоритм 0.1 в виде ациклического допускает особенно простую инте п етацию. На каждом шаге алгоритма (А, )5! ) интерпре- р фом и а;--его базовая вершина.

Ациклнческий г !аф и всех выходящих из нее дуг. Пример 0,23. Пусть А =(а, Ь, с, й) и В=-((а, Ь), (а, с), Ь, 51, ж~н~ при всех а' Е А , надо взять а, =-и. Тогда А,— -(Ь, с, й) и !г,=((Ь, й), (с й)гг; теп и а =,(с, ),'. родолжая аналогично, найдем а = р у е получился линейный порядок В'=-((а, Ь), (Ь, (с, й), (а, с), (Ь, с!), (а, й)!!. =- ((а, ), (Ь, с), Теорема 0.4. Алгоритм 0.1 дает линейный порядок )т', в который вложен данный частичный порядок )5!. Доказательство. П . Простое упражнение на индукцию. ( з а 5. Иекотоные понятия теОРии ГРАФОВ 0.$.г.

Представления деревьев Дерево является двумерной структурой, но во многих ситуациях удобно пользоваться лишь одномерными структурами данных. Слсдовательно, мы заинтересованы в том, чтобы иметь для деревьев одномерные представления, сохраняющие всю информацию, которая содержится в двумерных картинках. Под этим мы подразумеваем, что двумерную картинку можно воспроизвести по ее одномерному представлению. Очевидно, что одно из одномерных представлений дерева Т = (Л, В) — это запись самих множеств Л и В.

Существуют и другис представления. Например, для указания глубины вершин дерева можно использовать вложенные скобки. Напомним, что глубиной вершины называется длина пути от корня до этой вершины. Глубина вершины 1 на рис. 0.9 раппа О, глубина вершины 3 равна 1, а вершина 6 находитси на глубине 2. Глубиной (или енистой) дерева называется длина наибольшего пути. Глубина дерева на рис. 0.9 равна 2. Используя скобки для указания глубяны, можно представить изображенное на рис.

0.9 дерево в виде 1(2,3(4,8,0)). Таку!О запись будем называть левым скобочпым представлением, так как поддерево представляется выражением, заключенным в скобки, а его корень записывается непосредственно слева от левой скобки. Определение. Левое скобочпое представление дерева Т (обозначается !гер(Т)) можно получить, применяя к нему следующие рекурсивные правила.