Основы разработки трансляторов в САПР. Коробова И.Л - 27 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Пока поступают символы, хеширование которых дает индексы разных указателей, они заносятся в
таблицу аналогичным образом. Так, если мы записываем в таблицу символы S2, S3, S4, хеширование ко-
торых дает ссылки на указатели 1, 3, 6, таблица примет вид, представленный на рис. 13.
В конце концов, поступит символ S5, который ссылается на указатель, использовавшийся ранее, на-
пример на 6. Вот здесь и начинает действовать поле CHAIN. Символ S5 записывается в таблицу симво-
лов и добавляется к концу цепочки для этого указателя (рис. 14).
№
Хеш-
таблица
№
Аргу-
мент
Значе-
ние
CHAIN
0 1 S1 … 0
1 2 2 S2 … 0
2 3 S3 … 0
3 3 4 S4 … 5
4 1 5 S5 … 0
5
6 4
УК = 5
Рис. 14
На рис. 15 приведена блок-схема алгоритма занесения одного элемента S в таблицу символов с по-
мощью метода цепочек.
Пусть необходимо внести в таблицу символы S6, S7, S8, которые ссылаются на указатели 4, 3, 3, со-
ответственно (рис. 16).
начало
P1 = h(s)
P2 = h_tab(p1)
P2=0
УК = УК + 1
h_tabl(p1) = УК
tab(УК).name = S
tab(УК).tip = тип S
tab(УК).chain = 0
tab(P2) = S
Элемент S в
таблице найден
P1 = P2
P2 = tab(P2).
chain
P2 = 0
УК = УК + 1
tab(p1).chain = УК
tab(УК).name = S
tab(УК).tip = тип S
tab(УК).chain = 0
Рис. 15

Страницы