如何为表驱动栈式LL(1)解析器添加语义分析与代码生成？

已实现解析器概述 #

我已经实现了一个基于解析表和符号表的栈式LL(1)迭代解析器，通过栈管理语法符号、迭代处理词法单元，简化版代码如下：

#include "parser.h"

const int LL_TABLE[22][43] = { 
        {1, 2, 4, 0, 2, 0, 0, 0, 0, 0, 0, 2, 2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0,2},
        //{...}
        //{...}
        //...
    };


void processValue(int value, TStack *stack) {
    Pop(stack);
    switch(value) {
        //FUNCTION -> pub fn token_id ( FN_PARAMS ) TYPE_PREFIX  { STATMENT }
        case 5:
            Push_T_NT(stack,TOKEN_RIGHT_BRACE);
            Push_T_NT(stack,N_STATMENT);
            Push_T_NT(stack,TOKEN_LEFT_BRACE);
            Push_T_NT(stack,N_TYPE_PREFIX);
            Push_T_NT(stack,TOKEN_RIGHT_PAREN);
            Push_T_NT(stack,N_FN_PARAMS);
            Push_T_NT(stack,TOKEN_LEFT_PAREN);
            Push_T_NT(stack,TOKEN_IDENTIFIER);
            Push_T_NT(stack,TOKEN_FN);
            Push_T_NT(stack,TOKEN_PUB);
            break;
        //STATMENT -> if ( EXPRESION ) IS_NULL { STATMENT } ELSE STATMENT
        case 22:
            Push_T_NT(stack,N_ELSE);
            Push_T_NT(stack,TOKEN_RIGHT_BRACE);
            Push_T_NT(stack,N_STATMENT);
            Push_T_NT(stack,TOKEN_LEFT_BRACE);
            Push_T_NT(stack,N_IS_NULL);
            Push_T_NT(stack,TOKEN_RIGHT_PAREN);
            Push_T_NT(stack,N_EXPRESION);
            Push_T_NT(stack,TOKEN_LEFT_PAREN);
            Push_T_NT(stack,TOKEN_IF);
            break;
        //STATMENT -> while ( EXPRESION ) { STATMENT } STATMENT
        case 23:
            Push_T_NT(stack,N_STATMENT);
            Push_T_NT(stack,TOKEN_RIGHT_BRACE);
            Push_T_NT(stack,N_STATMENT);
            Push_T_NT(stack,TOKEN_LEFT_BRACE);
            Push_T_NT(stack,N_IS_NULL);
            Push_T_NT(stack,TOKEN_RIGHT_PAREN);
            Push_T_NT(stack,N_EXPRESION);
            Push_T_NT(stack,TOKEN_LEFT_PAREN);
            Push_T_NT(stack,TOKEN_WHILE);
            break;
    }
}


bool find_rule(LexerContext *context, TStack *stack) {
    //The first non-terminal that will be developed
    Push_T_NT(stack, N_PROGRAM);
    
    token = get_token(context);
    while (!IsEmpty(stack)){ 
        rule_stack = Top(stack);
        if (rule_stack->isTerm == 0){//Non-terminal
            processValue(LL_TABLE[rule_stack->value][token.type], stack);
        } else { //Terminal
            if (rule_stack->value == token.type){
                Pop(stack);
                token = get_token(context);
            } else {
                //Wrong syntax
                return 0;
            }
        }
    }   
    return 1;
}

int main() {
    if (find_rule(&context, &stack)){
        printf("Valid syntax\n");
    } else {
        printf("Error in syntax\n");
    }

    return 0;
}

扩展目标 #

• 添加语义分析：检查类型兼容性、变量声明合法性等
• 生成三地址码：如STRI2INT ⟨var⟩ ⟨symb1⟩ ⟨symb2⟩、GETCHAR ⟨var⟩ ⟨symb1⟩ ⟨symb2⟩、JUMP ⟨label⟩等

遇到的挑战 #

• 迭代式解析器中，不清楚何时插入语义动作最合适
• 如何在现有结构中管理符号表、维护变量类型、函数作用域等上下文信息
• 是否需要构建抽象语法树（AST），还是直接复用解析器现有栈完成任务

扩展建议与最佳实践 #

1. 语义动作的时机集成 #

迭代式LL(1)解析器的语义动作要绑定到产生式的归约时刻——也就是当某个非终结符对应的所有右部符号都被匹配/处理完成，即将从栈中弹出该非终结符的节点。

你的processValue是展开非终结符的入口，反过来，当栈中某个非终结符的所有子符号都处理完毕时，就是执行语义动作的节点。可以通过两种方式实现：

• 修改栈元素结构，给非终结符节点添加语义钩子函数指针
• 维护一个与解析栈同步的“语义动作栈”，当解析栈弹出非终结符时，取出对应动作执行

比如处理变量声明产生式VAR_DECL -> TYPE IDENTIFIER：当栈中依次弹出IDENTIFIER、TYPE，最后准备弹出VAR_DECL时，执行语义动作：将变量名、类型存入符号表，同时生成变量初始化的三地址码。

2. 符号表与上下文管理 #

采用分层符号表处理作用域：

• 全局作用域符号表作为根节点，函数、代码块（如if/while的{}）开启新的局部作用域符号表，作为父节点的子节点
• 解析进入作用域（匹配到TOKEN_LEFT_BRACE）时，创建新的局部符号表并压入符号表栈；离开作用域（匹配到TOKEN_RIGHT_BRACE）时，弹出局部符号表，回到父作用域

查询符号时优先从当前作用域的符号表查找，找不到再向上回溯父作用域。比如处理函数定义时：匹配到pub fn IDENTIFIER后，先将函数名、返回类型存入全局符号表；进入函数体的{时，创建函数局部符号表，将函数参数存入该局部表。

3. AST vs 直接栈处理 #

两种方案各有优劣，可根据需求选择：

• 直接栈处理：如果语言语义简单、三地址码生成逻辑直接，无需构建AST。比如处理表达式a + b时，栈中依次存储a的类型、+运算符、b的类型，归约时检查类型兼容性，生成ADD t1 a b的三地址码，将t1的类型压入栈作为表达式结果。
• 构建AST：如果语言有复杂语义（如嵌套作用域、复杂表达式求值顺序、优化需求），建议先构建AST。在归约时创建AST节点，将节点指针压入栈，最后遍历AST生成三地址码。这种方式更灵活，便于后续的语义检查和代码优化。

对于现有迭代解析器，推荐先尝试直接栈处理快速验证，后续需求复杂时再重构为AST方案。

代码修改示例（语义动作集成） #

修改栈元素结构，增加语义信息存储字段：

typedef struct StackElement {
    int isTerm; // 0=非终结符，1=终结符
    int value;  // 符号类型值
    // 新增语义字段：存储临时变量名、类型等信息
    char* temp_var;
    enum Type type;
} StackElement;

在find_rule中，归约非终结符时执行语义动作：

bool find_rule(LexerContext *context, TStack *stack, SymbolTableStack *sym_tab_stack) {
    Push_T_NT(stack, N_PROGRAM);
    token = get_token(context);
    while (!IsEmpty(stack)){ 
        rule_stack = Top(stack);
        if (rule_stack->isTerm == 0){//Non-terminal
            processValue(LL_TABLE[rule_stack->value][token.type], stack);
        } else { //Terminal
            if (rule_stack->value == token.type){
                // 记录终结符的语义信息（比如标识符的名字）
                if (token.type == TOKEN_IDENTIFIER) {
                    rule_stack->temp_var = strdup(token.value);
                }
                Pop(stack);
                token = get_token(context);
            } else {
                return 0;
            }
        }
        // 检查是否可归约变量声明非终结符
        if (can_reduce_var_decl(stack)) {
            // 弹出右部符号，提取语义信息
            StackElement* id_elem = Pop(stack);
            StackElement* type_elem = Pop(stack);
            // 执行语义动作：存入符号表
            add_symbol(get_current_sym_tab(sym_tab_stack), id_elem->temp_var, type_elem->type);
            // 生成变量初始化的三地址码
            printf("ASSIGN %s 0\n", id_elem->temp_var);
            // 将归约后的非终结符压栈，携带语义信息
            StackElement var_decl_elem = {0, N_VAR_DECL, NULL, type_elem->type};
            Push(stack, var_decl_elem);
            // 释放临时内存
            free(id_elem->temp_var);
        }
    }   
    return 1;
}

内容的提问来源于stack exchange，提问作者demon