sym.c

计算机系统结构的讲义,浓缩了一本一千多页的书.真的是好东西.

/*  
 * sym.c --
 *
 *  This file contains procedures that manipulate symbol values
 *  and expresssions involving symbols.
 *
 *  This file is part of DISC.  It was modified by Yinong Zhang 
 *  ([e-mail]) from the file "sym.c" in the distribution
 *  of "dlxsim" available at:
 *     ftp://max.stanford.edu/pub/hennessy-patterson.software/dlx.tar.Z
 *
 *  The original source code is copyright as follows:
 *
 * Copyright 1989 Regents of the University of California
 * Permission to use, copy, modify, and distribute this
 * software and its documentation for any purpose and without
 * fee is hereby granted, provided that the above copyright
 * notice appear in all copies.  The University of California
 * makes no representations about the suitability of this
 * software for any purpose.  It is provided "as is" without
 * express or implied warranty.
 */



#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "dlx.h"
#include "sym.h"

/*
 * For each defined symbol there exists a structure of the following
 * form in the machine's symbol table.  There can be several symbols
 * with the same name (in different files), so there can be a chain
 * of these structures hanging off each entry in the hash table.
 */

typedef struct Sym {
    char *fileName;		/* Name of file in which symbol is defined. */
    unsigned int address;	/* Address of symbol, if defined. */
    int flags;			/* Various flag bits:  see below. */
    struct Sym *nextPtr;	/* Next symbol with same, or NULL for end
				 * of list. */
} Sym;

/*
 * Flag bits in Sym structures:
 *
 * S_GLOBAL -			1 means this symbol has global scope.
 * S_NO_ADDR -			1 means this symbol doesn't yet have an
 *				address defined for it (S_GLOBAL is
 *				always set in this case).
 * S_REG -			1 means this symbol is a register.
 */

#define S_GLOBAL	1
#define S_NO_ADDR	2
#define S_REG		4

/*
 * The data structure below describes the state of parsing an expression.
 * It's passed among the routines in this module.
 */

typedef struct {
    DLX *machPtr;		/* Machine information for things like
				 * symbol table and error messages. */
    char *fileName;		/* Filename for symbol lookup;  see Sym_GetSym
				 * argument of same name for more info. */
    int ignoreUndef;		/* Non-zero means don't worry about
				 * undefined symbols. */
    char *expr;			/* Position of the next character to be
				 * scanned from the expression string. */
    int token;			/* Type of the last token to be parsed from
				 * expr.  See below for definitions.
				 * Corresponds to the characters just
				 * before expr. */
    char *tokenChars;		/* Poiner to first character of expression
				 * that mapped to token (i.e. the value of
				 * expr before the call to Lex that produced
				 * token). */
    int number;			/* If token is NUMBER, gives value of
				 * the number. */
} ExprInfo;

/*
 * The token types are defined below.  In addition, there is a table
 * associating a precedence with each operator.  The order of types
 * is important.  Consult the code before changing it.
 */

#define NUMBER		0
#define OPEN_PAREN	1
#define CLOSE_PAREN	2
#define END		3

/*
 * Binary operators:
 */

#define MULT		8
#define DIVIDE		9
#define MOD		10
#define PLUS		11
#define MINUS		12
#define LEFT_SHIFT	13
#define RIGHT_SHIFT	14
#define BIT_AND		15
#define BIT_XOR		16
#define BIT_OR		17

/*
 * Unary operators:
 */

#define	UNARY_MINUS	20
#define BIT_NOT		21

/*
 * Precedence table.  The values for non-operator token types are ignored.
 */

static int exprPrecTable[] = {
    0, 0, 0, 0, 0, 0, 0, 0,
    10, 10, 10,				/* MULT, DIVIDE, MOD */
    9, 9,				/* PLUS, MINUS */
    8, 8,				/* LEFT_SHIFT, RIGHT_SHIFT */
    5,					/* BIT_AND */
    4,					/* BIT_XOR */
    3,					/* BIT_OR */
    0, 0,
    11, 11				/* UNARY_MINUS, BIT_NOT */
};

/*
 * Forward declarations for procedures defined in this file:
 */
static 		int Lex(ExprInfo *);	
static int	GetValue(ExprInfo *, int);
	

/*
 *----------------------------------------------------------------------
 *
 * Sym_DeleteSymbols --
 *
 *	Remove all symbols associated with a particular file from a
 *	machine's symbol table.
 *
 * Results:
 *	None.
 *
 * Side effects:
 *	All symbols for "fileName" get removed from "machPtr"s symbol
 *	table.  This is typically done before (re-) loading a file into
 *	memory.
 *
 *----------------------------------------------------------------------
 */

void
Sym_DeleteSymbols(machPtr, fileName)
    DLX *machPtr;		/* Machine to manipulate. */
    char *fileName;		/* Name of file whose symbols should be
				 * deleted. */
{
    Tcl_HashEntry *hPtr;
    register Sym *symPtr;
    register Sym *prevPtr;
    Tcl_HashSearch search;

    for (hPtr = Tcl_FirstHashEntry(&machPtr->symbols, &search);
	    hPtr != NULL; hPtr = Tcl_NextHashEntry(&search)) {
	for (symPtr = (Sym *) Tcl_GetHashValue(hPtr), prevPtr = NULL;
		symPtr != NULL; prevPtr = symPtr, symPtr = symPtr->nextPtr) {
	    if (strcmp(symPtr->fileName, fileName) != 0) {
		continue;
	    }
	    if (prevPtr == NULL) {
		Tcl_SetHashValue(hPtr, symPtr->nextPtr);
	    } else {
		prevPtr->nextPtr = symPtr->nextPtr;
	    }
	    free(symPtr->fileName);
	    free((char *) symPtr);
	}
    }
}


/*
 *----------------------------------------------------------------------
 *
 * Sym_AddSymbol --
 *
 *	Add a new symbol to the symbol table for a machine.
 *
 * Results:
 *	A standard Tcl result is returned (normally TCL_OK), and an
 *	error string may be added to machPtr's interpreter.
 *
 * Side effects:
 *	Name is entered into the symbol table, if it isn't already
 *	there.  If address is -1 and global is 1, then the name is
 *	entered as a global symbol but no address is assigned (that
 *	will ostensibly come later).
 *
 *----------------------------------------------------------------------
 */

int
Sym_AddSymbol(machPtr, fileName, name, address, flags)
    DLX *machPtr;		/* Machine to manipulate. */
    char *fileName;		/* Name of file in which symbol defined. */
    char *name;			/* Name of symbol. */
    unsigned int address;	/* Address corresponding to symbol, or
				 * SYM_NO_ADDR if symbol is being declared
				 * global before it has been defined. */
    int flags;			/* OR-ed combination of flag bits: any of
				 * SYM_REGISTER, SYM_GLOBAL, SYM_NO_ADDR. */
{
    register Sym *symPtr;
    Tcl_HashEntry *hPtr;
    int new;
    
    hPtr = Tcl_CreateHashEntry(&machPtr->symbols, name,
	    (int *) &new);
/*    if (!new)
	return TCL_ERROR; */
    symPtr = (Sym *) Tcl_GetHashValue(hPtr);
    if (symPtr != NULL) {
	Sym *globalPtr, *localPtr;

	/*
	 * See if there are other symbols that might conflict with this
	 * one.  If there's an error due to a conflict, it is handled
	 * farther down.
	 */

	globalPtr = localPtr = NULL;
	for ( ; symPtr != NULL; symPtr = symPtr->nextPtr) {
	    if (strcmp(symPtr->fileName, fileName) == 0) {
		localPtr = symPtr;
	    } else {
		if ((symPtr->flags & (S_GLOBAL|S_NO_ADDR)) == S_GLOBAL) {
		    globalPtr = symPtr;
		}
	    }
	}

	if (localPtr != NULL) {

	    /*
	     * Is this call just updating information in a previously-entered
	     * symbol?  If so, then do it.
	     */

	    if (flags & SYM_GLOBAL) {
		localPtr->flags |= S_GLOBAL;
	    }
	    if (!(flags & SYM_NO_ADDR)) {
		if (!(localPtr->flags & S_NO_ADDR)) {
		    sprintf(machPtr->interp->result,
			    "symbol \"%.50s\" already defined in %.50s",
			    name, fileName);
		    return TCL_ERROR;
		}
		localPtr->address = address;
		localPtr->flags &= ~S_NO_ADDR;
	    }

	    /*
	     * Does this new symbol result in a conflict between two
	     * globally-defined symbols?
	     */

	    if ((globalPtr != NULL)
		    && ((localPtr->flags & (S_GLOBAL|S_NO_ADDR)) == S_GLOBAL)) {
		globalConflict:
		sprintf(machPtr->interp->result,
			"symbol \"%.50s\" already defined in %.50s",
			name, globalPtr->fileName);
		return TCL_ERROR;
	    }
	    return TCL_OK;
	}

	if ((globalPtr != NULL)
		&& ((flags & (SYM_GLOBAL|SYM_NO_ADDR)) == S_GLOBAL)) {
	    goto globalConflict;
	}
    }

    /*
     * Create and initialize the new symbol.
     */

    symPtr = (Sym *) calloc(1, sizeof(Sym));
    symPtr->fileName = (char *) calloc(1, (unsigned) (strlen(fileName) + 1));
    strcpy(symPtr->fileName, fileName);
    symPtr->address = address;
    if (flags & SYM_GLOBAL) {
	symPtr->flags |= S_GLOBAL;
    }
    if (flags & SYM_NO_ADDR) {
	symPtr->flags |= S_NO_ADDR;
    }
    if (flags & SYM_REGISTER) {
	symPtr->flags |= S_REG;
    }
    symPtr->nextPtr = (Sym *) Tcl_GetHashValue(hPtr);
    Tcl_SetHashValue(hPtr, symPtr);

    return TCL_OK;
}


/*
 *----------------------------------------------------------------------
 *
 * Sym_GetSym --
 *
 *	Lookup a symbol and return its address.
 *
 * Results:
 *	The return value is one of SYM_FOUND (the normal case, where the
 *	symbol exists), SYM_REGISTER (if the symbol was found and is a
 *	register), SYM_NOT_FOUND if no such symbol could be found,
 *	SYM_AMBIGUOUS if the symbol is multiply-defined, or
 *	SYM_REG_NOT_OK if the name referred to a register but
 *	registers are not acceptable here.  If SYM_FOUND or SYM_REGISTER
 *	is returned, *addrPtr is modified to hold the symbol's memory
 *	address or register number.
 *
 * Side effects:
 *	None.
 *
 *----------------------------------------------------------------------
 */

int
Sym_GetSym(machPtr, fileName, name, flags, addrPtr)
    DLX *machPtr;		/* Machine to use for name lookup. */
    char *fileName;		/* Non-null means only consider symbols
				 * that may be referenced from this file.
				 * NULL means consider any global or
				 * unambiguous symbol. */
    char *name;			/* Name of desired symbol. */
    int flags;			/* Zero or one of the following: 
				 * SYM_REGS_OK means consider normal registers;
				 * SYM_PSEUDO_OK means accept pseudo-reg
				 * names (e.g. "hi" and "lo") also. */
    unsigned int *addrPtr;	/* Address of symbol (or register number)
				 * gets stored here. */
{
    Tcl_HashEntry *hPtr;
    register Sym *symPtr;
    Sym *matchPtr;
    int matchCount;

    matchPtr = NULL;
    matchCount = 0;
    hPtr = Tcl_FindHashEntry(&machPtr->symbols, name);
    if (hPtr != NULL) {

	/*
	 * Loop through all the symbols with the given name, looking for
	 * a clear match (global symbol or symbol defined in given file).
	 */
    
	for (symPtr = (Sym *) Tcl_GetHashValue(hPtr); symPtr != NULL;
		symPtr = symPtr->nextPtr) {
	    if (symPtr->address == SYM_NO_ADDR) {
		continue;
	    }
	    if (symPtr->flags & S_GLOBAL) {
		found:
		*addrPtr = symPtr->address;
		if (symPtr->flags & S_REG) {
		    if (flags & (SYM_REGS_OK|SYM_PSEUDO_OK)) {
			return SYM_REGISTER;
		    }
		    return SYM_REG_NOT_OK;
		}
		return SYM_FOUND;
	    }
	    if (fileName != NULL) {
		if (strcmp(fileName, symPtr->fileName) == 0) {
		    goto found;
		}
	    } else {
		matchPtr = symPtr;
		matchCount++;
	    }
	}
    }

    /*
     * If there's been no match so far, see if the name refers to a
     * standard register name.
     */

    if (matchCount == 0) {
	int num;
	char *end;

	if (*name == 'f') {
	    num = strtoul(name+1, &end, 10);
	    if ((end != (name+1)) && (*end == 0) && (num <= 31) &&(num >= 0)) {
		if (num >= 32) {
		    return SYM_NOT_FOUND;
		}
		*addrPtr = num;
		if (!(flags & SYM_FREGS_OK)) {
		    return SYM_FREG_FOUND;
		}
		return SYM_REGISTER;
	    }
	}
	if ((*name == 'r') || (*name == '$')) {
	    num = strtoul(name+1, &end, 10);
	    if ((end != (name+1)) && (*end == 0) && (num <= 31) && (num >= 0)) {
		gotReg:
		if (num >= 32) {
		    if (!(flags & SYM_PSEUDO_OK)) {
			return SYM_NOT_FOUND;
		    }
		} else if (!(flags & (SYM_PSEUDO_OK|SYM_REGS_OK))) {
		    return SYM_REG_NOT_OK;
		}
		*addrPtr = num;
		return SYM_REGISTER;
	    }
	}
	if ((flags & SYM_PSEUDO_OK) && (strcmp(name, "pc") == 0)) {
	    num = PC_REG; goto gotReg;
	} else if ((flags & SYM_PSEUDO_OK) && (strcmp(name, "npc") == 0)) {
	    num = NEXT_PC_REG; goto gotReg;
	} else if (strcmp(name, "at") == 0) {
	    num = 1; goto gotReg;
	}
    }

    /*
     * One last check:  if there's an unambiguous local symbol, and that's
     * permitted, then return it.
     */

    if ((fileName == NULL) && (matchCount == 1)) {
	symPtr = matchPtr;
	goto found;
    }
    if (matchCount > 1) {
	return SYM_AMBIGUOUS;
    }
    return SYM_NOT_FOUND;
}


/*
 *----------------------------------------------------------------------
 *
 * Lex --
 *
 *	Lexical analyzer for expression parser.
 *
 * Results:
 *	TCL_OK is returned unless an error occurred while doing lexical