tailieunhanh - 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),. . | CHÖÔNG 8 TOÅ CHÖÙC BAÛNG DANH BIEÅU . Giôùi thieäu Coù 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) . Caùc taùc vuï treân baûng danh bieåu Baûng . Caùc taùc vuï treân baûng danh bieåu Teân chöông trình con Caùch goïi Haønh vi thöïc thi Enter Enter (id) Khi gaëp moät danh bieåu môùi ñöôïc khai baùo, thuû tuïc naøy seõ kieåm tra xem danh bieåu môùi ñoù coù truøng vôùi teân naøo trong cuøng moät taàm vöïc? Neáu khoâng, thuû tuïc enter seõ ñöa danh bieåu môùi vaøo baûng danh bieåu. Ngöôïc laïi enter seõ thoâng baùo loãi veà vieäc khai baùo moät danh bieåu nhieàu laà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ôùi nhaá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ûa haøm. Scopeentry Scopeentry Khi trình bieân dòch ñi vaøo moät taàm vöïc môùi, scopeentry seõ ñaùnh daáu treân Stack (baûng danh bieåu) moät taàm vöïc môùi. Scopeexit Scopeexit Khi trình bieân dòch ñi heát moät taàm vöïc scopeenxit seõ thaûi hoài nhöõng teân bieán khoâng coøn coù yù nghóa vaø taùi laäp moät taàm vöïc ngoaøi cuøng gaàn nhaát. . Baûng danh bieåu tuyeán tính (linear symbol table) Thí duï . Cho ñoaïn chöông trình trong ngoân ngöõ Algol. begin real A, B; begin real C, A; . end; end; I=5 5 4 A 3 2 1 C B A TAB B=3 3 2 1 3 1 BTAB Hình . Baûng danh bieåu tuyeán tính cuûa thí duï Caù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 = record key: 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: .