7
\$\begingroup\$

I'm building the above mentioned parser. It reads a string of assembler instructions. I want to become a better coder, so I wanted to get a code review to start learning to do things property.

As we know instruction is a string with an instruction mnemonic like "mov","lea","add" followed by 0 to 3 operands, separated by commas. like mov [ebp+0ch],eax mov [edx],ebx and others alike

Right now I'm posting an Operand parser implementation. It's job is to take string iterators for range that is considered to be an operand string formatted like

" [  eax  + 4 * ebx  +  00256h   ] " base+index_by_scale + offset
" [eax+4*ebx+00256h]  " index_by_scale + base + offset
" [00256h+eax+4*ebx]  " offset + base + index_by_scale
" [4*ebx+eax+00256h]  " index_by_scale + base + offset
"00256h"                offset 
"[eax+00256h]"          base + offset
"[eax]"                 base only

So any combinations and variations with or without spaces, with or without arithmetic

#include "AsmRegister.h"
#include "AsmOperand.h"

class AsmOperandParser{
public:

    //Parsing will happen with help of string iterators
    typedef std::string::const_iterator strIt;

    //custom throw class for now
    class AsmOperandExpressionParserError{};


    enum class ExpressionType {
        MemoryReference,
        RegisterValue,
        ImmediateValue,
        Multiplication,
        Addition
    };

    enum class SyntaxElementType {
        VariableName,
        SquareBracketOpen,
        SquareBracketClose,
        Plus,
        Minus,
        Mult,
        RegisterValue,
        IntegralValue,
        Invalid
    };
    //Simplest primitive of an input string 
    //can be [,+,-,*,], a register name or a integral value string
    struct SyntaxElement {
        SyntaxElement() {
            data.value = 0;
            type = SyntaxElementType::Invalid;
        }
        SyntaxElementType type;
        union Data {
            Register::Id registerId;
            int value;
        }
        data;
        std::string variableName;
    };

    //ExpressionNode is a node of a syntax tree
    //it uses a union to use the same space for several representations
    //in case it acts like a holder of more complex expressions, it 
    //then holds the structure below with left and right pointers to other nodes

    struct ExpressionNode;
    struct ExpressionNodeTypeExpression {
        ExpressionType type;
        ExpressionNode* left;
        ExpressionNode* right;
    };
    //It can also be a pure Register name represented with Register::Id enum
    struct ExpressionNodeTypeRegisterId {
        Register::Id id;
    };
    //or just an immediate value
    //so the last two are the leaf nodes of the syntactic tree
    struct ExpressionNodeTypeImmediateValue {
        int value;
    };
    //this is the union to hold the above structures
    union ExpressionNodeData {
        ExpressionNodeTypeExpression expr;
        ExpressionNodeTypeRegisterId registerId;
        ExpressionNodeTypeImmediateValue value;
    };

    //that's the implementation of the node
    //it uses RAII basically and I've decided to use raw pointers
    //it uses constructor overloading for initializing the proper union struct
    struct ExpressionNode {
        enum class Type {
            Expression,
            Immediate,
            Register
        };

        explicit ExpressionNode(int in_value) :type{ Type::Immediate } {
            data.value.value = in_value;
        }
        ExpressionNode(Register::Id in_id) : type{ Type::Register } {
            data.registerId.id = in_id;
        }
        ExpressionNode(ExpressionNode* left, ExpressionNode* right, ExpressionType expressionType) :type{ Type::Expression } {
            data.expr.left = left;
            data.expr.right = right;
            data.expr.type = expressionType;
        }
        ExpressionNode(ExpressionNode* left) :type{ Type::Expression } {
            data.expr.left = left;
            data.expr.type = ExpressionType::MemoryReference;
        }
        ~ExpressionNode(){
            if (type == Type::Expression) {
                if (data.expr.left) {
                    delete data.expr.left;
                }
                if (data.expr.right) {
                    delete data.expr.right;
                }
            }
        }
        ExpressionNodeData data;
        Type type;
    };
    //The main method that does the parsing loop and recursion
    static ExpressionNode* Parse(strIt& it, const strIt itEnd, char terminatorChar);

private:
    //This method is used inside the parser to walk the string and retrieve meaningful elements from it. It updates the it argument (string iterator)
    static SyntaxElement ReadNextSyntaxElement(strIt& it, const strIt& itEnd);
};

Here is a method to walk the string and extract meaningful elements

AsmOperandParser::SyntaxElement AsmOperandParser::ReadNextSyntaxElement(strIt& it, const strIt& itEnd) {
    SyntaxElement element;
    strIt startIt = it;
    bool validElements = false;
    bool singleElement = true;
    bool hasDecimalDigits = false;
    bool hasHexDigits = false;
    int numberOfNonDigits = 0;
    while (it != itEnd) {
        unsigned char testSymbol = *it;
        //whitespace passing
        if (testSymbol == ' ') {
            if (singleElement) {
                ++it;
                startIt = it;
                continue;
            }
            else break;
        }

        switch (testSymbol){
        case '+':
            element.type = SyntaxElementType::Plus;
            break;
        case '-':
            element.type = SyntaxElementType::Minus;
            break;
        case '*':
            element.type = SyntaxElementType::Mult;
            break;
        case '[':
            element.type = SyntaxElementType::SquareBracketOpen;
            break;
        case ']':
            element.type = SyntaxElementType::SquareBracketClose;
            break;
        }
        //The valid ranges of characters that we expect to parse are:
        //0-9 : 0x30-0x39
        //a-z : 0x41-0x5a
        //A-Z : 0x61-0x7a 
        //Invalid ranges are :
        // 0x00 - 0x29
        // 0x39 - 0x40
        // 0x5b - 0x60
        // 0x7b - 0xff
        //All the special characters are expected to be met in the previous block
        if (element.type != SyntaxElementType::Invalid) {
            //By default element.type is Invalid
            //So if we got here someone has changed it
            //it could be only the switch case block, where we have
            //one character elements. If they are the first symbols met,
            //we immediately return with their value.
            if (singleElement){
                ++it;
                return element;
            }
            //but they can also be in the end of our string walk in
            //situations like "eax+..." ,then they act like loop terminators
            //and we proceed to deal with "eax" 
            break;
        }
        else if (testSymbol - 0x30 < 9) {
            hasDecimalDigits = true;
        }
        else if (testSymbol - 0x41 < 0x3a) {
            //In case we are within this range that means we are in 
            if (testSymbol - 0x41 < 6 || testSymbol - 0x61 < 6) {
                hasHexDigits = true;
            }
            else if (testSymbol - 0x5c < 6) {
                element.type = SyntaxElementType::Invalid;
                return element;
            }
            else {
                ++numberOfNonDigits;
            }
        }
        else {
            element.type = SyntaxElementType::Invalid;
            return element;
        }
        singleElement = false;
        ++it;
    }
    if (numberOfNonDigits == 0 && !hasDecimalDigits) {

    }
    std::string elementString{ startIt,it };

    //Valid numeric value
    if (numberOfNonDigits == 1 && elementString.back() == 'h' && (hasDecimalDigits || hasHexDigits)) {
        element.data.value = strtol(elementString.c_str(), nullptr, 16);
        element.type = SyntaxElementType::IntegralValue;
    }
    else if (numberOfNonDigits == 0 && hasDecimalDigits && !hasHexDigits) {
        element.data.value = strtol(elementString.c_str(), nullptr, 10);
        element.type = SyntaxElementType::IntegralValue;
    }
    //Valid register value
    else {
        Register::Id registerId = Register::GetIdFromString(elementString);
        if (registerId != Register::Id::null) {
            element.type = SyntaxElementType::RegisterValue;
            element.data.registerId = registerId;
        }
        else {
            element.variableName = elementString;
            element.type = SyntaxElementType::VariableName;
        }
    }
    return element;
}

And this is the Parse method

AsmOperandParser::ExpressionNode* AsmOperandParser::Parse(strIt& it, const strIt itEnd, char terminatorChar) {
    //we are building the syntactic tree here in simplified form, because 
    //we have only one operator precedence rule exception for *
    //for others we can use straight recursion
    //tmpNode_a is what we return from recursive calls to Parse(..)
    ExpressionNode* tmpNode_a{ nullptr };

    //tmpNode_b is for swap operations
    ExpressionNode* tmpNode_b;
    while (it != itEnd && *it != terminatorChar) {
        auto syntaxElement = ReadNextSyntaxElement(it, itEnd);
        switch (syntaxElement.type) {
        case SyntaxElementType::IntegralValue:
            tmpNode_a = new ExpressionNode((int)syntaxElement.data.value);
            break;
        case SyntaxElementType::RegisterValue:
            tmpNode_a = new ExpressionNode(syntaxElement.data.registerId);
            break;
        case SyntaxElementType::SquareBracketOpen:
            //for '[' we call recursion to parse the insides of [ ... ]
            //and create a node that represents memory reference expression
            tmpNode_a = new ExpressionNode(Parse(it, itEnd, ']'));
            break;
        case SyntaxElementType::Plus:
            //in case of addtion operator we create a new node with addition 
            //expression and old node and recursive parse result as left and right
            tmpNode_a = new ExpressionNode(tmpNode_a, Parse(it, itEnd, terminatorChar), ExpressionType::Addition);
            break;
        case SyntaxElementType::Minus:
            tmpNode_a = new ExpressionNode(tmpNode_a, Parse(it, itEnd, terminatorChar), ExpressionType::Addition);
            break;
        case SyntaxElementType::Mult:
            //for multiplication we dont recurse, just read the next element
            syntaxElement = ReadNextSyntaxElement(it, itEnd);
            switch (syntaxElement.type) {
            case SyntaxElementType::IntegralValue:
                tmpNode_b = new ExpressionNode((int)syntaxElement.data.value);
                break;
            case SyntaxElementType::RegisterValue:
                tmpNode_b = new ExpressionNode(syntaxElement.data.registerId);
                break;
            default: //in case we have met something invalid we throw;
                if (tmpNode_b) delete tmpNode_b;
                if (tmpNode_a) delete tmpNode_a;
                throw AsmOperandExpressionParserError();
                break;
            }
            tmpNode_a = new ExpressionNode(tmpNode_a, tmpNode_b, ExpressionType::Multiplication);
            break;
        }
    }
    return tmpNode_a;
}
\$\endgroup\$
1
\$\begingroup\$

I see some things that may help you improve your code.

Eliminate unused variables

The variable validElements in the ReadNextSyntaxElement() is defined but never used. Since unused variables are a sign of poor code quality, you should seek to eliminate them. Your compiler is probably smart enough to warn you about such things if you know how to ask it to do so.

Provide default case

Within the switch statement in the Parse routine, a number of enumerated values are not explicitly handled. Either provide cases for the missing enum values, or better, provide a default case to catch anything that isn't otherwise handled. The latter is better because if any enumerations are added later, you don't have to worry about forgetting to update the switch as long as the default does something reasonable.

Consider using std::regex

If your compiler supports it, you might consider using std::regex to streamline some of the parsing functions. In particular, the relatively large ReadNextSyntaxElement would be shorter if it used a regex.

Fix the formatting

The indentation, especially toward the end of Parse() is inconsistent and makes it hard to understand the code.

Consider using standard parser tools

A task like this is well suited to being approached with tools like lex and yacc (or equivalents flex and bison). There is a bit of effort in learning to use the tools, but once you do, I think you will find that such tasks are rendered much simpler and more easily maintained if done using such tools. There are also other such tools including ANTLR and boost::spirit that you might wish to evaluate as other possible mechanisms to simplify the work.

\$\endgroup\$
  • \$\begingroup\$ Thanks a lot for your valuable info, Edward. I'm really considering regex to improve code readability. What do you think of it's performance compared with this kind of straight code? \$\endgroup\$ – Antiusninja Jan 29 '16 at 0:44
  • \$\begingroup\$ Also I wanted to know what would be a better way to provide default case th ReadNextSyntaxElement switch-case block where I supply only those cases for known symbols and use range-based check for the allowed alphabeth? \$\endgroup\$ – Antiusninja Jan 29 '16 at 0:46
  • \$\begingroup\$ I find that a regex, carefully written, can easily equal the performance of more lengthy hand-written equivalent code. For default case, you could perhaps print an error and exit(1); since something will have gone wrong if it's possible to get there. That's the advantage of having a default. Alternatively, you could throw an error, but there's not likely much that the caller can do to fix such a condition. \$\endgroup\$ – Edward Jan 29 '16 at 13:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.