基于S-Expression的C++/LLVM DSL词法分析器无限循环排查

我正在构建一个基于S-Expression、C++/LLVM编译的高性能领域特定语言（DSL），编写的小型词法分析器（Lexer）在无错误测试用例下触发无限循环（错误能正常捕获处理）。尝试过修改示例、重写代码、逐步调试，以及咨询AI工具，均未找到原因。运行时会无限输出换行分隔的2:。

原代码 #

#include <iostream>
#include <cstring>
#include <string>
#include <vector>

enum class TokenType {
    BLOCK,
    IF,
    LET,
    VAR,
    QUOTE,
    SET,
    LAMBDA,
    MACRO,
    INTEGER,
    FLOAT,
    STRING,
    BEGIN,
    END,
    SYMBOL,
    BUILTIN,
    TERMINATE
};

struct Token {
    TokenType type;
    std::string value;
};

class Lexer {
    std::string code;
    unsigned index = 0;

    Token gettok(void) {
        std::string data;

        while (index < code.length() && code[index] != '(' && code[index] != ')' && code[index] != '"' && !std::isspace(code[index]))
            data += code[index++];

        // Handle (...)
        if (data == "(") return { TokenType::BEGIN, data };
        if (data == ")") return { TokenType::END, data };

        // Handle $ID
        if (data[0] == '$') return { TokenType::SYMBOL, data };

        // String/Number/Comment handling are not relevant

        // Handle special operators
        if (data == "block") return { TokenType::BLOCK, data };
        if (data == "if") return { TokenType::IF, data };
        if (data == "let") return { TokenType::LET, data };
        if (data == "var") return { TokenType::VAR, data };
        if (data == "quote") return { TokenType::QUOTE, data };
        if (data == "set") return { TokenType::SET, data };
        if (data == "lambda") return { TokenType::LAMBDA, data };
        if (data == "macro") return { TokenType::MACRO, data };

        // Handle builtins
        return { TokenType::BUILTIN, data };
    }
public:
    Lexer(std::string const& arg) : code(arg + "  ") {}

    std::vector<Token> lex(void) {
        std::vector<Token> out;
        Token next = gettok();

        while (next.type != TokenType::TERMINATE) {
            out.push_back(next);
            std::cout << index << ": " << data << "\n";
            next = gettok();
        }

        return out;
    }
};

auto test= R"(
(function main (x) (block
    (let $out zero)
    $out)))";

int main(void) {
    Lexer lexer(test);
    auto foo = lexer.lex();
    for (auto& bar : foo) std::cout << bar.value << std::endl;
}

问题根源 #

1. 无终止条件：gettok()从未返回TERMINATE类型Token，当解析到字符串末尾时，依然返回空内容的BUILTINToken，导致lex()的循环永远无法退出。
2. 未跳过空白字符：遇到空白时，gettok()的while循环不执行，index不递增，每次调用都停在同一位置，触发无限循环。
3. 变量作用域错误：lex()中引用的data是gettok()的局部变量，属于编译错误，会导致未定义行为。
4. 括号识别逻辑错误：括号字符会被while循环跳过，data为空，无法匹配data == "("/")"的判断，导致括号被错误归类为BUILTIN。

修复后的代码 #

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cctype>

enum class TokenType {
    BLOCK,
    IF,
    LET,
    VAR,
    QUOTE,
    SET,
    LAMBDA,
    MACRO,
    INTEGER,
    FLOAT,
    STRING,
    BEGIN,
    END,
    SYMBOL,
    BUILTIN,
    TERMINATE
};

struct Token {
    TokenType type;
    std::string value;
};

class Lexer {
    std::string code;
    unsigned index = 0;

    // 跳过空白字符
    void skip_whitespace() {
        while (index < code.length() && std::isspace(code[index])) {
            index++;
        }
    }

    Token gettok(void) {
        skip_whitespace(); // 先跳过所有空白

        // 到达字符串末尾，返回终止Token
        if (index >= code.length()) {
            return { TokenType::TERMINATE, "" };
        }

        std::string data;

        // 单独处理括号，确保正确识别
        if (code[index] == '(') {
            index++;
            return { TokenType::BEGIN, "(" };
        }
        if (code[index] == ')') {
            index++;
            return { TokenType::END, ")" };
        }

        // 处理双引号包裹的字符串（简化实现）
        if (code[index] == '"') {
            index++;
            while (index < code.length() && code[index] != '"') {
                data += code[index++];
            }
            if (index < code.length()) index++; // 跳过结尾引号
            return { TokenType::STRING, data };
        }

        // 读取普通标识符、关键字、内置函数名
        while (index < code.length() && !std::isspace(code[index]) && code[index] != '(' && code[index] != ')' && code[index] != '"') {
            data += code[index++];
        }

        // 处理$开头的符号
        if (!data.empty() && data[0] == '$') {
            return { TokenType::SYMBOL, data };
        }

        // 匹配关键字
        if (data == "block") return { TokenType::BLOCK, data };
        if (data == "if") return { TokenType::IF, data };
        if (data == "let") return { TokenType::LET, data };
        if (data == "var") return { TokenType::VAR, data };
        if (data == "quote") return { TokenType::QUOTE, data };
        if (data == "set") return { TokenType::SET, data };
        if (data == "lambda") return { TokenType::LAMBDA, data };
        if (data == "macro") return { TokenType::MACRO, data };

        // 默认归类为内置函数或普通标识符
        return { TokenType::BUILTIN, data };
    }
public:
    Lexer(std::string const& arg) : code(arg) {}

    std::vector<Token> lex(void) {
        std::vector<Token> out;
        Token next = gettok();

        while (next.type != TokenType::TERMINATE) {
            out.push_back(next);
            std::cout << index << ": " << next.value << "\n"; // 使用Token的value字段输出
            next = gettok();
        }

        return out;
    }
};

auto test= R"(
(function main (x) (block
    (let $out zero)
    $out)))";

int main(void) {
    Lexer lexer(test);
    auto foo = lexer.lex();
    for (auto& bar : foo) std::cout << bar.value << std::endl;
}

修复要点 #

• 添加skip_whitespace()函数，解析前跳过所有空白，避免卡在空白字符上。
• 在gettok()开头判断是否到达字符串末尾，返回TERMINATEToken终止循环。
• 单独处理括号字符，确保被正确识别为BEGIN/END类型。
• 修复lex()中的变量作用域错误，改用next.value输出Token内容。
• 调整解析顺序，优先处理特殊字符（括号、字符串），再处理普通标识符。

内容的提问来源于stack exchange，提问作者Spencer Rosas-Gunn