dictionary.cpp

C Preprocessor,antlr的grammar语言描述,用于学习词法分析,语法分析

/*
 * PUBLIC DOMAIN PCCTS-BASED C++ GRAMMAR (cplusplus.g, stat.g, expr.g)
 *
 * Authors: Sumana Srinivasan, NeXT Inc.;            [e-mail]
 *          Terence Parr, Parr Research Corporation; [e-mail]
 *          Russell Quong, Purdue University;        [e-mail]
 *
 * VERSION 1.1
 *
 * SOFTWARE RIGHTS
 *
 * This file is a part of the ANTLR-based C++ grammar and is free
 * software.  We do not reserve any LEGAL rights to its use or
 * distribution, but you may NOT claim ownership or authorship of this
 * grammar or support code.  An individual or company may otherwise do
 * whatever they wish with the grammar distributed herewith including the
 * incorporation of the grammar or the output generated by ANTLR into
 * commerical software.  You may redistribute in source or binary form
 * without payment of royalties to us as long as this header remains
 * in all source distributions.
 *
 * We encourage users to develop parsers/tools using this grammar.
 * In return, we ask that credit is given to us for developing this
 * grammar.  By "credit", we mean that if you incorporate our grammar or
 * the generated code into one of your programs (commercial product,
 * research project, or otherwise) that you acknowledge this fact in the
 * documentation, research report, etc....  In addition, you should say nice
 * things about us at every opportunity.
 *
 * As long as these guidelines are kept, we expect to continue enhancing
 * this grammar.  Feel free to send us enhancements, fixes, bug reports,
 * suggestions, or general words of encouragement at [e-mail].
 * 
 * NeXT Computer Inc.
 * 900 Chesapeake Dr.
 * Redwood City, CA 94555
 * 12/02/1994
 * 
 * Restructured for public consumption by Terence Parr late February, 1995.
 *
 * Requires PCCTS 1.32b4 or higher to get past ANTLR. 
 * 
 * DISCLAIMER: we make no guarantees that this grammar works, makes sense,
 *             or can be used to do anything useful.
 */
/* 1999-2004 Version 3.0 July 2004
 * Modified by David Wigg at London South Bank University for CPP_parser.g
 */
/* 2004-2005 Version 3.1 November 2005
 * Modified by David Wigg at London South Bank University for CPP_parser.g
 */
/* 2005-2007 Version 3.2 November 2007
 * Modified by David Wigg at London South Bank University for CPP_parser.g
 *
 * See MyReadMe.txt for further information
 *
 * This file is best viewed in courier font with tabs set to 4 spaces
 *
 * See NotesScopes.txt for information about storing symbol names within scope levels
 *
 * Symbols names are stored in lists selected by hashing
 *
 * Symbols are also chained in lists for each scope level,
 *	[0] = template scope	Note: Not used at present
 *	[1] = external scope	Note: These symbols (types) are never deleted. "std" is allocated this scope in CPPParser::init()
 *	[2+]= function/variable scopes	Note: These symbol references are deleted when they go out of scope.
 */

#include <string>
#include <stdlib.h>
#include "Dictionary.hpp"

/* Hashing function described in                   */
/* "Fast Hashing of Variable-Length Text Strings," */
/* by Peter K. Pearson, CACM, June 1990. */
/* Table from p. 678.*/
/* Pseudorandom Permutation of the Integers 0 through 255: */
unsigned char Dictionary::randomNumbers[] =  
	{	
	  1, 14,110, 25, 97,174,132,119,138,170,125,118, 27,233,140, 51,
	 87,197,177,107,234,169, 56, 68, 30,  7,173, 73,188, 40, 36, 65,
	 49,213,104,190, 57,211,148,223, 48,115, 15,  2, 67,186,210, 28,
	 12,181,103, 70, 22, 58, 75, 78,183,167,238,157,124,147,172,144,
	176,161,141, 86, 60, 66,128, 83,156,241, 79, 46,168,198, 41,254,
	178, 85,253,237,250,154,133, 88, 35,206, 95,116,252,192, 54,221,
	102,218,255,240, 82,106,158,201, 61,  3, 89,  9, 42,155,159, 93,
	166, 80, 50, 34,175,195,100, 99, 26,150, 16,145,  4, 33,  8,189,
	121, 64, 77, 72,208,245,130,122,143, 55,105,134, 29,164,185,194,
	193,239,101,242,  5,171,126, 11, 74, 59,137,228,108,191,232,139,
	  6, 24, 81, 20,127, 17, 91, 92,251,151,225,207, 21, 98,113,112,
	 84,226, 18,214,199,187, 13, 32, 94,220,224,212,247,204,196, 43,
	249,236, 45,244,111,182,153,136,129, 90,217,202, 19,165,231, 71,
	230,142, 96,227, 62,179,246,114,162, 53,160,215,205,180, 47,109,
	 44, 38, 31,149,135,  0,216, 52, 63, 23, 37, 69, 39,117,146,184,
	163,200,222,235,248,243,219, 10,152,131,123,229,203, 76,120,209
	};

char *Dictionary::strings = NULL;
char *Dictionary::strp = NULL;
unsigned Dictionary::strsize = 0;

Dictionary::
Dictionary(int nb, int ns, int nc)
	{
	int i;

	// allocate buckets for names
	bucket = new (DictEntry *[nb]);
	if (bucket==NULL) 
		panic("can't alloc buckets");

	// Initialize buckets for names
	nbuckets = nb;
	for (i=0; i<nb; i++) 
		bucket[i]=NULL;

	// allocate a scope list for the start of each scope list
	scope = new (DictEntry *[ns]);
	if (scope==NULL) 
		panic("can't alloc scopes");

	// allocate an endScope list for the end of each scope list
	endScope = new (DictEntry *[ns]);
	if (endScope==NULL) 
		panic("can't alloc endScope");

	// Initialize scopes and endscopes
	nscopes = ns;
	for (i=0; i<ns; i++) 
		{
		scope[i]=NULL;
		endScope[i] = NULL;
		}

	currentScope = 0;

	strsize = nc;
	strings = new char[nc];
	strp = strings;
	}

Dictionary::
~Dictionary()
	{
	delete [] bucket;
	delete [] scope;
	delete [] endScope;
	nbuckets = nscopes = 0;
	currentScope = -1;
	}

/* Hashing function described in                   */
/* "Fast Hashing of Variable-Length Text Strings," */
/* by Peter K. Pearson, CACM, June 1990.           */
int Dictionary::
hash(const char *string)
	{
	int hash1  = 0;
	int hash2  = 0;
	int length = 0;
	int r = 0;

	while(*string != 0)
		{
		length++;
		/* Hash function is XOR of successive characters randomized by
		 * the hash table.
		 */
		hash1 ^= randomNumbers[*string++];
		if (*string != 0)
			hash2 ^= randomNumbers[*string++];
		}
	r = (hash1 << 8) | hash2;
	return r;
	}

/* Return ptr to 1st entry found in table under key
 * (return NULL if none found).
 */
DictEntry *Dictionary::
lookup(const char *key,CPPSymbol::ObjectType tp)
	{
	//printf("Dictionary.cpp lookup entered with %s for type %d\n",key,tp);
	// tp is type to be looked for 
	// Default, 0, is to look for any symbol irrespective of type
	// Each new DictEntry is stored at start of its list so most
	// recent additions are reached first
	//DictEntry *q;
	CPPSymbol *q;	// CPPSymbol is subclass of DictEntry
	//int scope = getCurrentScopeIndex();
	//if(sc != -1)
	//		scope = sc;

	int h = hash(key) % nbuckets;
	q = (CPPSymbol *) bucket[h];

	// This searches symbol bucket for CPPSymbol entries
	for (q; q != NULL; q = (CPPSymbol *) q->getNext())
		{
		//printf("Dictionary.cpp lookup symbol %s in scope %d current scope %d\n",
		//	q->getKey(),q->this_scope,getCurrentScopeIndex());

		if (h != q->getHashCode())
			fprintf(stderr,"dictionary.cpp lookup, h not equal to q->getHashCode() for %s\n",key);

		if ( h==q->getHashCode() && strcmp(key, q->getKey()) == 0)
			{
			if(tp==0)	// Search for first matching symbol
				return q;
			else
				{
				CPPSymbol::ObjectType type = q->getType();
				if(tp==CPPSymbol::otTypename)	// Search for first type name
					{
					if (type==CPPSymbol::otTypedef||
						type==CPPSymbol::otEnum||
						type==CPPSymbol::otClass||
						type==CPPSymbol::otStruct||
						type==CPPSymbol::otUnion)
						return q;
					}
				else if(tp==CPPSymbol::otNonTypename)	// Search for first non type name
					{
					if (type==CPPSymbol::otVariable||
						type==CPPSymbol::otFunction)
						return q;
					}
				else if(type==tp)	// Search for first symbol with specific type
					return q;
				else
					return NULL;
				}
			}
		}
	return NULL;
	}

void Dictionary::
define(const char *key, DictEntry *entry)
	{
	defineInScope(key, entry, currentScope);
	}

void Dictionary::
defineInScope(const char *key, DictEntry *entry, int sc)
	{
	int h = hash(key) % nbuckets;	// July 2005, nbuckets = 4001 See CPP_parser.g
	//printf("Dictionary.cpp defineInScope key %s hash(key) %d bucket %d scope %d\n",
	//	key,hash(key),h,sc);
	entry->this_scope = sc;
	entry->setKey(strdup(key));	// Make a local copy of key
	entry->setHashCode(h);
	entry->setNext(bucket[h]);	// Set next pointer to current entry in bucket
	bucket[h] = entry;			// Replace current entry in bucket
	if (endScope[sc]==NULL)
		scope[sc] = endScope[sc] = entry;
	else
		{
		endScope[sc]->setScope(entry);
		endScope[sc] = entry;
		}
	}

int Dictionary::
getCurrentScopeIndex()
	{
	return currentScope;
	}

DictEntry *Dictionary::
getCurrentScope()
	{
	if (currentScope<0 || currentScope>nscopes)
		panic("getCurrentScope: no scope");
	return scope[currentScope];
	}

void Dictionary::
saveScope()
	{
	// Advance scope number (for included scope)
	currentScope++;
	if (currentScope>=nscopes) 
		panic("saveScope: overflow");
	//printf("Dictionary saveScope entered. Scope now %d\n",currentScope);
	}

void Dictionary::
restoreScope()
	{
	// Reduce scope number for next highest scope
	if (currentScope==0) 
		panic("restoreScope: underflow");
	currentScope--;
	//printf("Dictionary restoreScope entered. Scope now %d\n",currentScope);
	}

/*	This unlinks all entries from the Dictionary that are members
 *	of the current scope.  The scope level is not restored to the previous
 *	scope however. This requires use of restoreScope() above
 */
DictEntry *Dictionary::
removeScope(int sc)
	{
	DictEntry *de, *r;
	if (sc == -1)	// removeScope() without parameter value defaults sc to -1
		sc = currentScope;
	for (de=scope[sc]; de!=NULL; de=de->getNextInScope())
		{
		remove(de); 
		}
	r = scope[sc];
	scope[sc] = endScope[sc] = NULL;
	return r;
	}

//	Remove this dictEntry from its bucket by unlinking it
DictEntry *Dictionary::
remove(DictEntry *de)
	{
	DictEntry *prev, *curr;
	if (de==NULL) 
		panic("Dictionary.cpp remove: NULL ptr");
	int h = hash(de->getKey()) % nbuckets;	// Find pointer to bucket
	for (prev=NULL, curr=bucket[h]; curr!=NULL; prev=curr, curr=curr->getNext())
		{
		if (de==curr)
			{
			if (prev==NULL) 
				bucket[h] = de->getNext();
			else 
				prev->setNext(de->getNext());
			de->setNext(NULL);
			return de;
			}
		}
	return NULL;	// should never get here...
	}

/*	Lookup the object referred to by 'key' and then physically remove
 *	it from the Dictionary.  Return the object referred to by the key.
 *	If more than one definition is found for 'key', then only the
 *	first one is removed.  Return NULL if not found.
 *  Note: DW 12/06/03 Probably not used
 */
DictEntry *Dictionary::
remove(char *key)
	{
	DictEntry *q, *prev;

	int h = hash(key) % nbuckets;
	for (prev=NULL, q = bucket[h]; q != NULL; prev = q, q = q->getNext())
		{
		if (h==q->getHashCode() && strcmp(key, q->getKey()) == 0)
			{
			if (prev==NULL) 
				{
				bucket[h] = q->getNext();
				} 
			else 
				{
				prev->setNext(q->getNext());
				}
			q->setNext(NULL);
			return q;
			}
		}
	return NULL;      // should never get here, but make compiler happy
	}

void Dictionary::
dumpScope(FILE *f, int sc)
	{	
	DictEntry *s;

	if (sc == -1)	// dumpScope() without parameter value defaults sc to -1
		sc = currentScope;
	for (s=scope[sc]; s!=NULL; s=s->getNextInScope())
		{
		dumpSymbol(f, s);
		}
	}

// This is overridden in CPPDictionary.hpp
void Dictionary::
dumpSymbol(FILE *f, DictEntry *de)
	{
	fprintf(f, "%s\n", de->getKey());
	}

// Diagnostic function
// Contents of first 10 scopes printed
void Dictionary::
dumpScopes()
	{	
	DictEntry *dictEntry;
	int i;

	printf("Scopes");
	for (i=0; i<10; i++)
		{
		printf("     %d     ",i);
		}
	printf("\n");
	printf(" first");
	for (i=0; i<10; i++)
		{
		if (scope[i]!=NULL)
			{
			dictEntry = scope[i];
			printf("%10s ",dictEntry->getKey());
			}
		else
			{
			printf("           ");
			}
		}
	printf("\n");
	printf(" last ");
	for (i=0; i<10; i++)
		{
		if (endScope[i]!=NULL)
			{
			dictEntry = endScope[i];
			printf("%10s ",dictEntry->getKey());
			}
		else
			{
			printf("           ");
			}
		}
	printf("\n");
	}

/* Add a string to the string table and return a pointer to it.
 * Bump the pointer into the string table to next avail position.
 */
char *Dictionary::
strdup(const char *s)
	{
	char *start=strp;
	if (s==NULL) 
		panic("strdup: NULL string");
	if (start+strlen(s)+1 > &(strings[strsize-2]))
		panic("string table overflow");
	while (*s != '\0') 
		{ 
		*strp++ = *s++; 
		}
	*strp++ = '\0';
	return start;
	}

void Dictionary::
panic(char *err)
	{
	fprintf(stdout, "Dictionary panic: %s\n", err);
	exit(-1);
	}