Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 71
Текст из файла (страница 71)
Предполагая, что сложение и умножение ассоциативны н коммутатианы, получаем иисти, обведенные иа рис. 1!.!3 Рнс. !!.!а. Сннтвкскчссквс дерево с ннствнн. штриховыми линиямн. Ассоциативное дерево для Т изображена иа рис. 1!.16. Отвтетим, что ассоциативное дерево не обязано быть двоичным. Е) Вершины вссоцна!ианого дерева можно ломсшитгьв целыми числами, начиная снизу, следункцим образом: (1) Лист, являющийся самым левым прямым потомком своего предка, помечается 1. Все остальные листья помечаются О. (2) Пусть л — внутренняя вершина, прямые потомки которой л,, л„..., лн помечены 1„1„..., 1, гл 2.
(а) Если одна из чисел 1„1„...,1 превосходит остал! ные, берем его н качестве метки вершины л. (б) Если вершина л ииеет коммугативную операцию и л,— внутренняя вершина с 1ь= 1, а остальные вершины ьь.с. АРиеметические ВИРАжения гл ь! оптимизлция колА Рнс.
!!.16. Ассе натннное дерево. зат л„..., л, Р иье„..., и„— лист~я, то в качестве метки вершины л берем 1, (в) Если условие (б) не выполняется, 17 — ---17 для неко. торых ьФ) и 1,, не меныпе остальных 1», в качестве метки вершины и берем 17+1, Рнс. ь!.ьт. Помеченное ессоннагненье нерсес. Пример 11.24. Рассмотрим ассоцна тинное дерево на рис. 11.1б. Польеченное ассоциативное дерево изображено на рис. 11.17.
Отметим, что к третьему и четвертому прямым поточнам корня применяется условие(2б) процедуры разметки, поскольку умножение коммутативно. ЕЗ Приведем теперь алгоритм, принимающий на вход данное синтаксическое дерево и вырабатывающий такое дерево нз класса эквивалентности для данного дерева, которое имеет минимальную оценку. Ллгоритм 11.4. Построение синга кон !еского дерева с мииемальной оценкой в предположении, что одни операции коммутативны, другие коммутативны и ассоциативны и больпье никакие алгебраические законы не учитываются.
Вход. Синтаксическое дерево Т и множество с( коммутатнвных и коммутативно-ассоцна'тинных заиМов. Выход. Синтнксическое дерево нз (Т) 4 с миинмальаой оценкой. Метод. Строим сначала помеченное ассопиативное дерево Т лля Т. Ватель вычисляем асоштп(е(и,), где всашши!е — пропедура, определенная ниже, а и,— корень дерева ТС Выходом асошши(е(и,) служит синтаксическое дерево из (Т) 1 с минимальной оценкой Пройсдура нсопппи(е(ьь). Лргумептои и служит вершина помеченного ассоциативного дерева.
Если л- лист, полагаем асоьпши1е(и) =ьь. Если л — внутренняя вершина, рассмотрим грн случая: (!) Пусть вершина имеет два прямых потолька и, и и, (в ука. ванном порядке) и операция, связанная с и, комльутатевна (и, возможно, ассоциативна). (а) Если и, — лист, а л, иет, то выход асопппи(е(и)— дерево на рис.
11.18, а. (б) В противном слуьае асапппп!е(и) †дере на рнс. 11.18, б. (2) Предположим, что операция О, связанная с и, коимута. тиана и ассопиативна и вершина и имеет прямых потомков и„л„..., и, т)3 (в порядке слева направо). Пусть и,„— вершина из и„..., и с наиболыпсй меткой. Если одной н той же наибольшей меткой помечены ЛвЕ ипи более вершин, то верьпину л,„выбираем так, чтобы она была внутренней. Обозначим череа р„ре, ..., р, вершины в (и,, ..., л„) — (и „„) в любом порядке. Тогда выходом асошпш1е(и) служит двоичное дерево иа рис. 11.19, где г,(1щ(<т — 1) — йавые вершины, связанные с коммутативной и ассоциативной операцией О, соответствующей вершине и.
гл. !!. оптимнзлция кодл 13) Если операция, связанная с л, не коммутатнвна и не ассоциативна, то выходом асоттн1е)л) служит дерево на рис. 11.18, б '). Е) цл. дпиометнчнскис выпджнния Лемма 11.12. Пршпь Т вЂ” помеченное гиюпаксическое дерево, и 5 — кисте в Т'). При)положим, что метко г прямых потомков вери!ин иэ 5 дальше пеги равнье йг, где )б — числв сумматоров. Тогда ло крайнеи мере г — 1 вершим из 5 являются старшими. Рее. 1!.18. Результпт процедуры асом!пе!е.
Пример 11.28. Примевим алгоритм 11.4 к помеченному асса. циативночу дереву, иэображю!ному на рнс. 11.17. Применяп асопппи)е, а точнее случай 12) и корню, берем в качестве л,„ первого слева прячого потомка. Двоичное дерево, являющееся выходом алгоритма !1.4, показано на рис. 1!.20. Е) 11.4 Закончим этот раздел доказательством того, что алг ри находит в )Т")4 дерево с минимальной оценкой. Центральной в нашем доказательстве будет следующая лемма. ') В мпп глупее е пиеет ровно дза лрепыл мппиеа.— Прил.
персе. ззе Рпе !1 1В. Рееулюет процедуры еепмюп1е. До к аз а те льет во. Будем доказывать лемму ипдукпией по числу вершин в Т. Базис, случай одной вершины, тривиален. Предположим поэтому, что утверждение верно для всех деревьев с числом вершин, мепыаим, чем в Т. Пусть и — корень кисти 5, н пусть и имеет прямых потомков и, и и, с метками 1, и 1,, Пусть 7; и Т,— имена поддеревьев с корнямн л, и и, соответственно. Случай 11 ни и„ ни л, не принадлежат 5. Очевидно, гта в этом случае утверждение верно ') Цпкееегельетеп бут! епглееппепе е Эпппулнспэппее, еелп 8 — лтпбп ппеть, либо пдееечпеп еерюпеа, не ехпдпщеее е пасть.— Прил. иерее.
1Зл.леп,д .и: пп, .з ГЛ И. ОПТИМИЗЬШта КОДА Случай 2; л, принадлежит 5, а и, нет. Поскольиу число вершин в дереве Т, лтеньше, чем в Т, к нему прниенимо поедположение индукции, Таким образом, в Т, множество 5 — (л) содержит по крайней мере г — 2 старших вершин, если (т -Дг, пем сл и по крайней мере г — 1 старших вершин, если 1 ( Дг. В п с, 1 м учве утверждение тривиально. В обоих случаях результат очевидец, если г(1. Поэтому рассмотрим случай г ) ! и 1з~ Лг.
Рис. 1!.20 Выход вдгорвтме П.е. Тогда 5 — (и) имеет по крайней море олного прямого потомка, метка которого больше нли ранца Р), так что 1, ) У. Такилз образом, п — старшая вершина и 5 содержит не менее г — 1 старших вершин, Случай Зг л, принадлежит 5, а л, нет. Этот случай анзлогичен случаю 2.
С лучай йг л, и а, принадлежат 5, Пусть г, прямых потоыков вершин из 5 с лтеткамн, нс меньшими Дг, являются лотомками вершины лю а г, из них являются потомками вершины пю Тогда г,+г,=г. По предположению индукции части кисти 5 заь и т. дРиомвтичнскиа Вырлжаиия в Т, и Т, имеют соответственно не менее г, — 1 и не менее г, — 1 старших вершин. Если ни го ни г, не равны нулю, то 1,) ДГ и 1,) Дг, так что л — старшая вершина. Такиы образом, 5 имеет по крайней мере (г,— 1]+(г,— 1)+ 1 =г — 1 старших вершин.
Если г,=б, то г,=г, так что часть кисти 5 в Т, имеет не невес г — 1 старших вер!Дин. Случай г,—.-б аналогичен. ( ! Теорема 11.9. Алгоритм ПА вырабатывает дерево аз [Т(,1 с минимальной оценкой. Пока за тел ь ст во. Прямая индукции по числу вершин в ассоциативном дереве А показывает, что в результате прн. мснепия процедуры асопппп1е к его корню будет построено синтаксическое дерево Т, корень которого после разметки, описанной в алгоритме 1!.1, помечен тан же, как корень дерева А. Никакое дерево из [Т)ш не имеет корня с ыеткой, меньшей, чем > корня лорена А, и ннкакое дерево из[Т)А не имеет меньше, чеы в А, старших и младших вершин.
Предположим, !то это не так. Тогда пусть Т вЂ” наименывее') дерево, для которого одно из этих условий нарушается, Пусть 0 †операц в корне дерева Т, Случай 1: операция В не ассоциативна и не коммутативна. Любое ассоциативвое или коммутативное преобразование лерева Т должно совершаться целиком внутре поддерева, корнем которого служит одия из двух прямых потомков корня дерева Т. Такиы образом, касается ли нарушение метки, числа старших или числа младших вершки, оно должно проявиться в одном ни этих поддеревьев, что противоречит минимальности дерева Т. Случай 2г операция 0 комыутативна, ио не ассоциативна.
Этот случай аналогичен случаю 1, по теперь колгмутатваное преобразование можно применить к корав. Но нн шаге (1) пропел)ры асопппн!е уже учитывалась возможность применения этого преобразования, так что любое нарушение в дереве Т вновь приведет к наруа!ени!о в одном из его поддеревьев. '! Здесь «знмеььшес попимеется в следующем сммсле. По кзждоиу,!зинону сиитвнсн'гесному дереву Т, можно построить ессоннзтив~ос дерево А. В р *ул тате применения н А прояедуры ясошшше получается шишянсичсское дсрсяо Т, «отороыу соотеетствует множество )Т) . Выберем тсш'рь из всех множеств (Т1 1 для всевозможных леревьев Тт все деревья, для ко.
торах прн сопостнвленин с соответствуюшям леревом А перушвется одно из нергчяслениых выше условий. Рззлмр (чнсло вершин) з)их деревьев огра нчее снизу, и южняп гренннн достигешся. Вьберсм среди зтнк деревьев дерево с няименьшии числом вершин — При,н. персе. эзр 13* гл. ||. оптимиа*кня кодл упглжнання кпалжнаиня заа Заэ 13*». л, д у»»», т. 3 Случай 3| операция О коммутативпа н ассопнатиана.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
