I am currently developing a kind of static analysis tool that performs pattern matching. I am using Flex to generate lexical analyzer, and I wrote code to manage the symbol table. I am not very experienced with C, so I decided to implement the symbol table as a linear linked list.
#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;
}
}
}
However, when I use add_entry()
to add symbols, and then try to find them with find_entry()
, find_entry()
returns null. Can someone please assist?
It looks like you're trying to represent the list as a header object (start), followed by the actual elements of the list. This is a good idea since it simplifies the empty-list case, but you've not got the implementation right.
When you add, you need to remove the special case code you've got for last_entry being start. The start node will never contain symbol data.
When you lookup, you've got to make sure you skip the head (start) since it doesn't contain symbol data. A second bug in your lookup code is that you stop searching when p->next is NULL (which means you can never return the final element in your list.) You should stop when p is NULL.
Of course, you shouldn't be using a linked list at all: a hash table would be a better choice since it's got better performance and memory efficiency.