C中的符号表

Question

我目前正在开发一种执行模式匹配的静态分析工具.我正在使用Flex生成词法分析器,我编写了代码来管理符号表.我对C不太熟悉,所以我决定将符号表实现为线性链表.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct symtab {
   int id;
   char *name;
   int type;
   struct symtab *next;
};

enum types {
   KEYWORD = 1,
   CONSTANT,
   IDENTIFIER,
   OPERATOR,
   DELIMITER,
   WHITESPACE
};

struct symtab *last_entry(struct symtab *start)
{
   struct symtab *p;
   p = start;
   while(p -> next != NULL) {
      p = p -> next;
   }
   return p;
}

void add_entry(char* name, int type, struct symtab *start)
{
   struct symtab *new;
   new = last_entry(start);
   int id;
   if(new == start) {
      new = start;
      id = 0;
   }
   else {
      new = malloc(sizeof(struct symtab));
      id = last_entry(start) -> id;
      last_entry(start) -> next = new;
   }
   new -> id = id + 1;
   new -> name = name;
       new -> type = type;
   new -> next = NULL;
}

struct symtab *find_entry(char* name, struct symtab *start)
{
   struct symtab *p;
   p = start;
   while(p -> next != NULL) {
      if(strcmp(p -> name, name) == 0) {
         return p;
      }
   }
}

但是,当我add_entry()用来添加符号,然后尝试找到它们时find_entry(),find_entry()返回null.有人可以帮忙吗？

Answer 1

看起来您试图将列表表示为标题对象(开始),然后是列表的实际元素.这是一个好主意,因为它简化了空列表的情况,但你没有得到正确的实现.

添加时,您需要删除为last_entry启动时获得的特殊情况代码.起始节点永远不会包含符号数据.

查找时,您必须确保跳过头(开始),因为它不包含符号数据.查找代码中的第二个错误是当p-> next为NULL时停止搜索(这意味着你永远不能返回列表中的最后一个元素.)当p为NULL时你应该停止.

当然,您根本不应该使用链表:哈希表是更好的选择,因为它具有更好的性能和内存效率.