mixal::Expression Class Reference

#include <expression.h>

Public Member Functions
	Expression ()
	Expression (const std::string &expression, const std::string &lineSymbol="")
bool	evaluated () const
const AtomicValue &	result () const
bool	literalConstant () const
const std::unordered_set< std::string >	depends () const
const std::vector< Atomic >	atomics () const
const std::vector< Operation >	operations () const
void	parse (const std::string &expression, const std::string &lineSymbol)
bool	evaluate (const std::unordered_map< std::string, AtomicValue > &constants)
void	replaceSymbol (const std::unordered_map< std::string, std::string > &mapping)
void	reset ()
bool	operator== (const Expression &expression)
bool	operator!= (const Expression &expression)

Static Public Member Functions
static Expression	getConstExpression (const AtomicValue &value)
static Expression	getConstExpression (const std::string &symbol)
static Expression	getConstOffsetExpression (const std::string &symbol, int32_t offset)
static bool	isValidFirst (char ch)
static bool	isValidChar (char ch)

Friends
std::ostream &	operator<< (std::ostream &out, const Expression &expression)

Detailed Description

Parse and store expressions.

Definition at line 103 of file expression.h.

Constructor & Destructor Documentation

Expression() [1/2]

mixal::Expression::Expression

(

)

Initialize with zeros.

Definition at line 13 of file expression.cpp.

                       : _evaluated(false), _result(), _literalConstant(false),
    _depends(), _atomics(), _operations() {
}

Referenced by getConstExpression(), and getConstOffsetExpression().

Expression() [2/2]

mixal::Expression::Expression ( const std::string &  expression, const std::string &  lineSymbol = ""  )

explicit

Initialize with parsing

See also

parse(const std::string&, const std::string&)

Definition at line 17 of file expression.cpp.

                                                                               :
    _evaluated(false), _result(), _literalConstant(false),
    _depends(), _atomics(), _operations() {
    parse(expression, lineSymbol);
}

References parse().

Member Function Documentation

atomics()

const std::vector<Atomic> mixal::Expression::atomics ( ) const

inline

Get the atomics in the expression.

Definition at line 154 of file expression.h.

{ return _atomics; }

depends()

const std::unordered_set<std::string> mixal::Expression::depends ( ) const

inline

Get the symbols that should be evaluated before evaluating this expression.

Definition at line 152 of file expression.h.

{ return _depends; }

evaluate()

bool mixal::Expression::evaluate

(

const std::unordered_map< std::string, AtomicValue > &

constants

)

Try to evaluate the parsed expression.

Parameters

constants

A dictionary that maps from symbol names to evaluated atomic values.

Returns

Return true if the expression can be evaluated with the given dictionary.

Definition at line 233 of file expression.cpp.

                                                                                   {
    if (_atomics.size() == 0) {
        return false;
    }
    auto evalAtomic = [&constants](const Atomic& atomic, AtomicValue* result) -> bool {
        if (atomic.type == AtomicType::INTEGER) {
            result->negative = atomic.negative;
            result->value = atomic.integer;
            if (atomic.negative) {
                result->value = -result->value;
            }
        } else {
            auto it = constants.find(atomic.symbol);
            if (it == constants.end()) {
                return false;
            }
            *result = it->second;
            if (atomic.negative) {
                result->negative = !result->negative;
                result->value = -result->value;
            }
        }
        return true;
    };
    AtomicValue first, second;
    if (!evalAtomic(_atomics[0], &first)) {
        return false;
    }
    for (size_t i = 0; i < _operations.size(); ++i) {
        if (!evalAtomic(_atomics[i + 1], &second)) {
            return false;
        }
        switch (_operations[i]) {
        case Operation::ADD:
            first.value += second.value;
            break;
        case Operation::SUBTRACT:
            first.value -= second.value;
            break;
        case Operation::MULTIPLY:
            first.value *= second.value;
            break;
        case Operation::FLOOR_DIV:
            first.value /= second.value;
            break;
        case Operation::FIELD:
            first.value = first.value * 8 + second.value;
            break;
        }
        if (first.value > 0) {
            first.negative = false;
        } else if (first.value < 0) {
            first.negative = true;
        }
    }
    _evaluated = true;
    _result = first;
    return true;
}

References mixal::Atomic::integer, mixal::Atomic::negative, result(), mixal::Atomic::symbol, and mixal::Atomic::type.

evaluated()

bool mixal::Expression::evaluated ( ) const

inline

Whether the expression has been evaluated.

Definition at line 144 of file expression.h.

{ return _evaluated; }

Referenced by mixal::ParsedResult::evaluated(), and mixal::operator<<().

getConstExpression() [1/2]

Expression mixal::Expression::getConstExpression ( const AtomicValue &  value )

static

Get a constant expression based on a given atomic value.

Definition at line 23 of file expression.cpp.

                                                                  {
    auto expr = Expression();
    expr._evaluated = true;
    expr._result = value;
    expr._atomics.emplace_back(Atomic(AtomicType::INTEGER, value.value));
    return expr;
}

References Expression().

Referenced by mixal::Computer::loadCodes(), and mixal::Parser::parseLine().

getConstExpression() [2/2]

Expression mixal::Expression::getConstExpression ( const std::string &  symbol )

static

Get a constant expression based on a given symbol.

The evaluation will depend on the given symbol.

Definition at line 31 of file expression.cpp.

                                                                 {
    auto expr = Expression();
    expr._atomics.emplace_back(Atomic(AtomicType::SYMBOL, symbol));
    expr._depends.insert(symbol);
    return expr;
}

References Expression().

getConstOffsetExpression()

Expression mixal::Expression::getConstOffsetExpression ( const std::string &  symbol, int32_t  offset  )

static

Get a constant expression based on a given symbol and an offset.

This is used for representing the offset from an address.

Definition at line 38 of file expression.cpp.

                                                                                       {
    auto expr = Expression();
    expr._atomics = {Atomic(AtomicType::SYMBOL, symbol), Atomic(AtomicType::INTEGER, offset)};
    expr._operations = {Operation::ADD};
    expr._depends.insert(symbol);
    return expr;
}

References Expression().

Referenced by mixal::Computer::loadCodes().

isValidChar()

bool mixal::Expression::isValidChar ( char  ch )

static

Whether a character is valid inside an expression.

Besides the valid characters at the beginning, the rest characters in the operations are also valid: / and :.

See also

isValidFirst(char)

Definition at line 50 of file expression.cpp.

                                    {
    return isValidFirst(ch) || ch == '/' || ch == ':';
}

References isValidFirst().

Referenced by mixal::Parser::parseLine().

isValidFirst()

bool mixal::Expression::isValidFirst ( char  ch )

static

Whether an expression can start with the given character.

The first character could be:

• [0-9A-Z], for symbols.
• *, for current location.
• [+-], for the sign of an atomic.
• =, for literal constant.

Definition at line 46 of file expression.cpp.

                                     {
    return isalnum(ch) || ch == '+' || ch == '-' || ch == '*' || ch == '=';
}

Referenced by isValidChar(), and mixal::Parser::parseLine().

literalConstant()

bool mixal::Expression::literalConstant ( ) const

inline

Whether this is a literal constant, which is surrounded by =.

Definition at line 149 of file expression.h.

{ return _literalConstant; }

Referenced by mixal::Computer::executeSingle().

operations()

const std::vector<Operation> mixal::Expression::operations ( ) const

inline

Get the operations in the expression.

Definition at line 156 of file expression.h.

{ return _operations; }

operator!=()

bool mixal::Expression::operator!=

(

const Expression &

expression

)

Whether two expressions are different.

Definition at line 331 of file expression.cpp.

                                                        {
    return !((*this) == expression);
}

operator==()

bool mixal::Expression::operator==

(

const Expression &

expression

)

Whether two expressions are the same.

Definition at line 314 of file expression.cpp.

                                                        {
    if (_atomics.size() != expression._atomics.size()) {
        return false;
    }
    for (size_t i = 0; i < _atomics.size(); ++i) {
        if (_atomics[i] != expression._atomics[i]) {
            return false;
        }
    }
    for (size_t i = 0; i < _operations.size(); ++i) {
        if (_operations[i] != expression._operations[i]) {
            return false;
        }
    }
    return true;
}

parse()

void mixal::Expression::parse	(	const std::string &	expression,
		const std::string &	lineSymbol
	)

Try to parse an expression string.

Parameters

expression	A string containing only the expression.
lineSymbol	The symbol representing the current location. Used for * to point to the current location.

Exceptions

ExpressionError

When the input expression string is invalid.

Definition at line 89 of file expression.cpp.

                                                                               {
    this->reset();
    const char END_CHAR = '#';  // The character that indicates the end of the input.
    const int INIT_INDEX = -1;  // The uninitialized index value.
    ExprParseState state = ExprParseState::START;
    int lastAtomicStart = INIT_INDEX;     // The start index of the last atomic.
    int lastOperationStart = INIT_INDEX;  // The start index of the last operation.
 
    // Check whether this is a literal constant that starts and ends with a `=`.
    int start = 0;
    int exprLen = static_cast<int>(expression.size());
    if (exprLen > 2 && expression[0] == '=' && expression[exprLen - 1] == '=') {
        _literalConstant = true;
        start = 1;
        --exprLen;
    }
 
    // Parsing the expression.
    for (int i = start; i <= exprLen; ++i) {
        char ch = i < exprLen ? expression[i] : END_CHAR;
        switch (state) {
        case ExprParseState::START:
            if (ch == '+' || ch == '-' || ch == '*' || isalnum(ch)) {
                state = ExprParseState::ATOMIC;
                lastAtomicStart = i;
            } else if (ch == END_CHAR) {
                throw ExpressionError(i, "The expression is empty.");
            } else {
                throw ExpressionError(i,
                    "Invalid character found at the start of the expression: " + std::string(1, ch));
            }
            break;
 
        case ExprParseState::ATOMIC:
            assert(lastAtomicStart != INIT_INDEX);
            if (expression[lastAtomicStart] == '*' ||
                (lastAtomicStart + 1 < i &&
                 (expression[lastAtomicStart] == '+' || expression[lastAtomicStart] == '-') &&
                 expression[lastAtomicStart + 1] == '*')) {
                // The atomic that matches `*`, `+*`, or `-*`.
                if (ch == END_CHAR) {
                    state = ExprParseState::END;
                } else if (isOperationFirst(ch)) {
                    state = ExprParseState::OPERATION;
                    lastOperationStart = i;
                } else {
                    throw ExpressionError(i,
                        "Invalid character found while trying to find an operation: " + std::string(1, ch));
                }
                bool negative = expression[lastAtomicStart] == '-';
                _atomics.emplace_back(Atomic(AtomicType::ASTERISK, lineSymbol, negative));
                _depends.insert(lineSymbol);
            } else if (isalnum(ch) ||
                ((expression[lastAtomicStart] == '+' || expression[lastAtomicStart] == '-') &&
                 lastAtomicStart + 1 == i && ch == '*')) {
            } else {
                if (ch == END_CHAR) {
                    state = ExprParseState::END;
                } else if (isOperationFirst(ch)) {
                    state = ExprParseState::OPERATION;
                    lastOperationStart = i;
                } else {
                    throw ExpressionError(i,
                        "Invalid character found while trying to find an operation: " + std::string(1, ch));
                }
                bool isInteger = true, negative = false;
                int32_t integerValue = 0;
                if (expression[lastAtomicStart] == '-') {
                    negative = true;
                    ++lastAtomicStart;
                } else if (expression[lastAtomicStart] == '+') {
                    ++lastAtomicStart;
                }
                if (lastAtomicStart == i) {
                    throw ExpressionError(i, "The atomic is empty: " +
                        std::to_string(expression[lastAtomicStart - 1]));
                }
                // Check the type of the atomic. Note that symbols can start with digits.
                for (int j = lastAtomicStart; j < i; ++j) {
                    if (isalpha(expression[j])) {
                        isInteger = false;
                        break;
                    }
                    int32_t digit = expression[j] - '0';
                    if (integerValue > (std::numeric_limits<int32_t>::max() - digit) / 10) {
                        throw ExpressionError(i, "The integer value is too large: " +
                            expression.substr(lastAtomicStart, i - lastAtomicStart));
                    }
                    integerValue = integerValue * 10 + digit;
                }
                if (isInteger) {
                    _atomics.emplace_back(Atomic(AtomicType::INTEGER, integerValue, negative));
                } else {
                    auto symbol = expression.substr(lastAtomicStart, i - lastAtomicStart);
                    _atomics.emplace_back(Atomic(AtomicType::SYMBOL, symbol, negative));
                    _depends.insert(symbol);
                }
            }
            break;
 
        case ExprParseState::OPERATION:
            assert(lastOperationStart != INIT_INDEX);
            if (ch == '/') {
                // The `/` could be continuous for `//`.
            } else if (ch == END_CHAR) {
                throw ExpressionError(i, "No atomic found after the binary operator");
            } else {
                state = ExprParseState::ATOMIC;
                lastAtomicStart = i;
                if (i - lastOperationStart == 1) {
                    switch (expression[lastOperationStart]) {
                    case '+':
                        _operations.emplace_back(Operation::ADD);
                        break;
                    case '-':
                        _operations.emplace_back(Operation::SUBTRACT);
                        break;
                    case '*':
                        _operations.emplace_back(Operation::MULTIPLY);
                        break;
                    case '/':
                        _operations.emplace_back(Operation::FLOOR_DIV);
                        break;
                    case ':':
                        _operations.emplace_back(Operation::FIELD);
                        break;
                    }
                } else {
                    // TODO(admin): Add float division.
                    throw ExpressionError(i, "Unknown binary operator found");
                }
            }
            break;
 
        case ExprParseState::END:
            break;
        }
    }
    // The parsing should always end with END state.
    assert(state == ExprParseState::END);
    // Since all the operations are binary, there should be exactly one more operations than atomics.
    assert(_atomics.size() == _operations.size() + 1);
}

References mixal::isOperationFirst(), and reset().

Referenced by Expression(), and mixal::Parser::parseLine().

replaceSymbol()

void mixal::Expression::replaceSymbol

(

const std::unordered_map< std::string, std::string > &

mapping

)

Replace the symbols in the expression.

This is used for replacing local symbols.

Definition at line 293 of file expression.cpp.

                                                                                    {
    for (auto& atomic : _atomics) {
        if (atomic.type == AtomicType::SYMBOL) {
            auto it = mapping.find(atomic.symbol);
            if (it != mapping.end()) {
                atomic.replaceSymbol(it->second);
                _depends.erase(it->first);
                _depends.insert(it->second);
            }
        }
    }
}

reset()

void mixal::Expression::reset

(

)

Clear the parsed results.

Definition at line 306 of file expression.cpp.

                       {
    _evaluated = false;
    _literalConstant = false;
    _depends.clear();
    _atomics.clear();
    _operations.clear();
}

Referenced by parse().

result()

const AtomicValue& mixal::Expression::result ( ) const

inline

Get the evaluated atomic value.

Definition at line 146 of file expression.h.

{ return _result; }

Referenced by evaluate(), and mixal::operator<<().

Friends And Related Function Documentation

operator<<

std::ostream& operator<< ( std::ostream &  out, const Expression &  expression  )

friend

Output the expression.

Definition at line 346 of file expression.cpp.

                                                                      {
    if (expression._atomics.size() > 0) {
        out << expression._atomics[0];
    }
    for (size_t i = 0; i < expression._operations.size(); ++i) {
        out << expression._operations[i];
        out << expression._atomics[i + 1];
    }
    return out;
}

---

The documentation for this class was generated from the following files:

• include/expression.h
• src/expression.cpp