parser.cpp

C-MINUS编译器

#include "parser.h"

/*************************************************
Copyright (C), 2002-2008, lonelyforest.
File name:     parser.cpp
Author:   林公玉(lonelyforest)
Version:  1.0
Date: 22-03-06 16:14
Description:   实现 parser.h 中的各个功能，修改于
    23-04-06 19:33
*************************************************/

// 
/**: TreeNode implementation ...
&
* author:	lonelyforest
* data:		2006.03.22
*/
//-----------------------------------------------------------------------------
TreeNode::TreeNode() : father( NULL ), sibling( NULL), lineno( 0 ),
bArr( false )
{
	for (int i = 0; i < MAX_CHILDREN; ++i)
	{
		child[i] = NULL;
	}
}

// destruction
TreeNode::~TreeNode()
{
	for (int i = 0; i < MAX_CHILDREN; ++i)
	{
		if (child[i]) delete child[i];
	}

	if (sibling ) delete sibling;
}

//-----------------------------------------------------------------------------
TreeNode* TreeNode::LastSibling()
{
	TreeNode* last = this;
	while (last->sibling) last = last->sibling;
	return last;
}

//-----------------------------------------------------------------------------
/**: parser tree implementation .. 
&
* author:	lonelyforest
* data:		2006.03.26
*/
Parser::Parser(const string &filename):treeFile(filename)
{ // filename needs extern name(.c);

	/* scan 可以直接声明为类成员，然后在类初始化之前构造，
	* 我都测试过，不过这样作为指针比较灵活，方便我作扩充，
	* 和修改不同的需要！
	* 也考虑过采用继承的方式，但是我担心那样会不会庞大不可靠？ 呵呵
	* 缺乏高人指点， 凑活着作吧。
	*/
	scan = new Scanner(filename);
	
	
	m_program = NULL;
	indent = -1;
	traceParse = true;

	int pos = treeFile.rfind('.');
	treeFile.erase(pos, treeFile.size()-1);
	treeFile += ".st";	// syntax tree;
}

// destruction
Parser::~Parser()
{
	if (scan)		delete scan;
	if (m_program)	delete m_program;
}

// build parse tree
//-----------------------------------------------------------------------------
TreeNode* Parser::BuildSyntaxTree()
{
	m_program = program();
	return m_program;
}

/**: PrintTree(TreeNode* pNode);
&	get the file that printed the syntax tree;
* author:	lonelyforest
* data:		2006.03.26
*/
//-----------------------------------------------------------------------------
void Parser::getTreeFile()
{
	if (!m_program)
	{
		m_program = program();
	}

    if (traceParse) {
	   if ( !is_good() )
	   {
		outputMsg(-1, "Error(s) occur while parsing, stop printing syntax tree!");
	   }
	   else
	   {
		//outputMsg(-1, "successfully build the syntax tree, printing syntax tree now ...");

		out.open(treeFile.c_str());
		if (!out)
		{
			outputMsg(-1, "Create syntax tree file fail, syntax tree print stop now ... ");
		}
		else
		{
			PrintTree(m_program);
			sprintf(msg_temp, "Ok, treeFile has successfully save to  \"%s\"...", treeFile.c_str());
			outputMsg(-3,  msg_temp);   // -3 means Syntax tree file.
		}
		
		out.close();
	   }
    }
}


/**: PrintTree(TreeNode* pNode);
&
* author:	lonelyforest
* data:		2006.03.26
*/
//-----------------------------------------------------------------------------
void Parser::PrintTree(TreeNode* pNode)
{
	indent++;
	while (pNode != NULL) {
		for (int i  = 0; i < indent; ++i)
		{
			out << "\t";
		}

		switch (pNode->nodekind) {
			case funK:
				out << "Function declaration: "
					<< scan->key_word[(int)pNode->type].str
				    << " " <<pNode->name << endl;
				break;
			case varK:
				out << "Variable declaration: "
					<< scan->key_word[(int)pNode->type].str
					<<" " << pNode->name;
				if (pNode->bArr) out << "[" << pNode->iArrSize <<"] ";
				out  << endl;
				break;
			case paramK:
				out << "parameter: "
					<< scan->key_word[(int)pNode->type].str
					<< " "<< pNode->name ;
				if (pNode->bArr) out << "[]";
				out << endl;
				break;
			case stmtK:	// switch
				switch (pNode->kind.stmt){
					case readK:
						out << "call read(), args: " << endl;
						break;
					case writeK:
						out << "call write(), args:" << endl;
						break;
					case callK:
						out << "call " << pNode->name << "(), args:" << endl;
						break;
					case ifK:	out << "if" << endl;	break;
					case whileK: out<< "while"<<endl;	break;
					case returnK: out <<"return"<<endl; break;
					default:	out << "unknown node kind, maybe parser bug!" <<endl;
						break;
				} //  end of switch (pNode->kind.stmt)
				break;
			case expK:	// switch (pNode->kind.exp
				switch (pNode->kind.exp) {
					case OpK:
						out << "Op: " << pNode->name << endl;
						break;
					case ConstK:
						out << "const: " << pNode->name <<endl;
						break;
					case IDK:
						out << "ID: " << pNode->name;
						if (pNode->bArr) {
						    pNode = pNode->child[0];
							if (pNode) out << "[" << pNode->name  <<"]";
						}

						out << endl;
						break;
					default:
						out << "unkown node kind, maybe parser bug!" << endl;
						break;
				} // end of switch (pNode->kind.exp)
				break;
			default:
				out << "unkown node kind, maybe parser bug!" <<endl;
				break;
		} // end  switch (pNode->nodekind)

		for ( int k = 0; k < MAX_CHILDREN; ++k)
        	{
        		if (pNode->child[k] != NULL)
				PrintTree(pNode->child[k]);
        	}

		// 以前居然忘记了写这句， 差点吧我害死！
		pNode = pNode->sibling;
	} // end while

	--indent;
}


/**: help functions 
&
* author:	lonelyforest
* data:		2006.03.29
*/
//------------------------------------------------------------------------------
// create a new node
TreeNode* Parser::newNode(const NodeKind kind, const enum tokenType Type, 
						  const string &ID)
{
	TreeNode* temp = new TreeNode();
	temp->lineno = scan->lineno();
	temp->nodekind = kind;
	temp->type  = Type;
	temp->name  = ID;
	temp->scope = Scope;

	return temp;
}

// create a new statment node
TreeNode* Parser::newStmtNode(const StmtKind Kind, const string &Name)
{
	TreeNode *t = new TreeNode();
	t->lineno  = scan->lineno();
	t->nodekind = stmtK;
	t->kind.stmt = Kind;
	t->type		= k_NONE;
	t->name		= Name;
	t->scope	= Scope;

	return t;
}

// create a new expression node
TreeNode* Parser::newExpNode(const ExpKind Kind, const enum tokenType Type,
							 const string &Name)
{
	TreeNode *t = new TreeNode();
	t->lineno = scan->lineno();
	t->nodekind = expK;
	t->kind.exp = Kind;
	t->type		= Type;
	t->name		= Name;
	t->scope	= Scope;

	return t;
}

// get next token and check if its type is expected..
//-----------------------------------------------------------------------------
bool Parser::match(enum tokenType Type)
{
	cToken = scan->nextToken();
	return (cToken.type == Type);
}

// for the error recovery ...
void Parser::consumeUntil(const tokenType Type)
{
	while (cToken.type != Type && cToken.type != k_EOF)
		cToken = scan->nextToken();
}

void Parser::consumeUntil(const tokenType type1, const tokenType type2)
{
	while ( cToken.type != type1 && cToken.type != type2
		&& cToken.type != k_EOF)
		cToken = scan->nextToken();
}
//-----------------------------------------------------------------------------

/**: Grammar fuction implementations ...
&
* author:	lonelyforest
* data:		2006.03.29
*/
//-----------------------------------------------------------------------------

/**: 1. program -> delaration_list
&
* author:	lonelyforest
* data:		2006.03.30
*/
TreeNode* Parser::program()
{
	return declaration_list();
}

/**: 2. declaration-list → declaration-list declaration | declaration
&
* author:	lonelyforest
* data:		2006.03.30
*/
TreeNode* Parser::declaration_list()
{
	TreeNode *program = NULL,
		*last	= NULL,
		*temp	= NULL;
	cToken	= scan->nextToken();

	while (cToken.type != k_EOF)
	{
		if (cToken.type != k_INT && cToken.type != k_VOID
			&& cToken.type != SEMI)
		{
			scan->add_err();
			sprintf(msg_temp, "Syntax error: invalid type \'%s\'",
				cToken.str.c_str());
			outputMsg(scan->lineno(), msg_temp);
			consumeUntil(SEMI, RBRACE); // ';', '}'
		}
		else if ((temp = declaration()) != NULL)
		{
			if (!program)
			{
				program = temp;
				last = temp->LastSibling();
			}
			else
			{
				last->sibling = temp;
				last = temp->LastSibling();
			}
		}

		cToken = scan->nextToken();
	}

	return program;
}


/**: 3. declaration → var-declaration | fun-declaration
&
* author:	lonelyforest
* data:		2006.03.30
*/
//-----------------------------------------------------------------------------
TreeNode* Parser::declaration()
{
	Scope = "global";	// use global fun or var
	TreeNode* temp = NULL;
	tToken = cToken;
	cToken = scan->nextToken();
	iToken = cToken;

	if (iToken.type != k_ID)
	{
		scan->add_err();
		sprintf(msg_temp, "Syntax error: %s is a reserved token", iToken.str.c_str());
		outputMsg(scan->lineno(), msg_temp);
		consumeUntil(SEMI, RBRACE);
	}
	else
	{
		cToken = scan->nextToken(); // expected a '(', '[' or  ','
		if (cToken.type == LPARAN) 
		{  // '(' is fun declaration
			temp = fun_declaration();
		}
		else if (cToken.type == SEMI || cToken.type == LSQUARE
			|| cToken.type == COMMA)
		{
			temp = var_declaration();
		}
		else
		{
			scan->add_err();
			sprintf(msg_temp, "Syntax error: missing \';\' after indentifer %s",
				iToken.str.c_str());
			outputMsg(scan->lineno(), msg_temp);
			consumeUntil(SEMI, RBRACE);
		}
	}

	return temp;
}

/**: 4. var-declaration → type-specifier ID(,...); | type-specifier ID [ NUM ](,...);
&	 5. type-specifier → int | void
*
* author:	lonelyforest
* data:		2006.03.30
*/
//-----------------------------------------------------------------------------
TreeNode* Parser::var_declaration()
{ // now, cToken.str == ";", "," or "["
	TreeNode* temp = newNode(varK, tToken.type, iToken.str);

	if (cToken.type == LSQUARE)
	{ // array
		cToken = scan->nextToken(); // must NUM
		if (cToken.type != k_NUM)
		{
			scan->add_err();
			sprintf(msg_temp, 
				"Syntax error: missing array size in declaration of array %s[]",
				iToken.str.c_str());
			outputMsg(scan->lineno(), msg_temp);
			delete temp;
			consumeUntil(SEMI, RBRACE);	// error recovery in global declaration

			return NULL;
		}

		temp->bArr = true;
		temp->iArrSize = atoi(cToken.str.c_str());

		if (!match(RSQUARE))
		{ // need "]" 
			scan->add_err();
			sprintf(msg_temp, 
				"Syntax error: missing \']\' in declaration of array %s[]",
				iToken.str.c_str());
			scan->push();	// error recovery here
		}

		cToken = scan->nextToken(); // ";" or ","
	}

	if (cToken.type == COMMA)
	{
		iToken = cToken = scan->nextToken(); // next ID
		if (iToken.type != k_ID)
		{
			scan->add_err();
			sprintf(msg_temp, "Syntax error: %s is a reserved token", iToken.str.c_str());
			outputMsg(scan->lineno(), msg_temp);
			consumeUntil(SEMI, RBRACE);

			return temp;
		}

		cToken = scan->nextToken(); // expected ";", ",", "["
		if (cToken.type == SEMI || cToken.type == COMMA 
			|| cToken.type == LSQUARE)
		{
			temp->sibling = var_declaration();
		}
		else
		{
			scan->add_err();
			sprintf(msg_temp, 
				"Syntax error: missing \';\' after indentifer \"%s\"",
				iToken.str.c_str());
			outputMsg(scan->lineno(), msg_temp);
			scan->push();
			return temp;
		}
	}
	else if (cToken.type != SEMI)
	{
		scan->add_err();
		outputMsg(scan->lineno(),
			"Syntax error: missing \';\' after declaration sequence");
		consumeUntil(SEMI, RBRACE);
	}

	return temp;
}


/**:  6. fun-declaration → type-specifier ID ( params )  compound-stmt
&
* author:	lonelyforest
* data:		2006.03.30
*/
TreeNode* Parser::fun_declaration()
{	// cToken.str == "(", tToken contains type_specifier, iToken contains ID
	TreeNode *temp = newNode(funK, tToken.type, iToken.str);
	Scope = iToken.str;	// update function scope now,
	TreeNode *p = NULL;

	p = temp->child[0] = params();

	if (p) p->father = temp;
	while (p && p->sibling)
	{
		p = p->sibling;
		p->father = temp;
	}

	scan->push();

	if (!match(RPARAN))
	{
		scan->add_err();
		sprintf(msg_temp, 
			"Syntax error: missing \')\' in function %s(...) declaration",
			iToken.str.c_str());
		outputMsg(scan->lineno(), msg_temp);
		scan->push();
	}

	// compound statements
	p = temp->child[1] = compound_stmt();
	if (p) p->father = temp;
	while (p && p->sibling)
	{
		p = p->sibling;
		p->father = temp;
	}

	return temp;
}

/**: 7. params → params-list | void
&	 8. param-list→ param-list, param | param
&	 9. param→ type-specifier ID | type-specifier ID [ ]
* author:	lonelyforest
* data:		2006.03.30
*/
TreeNode* Parser::params()
{
	TreeNode *first = NULL;
	TreeNode *temp  = NULL;
	tToken = cToken = scan->nextToken();

	if (cToken.type == RPARAN)
	{
		scan->push();
		return temp; // NULL
	}

	if (tToken.type == k_VOID)
	{
		if (match(RPARAN))
		{ 
			scan->push();
			return temp;	// NULL
		}
		else
		{
			scan->push();	// not ")"
		}
	}

	while (tToken.type == k_INT || tToken.type == k_VOID)
	{
		iToken = cToken = scan->nextToken();
		if (iToken.type != k_ID)
		{
			scan->add_err();
			sprintf(msg_temp, 
				"Syntax error: invalid parameter \"%s\"",
				iToken.str.c_str());
			outputMsg(scan->lineno(), msg_temp);
		}
		else
		{
			temp = newNode(paramK, tToken.type, iToken.str);
			temp->sibling = first;
			first = temp;
		}

		cToken = scan->nextToken();
		if (cToken.type == LSQUARE)
		{
			temp->bArr = true;
			if (!match(RSQUARE))
			{
				scan->add_err();
				outputMsg(scan->lineno(), "Syntax error: arrar parameter missing \']\'");
				consumeUntil(COMMA, RPARAN);
			}
			else
			{
				cToken = scan->nextToken();	// ','
			}
		}

		if (cToken.type == RPARAN)	break; // ')'
		else if (cToken.type == COMMA) // ','
		{
			tToken = cToken = scan->nextToken();
		}
		else
		{
			break;
		}
	}

	scan->push();	// next is ')'

	return first;
}

/**:   10. compound-stmt → { local-declarations statement-list }
&
* author:	lonelyforest
* data:		2006.03.30
*/
TreeNode* Parser::compound_stmt()
{
	TreeNode *first = NULL,
		*last	= NULL,
		*temp	= NULL;
	bool noBraces = false;

	if (!match(LBRACE))
	{	// match "{"
		noBraces = true;
		scan->push();
	}

	// local-declarations
	while (true)
	{
		tToken = cToken = scan->nextToken();
		if (cToken.type == k_INT || cToken.type == k_VOID)
		{
			temp = local_declarations();
		}
		else
		{
			scan->push();
			break;
		}

		if (noBraces)	return temp;
		if (temp)
		{
			if (!first)
			{
				first = temp;
				last = temp->LastSibling();
			}
			else
			{
				last->sibling = temp;
				last = temp->LastSibling();
			}
		}
	}

	cToken = scan->nextToken();
	while (true)
	{
		temp = NULL;
		if (cToken.type == RBRACE)
		{
			if (noBraces)
			{
				scan->add_err();
				outputMsg(scan->lineno(), "Syntax error: unpaired \'}\'");
			}

			break;
		}

		if (cToken.type == k_EOF)
		{