Monster token parser function

This function will read an expression (made up of tokens) from the vector of tokens passed into it. It will remove the tokens that make up the expression from the vector and return them.

A token is added to the expression if

• it is the first token
• it has an operator before it

Brackets are handled in parseBracketTokens (which calls this function)

RawExpression *parseExpressionTokens(
vector<Token*> &tokens, bool brackets = false) {

// This is a vector of elements that make up an expression
vector<RawExpressionElement*> elements;

while(tokens.size() > 0) {

// Operands must be at the start of an expression or after an operator
if(tokenIsOperand(tokens[0])) {

if(elements.size() == 0 ||
eElementIsRelationalOperator(elements.back())) {
elements.push_back(makeEElementFromToken(tokens[0]));
removeToken(tokens, 0);
continue;
}

// This token is part of the next expression, break from the loop
break;
}

if(tokenIsRelationalOperator(tokens[0])) {

// Make sure we have an operand left of it

if(tokens[0]->type == TOKEN_MINUS) {
if(elements.size() == 0 ||
!eElementIsOperand(elements.back())) {

// handle the minus number or symbol :O

}
}

if(elements.size() != 0 &&
eElementIsOperand(elements.back())) {
elements.push_back(makeEElementFromToken(tokens[0]));
removeToken(tokens, 0);
continue;
}

throw(string("Operator has bad lhand:") + tokenToString(tokens[0]));
}

// A closing bracket marks the end of an expression

if(tokens[0]->type == TOKEN_CLOSEBRACKET) {
if(!brackets)
throw(string("Unmatched closing bracket"));

break;
}

// Handle brackets and function calls

if(tokens[0]->type == TOKEN_OPENBRACKET) {

// Check if it follows an identifier (if so, its a function call)

if(elements.size() != 0 &&
elements.back()->e_type == REE_IDENTIFIER) {
RawExpression *e = parseBracketTokens(tokens);
string id = ((IdentifierREElement*)elements.back())->id;
removeExpressionElement(elements, elements.size()-1);
elements.push_back(new FunctionCallREElement(id, e));
continue;
}

// This is not a function call
if(elements.size() == 0 ||
!eElementIsOperand(elements.back())) {
RawExpression *e = parseBracketTokens(tokens);
elements.push_back(e);
continue;
}

// This is part of another expression
break;
}

// Parse Identifiers

if(tokens[0]->type == TOKEN_IDENTIFIER) {
elements.push_back(makeEElementFromToken(tokens[0]));
removeToken(tokens, 0);
continue;
}

// Unknown token, throw an error

throw(string("Unexpected token in expression:") +
tokenToString(tokens[0]));
}

// Make sure expression doesn't end with an operator.
if(elements.size() > 0 && !eElementIsOperand(elements.back()))
throw(string("Operator missing rhand value"));

return new RawExpression(elements);
}


I would like to split this code up into something like

if(processOperand(tokens)) continue;
if(processRelationalOperator(tokens)) continue;
if(precessBracket(tokens)) continue;
if(processIdentifier(tokens)) continue;


But the fact that it has to continue or break in some cases leaves me questioning the best was to approach this.

I think I might have to define a new type something like { NOT_RELEVANT, PART_OF_EXPRESSION, END_OF_EXPRESSION }

and then do this

ExpressionElement *e; // Use this an out ptr in the function call below
result = processOperand(tokens, e);
if(result == END_OF_EXPRESSION) break;
// else its NOT_RELAVANT so try parsing the next type


But it seems like a bad idea to define a new type for this.

What do you think?

My first thought is that parsers should be implemented as table driven state machines for exactly the reason you see in the code :-)

Actually, I think breaking this into a set of separate functions is one good approach, and adding a new enum to support it makes it very clear the state of the expression after each step.

Another option I would consider is determining the paths through the code and possibly doing some optimizations around them at the expense of clarity. There appear to be several places where once you first entered a conditional block, you have committed to not doing any other code in the loop. Re-arranging these may eliminate some of the separate continue/break statements and allow easier refactoring.

About refactoring this concrete routine (not algorithm itself):

• Replace elements.size() == 0 by elements.empty(); it is faster.
• Replace whole while cycle with for_each
• Normalize tokens identification ( now some tokens are identified by separate routines, but some are identified via if(type == blabl) )
• Move logic after each token identifying if to separate routines:

class TokenToElements{
typedef vector<RawExpressionElement *> el_vec_t;
el_vec_t &elements;
public:
TokenToElements( el_vec_t &e ):elements( e ){};

enum TokenType{
TK_OPERAND,
TK_REL_OP,
TK_CLOSEBRACKET,
TK_OPENBRACKET,
TK_IDENTIFIER,
TK_UNKNOWN
};

TokenType get_token_type( Token *token ){
if ( tokenIsOperand( token ) ) return TK_OPERAND;
if ( tokenIsRelationOperator( token ) ) return TK_REL_OP;
if ( token->type == TOKEN_CLOSEBRACKET ) return TK_CLOSEBRACKET;
if ( token->type == TOKEN_OPENBRACKET ) return TK_OPENBRACKET;
if ( token->type == TOKEN_IDENTIFIER ) return TK_IDENTIFIER;
return TK_UNKNOWN;
};

void do_operand( Token *token ){ ... };
void do_relation_operator( Token *token ){ ... };
void do_closebraket( Token *token ){ ... };
void do_openbraket( Token *token ){ ... };
void do_identifier( Token *token ){ ... };

void opearator()( Token *token ){
switch( get_token_type( token ) ){
case TK_OPERAND:
do_operand( token );
break;
case TK_REL_OP:
do_relation_operator( token );
break;
case TK_CLOSEBRACKET:
do_closebraket( token );
break;
case TK_OPENBRACKET:
do_openbraket( token );
break;
case TK_IDENTIFIER:
do_identifier( token );
break;
default:
throw std::runtime_error( "Unexpected token in expression:" + tokenToString( token ) );
};
};
};

RawExpression *parseExpressionTokens(
vector<Token*> &tokens, bool brackets = false) {

// This is a vector of elements that make up an expression
vector<RawExpressionElement*> elements;

std::for_each( tokens.begin(), tokens.end(), TokenToElements( elements ) );
};


Another solution is return pointer to callback function from get_token_type and call it instead of switch. Code of TokenToElement::operator() will be even shorter:

typedef void (TokenToElement::*hndl_fun_t)( Token *);

void operator()( Token * token ){
hndl_fun_t hndl = get_token_handler( token )
(this->*hdnl)( token );
};

• This wont work. I need to know if the next token is part of the current expression. If it is not I need to leave the loop. – t123 Apr 14 '11 at 11:44
• you have 'elements' array in every of your routines in 'TokenToElements' functor :) so your logic from monster function can be copied without problems. – Максим Кошелев Apr 15 '11 at 8:00