From: rcarter@wpi.WPI.EDU (Randolph Carter (nee. Joseph H. Allen))
Newsgroups: comp.programming
Subject: Everything in symbol table (was Re: keywords in the symbol table?)
Keywords: symbol table keyword lexical
Date: 11 Apr 92 13:26:46 GMT
Article-I.D.: wpi.1992Apr11.132646.20672
Organization: Worcester Polytechnic Institute

"cg@myrias.ab.ca (Chris Gray)" writes:
>In article <1992Apr9.024922.24759@u.washington.edu> eriksea@carson.u.washington.edu (Erik Seaberg) writes:
>>stephen@estragon.uchicago.edu (Stephen P Spackman) writes:
>>>*WHY* do people want a lexer that picks up keywords?

>>IMHO, a lexer shouldn't know anything about symbol tables.  It doesn't
>>have anything useful to enter in one except "this identifier has been
>>mentioned by name."  And most all of the information in a symbol table
>>entry doesn't apply to keywords ("if" doesn't have a type or scope).  A
>>parser uses keywords to delimit large constructs; they don't have to look
>>like identifiers - I think it makes a lot of sense to give the lexer its
>>own fast little table to screen out keywords (if they happen to look like
>>identifiers) and leave the more expensive symbol table lookups for when
>>they're necessary, and keep the symbol table(s) internal to the parser.

>Read what Stephen said again. You will notice that his method results in
>exactly one lookup or enter of ANY symbol into the one master table. What
>you are suggesting usually ends up with 3, and always at least 2. One is the
>first check to see if the symbol is a keyword or not. The other is looking it
>up and/or entering it into the main symbol table. Depending on how you did your
>block-structured language compiler, you might end up with a whole sequence
>of lookups. 

Go one step fruther.. have the lexer handle only three things: whitespace,
constants and symbols.  The symbols can be identifiers, keywords or
punctuation.  Making a hash table which handles indeterminately terminated
strings (I.E., any wierd symbol, >=, >>, >, >>=, etc.) turns out to be easy.

You have two tables: one is normal hash table- one entry for each complete
string.  The second is a hash table of integers.  For each symbol you enter
into the normal hash table, you also increment one of the integers in the
second hash table for each left-hand substring.  For example, if you add
"hello":

	normal_table[ hash("hello") ]  =  new symbol entry

	and

	length_table[ hash("h") ]++;
	length_table[ hash("he") ]++;
	length_table[ hash("hel") ]++;
	etc.

So what you'de really do is have the hash function iterator itself increment
the length_table entries while the string is being hashed.

Likewise, you decrement length_table entries and remove a normal_table entry
to remove a symbol from the table.

The lookup algorithm then becomes this:

unsigned long hash=0

  lookup:
    hashsave=hash
   loop:
    get next input character
    iterate it into the current hash value (hash=hash*XXX+c)
    check length table: if !length_table[hash%size]
       unget all characters lookup has read in so far
       hash=hashsave
       return NOTFOUND
    check main table: if normal_table[hash%size]
       recursive call to lookup. if it found a symbol, return it
       if it finds no longer strings, return what was found above
    else goto loop;

Oh, and you want to make the length table n times larger than the normal
hash table, where n is the average symbol length (this isn't so bad since
the integers can be small)

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

See?  There's really no excuse why ADA and C++ don't let you define
operators instead of just being able to overload them.

I've slowly (over the last year) been working on a new experimental language
which allows this, punctuation-less block structuring (it depends on the
indentation) and implicit expression termination (it depends if the
expression can end at the end of a line and ambiguities are resolved by
noticing how close symbols are to each other).  I'm at the point where all I
have to add is type propagation to have a working compiler (which generates
really crummy code).

I've found that the above is fine for looking up existsing symbols, but to
add new symbols you have to do special things because you don't know where
new symbols end.  In my language, new symbols have to use the C identifier
character set or they can contain anything if surrounded by a pair of
backslashes.  This worked out nicely because you only have to do weird
things for new weird symbols.

Operator symbols get precidence and associativity information along with
them.  A precedence parser with a few extensions then was enough to parse
expressions and the whole rest of the language was simple enough so that the
entire parser was only 300 lines of C.  I couldn't use yacc because it
doesn't allow you to add new things during run-time and I couldn't do the
implicit expression termination with it properly. 

Here's some sample code (a precidence parser similer to that used for the
language):

	*TOKEN parse(I prec)
	  *TOKEN n=0, t=get_token()
	  if t.type==LEFT_PAREN n=parse(0) t=get_token()
	  else if t.type==CONSTANT n=t
	  else if t.type&PREFIX && t.prefixprec > prec
            t.right=parse(t.prefixprec)
            t.type&=~(INFIX|POSTFIX)
	    n=t
	  else unget_token(t)
          if !n return 0
	  loop
	    t=get_token()
            if t.type&INFIX && ( t.infixprec>prec ||
               t.r_ass && t.infixprec==prec )
	      t.type&=~(PREFIX|POSTFIX)
	      t.left=n t.right=parse(t.infixprec)
              n=t
            else if t.type&POSTFIX && t.postfixprec>prec
              t.type&=~(PREFIX|INFIX)
              t.right=parse(t.postfixprec)
              n=t
            else unget_token(t) return n
Newsgroups: comp.programming