Re: Smart way to store records (structs)

Mr.E wrote:
> Would someone offer suggestions as to how I should store structs for
> symbol table lookup?
...
> My first thought was linked list but the size of the records aren't
> going to grow or shrink so that seemed useless. My second thought was
> to create a pointer block containing a textual version of the record
> with type and size information. I think that might work but I suspect
> it will be slow. considering you have to verify the field member and
> if it points to another record and another...


Why would it be slow? Most records have only a handful of members and
you shouldn't be doing string compares. Linear searching for a pointer
in a list of a few is very fast. If you're really concerned, you could
organize the pointers in a balanced search tree!


As I can't tell exactly what you have in mind, let me recommend a
general approach to symbol tables (inspired by Wolf's Bliss-11
compiler): have a global name table that maps _all_ distinct names to a
name record (including, keywords, variables, record fields, whatnot).
The idea being that doing the lexical analysis you should only ever have
to collect and hash strings corresponding to name once. From there you
can then map them to semantic symbols (some of which will have the same
name). Fx.


struct name {
        int is_keyword;
        char *as_text;
        unsigned hash_value;
        struct symbol *current_binding;
        ... etc
}


struct symbol {
        struct name *name;
        struct symbol *function_context;
        struct symbol *scope_sibling;
        ... etc
}


This unique name record can then be used to track what that name means
in the current context (current_binding). Fx. when parsing


      int foo;
      int bar(int foo)
      {
            if (foo) {
                  double foo = 3.14;
      ....


the lexer will return the same name for all four occurances of "foo",
but the parser will use and update the current_binding to reflect the
current semantic meaning of "foo", that is, the symbol bound to the name.


Back to records: with this model, records are just a collection of
symbols. Organize them anyway you want (array, linked list, search
tree). My recommendation: do whatever is _simplest_ to you.


Regards,
Tommy

Return to the comp.compilers page.
Search the comp.compilers archives again.