symbol -- C functions for symbol table management

SYNOPSIS

typedef struct symboltable_tag {
	internal definitions
} SymTab;

typedef user-defined type SymVal;

typedef struct symbol_tag {
	char	* name;			/* copy of name */
	int	type;			/* type of symbol */
	int	blocklevel;		/* nesting depth */
	int	hashvalue;		/* hash bucket # */
	struct symbol_tag * next;	/* list: next */
	struct symbol_tag * prev;	/* list: prev */
	struct symbol_tag * hnext;	/* hash: next */
	struct symbol_tag * hprev;	/* hash: prev */
	SymVal	uvalue;			/* user slot */
} Symbol;
#define HASH_SIZE	256
typedef void (*SymFunc)(Symbol*);
typedef int (*SymFunc1)(Symbol*, void*);
#define NIL_SYM_FUNC ((void (*) (Symbol*)) 0)

The files symbol.h and symbol.c in the ROOTDIR/examples/lexyacc/samples/symbol directory contain code for creating and managing symbol tables. You can use this code in your own applications and redistribute the binaries, according to the MKS LEX & YACC license agreement, as long as you do not provide the source code to other (unlicensed) users.

You need to modify symbol.h to define SymVal to hold whatever values you want to store for a variable. Currently SymVal just stores an integer. You may also want to adjust the size of the hash table, given as HASH_SIZE, for larger or smaller examples.

The file symbol.c contains the code for creating and managing symbol tables. The definitions in symbol.h are used by symbol.c. The functions are designed to be as general as possible, to support a wide variety of applications, while not sacrificing performance.

Multiple scopes are supported, as well as multiple independent symbol tables. The symbol table data structure is based on a combined linked list and hash table representation.

The SQL, dBase, HyperTalk, and PIC examples all use this symbol code.

Symbol Table Header

The sym_init() function is used to allocate a new symbol table header. This header must then be passed to all the symbol table functions, as shown in the Functions segment.

Scope

The current scope of the symbol table is represented as a non-negative integer within each symbol tag, with 0 being the highest (that is, global) scope. New symbols are added at the current scope level, which is maintained in the symbol table header.

When a new scope is entered, the scope level in the symbol table header is incremented. When a scope is abandoned, the scope level in the symbol table header is decremented and all symbols with a scope level greater than the new scope level are deleted.

Structure

Symbols are kept on two doubly-linked lists, one of which is used for quick hash searches, while the other provides a linked list of symbols in chronological order of creation.

Both the linked-list and hash-table representations have a guaranteed ordering. In the linked-list, new symbols are pushed on to the head of the list. This guarantees that the scope level of the symbols are sorted in descending order. In the hash table, each bucket just contains a pointer to a linked-list of symbols. When a new symbol is created, it is pushed onto the front of this list.

With both sets of lists, you can find symbols quickly (using the hash table), and still traverse all the symbols at a given scope (by using the linked list).

Functions

SymTab* sym_init(SymFunc new, SymFunc delete)

initializes a new symbol table, returning a pointer to the new symbol table header. SymFunc new is either NIL_SYM_FUNC(), or a pointer to a function returning void which is called as

(*new)(Symbol*)

for every newly created Symbol. This function can be used for diagnostics or to fill in the user slot. SymFunc delete is either NIL_SYM_FUNC(), or a pointer to a function returning void which is called as

(*delete)(Symbol*)

for every Symbol just before it is deleted. Symbols are deleted when a local block is discarded, or by sym_delete() when an entire symbol table is being deleted.

The tabp returned from sym_init() is a pointer to a symbol table header, that must be passed to all of the following functions.

void sym_delete(SymTab* tabp)

deletes the given table, and frees all space used by it.

void sym_globalscope(SymTab* tabp)

sets sym_lookup() and sym_intern() to work on a global scope; that is, look for a symbol corresponding to a given name within all scopes.

Note:: This is the default search mode for a newly created symbol table.

void sym_localscope(SymTab* tabp)

causes sym_lookup() and sym_intern() to work on a local scope; that is, search for symbols only within the current scope.

Symbol* sym_lookup(SymTab* tabp, char* name)

is used to find a symbol in the symbol table. The name is the name of the symbol to lookup. The scope of lookup is determined by the last use of sym_localscope() or sym_globalscope(); the default search is global. NULL is returned if the symbol is not found.

void sym_alloc(SymTab* tabp)

causes sym_intern() and sym_create() to allocate fresh memory for the name of a newly created symbol. This is the default.

void sym_noalloc(SymTab* tabp)

causes sym_intern() and sym_create() to save memory when creating a new symbol, by saving the given name pointer for the symbol name.

Note:: Use this only if you know that the string that you passed will not be overwritten. For example, do not do this if the name you are passing is in yytext, since it is always overwritten!

Symbol* sym_create(SymTab* tabp, char* name, int type)

creates a new symbol without searching. The scope level of the new symbol is the same as the current scope level. The symbol's name is name, and the type is type. A pointer to the new symbol table entry is returned.

Symbol* sym_intern(SymTab* tabp, char* name, int type)

does a lookup for a named symbol. If the symbol is not found, a new symbol is created with the given name and type. Scope rules are followed (as for sym_lookup()). A pointer to either the found or the newly created symbol is returned.

Symbol* sym_coalesce(SymTab* tabp, Symbol* sp)

removes a given symbol from the symbol table, and searches for another symbol with the same name. If that search is successful, a pointer to the found symbol is returned, otherwise NULL.

void sym_enterBlock(SymTab* tabp)

causes a new scope to be entered. The SymTab header maintains a current scope number for you.

void sym_leaveBlock(SymTab* tabp)

causes the current scope to be dropped. All symbols in this scope are deleted.

void sym_all(SymTab* tabp, SymFunc1 fn, void* arg)

void sym_all(SymTab* tabp, SymFunc1 fn void* arg)

traverses the symbol table, performing a given function once for every symbol. The function SymFunc1 fn is called as:

(*fn)(Symbol* sp, void* arg)

The first argument is a pointer to the symbol, and arg is an additional argument that the user can define.

FILES

ROOTDIR/examples/lexyacc/samples/symbol/symbol.h: is the header definitions for symbol table management in C.
ROOTDIR/examples/lexyacc/samples/symbol/symbol.c: contains the C code for symbol table management.

symbol
C functions for symbol table management

Miscellaneous Information