parse_expr.cpp

斯坦福Energy211/CME211课《c++编程——地球科学科学家和工程师》的课件

#include "eval_expr.h"

int Term( value_stack& s, int token, string& tok_str );
int ExprRest( value_stack& s, int token, string& tok_str );
int Factor( value_stack& s, int token, string& tok_str );
int TermRest( value_stack& s, int token, string& tok_str );

// The grammar for expressions is:
//
// E  -> TE'
// E' -> ATE' | empty string
// A  -> + | -
// T  -> FT'
// T' -> MFT' | empty string
// M  -> * | /
// F  -> number | -F | ( E )
// 
// where E is an expression, T is a term, F is a factor,
// E' is the remainder of an expression after the first
// term, and T' is the remainder of a term after the
// first factor.  The | is used to separate alternatives
// for each grammar symbol.
//
// The next several functions implement the parsing of
// the various grammar symbols.  All of them take the
// same arguments: the stack of values used to evaluate
// the expression, the code of the most recently read
// token, and the text of that token.  The return value
// is always the code of the next token to be processed,
// and tok_str, passed by reference, has been modified
// to contain the text corresponding to that token.
//
// The calls that each function makes are determined by
// the grammar.  For example, E -> TE' results in Expr
// calling Term and ExprRest.

// An expression begins with a term.  ExprRest handles
// anything that follows
int Expr( value_stack& s, int token, string& tok_str )
{
	token = Term( s, token, tok_str );
	return ExprRest( s, token, tok_str );
}

// The remainder of an expression, after the first term,
// consists of either nothing, or an additive operator
// followed by at least one term
int ExprRest( value_stack& s, int token, string& tok_str )
{
	// To preserve left associativity of addition and
	// subtraction, we use a while loop to read terms,
	// instead of calling this function recursively,
	// which would cause right associativity since it's
	// at the end of the grammar rule
	while ( token == TOK_ADD || token == TOK_SUB )
	{
		int op = token;
		// Read past operator
		token = nexttoken( tok_str );
		// Then read next term
		token = Term( s, token, tok_str );
		// Pop, add or subtract, then push
		double x2 = s.top();
		s.pop();
		double x1 = s.top();
		s.pop();
		double y = ( op == TOK_ADD ? x1 + x2 : x1 - x2 );
		s.push( y );
	}
	// Now, the next input should be end-of-string
	return token;
}

// A term begins with a factor.  TermRest handles
// anything that follows
int Term( value_stack& s, int token, string& tok_str )
{
	token = Factor( s, token, tok_str );
	return TermRest( s, token, tok_str );
}

// The remainder of a term, after the first factor,
// consists of either nothing, or a multiplicative
// operator followed by at least one factor
int TermRest( value_stack& s, int token, string& tok_str )
{
	// To preserve left associativity of multiplication
	// and division, we use a while loop to read factors,
	// instead of calling this function recursively,
	// which would cause right associativity since it's
	// at the end of the grammar rule
	while ( token == TOK_MUL || token == TOK_DIV )
	{
		int op = token;
		// Read past operator
		token = nexttoken( tok_str );
		token = Factor( s, token, tok_str );
		// Pop, multiply or divide, then push
		double x2 = s.top();
		s.pop();
		double x1 = s.top();
		s.pop();
		double y = ( op == TOK_MUL ? x1 * x2 : x1 / x2 );
		s.push( y );
	}
	// Now, the next input should be an additive 
	// operator, or end-of-string
	return token;
}

// A factor is either a number, a negated factor, or
// a parenthesized expression.  A number consists of
// digits, followed by an optional decimal point, 
// followed by more optional digits. 
int Factor( value_stack& s, int token, string& tok_str )
{
	if ( token == TOK_NUM )
	{
		// push the number onto the stack
		istringstream is( tok_str );
		double x;
		is >> x;
		s.push( x );
		token = nexttoken( tok_str );
	}
	else if ( token == TOK_SUB )
	{
		token = nexttoken( tok_str );
		token = Factor( s, token, tok_str );
		// pop, negate, push
		double x = s.top();
		s.pop();
		s.push( -x );
	}
	else if ( token == TOK_LPAR )
	{
		token = nexttoken( tok_str );
		token = Expr( s, token, tok_str );
		if ( token != TOK_RPAR )
			throw exception();
		else
			token = nexttoken( tok_str );
	}
	else
		throw exception();
	return token;
}