Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 69
Текст из файла (страница 69)
Докажем, что значение метки корня помеченного синтаксического дерева, построенного алгоритмом 11,1, равно наименьп1ему числу сумматоров, необходимому для того, чтобы вычислить выражение, не прибегая к командам ВТОЕЕ. Начнем с нескольких замечанвй по поводу алгоритма 1! АЕ Лемма 11.18. Программа, емработаннал процедурой соде(п, 1) г алгоритме ! 1.2, лрагильно гычисллет значение вершины л, помещая гго на гсй сумматор.
До к аз а т ел ь ст во. Элементарная индукция по высоте вершины. (П Лемма 11.8. Если алгоритм 11.2 ири 1Ч доступныл сумматорах применяется к корню синтаксического дгргга, то лри вьтоэг процедуры соде(п, 1) г тршине л с меткой ! либо (!) 1) Я и для этого гмзога доступим Лг сумматоров (т. Р. 1.=1), либо (2) ! (Л! и длл этого гмзсга доступны по крайней мере ! сумматоров (т. г. 1(Лг — 1-1-1). Доказательство. Снова элементарная индукцня, на этот раз по числу вызовов соде (а, !), сделанных до рассматриваемого вызова.
Е) Теорема 11.8. Пусть Т вЂ” сингликгичггког дгрего, 1 — метка гго корня, Лà — число доступных сул1маторог. Программа, гмчигэяюи!ая Т без ислотэтанил команд ЗТОЕЕ, существует тогда и только тогда, когда 1( Л!. дока за тельство. Достаточнослм. Если !(Лг, то шаг (7) процедуры соде(п, 1) никогда ве выполняется, Действнтельно, вершина, прямые потомки иоторой помечены числом не менее Ч, сама помечена числом не менее Л!+1. Команда 5ТОЕЕ гене. рируется только на шаге (7). Поэтому при !(ЛГ программа, вырабатываемая алгоритмом 11.2, не содержит команд ЗТОЕЕ.
7)гсбходилгсть Пусть 1> Ч. Поскольку М) 1, должно быть 1=-2. Предположим, что утверждение неверно. Тогда без потери общности можно считать, что дерево Т имеет программу Р, вы1исляющую его с помощью М сумматоров, Р не содержит команд ЗТОЙЕ и яе существует синтаксического дерева Т', имеющего меньше вершин, чем Т, и также не удовлетворяющего утверждению. Поскольку метка корня дерева Т превосходит 1, Т не может состоять нз единсзеенного лис1а. Пусгь л — корень, а и и п — его прямые потомки сметками 1, и 1,соответственно.
1 1 зтз Случай 1: 1,=1. Значение л можно вычислнть, только если значение л, появится в неко~орый момент на сумматоре, поскольку п, не может быть листом. Формируем из Р новую программу Р', удаляя операторы, следующие за вычислением значения л,.
Тогда Р' вычисляет поддерево с корнем л, и не содержит команд ЭТОЙ Е. Таким образом, утверждение неверно прн числе вершин, меньшем, чем в Т, вопреки предположению относительно Т. Случай 21 1„=-!. Этот случай аналогичен случаю 1. Слу1ай 31 1,=1,=1 — 1. Мы уже предполагалн, что никакие двв листа не имеют одинаковых имен связанных с иимн переменных. Без потери общности можно считать, что программа Р „коротка, насколько возможно" в том смысле, что если удалить л1сбой из операторов, то в конце программы значения л в том же сумматоре уже не будет.
Таким образом, первым оператором программы должен быть 1 ОАР Х, А, где Х вЂ и переменной, связанной с некоторым листом дерева Т, так как иначе первый оператор можно было бы удалить. Пусть Х вЂ” значение листа, являющегося потомком вершины л, (возможно, самой вершикы л,). Случай, когда Х вЂ” значение потомка вершины л,, аналогичен; мы его рассьгатривать не будем. До тех пор пока не вычнслитсн значение л„иссгда по крайней мере один сумматор будет хранить значейие, содержащее Х.
Этим значением нельзя воспользоваться в правильном вычислении значения л,. Поэтому из Р можно получить программу Р', вычислнющую значение я„помеченную ! — 1, не использующую команд ЗТОЕЕ и требующую одновременно не более Л1 —.1 сум. маторов. Читателю предлагаем показать, что для Р' можно построить эквивалентную программу Р, для которой никогда не понадобится более Л1 — 1 различных сумматоров. (Отметим, что в Р' могут употребляться все ЛГ суммагоров, даже если одновременно их используется не более Лà — !.) Таким образом, утверждение теоремы неверно для поддерева с корнем л„ а это противоречит предположению о минимальности дерева Т.
Отсюда следует, что теорема справедлива. Т) 11ЭВЗ. Программы с командамн 51'О((Е Выясним теперь, сколько команд ЕОАР и 5ТОВЕ требуется лля вычисления свнтаксического дерева, если пользоваться Лг сумматорами, когда корень помечен числом, превышающим Л1. Нам пригодятся следующие определения. Определение, Пусть Т вЂ” синтаксическое дерево, а Лг — число доступных сумматоров. Вершина из Т называется старимй, если каждый ее прямой потомок помечен числом, не меныпим чем уд Вершина называется м.шди1ги, если оиа является листом и левым Гл и оптимизлция кодл прямым потомком своего прямого предка (т. е.
зто лист с мет- кой !). Пример 11.19. Рассмотрим синтаксическое дерево, изображенное на рис. ! 1.9, при 61=2. Здесь одна стершая вершина— корень и четыре младших вершивы — листья со аначениями А, Л,Лнб. Е) Лемма 11.!О. Пусть Т вЂ” синтоксишское дерево. П рограммо Р, вычисгяющая Т и шпольвующол т команд ЕОАР, существует тогда и только тогда, когда Т илгввт яс бо гее т млодиг их вершин. До к а з а т ел ь с т во.
Если присмотреться к процедуре соде(а, !) нз алгоритма 1!.2, то можно заметить, что оператор 1.ОАР вставляется только на шаге (2). Поскольку шаг (2) применяется только к младшим вершинам, достаточность доказана. Необходимость доказываетсл, как в теорелге 1!.6, с !четом того, что значение на сумматоре может появиться только в результате команды ЕОАО, а левый аргумент любой операции должен быть на сумметоре.
Лемма 11.11. Пусть Т вЂ” синтаксическое дерево. Л рограмма Р, вьшшгляющая Т э иююльзу1ощая М команд ЗТОКЕ, существует тогдо я только тогда, когда Т имеет ие более М старших вершои. До к аз а тел ьс тво. Достаточногть. Исследуя снова процсдуру соде(л, 1), видим, что команда ЗТОКЕ вставляется только на шаге (7), а он применяется только к старшим вершвнам.
Необходимость. Эта часть доказынащся инлукцией по числу вершин в Т. Базис индукции, т. е, случай, когда дерево и»ест вершину, тривиален, так как вершина помечена 1 н, зна шт, старших вершин нет. Предположим, что утверждение верно для синтаксических деревьев с числом вершин вплоть до й — 1, и пусть Т имеет й вершин. Рассмотрим программу Р, вычисляющую Т, и обозначим через М число старших вершин в 7'. Без потери общности можно считать, что Р содержит не больше ко»анд ОТОКЕ, чем любая другая программа, иычисляющая Т При М -О нужный результат очевиден, поэт'ому будем считать, что М)1. Тогда Р содержит хотя бы одну команду ЗТОКЕ, поскольку метка старшей вершины не меньше Л-1-1, и если бы в Р не было команд ЗТОКЕ, теорема 11.6 была бы неверна.
Значение, запомненное первой командой БТОКЕ, должно быть значеннсм некоторой вершины л из Т, а иначе было бы легко найти вычисляющую Т программу, в которой команд БТОКЕ меньше, чем в Р. Кроме того, по той же самой причине можмо считать, что и не лист Пусть Т' †синтаксическ дерево, полу- 374 111 лРивметичсские выРьжьния чаюцгееся ич Т, если сделать вершину л листом и дать ей в качестве значения некоторое новос имя Л.
Тогда у Т' будет меньше вершин, чем у Т, так что к нему можно применить предположевие индукции. Можно найти программу Р', вычисляющую Т' и использующую ровно на одну команду ЗТОКЕ меньше, чем Р. Программл Р' получается нз Р, если удалить в точности те операторы, поторые нужны дяя вычисления первого зало»неи. ного значения, и затем заменить в Р ссылки на ичейку, участвующую в этой команде БТОКЕ, вмепем Х, пока в этой ячеике ие будег запомнено новое аначение. Если мы сможем показагь, что Т* имеет не менее М вЂ” 1 старших вершин, то лемма будет доказана, поскольку по предположеннго индукции Р' имеет не менее М вЂ” 1 команд ЗТОКЕ и, значит, Р имеет не менее М команд ВТОКЕ. Ясно, что ни олин из потомков вершины л в Т не может быть старшим, поскольку в этом случае будет неверна теорема 11.6. Рассмотрим старшую вершину л' в Т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
