发现只要写出 BNF 式，用 LL1 的自上向下分析法很轻易的就解决问题。下面是一个简单的四则运算式子，在次基础上可以很轻易的加入其他的元素，比如浮点数，负数等。下面是 BNF 式：

////////////////////////////////////////////////////////////////////
// BNF 式子：
// 
// 语法器中
// S := S1
// S1 := S2 + S2 | S2 - S2 | S2
// S2 := S3 * S3 | S3 - S3 | S3
// S3 := ( S ) | N

// 以下放在词法分析部分完成
// N  := Digit N | Digit
// Digit := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
//
////////////////////////////////////////////////////////////////////

对应的函数是这几个：

// 语法处理
int ParseResult();			// S  := S1
int ParsePlusMinus();		        // S1 := S2 + S2 | S2 - S2 | S2
int ParseMultiplyDivide();	        // S2 := S3 * S3 | S3 - S3 | S3
int ParseNum();				// S3 := ( S ) | N 

// 词法分析
enTokenType GetNextToken();

实现过程：

// 语法器接受的符号类型
enum enTokenType			
{
	TOKEN_NUM,		// 数

	// op
	TOKEN_PLUS,		// + 
	TOKEN_MINUS,		// -
	TOKEN_MULTIPLY,		// *
	TOKEN_DIVIDE,		// /

	TOKEN_LBRACKET,		// (
	TOKEN_RBRACKET,		// )

	// over
	TOKEN_END,		// 终结符
};

char szBuf[0xFF];				// 计算的表达式

enTokenType NextToken;				// 读入的下一个符号
int	nNextValue;				// 下一个数值



////////////////////////////////////////////////////////////////////////// 实现

int _tmain(int argc, _TCHAR* argv[])
{

	if ( argc <= 1 ) return 1;
	memset( szBuf, 0, sizeof( szBuf));
	_tcscpy( szBuf, argv[1]);

	int nResult = ParseResult();
	std::cout << "数值是" << nResult << std::endl;
	system( "pause");
	return 0;
}


// 简单的错误处理
void Error( const char* strError );

// S  := S1
int ParseResult()
{
	return ParsePlusMinus();
}

// S1 := S2 + S2 | S2 - S2 | S2
int ParsePlusMinus()
{
	int nResult = ParseMultiplyDivide();
	for (;;)
	{
		switch( NextToken )
		{
		case TOKEN_PLUS:						// +
			nResult +=  ParseMultiplyDivide();
			break;
		case TOKEN_MINUS:						// - 
			nResult -= ParseMultiplyDivide();
			break;
		default:
			return nResult;
		}
	}
}

// S2 := S3 * S3 | S3 - S3 | S3
int ParseMultiplyDivide()
{
	int nResult = ParseNum();
	for (;;)
	{
		switch( NextToken )
		{
		case TOKEN_MULTIPLY:					// *
			nResult *= ParseNum();
			break;
		case TOKEN_DIVIDE:					// /
			{
				int nRight = ParseNum();
				if ( nRight == 0 )	
					Error( "被除数不能为 0 ");
				else
					nResult /= nRight;
			}
			break;
		default:
			return nResult;
		}
	}
}

// S3 := ( S ) | N 
int ParseNum()
{
	int nResult = 0;

	NextToken = GetNextToken();
	switch( NextToken )
	{
	case TOKEN_LBRACKET:						// (
		nResult = ParseResult();			
		if ( NextToken != TOKEN_RBRACKET )
			Error( "期待的 ) 没有到来");
		NextToken = GetNextToken();
		return nResult;
	case TOKEN_RBRACKET:						// )
		return nResult;
	case TOKEN_NUM:							// 一个整数
		nResult = nNextValue;
		NextToken = GetNextToken();
		return nResult;
	case TOKEN_END:							// 终结
		return nResult;
	default:
		Error( "遇到不期待的符号");
		NextToken = GetNextToken();
		break;
	}
}

// 词法分析
// N  := Digit N | Digit
// Digit := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
enTokenType  GetNextToken()
{
	static char* pCharPos = szBuf;
	char ch = *pCharPos;

	if ( (pCharPos - szBuf) >= _tcslen( szBuf ) )
	{
		return TOKEN_END;
	}
	if ( isdigit( ch ) )
	{
		nNextValue = 0;
		while ( isdigit( ch ))
		{
			nNextValue = 10 * nNextValue + (ch - '0');
			pCharPos++;
			ch = *pCharPos;
		}
		return TOKEN_NUM;
	}
	else 
	{
		switch( ch )
		{
		case '+': pCharPos++;	return TOKEN_PLUS;
		case '-': pCharPos++;	return TOKEN_MINUS;
		case '*': pCharPos++;	return TOKEN_MULTIPLY;
		case '/': pCharPos++;	return TOKEN_DIVIDE;
		case '(': pCharPos++;	return TOKEN_LBRACKET;
		case ')': pCharPos++;	return TOKEN_RBRACKET;
		default:
			Error( "遇到不可接受的符号");
		}
	}
	pCharPos++;
}

// 简单的错误处理
void Error( const char* strError )
{
	std::cout << "----------------------" << std::endl;
	std::cout << "       " << strError << std::endl;
	std::cout << "----------------------" << std::endl;
	exit( 0 );
}

• 相关文章