parser.cpp

编译器 用C语言对下述文法和单词表定义的语言设计编制一个编译器

/******************************************************************************
 * parser.cpp
 *
 * 2008-04-20 15:38
 * 周鑫([e-mail])
 *
 * 语法分析器实现。
 *****************************************************************************/

#include <QString>
#include "parser.h"

Parser::Parser()
{
	parameter = 0.0;
	originX = 0.0;
	originY = 0.0;
	scaleX = 1.0;
	scaleY = 1.0;
	rotAngle = 0.0;
	noError = true;
	glossary = new Glossary;
}

Parser::~Parser()
{
	delete glossary;
}

bool Parser::build( const QString &fileName )
{
	_errorList.clear();
	_errorList << "Debug Message: \n";

	glossary->openFile( fileName );
	fetchToken();			//获取第一个记号
	program();			//递归下降分析

	return noError;
}

void Parser::fetchToken()
{
	token = glossary->getToken();
	if( token.type == ERRTOKEN )
	{
		syntaxError(1);
	}
}

void Parser::matchToken( enum TokenType type )
{
	if( token.type != type )
	{
		//syntaxError(2);
	}
	else
	{
		_errorList << QString( "Match Token: %1" ).arg( TypeString[ type ] );
	}
	fetchToken();
}

void Parser::syntaxError( int errorCase )
{
	switch( errorCase )
	{
		case 1:
			_errorList << QString( "Line %1:\tError token: %2" )
				.arg( glossary->lineNo() ).arg( token.lexeme );
			break;
		case 2:
			_errorList << QString( "Line %1:\tUnexcepted token: %2" )
				.arg( glossary->lineNo() ).arg( token.lexeme );
			break;
	}
	noError = false;
}

void Parser::program()
{
	while( token.type != NONTOKEN )
	{
		statement();
		matchToken( SEMICO );
	}
}

void Parser::statement()
{
	switch( token.type )
	{
		case ORIGIN:
			originStatement();
			break;
		case SCALE:
			scaleStatement();
			break;
		case ROT:
			rotStatement();
			break;
		case FOR:
			forStatement();
			break;
		default:
			//syntaxError(2);
			break;
	}
}

//----------------------------originStatement的递归子程序
void Parser::originStatement()
{
	struct ExprNode *tmp;

	matchToken( ORIGIN );
	matchToken(IS );
	matchToken( LBRACKET );
	tmp = expression();
#if 0
#ifndef PARSER_DEBUG
	originX = GetExprValue( tmp );		//获取横坐标的平移距离
	DelExprTree( tmp );
#endif
#endif
	matchToken( COMMA );
	tmp = expression();
#if 0
#ifndef PARSER_DEBUG
	originY = GetExprValue( tmp );		//获取纵坐标的平移距离
	DelExprTree( tmp );
#endif
#endif
	matchToken( RBRACKET );
}

//-------------------------------scaleStatement的递归子程序
void Parser::scaleStatement()
{
	struct ExprNode *tmp;

	matchToken( SCALE );
	matchToken( IS );
	matchToken( LBRACKET );
	tmp = expression();
#if 0
#ifndef PARSER_DEBUG
	scaleX = GetExprValue( tmp );		//获取横坐标的平移距离
	DelExprTree( tmp );
#endif
#endif
	matchToken( COMMA );
	tmp = expression();
#if 0
#ifndef PARSER_DEBUG
	scaleY = GetExprValue( tmp );		//获取纵坐标的平移距离
	DelExprTree( tmp );
#endif
#endif
	matchToken( RBRACKET );
}

//-----------------------rotStatement的递归子程序
void Parser::rotStatement()
{
	struct ExprNode *tmp;

	matchToken( ROT );
	matchToken( IS );
	tmp = expression();
#if 0
#ifndef PARSER_DEBUG
	rotAngle = GetExprValue( tmp );
	DelExprTree( tmp );
#endif
#endif
}

//----------------------------forStatement的递归子程序
void Parser::forStatement()
{
	//各表达式语法树根节点指针
	struct ExprNode *start_ptr, *end_ptr, *step_ptr, *x_ptr,*y_ptr;

	matchToken( FOR );
	matchToken( T );
	matchToken( FROM );

	start_ptr = expression();		//构造参数起点表达式语法树

	matchToken( TO );

	end_ptr = expression();			//构造参数终点表达式语法树

	matchToken(STEP);

	step_ptr = expression();		//构造参数步长表达式语法树

	matchToken( DRAW );
	matchToken( LBRACKET );

	x_ptr = expression();			//构造横坐标表达式的语法树

	matchToken( COMMA );

	y_ptr = expression();			//构造纵坐标表达式语法树

	matchToken( RBRACKET );
}

// expression = term { (PLUS | MINUS) term }
struct ExprNode *Parser::expression()
{
	struct ExprNode *left, *right;	//左右子树节点的指针
	TokenType token_tmp;			//当前记号
	left = term();				//分析左操作数且得到其语法树
	while( token.type == PLUS || token.type ==MINUS )
	{
		token_tmp = token.type;
		matchToken( token_tmp );
		//分析右操作数且得到其语法树
		right = term();
		//构造运算的语法树，结果为左子树
		left = makeExprNode( token_tmp, left, right);
	}
	printSyntaxTree( left );
	return left;				//返回最终表达式的语法树
}

// term = factor { (MUL | DIV) factor }
struct ExprNode *Parser::term()
{
	struct ExprNode *left,*right;
	TokenType token_tmp;

	left = factor();
	while ( token.type == MUL || token.type == DIV )
	{
		token_tmp = token.type;
		matchToken( token_tmp );
		right = factor();
		left = makeExprNode( token_tmp, left, right);
	}
	return left;
}

// factor = PLUS factor | MINUS factor | component
struct ExprNode *Parser::factor()
{
	struct ExprNode *left, *right;

	if ( token.type == PLUS )		//匹配一元加运算
	{
		matchToken( PLUS );
		right = factor();		//表达式退化为仅有右操作数的表达式
	}
	else if ( token.type == MINUS )		//匹配一元减运算
	{
		matchToken( MINUS );		//表达式转化为二元减运算的表达式
		right = factor();
		left = new ExprNode;
		left->opCode = CONSTANT;
		left->Content.CaseConst = 0.0;
		right = makeExprNode( MINUS, left, right );
	}
	else
	{
		right = component();		//匹配非终结符component
	}
	return right;
}

// component = atom POWER component | atom
struct ExprNode *Parser::component()
{
	struct ExprNode *left, *right;

	left = atom();
	if( token.type == POWER )
	{
		matchToken( POWER );
		right = component();		//递归调用component以实现POWER的右结合
		left = makeExprNode( POWER, left, right );
	}
	return left;
}

// atom = CONSTANT | T | FUNC LBRACKET expression RBRACKET | LBRACKET expression RBRACKET
struct ExprNode *Parser::atom()
{
	struct Token tempToken = token;
	struct ExprNode *address, *tempNode;

	switch ( token.type )
	{
		case CONSTANT:
			matchToken( CONSTANT );
			address = makeExprNode( CONSTANT, tempToken.value );
			break;
		case T:
			matchToken( T );
			address = makeExprNode( T );
			break;
		case FUNC:
			matchToken( FUNC );
			matchToken( LBRACKET );
			tempNode = expression();
			address = makeExprNode( FUNC, tempToken.pFunction, tempNode );
			matchToken( RBRACKET );
			break;
		case LBRACKET:
			matchToken( LBRACKET );
			address = expression();
			matchToken( RBRACKET );
			break;
		default:
			syntaxError(2);
	}
	return address;
}

//-----------------------生成语法树的一个节点
struct ExprNode *Parser::makeExprNode( enum TokenType opcode, ... )
{
	struct ExprNode *ExprPtr = new ( struct ExprNode );
	ExprPtr->opCode = opcode;		//接收记号的类别
	va_list ArgPtr;
	va_start( ArgPtr, opcode );
	switch( opcode )			//根据记号的类别构造不同的节点
	{
		case CONSTANT:			//常数节点
			ExprPtr->Content.CaseConst = (double)va_arg( ArgPtr, double );
			break;
		case T:				//参数节点
			ExprPtr->Content.CaseParmPtr = &parameter;
			break;
		case FUNC:			//函数调用节点
			ExprPtr->Content.CaseFunc.MathFuncPtr =
				(FuncPtr)va_arg( ArgPtr, FuncPtr );
			ExprPtr->Content.CaseFunc.Child =
				(struct ExprNode *)va_arg( ArgPtr, struct ExprNode * );
			break;
		default:			//二元运算节点
			ExprPtr->Content.CaseOperator.Left =
				(struct ExprNode *)va_arg( ArgPtr, struct ExprNode * );
			ExprPtr->Content.CaseOperator.Right =
				(struct ExprNode *)va_arg( ArgPtr, struct ExprNode * );
			break;
	}
	va_end( ArgPtr );
	return ExprPtr;
}

//------------------先序遍历并打印表达式的语法树
void Parser::printSyntaxTree( struct ExprNode *root, int indent )
{
	switch ( root->opCode )
	{
		case PLUS:
			_errorList << QString( indent, '\t' ) + "+" ;
			break;
		case MINUS:
			_errorList << QString( indent, '\t' ) + "-";
			break;
		case MUL:
			_errorList << QString( indent, '\t' ) + "*";
			break;
		case DIV:
			_errorList << QString( indent, '\t' ) + "/";
			break;
		case POWER:
			_errorList << QString( indent, '\t' ) + "^";
			break;
		case FUNC:
			_errorList << QString( indent, '\t' ) + QString( "0x%1" )
				.arg( (unsigned long)(root->Content.CaseFunc.MathFuncPtr), 0, 16 );
			break;
		case CONSTANT:
			_errorList << QString( indent, '\t' ) + QString( "%1" )
				.arg(root->Content.CaseConst);
			break;
		case T:
			_errorList << QString( indent, '\t' ) + "T";
			break;
		default:
			_errorList << QString( indent, '\t' ) + "Error Tree Node!";
			return;
	}

	//叶子节点返回
	if ( root->opCode == CONSTANT || root->opCode == T )
	{
		return;
	}
	//递归打印一个孩子的节点
	if ( root->opCode == FUNC )
	{
		printSyntaxTree( root->Content.CaseFunc.Child, indent+1 );
	}
	//递归打印两个孩子的节点
	else
	{
		printSyntaxTree( root->Content.CaseOperator.Left, indent+1 );
		printSyntaxTree( root->Content.CaseOperator.Right, indent+1 );
	}
}