Bài giảng môn học Trình biên dịch - Chương 8: Tổ chức bảng danh biểu

Bài giảng chương 8 trình bày những nội dung cơ bản như: Các tác vụ trên bảng danh biểu, Bảng danh biểu tuyến tính (linear symbol table), Bảng danh biểu băm (hash symbol table), Hàm băm (hashing function),... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng môn học Trình biên dịch - Chương 8: Tổ chức bảng danh biểuCHÖÔNG 8TOÅ CHÖÙC BAÛNG DANH BIEÅU8.1. Giôùi thieäuCoù boán phöông phaùp truy xuaát treân baûng danh bieåu:1. Tìm kieám tuyeán tính (linear search)2. Tìm kieám nhò phaân (binary search)3. Tìm kieám treân caây (tree search)4. Maõ hoùa baêm (hash coding)8.2. Caùc taùc vuï treân baûng danh bieåuBaûng 8.1. Caùc taùc vuï treân baûng danh bieåuTeân chöông trìnhconCaùch goïiHaønh vi thöïc thiEnterEnter (id)Khi gaëp moät danh bieåu môùi ñöôïc khaibaùo, thuû tuïc naøy seõ kieåm tra xem danhbieåu môùi ñoù coù truøng vôùi teân naøo trongcuøng moät taàm vöïc? Neáu khoâng, thuû tuïcenter seõ ñöa danh bieåu môùi vaøo baûngdanh bieåu. Ngöôïc laïi enter seõ thoâng baùoloãi veà vieäc khai baùo moät danh bieåu nhieàulaàn trong cuøng moät taàm vöïc.loc (haøm)n := loc (id)Khi caàn truy xuaát moät danh bieåu, loc seõtìm treân baûng danh bieåu töø phaân töû môùinhaát cuûa taàm vöïc môùi nhaát ñeán phaân töûcuõ nhaát cuûa taàm vöïc cuõ nhaát ñeå tìm vò trícuûa id vaø traû veà thoâng qua teân loc cuûahaøm.ScopeentryScopeentryKhi trình bieân dòch ñi vaøo moät taàm vöïcmôùi, scopeentry seõ ñaùnh daáu treân Stack(baûng danh bieåu) moät taàm vöïc môùi.ScopeexitScopeexitKhi trình bieân dòch ñi heát moät taàm vöïcscopeenxit seõ thaûi hoài nhöõng teân bieánkhoâng coøn coù yù nghóa vaø taùi laäp moät taàmvöïc ngoaøi cuøng gaàn nhaát.8.3. Baûng danh bieåu tuyeán tính (linear symbol table)Thí duï 8.1. Cho ñoaïn chöông trình trong ngoân ngöõ Algol.begin real A, B;begin real C, A;.......end;end;I=554A321CBATABB=332131BTABHình 8.1. Baûng danh bieåu tuyeán tính cuûa thí duï 8.1Caùc taùc vuï treân baûng danh bieåu tuyeán tính ñöôïc trình baøy nhö sau:Giaûi thuaät:const tab lim = …..;btablim = …..;type tabinden = 1 .. tablim;item = recordkey: alfa; /* alfa laø kieåu chuoãi caùc kyù töï */end;var btab: array [1 .. btablim] of integer;tab: array [1 .. Tablim] of item;b: 1 • • tablim;t: tabindex;procedure enter (id: alfa)var sb: tabindex;begin sb := btab [b –1];