3. 词法分析与解析：从文本到结构

各位同学，欢迎来到第三章。这一章，我们要啃一块硬骨头——如何让计算机“读懂”你写的HDL代码。

说白了，就是要把你写的 module counter(...) 这种文本，变成计算机能理解的数据结构。我当年刚接触这个领域时，觉得这步特别玄乎。后来亲手写了一个解析器，才明白——嗯，其实就是个模式匹配的游戏。

3.1 HDL词法分析器设计

词法分析，也叫扫描（Scanning）。它的任务很简单：把源代码字符串，拆成一个个有意义的“词素”（Token）。

举个例子，对于这段Verilog代码：

module counter(input clk, input rst);
    reg [3:0] count;
endmodule

词法分析器会把它拆成：

Token类型	词素
KEYWORD_MODULE	module
IDENTIFIER	counter
LPAREN	(
KEYWORD_INPUT	input
IDENTIFIER	clk
COMMA	,
...	...

我在项目中遇到过一个问题：有人把 endmodule 写成了 end_module。词法分析器直接报错，排查了半天。所以，词法分析器的容错性很重要。

3.1.1 状态机实现

词法分析器最经典的做法，就是有限状态机（FSM）。

为什么用状态机？因为HDL的语法规则，本质上就是一系列的状态转换。比如：

• 遇到 /，可能是除法，也可能是注释开始
• 遇到 "，字符串开始
• 遇到数字，进入数字解析状态

我习惯用一张状态转换表来设计。下面是我手绘的一个简化版：

你看，从初始状态出发，根据当前字符决定跳转到哪个状态。这就是词法分析的核心逻辑。

3.1.2 代码实现片段

下面是一个简化版的词法分析器核心循环：

typedef enum {
    START, IDENTIFIER, NUMBER, COMMENT, DONE
} State;

Token getNextToken() {
    State state = START;
    char buffer[256];
    int idx = 0;
    
    while (state != DONE) {
        char c = getChar();
        switch (state) {
            case START:
                if (isAlpha(c) || c == '_') {
                    state = IDENTIFIER;
                    buffer[idx++] = c;
                } else if (isDigit(c)) {
                    state = NUMBER;
                    buffer[idx++] = c;
                } else if (c == '/') {
                    char next = peekChar();
                    if (next == '/') {
                        state = COMMENT;
                        getChar(); // 吃掉第二个/
                    }
                }
                break;
            case IDENTIFIER:
                if (isAlphaNum(c) || c == '_') {
                    buffer[idx++] = c;
                } else {
                    ungetChar(c);
                    state = DONE;
                }
                break;
            // ... 其他状态处理
        }
    }
    return makeToken(buffer);
}

3.2 语法分析器（Parser）实现

词法分析搞定了，接下来就是语法分析。这一步，说白了就是检查Token序列是否符合语法规则。

你想想看，如果词法分析是“认字”，那语法分析就是“造句”。它要判断 module ... endmodule 这个结构是否完整，always @(posedge clk) 后面跟的是不是合法的语句。

3.2.1 递归下降解析

我个人最喜欢用递归下降解析法。为什么？因为它直观，代码结构和语法规则一一对应。

比如，Verilog中模块定义的语法规则是：

module_declaration ::= 
    'module' identifier '(' port_list ')' ';' 
    module_item* 
    'endmodule'

对应的解析函数就是：

void parseModule() {
    expect(KEYWORD_MODULE);      // 匹配 'module'
    Token name = expect(IDENTIFIER); // 匹配模块名
    expect(LPAREN);              // 匹配 '('
    parsePortList();             // 解析端口列表
    expect(RPAREN);              // 匹配 ')'
    expect(SEMICOLON);           // 匹配 ';'
    
    while (peek() != KEYWORD_ENDMODULE) {
        parseModuleItem();       // 解析模块内部项
    }
    expect(KEYWORD_ENDMODULE);   // 匹配 'endmodule'
}

你看，每个语法规则对应一个函数。函数里调用其他规则对应的函数，形成递归。这就是“递归下降”名字的由来。

3.2.2 运算符优先级处理

处理表达式时，优先级是个绕不开的问题。比如 a + b * c，应该先算乘法。

我习惯用“优先级爬升法”（Precedence Climbing）。核心思想是：每个运算符都有一个优先级数字，解析时根据优先级决定是否继续“爬升”。

int parseExpression(int minPrec) {
    ASTNode* left = parsePrimary();  // 解析基本单元
    
    while (true) {
        Token op = peek();
        int prec = getPrecedence(op);
        if (prec < minPrec) break;   // 优先级不够，停止
        
        consume(op);                 // 吃掉运算符
        ASTNode* right = parseExpression(prec + 1); // 递归解析右边
        left = makeBinaryOp(left, op, right);
    }
    return left;
}

这段代码很精妙。它用 minPrec 参数控制何时停止递归，自然实现了优先级。比如 + 优先级是10，* 是20。解析 a + b * c 时：

• 先解析 a，遇到 +，优先级10 >= 0，继续
• 递归解析右边，minPrec=11
• 解析 b，遇到 *，优先级20 >= 11，继续
• 递归解析右边，minPrec=21
• 解析 c，没有运算符了，返回
• 最终得到 a + (b * c)

3.3 抽象语法树（AST）的构建

语法分析器解析的同时，我们还要构建AST。AST是什么？它是源代码的树形表示，去掉了括号、分号这些语法糖，只保留核心结构。

举个例子，对于 assign out = a & b | c;，AST长这样：

你看，AST把运算符变成了内部节点，操作数变成了叶子节点。这样后续的代码生成、优化都方便多了。

3.3.1 AST节点设计

我习惯用联合体（union）或者继承来设计AST节点。C语言里，我常用这种方式：

typedef enum {
    NODE_ASSIGN, NODE_BINARY_OP, NODE_IDENTIFIER, NODE_NUMBER
} NodeType;

typedef struct ASTNode {
    NodeType type;
    union {
        struct { char* name; ASTNode* rhs; } assign;
        struct { char op; ASTNode* left; ASTNode* right; } binop;
        struct { char* name; } identifier;
        struct { int value; } number;
    } data;
} ASTNode;

每个节点知道自己是什么类型，然后通过联合体访问对应的数据。这样既节省内存，又清晰。

3.3.2 AST的遍历

AST建好了，怎么用？遍历它。最常见的遍历方式是深度优先：

void traverse(ASTNode* node) {
    if (!node) return;
    
    switch (node->type) {
        case NODE_ASSIGN:
            traverse(node->data.assign.rhs);
            // 处理赋值语句
            break;
        case NODE_BINARY_OP:
            traverse(node->data.binop.left);
            traverse(node->data.binop.right);
            // 处理二元运算
            break;
        case NODE_IDENTIFIER:
            // 处理标识符
            break;
        case NODE_NUMBER:
            // 处理数字
            break;
    }
}

这种遍历方式，说白了就是“先处理子节点，再处理父节点”。后续的代码生成、优化，都是在这个遍历框架上做文章。

3.4 小结

这一章我们走完了从文本到AST的全过程。词法分析把字符串变成Token流，语法分析把Token流变成AST。这两步是编译器的基石。

我个人觉得，写解析器最考验的是耐心。你可能会遇到各种奇怪的语法错误，但别灰心。每修复一个bug，你对HDL的理解就更深一层。

嗯，今天就到这里。记住：好的解析器，是调试出来的，不是设计出来的。

---