Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 51
Текст из файла (страница 51)
Если Лг имеет левое поддерево, содержащее вершину, помеченную а, го а <11; если Л! имеет правое поддерево с вершиной, помеченной у, то 0<7 Для внесения объектов в дерево двоичного поиска можно применить следующий алгоритм. Алгоритм 10.1. Внесение объектов в дерево двоичного поиска. Вход. Последовательность объектов а„..., а„из множества объектов А с линейным порядком " на А. Выход. Двоичное дерево, каждая из верпгин которого помечена одним из элементов а„ ...,ав и такое, что если веРшина Лг помечена а и некшорый ее потомок Л" помечен р, то 0 < а тогда и только тогда, когда ЛГ' — левое поддерево вершины Л'. юх Метод.
(1) Создать одиночную вершину (корень) и пометить ее а,. (2) Предпшголгим, что а„..., аг, унге размещены в дереве, 1 > О. Если в =к+1, остановиться. В противном случае внести аг в дерево, выполняя шаг (3] начиная с корня. (3) Пусть этот шаг аыполняется в вершине Лг с меткой Р.
(а) Если а, <Р и Лг имеет левого прямого потомка Лг„ выпалнвть шаг (3) в вершине Лг, Если Л' не имеет левого прямого потомка, создать его и поиетить ас Вернуться к шагу (2). б) Есле !)<а, и Лг имеет правого прямого потомка Л'„ выполнить шаг (3) в вершине Лг,. Если Лг пе имеет правого прямого потомка, создать его и пометить ао Вернуться к шагу (2). П Метод поиска объекта по существу совпадает с методом внесения, за исключением того, что на шаге (3) в каждой вершние надо проверять, является ли ее метка требуемым объектом. Пример 10.3. Пусть на вход алгоритма 10.1 подается последовательность объектов ХУ, М, ЯВ, АСЕ и ОР. Упорядоченгге пред~голагается алфавитным. Построенное дерево изображено на рис. 10.3. гл ~э. оогьнизлция иноормлпии ыл.тлзлицы имсц 10.1.3. Уабпмцьэ расстанавкм руэккл цф Функция рэсслккэукк а-э 774 Можно показать, что, после того как в дерево двоичэюго пояска помещено л объектов, ожидаемое число вершин, которые надо просмотреть для поиска одного объекта, пропорционально )ой и.
Зт'а цена приемлема, хотя таблицы расстановки, которые мы теперь обсудим, дают мевьшее ожидаемое время пояска. Наиболее эффективный и широко применяемый в компиля. торах метод при работе с таблицами ииев дают таблицы рас. стаяовки. Таблица имен, организованная на принцппе рапота. нонки, схематически ивображена на рис. 10.4. пмп укдедгсль в Рпс !0.4. Слепа памяти, яспольэумжеб рвсстаяовку: о — таблица расстановки, б †табли даяния. Механизм расстановки состоит из функции расстановки 6, тибчээцы расстановки и таблицы данных.
Таблица расстановки содержит и элементоп, где л фиксировано заранее. Каждый элемеэп в таблице расстановки имеет лва цолм: поле имени и поле указателя Предполагается, что вначале все элементы в таблице расстанонки пусты '). Если ранее встретился объект а, то в некоторой ячейке таблицы расстановки, обычно 6(а), есть элемент, поле имени которого содержит а (или, возможно, указатель на ячейку в таблице имен, где хранится а) и поле указателя которого содержит указатель на часть таблицы данных, содержащую информацию, связанную с сэ. ') Ицогда вяачале удобно помещать в таблицу рассэавовкв эаремрепуояаякме слова п имена стаядаргпых функций.
Таблица данных физически может совпадать с табляней расстановки. 1-!апрнмер, если для каждого объекта нужно й слав информации, то можно использовать таблицу расстановки размером йл. Каждый объект, запомненный в таблине расссановкн, занимал бы часть из й последовательных слов пампти. Ячейку) таблицы рвссгановки, соответствующую объекту а, легко найти, умножая адрес 6(а) расстановки для а на Й и беря полученный адрес в качестве первой кчейки набора слов для а. Функция расстановки 6 †э фактически набор функций 77„ Йо ..,, Йло каждая из которых отображает набор обьектов в мйожество целых чисел (О, 1, ..., и†1).
Функцию 6, будем на. зывать первичной функцией расгтанаэни. Когда встречается новый объект а, для вычислении 6(а) можно воспользоваться следующим алгоритмом. Если объект уже встречался ранее, то 6(а)— ячейка в таблице расстанопки, в которой хранится а. Если объеит а ранее не встречался, то 6(а) --пустая ячейка, в которой можно запомнить а '). Алгоритм 102.
Вычисление адреса таблицы расстановки. Вход. Объект а, функция расстановки 6, состоящая из по. следовательности функцнй 6„6„..., йьо каждая из которых отображает множество объектов в множество целых чисел (О, 1, ... ..., л — 1), и (не обязательно пустая) таблица расстановки с и ячейками. Выход. Адрес расстановки 6(а) и указание, встречался ли объект а ранее. Если а уже есть в таблице расстановки, то 6(а) †ячей, отведенная для а. Если объекта ранее ие встречался, то 6(а) †пуст ячейка, в которой а запоминается. Метод.
(!) Вычисляем по порядку й,(а), й,(а), ..., 6 (а), выполняя шаг (2) до тех пор, пока не возникнет „конфликт". Если 6„(а) дает койфликт, останавливаемся и сообщаем о неудаче. (2) Вычисляем 67(а): (а) Еглп ячейка Йг(а) п таблице рагстановки пуста, полагаем 6(а) =67(а), сообщаем, что объект а ранее це встречался, н останавливаемся. (б) Если ячейка 6,(сэ) не пуста, проверяем поле ее имени '), Если именем является а, полагаем й(а) = 67(а), со- э) Строгп творя, пря таком определеяяп й е фчькцвя, поскольку один п тот же объект может отображаться в раэлячпме поэпаэп табляци. В действптельяостк й — фупкпвя лвуя аргуисвтов: а я самоа таблцци.— Лрип. перев.
') Если пале имени еодержпт указатель па таблицу имев, надо проверять по этой таблице деаставтельксе ямя, гл ш оюлнизлция инеормлцни со,с. тлнлицы имен общасм, что объект а уже встречался, и останавливаемся, Если именем является не а, то возник конфликт; поэта. раем шаг (2) для вычисления другого адреса. Кахсдый раз, когда провернется ячейка й,(а), мы говорим, что осуществлнется так называемая проба таблицы. Когда таблпца расстановки слабо заполнена, конфликты бывают редко и для нового объекта а значение й(а) мохсно вычислить очень быстро. Обычно длн этого достаточно вычислить значение первичаой функции расстановки 6,(а). По мере заполнения таблицы растет вероятность того, что для каждого нового объекта а ячейка й,(а) будет улсе содержать другой объект.
Таким образом, конфликты становятся том более частыми, чем болыпе объектов внесено в таблицу, так что число проб, тре. бусмых для определенна И(а), увеличивается. Однако можно так конструировать таблицы расстановки, что они по всем характеристикам будут значительно превосходить дсрсвья двоичного поиска. В идеале хотелось бы иметь такую первичную функцию расстановки 6„ чтобы опа давала резлнчные положения в таблипе расстановки для любых двух различных объектов, Разумеется это, вообще говоря, невозможно, поскольку общее число возможных объектов обычно значительно больше числа л позиций в таблице.
На практике л делают несколько больше ожидаелюго числа различных объектов. Однако необходимо предусматривать некоторые действия на тот случай, если таблица будет переполнена. Для гого чтобы запомнить информацию оба,сначала вычисляется И(а). Если объект а ранее не встречался, то его имя запоминается в поле имени позиции 6(а). (Если используется отдельная таблица имен, то а запоминается в следующей ее пустой позиции, а указатель на эту позицию помещается в поле имени ячейни й(а).) Затем а таблице данных отводится очеред. иой подходящий участок памяти, а указатель на него помещается в поле указателя ячейки 6(а), Потом информация размацаетсп в этом участке памяти таблицы данных.
Точно так же, чтобы нанти информапию оба, можно вычислить 6(а) с помощью алгоритма !0.2(если а есть в таблице). Для локализации в памяти таблицы данных информации, относящейся н сс, используется указатель в поле указателя. Пример 10.4. Возьмем л = 10, и пусть объектами будут про.
извольные цепочки прописных латинских букв. Определим СОВЕ(а), где а — цепочка букв, как сумму „числовых значений" каждой буквы в а, считая, что А имеет числовое значение 1,  — числовое значение 2 и т. д. Определим йг(а) для Ос 1 ( 9 27е как (СОЮЕ(а)-,'-/) пю410'). Внесем в таблицу расстановки объекты А, ТУ и ЕР. Вычисляем 6,(А) = (!шоб 10) = 1, так что А вносилс в позицию 1. Объект % вносим в позицию 6(%)=(23шо410)=3. Затем встречается ЕР. Вычисляем й (ЕР) =-(5", 5) шоб 10 = 1. Поснольку позиция 1 уже занята, пробуем 6,(ГР). (5-1-5-1- +1) глоб 10=-2. Такилс обравом, для ЕР отводится позиция 2, уумл ухеоелее Рнс. 10.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
