不同数据结构在编译器设计中的作用是什么？

  • Z时代
  • 2024-01-10
  • 分类：综合

在编译期间，每次遇到标识符时都会搜索符号表。如果找到新名称或有关现有名称的新信息，则会添加数据。因此，在设计符号表结构时，它希望有一种方案能够使我们能够有效地插入新条目并识别表中的当前条目。

数据结构中使用了四个符号表，如下所示 -

  • Lists - 为符号实现数据结构的最简单和清晰的是如图所示的线性记录列表。

它可以使用单个数组或多个等效数组来保存名称及其相关数据。新名称按照遇到的顺序插入到列表中。它可以检索我们搜索的名称的数据，从数组的开头一直到指针 AVAILABLE 标记的位置，该指针表示数组空部分的开始。

  • 自组织列表- 以一点额外空间为代价，我们可以使用一个技巧来节省搜索符号表所花费的大部分时间。它可以为每条记录添加一个 LINK 字段，我们按照 LINK 指示的顺序搜索列表。当一个名字被引用或它的记录被第一次创建时，它可以通过移动指针将该名字的记录移动到列表的前面。

  • Search Tree - 一种更有效的符号表组织方法是在每条记录中插入两个链接字段 LEFT 和 RIGHT。我们使用这些字段将记录链接到二叉搜索树中。

这棵树的特性是，所有名称 NAME (j) 从 NAME (i) 可通过链接 LEFT (i) 访问，然后按照任何链接序列将按字母顺序排列在 NAME (i) 之前（象征性地，NAME (j) <姓名 (i))

二叉搜索树算法

  • 最初，Ptr 将指向树的根。

  • 虽然 Ptr ≠ NULL 做

  • 如果 NAME = NAME (Ptr)

  • 然后返回真

  • else if NAME<NAME (Ptr) then

  • Ptr-LEFT(Ptr)

  • 否则 Ptr-= RIGHT (Ptr)

  • 循环结束

  • 哈希表- 哈希表包括从 0 到 K - 1 的 K 个条目。这些条目是指向符号表的指针，指向符号表的名称。它可以决定 "Name" 是否在符号表中，我们使用哈希函数 'h' 这样 h (Name) 将产生 0 到 K - 1 之间的整数。它可以通过位置 = 搜索任何名称h(Name)。

以上是 不同数据结构在编译器设计中的作用是什么？ 的全部内容， 来源链接： utcz.com/z/363455.html

回到顶部