ExpressionParser.cpp

#include "ExpressionParser.h"

#include <cctype>
#include <stdexcept>

// ========================
// ExpressionParser.cpp
// 递归下降表达式解析器实现，将字符串转为 Expression 语法树。
// ========================

namespace {
// 工具函数：将标识符转为大写，便于大小写无关匹配。
std::string toUpper(std::string text) {
    for (char& ch : text) {
        ch = static_cast<char>(std::toupper(static_cast<unsigned char>(ch)));
    }
    return text;
}
}
// 关于namespace
// 让 toUpper 只在本文件内部可见
// 避免和其他文件的同名函数冲突

// 构造函数：初始化源字符串，准备词法分析。
ExpressionParser::ExpressionParser(std::string source) : m_source(std::move(source)) {
    // 把传进来的 source 字符串（表达式内容）保存到成员变量 m_source 里
    skipWhitespace();
    // 跳过 m_source 开头的所有空白字符，让 m_index 指向第一个有效字符
    m_current = readToken();
    // 读取第一个 token，并保存到 m_current
}


// 解析入口：解析完整表达式，若有多余内容则报错。
std::unique_ptr<Expression> ExpressionParser::parse() {
    auto expr = parseExpression();
    if (m_current.type != TokenType::End) {
        throw std::runtime_error("Unexpected token after expression");
    }
    return expr;
}


// 前进到下一个 token。
void ExpressionParser::advance() {
    skipWhitespace();
    m_current = readToken();
}


// 跳过空白字符。
void ExpressionParser::skipWhitespace() {
    while (m_index < m_source.size() && std::isspace(static_cast<unsigned char>(m_source[m_index]))) {
        ++m_index;
    }
}


// 词法分析：读取下一个 token，支持数字、标识符、操作符、括号。
// 也就是ppt中 tokenizer.h/cpp 的功能
// @return Token 结构体，包含类型和内容
// @throws std::runtime_error 遇到非法字符
ExpressionParser::Token ExpressionParser::readToken() {
    if (m_index >= m_source.size()) {
        return {TokenType::End, "", 0};
    }
    // 如果已经读到字符串结尾，返回一个 End 类型的 Token，表示输入结束

    char ch = m_source[m_index];
    // 取当前位置的字符，准备判断它属于哪种类型

    // 解析整数常量
    if (std::isdigit(static_cast<unsigned char>(ch))) {
        int value = 0;
        while (m_index < m_source.size() && std::isdigit(static_cast<unsigned char>(m_source[m_index]))) {
            value = value * 10 + (m_source[m_index] - '0');
            ++m_index;
        }
        // 如果是数字，循环读取所有连续的数字字符，拼成一个整数 value
        return {TokenType::Number, "", value};
    }

    // 解析标识符（变量名或 MOD）
    if (std::isalpha(static_cast<unsigned char>(ch))) {
        std::string ident;
        // 用于存储识别出来的完整标识符
        while (m_index < m_source.size() &&
               (std::isalnum(static_cast<unsigned char>(m_source[m_index])) || m_source[m_index] == '_')) {
            // 循环条件
            // (isalnum : 字母or数字 || _ : 下划线) 判断合法变量名 如 A、X1、SUM_2
            // ident.push_back(static_cast<char>(std::toupper(static_cast<unsigned char>(m_source[m_index]))));
            ident.push_back(static_cast<char>(static_cast<unsigned char>(m_source[m_index])));
            ++m_index;
        }
        if (ident == "MOD") {
            return {TokenType::Mod, ident, 0};
        }
        return {TokenType::Identifier, ident, 0};
    }

    // 解析操作符和括号
    
    ++m_index;
    // 现在 m_index是下一个待处理的字符的下标
    // ch是当前字符
    switch (ch) {
    case '+': return {TokenType::Plus, "+", 0};
    case '-': return {TokenType::Minus, "-", 0};
    case '*':
        // 检查是否为幂运算符 **
        if (m_index < m_source.size() && m_source[m_index] == '*') {
            ++m_index;
            return {TokenType::Power, "**", 0};
        }
        return {TokenType::Multiply, "*", 0};
    case '/': return {TokenType::Divide, "/", 0};
    case '(':
        return {TokenType::LParen, "(", 0};
    case ')':
        return {TokenType::RParen, ")", 0};
    default:
        throw std::runtime_error(std::string("Unexpected character in expression: ") + ch);
    }
}


// 若当前 token 类型匹配则前进，否则不动。
// 是expect函数的辅助函数
bool ExpressionParser::match(TokenType type) {
    if (m_current.type == type) {
        advance();
        return true;
    }
    return false;
}


// 断言当前 token 类型，否则抛出 message。
void ExpressionParser::expect(TokenType type, const std::string& message) {
    if (!match(type)) {
        throw std::runtime_error(message);
    }
}


// 解析表达式
std::unique_ptr<Expression> ExpressionParser::parseExpression() {
    return parseAddSub();
    // 从 最低优先级：加减 开始
}


// 解析加减表达式，左结合。
std::unique_ptr<Expression> ExpressionParser::parseAddSub() {
    auto left = parseMulDiv();
    while (m_current.type == TokenType::Plus || m_current.type == TokenType::Minus) {
        std::string op = ( m_current.type == TokenType::Plus ) ? "+" : "-";
        advance();
        auto right = parseMulDiv();
        left = std::make_unique<CompoundExpression>(op, std::move(left), std::move(right));
    }
    return left;
}


// 解析乘除/MOD 表达式，左结合。
std::unique_ptr<Expression> ExpressionParser::parseMulDiv() {
    auto left = parseExponent();
    while (m_current.type == TokenType::Multiply ||
           m_current.type == TokenType::Divide ||
           m_current.type == TokenType::Mod) {
        std::string op;
        if (m_current.type == TokenType::Multiply) op = "*";
        else if (m_current.type == TokenType::Divide) op = "/";
        else op = "MOD";
        advance();
        auto right = parseExponent();
        left = std::make_unique<CompoundExpression>(op, std::move(left), std::move(right));
    }
    return left;
}


// 解析幂运算，右结合。
std::unique_ptr<Expression> ExpressionParser::parseExponent() {
    auto left = parseUnary();
    if (m_current.type == TokenType::Power) {
        advance();
        auto right = parseExponent();
        left = std::make_unique<CompoundExpression>("**", std::move(left), std::move(right));
    }
    return left;
}


// 解析一元正负号。
std::unique_ptr<Expression> ExpressionParser::parseUnary() {
    if (m_current.type == TokenType::Plus) {
        advance();
        return parseUnary();
    }
    if (m_current.type == TokenType::Minus) {
        advance();
        
        // 假如说是(-2)这种情况，直接构造成常量
        if (m_current.type == TokenType::Number) {
            int value = m_current.value;
            advance();
            return std::make_unique<ConstantExpression>(-value);
        }

        // 递归处理负号后面表达式
        auto operand = parseUnary();
        // 负号等价于 0 - operand
        return std::make_unique<CompoundExpression>("-",
                                                    std::make_unique<ConstantExpression>(0),
                                                    std::move(operand));
    }
    return parsePrimary();
}


// 解析基本单元：常量、变量、括号表达式。
std::unique_ptr<Expression> ExpressionParser::parsePrimary() {
    if (m_current.type == TokenType::Number) {
        int value = m_current.value;
        advance();
        return std::make_unique<ConstantExpression>(value);
    }
    if (m_current.type == TokenType::Identifier) {
        std::string name = m_current.text;
        advance();
        return std::make_unique<IdentifierExpression>(name);
    }
    if (m_current.type == TokenType::LParen) {
        advance();
        auto expr = parseExpression();
        expect(TokenType::RParen, "Missing closing parenthesis");
        return expr;
    }
    throw std::runtime_error("Invalid expression");
}