parser.cpp

一个经典的词法分析器

#include "afxwin.h"
#include "iostream.h"
#include "EMBSQL.h"

enum tokTypes {
	EQUALS,
	LESS_THAN,
	GREATER_THAN,
	NOT,
	LIKE,
	UNDEFINED
};

extern CString dllError;	 // contains an error upon memory misalignment
extern SCCollection* tables; // the collection of tables in shared memory

////////////
//
// Create the in memory database object
//
CESql::CESql()
{
	printStack = false;
	if (dllError != "") {
		errorString = dllError;
		return;
	}
	stack = new SCCollection();
	if (tables == NULL)
		tables = new SCCollection();
	eStack = new CEStack();					// create a stack interpreter object
}

//
// Destroy the in memory dastabase access object
CESql::~CESql()
{
	stack->Clear();
	delete stack;
	delete eStack;
}

//
// Return the number of tables in the catalog
int CESql::Catalog()
{
	if (tables == NULL) return 0;
	return tables->GetSize();
}

//
// Return a catalog at index i

CString CESql::GetCatalog(int i)
{
	SCTable* tbl;
	if (tables == NULL) return "";
	if (i >= tables->GetSize()) return "";
	tbl = (SCTable*)tables->GetAt(i);
	return CString(tbl->Name());
}

//
// Delete a table from the database
bool CESql::DeleteTable(CString table)
{
	SCTable* tbl;
	tbl = FindTable(table);
	if (!tbl) return false;
	delete tbl;
	return true;
}

//
// Execute an SQL statament in memory
SCCollection* CESql::Sql(const CString stmt)
{
	int i = 0;
	SCColumn** cols;
	tokenString = "";
	inputString = stmt;
	errorString = "";

	inputString.TrimLeft();				// get rid of white space
	inputString.TrimRight();

	nCols = -1;
	columnInfo = NULL;
// 
// Find one of the three commands we recognize. The OR operation will succeed as
// soon as ANY return true
//
	stack->Clear();	
	stack->Print();
	// clear the execution stack
	if (Select() || Insert() || Update() || Delete()) {
		if (!inputString.IsEmpty())
			errorString = "Warning, substring '" + inputString + "' was ignored";
		Execute(stack);
		return result;
	}
	if (CreateTable()) {			// create table is a little tricky, we need to get the columns
		Execute(stack);				// and the name before we actually call the method that creates it
		if (errorString != "")
			return NULL;
		cols = (SCColumn**)result;	// ideally the stack should do it, but it doesn't have the this pointer
		while(cols[i] != NULL)
			i++;
		DefineTable(eStack->TableInQuestion(),cols,i);

		SCTable* tbl = FindTable("embsqlCatalog");	// add to self catalog
		void **row = new void*[1];
		row[0] = (void*)(LPCSTR)eStack->TableInQuestion();
		tbl->AddRow((const void**)row);
		delete row;

		return result;
	}

	errorString = "Unrecgnized command: " + inputString;
	return NULL;						// no language construct was recognized, error!
}

//
// Define a table in shared memory
bool CESql::DefineTable(CString nm, SCColumn *cols[], int n)
{
	SCTable* tbl;
	if (!tables) return false;
	if ((tbl = FindTable(nm)) != NULL)
		return false;
	tbl = new SCTable(nm,cols,n);
	tables->Add((CObject*)tbl);
	return true;
}

//
// Get the column information from a table in shared memory
SCColumn** CESql::GetColumnInfo(CString nm, int *nC)
{
	SCTable* tb = NULL;
	*nC = -1;
	tb = FindTable(nm);
	if (!tb) return NULL;
	*nC = tb->Columns();
	return tb->GetColumnInfo();
}

//
// Given a table name, find the object in shared memory
SCTable* CESql::FindTable(CString nm)
{
	SCTable *tb = NULL;
	if (!tables)
		return NULL;
	for (int j=0;j<tables->GetSize();j++) 
		tb = (SCTable*)tables->GetAt(j);

	for (int i=0;i<tables->GetSize();i++) {
		tb = (SCTable*)tables->GetAt(i);
		if (nm.CompareNoCase(tb->Name())==0)
			return tb;
	}
	return NULL;
}

//
// Given table name and a list of columns, add the columns to the table object
// as a row of data.
bool CESql::AddRow(CString nm, SCColumn *cols[])
{
	SCTable *tb = FindTable(nm);
	if (tb == NULL)
		return false;
	return tb->AddRow(cols);
}

//////////////////////////////////////////////////////////////////////////////////
//
// Grammer:
// MBSQL = <keywords>
// <keywords>		::= <select> | <insert> | <update> | <delete>
// <select>			::= SELECT <attributes> FROM <table> <where-clause>
// <insert>			::= INSERT INTO <table> (<attribute-list>) VALUE(<value-list>)
// <update>			::= UPDATE <table> SET(<assignment-list>) <where-clause>
// <delete>			::= DELETE FROM <table> <where-clause>
// <table>			::= <anumeric-name>
// <where-clause>	::= null | WHERE <E>
// <attributes>		::= * | <anumeric-name>
// <attribute-list>	::= <anumeric-name> <alist-tail>
// <alist-tail>		::= NULL | , <alist-tail>
// <value-list>		::= <number> | <string-literal>
// <anumeric-name> ::= <alpha> [<alpha>* | <digit>*]
// <number>			::= [-] <whole> <fraction-part>
// <whole>			::= <digit> <digit-tail>
// <digit-tail>		::= <digit> <digit-tail> | null
// <fraction-part>	::= null | . <digit-tail>
// <alpha>			::= a..z, A..Z
// <digit>			::= 0..1
// <E>				::= <T> <E'>
// <E'>				::= <compare> <T> <E'> | e
// <T>				::= <Z> <T'> | e
// <T'>				::= <associate> <Z> <T> | e
// <Z>				::= <F> <Z'> | e
// <Z'>				::= <conjugate> <T'> | e
// <F>				::= (<E>) | <id>
// <conjugate>		::= * | /
// <associate>		::= + | -
// <compare>		::= = | < | <= | > | >= | <> | LIKE | NOT LIKE
// <id>				::= <number> | <anumeric-name>
//

//
// Keyword SELECT handler
bool CESql::Select()
{
	SCCollection* saveStack = NULL;
	CString table = "";
	if (!GetToken("SELECT")) return false;	// keyword hook
	if (!GetListIds()) return true;			// attributes to select
	if (!GetToken("FROM")) {
		errorString = "Expected 'FROM' but found '" + tokenString + "'";
		return true;
	}
	if (!GetIdentifier())  {				// table to use
		errorString = "No table specified";
		return true;		
	}
	table = tokenString;
	SetColumnInfo(table);
	stack->Push(table);

	if (inputString.IsEmpty()) {			// eos means select all
		stack->Push("SELECT");				// so push the op and return
		return true;
	}
	saveStack = stack;						// preserve the old stack
	stack = new SCCollection();				// make a new stack
	WhereClause();							// evaluate the expression for where
	stack->CopyIntoStack(saveStack);		// push onto the saved stack at the end
	saveStack->Clear();						// otherwise the where expression would be evaluated
	delete saveStack;						// before the attributes are identified.
	stack->Push("SELECT");					// Push the operator
	return true;
}

bool CESql::Delete()
{
	SCCollection* saveStack = NULL;
	CString table = "";
	if (!GetToken("DELETE")) return false;	// keyword hook
	if (!GetToken("FROM")) {
		errorString = "Expected 'FROM' but found '" + tokenString + "'";
		return true;
	}
	if (!GetIdentifier()) {
		errorString = "Expected table name not found";
		return true;						// table to use
	}
	table = tokenString;
	SetColumnInfo(table);
	stack->Push(table);
	if (inputString.IsEmpty()) {			// eos means delete all
		stack->Push("DELETE");				// so push the op and return
		return true;
	}
	saveStack = stack;						// preserve the old stack
	stack = new SCCollection();				// make a new stack
	WhereClause();							// evaluate the expression for where
	stack->CopyIntoStack(saveStack);		// push onto the saved stack at the end
	saveStack->Clear();						// otherwise the where expression would be evaluated
	delete saveStack;						// before the attributes are identified.
	stack->Push("DELETE");					// Push the operator
	return true;
}
//
// UPDATE keyword handler. Returns false if the keyword was not found
bool CESql::Update()
{
	SCCollection* saveStack = NULL;
	CString table = "";

	bool hasParens = false;					// make sure parens, if used match up
	if (!GetToken("UPDATE")) return false;	// keyword hook
	if (!GetIdentifier()) {
		errorString = "Expected table name not found";
		return true;
	}
	table = tokenString;					// get the table name
	SetColumnInfo(table);

	if (!GetToken("SET")) {
		errorString = "Expected 'set' keyword not found";
		return true;
	}
	if (GetToken("(")) hasParens = true;	// check for open paren
	if (!GetAssignment()) {
		errorString = "Error in assignments " + errorString;
		return true;						// push the assignment ids onto the stack
	}
	if (hasParens) {						// match the open paren with close paren, if needed
		if (!GetToken(")")) {
			errorString = "Expected ) at: " + inputString;
			return true;
		}
	}
	if (!inputString.IsEmpty()) {			// unconditional update if no WHERE clause found
		saveStack = stack;					// save the stack
		stack = new SCCollection();
		WhereClause();						// evaluate the WHERE expression
		stack->CopyIntoStack(saveStack);	// copy the old stack onto the new stack
		saveStack->Clear();					// this allows the stack interpreter to identify
		delete saveStack;					// the assignment ids before having to evaluate the
	}
	stack->Push(table);						// push the table name onto the stack
	stack->Push("UPDATE");					// push the operation
	return true;
}

//
// INSERT Keyword handler. Returns false if the keyword was not found.
bool CESql::Insert()
{	
	CString table = "";
	if (!GetToken("INSERT")) return false;	// Keyword hook
	if (!GetToken("INTO")) return true;

	if (!GetIdentifier()) return true;		// get the table name
	table = tokenString;
	SetColumnInfo(table);

	if (!GetToken("(")) return false;		// ( required
	if (!GetListIds()) return true;			// push the list of ids onto the stack
	if (!GetToken(")")) return true;;		// ) required
	if (!GetToken("VALUES")) return true;

	if (!GetToken("(")) return true;		// ( required
	if (!GetListExps()) return true;		// get list of expressions
	if (!GetToken(")")) return true;;		// ) required

	stack->Push(table);						// push table name onto the stack
	stack->Push("INSERT");					// push the operator onto the stack
	return true;
}

//
// CREATE TABLE keywords handler
bool CESql::CreateTable()
{
	CString table = "";
	if (!GetToken("CREATE")) return false;
	if (!GetToken("TABLE")) return true;
	if (!GetIdentifier()) return true;		// get the table name
	table = tokenString;
	SetColumnInfo(table);
	if (!GetToken("(")) return true;		// ( required
	if (!GetListDecls()) return true;		// get the list of declarators, will eat last '('
	stack->Push(table);
	stack->Push("CREATE TABLE");
	return true;
}

bool CESql::GetListDecls()
{
	CString token1, token2;
	char size[16] = "";
	int i = 0;
	bool rc = true;
	while(rc) {
		if (!GetIdentifier()) {
			if (GetToken(")")) {
				sprintf(size,"%d",i);
				stack->Push(CString(size));
				return true;
			}
			if (!GetToken(",")) {
				errorString = "expected ',' not found";
				return false;
			}
			if (!GetIdentifier()) {
				errorString = "expected identifier not found";
				return false;
			}
		}
		token1 = tokenString;
		if (GetToken("FLOAT")) {
			stack->Push("float");
			stack->Push(token1);
			i++;
		}
		else {
			if (GetToken("CHAR")) {
				if (!GetToken("(")) {
					errorString = "Expected '(' not found";
					return false;
				}
				if (!GetNumber()) {
					errorString = "Expected number not found";
					return false;
				}
				token2 = tokenString;
				if (!GetToken(")")) {
					errorString = "Expected ')' not found";
					return false;
				}
				stack->Push(token2);
				stack->Push("char");
				stack->Push(token1);
				i++;
			}
			else {
				errorString = "Unexpected token: " + tokenString;
				return false;
			}
		}
	}
	return true;
}

//
// WHERE handler. Returns false when the keyword was not found
bool CESql::WhereClause()
{
	if (!GetToken("WHERE")) return false;	// Keyword hook
	E();									// Parse the expressions
	stack->Push("WHERE");					// push the operator onto the stack
	return true;
}

////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////
//
// EXPRESSIONS PART OF GRAMMER
// 
// PRECENDECE, WEAKEST TO STRONGEST
//
//  1. =,<,<=,>,>=,<>,LIKE,NOT LIKE
//  2. +,-
//  3. *,/
//  4. AND, OR
//
// Production riules
//

//
// Left hand side form: Format: attribute = <expression>
bool CESql::LHS()
{
	if (!GetIdentifier()) return false;		// identifier to assign into
	stack->Push(tokenString);
	if (!GetToken("=")) return true;
	E();									// push expression onto the stack
	stack->Push("ASSIGNMENTS");				// push the operator onto the stack
	return true;
}

// 
// Expression. Finds highest precedence operators
//