如何向表驱动的 LL(1) 解析器添加语义分析和代码生成？

Question

我实现了一个由解析表和符号表驱动的基于堆栈的 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⟩等）。

挑战：

1. 由于这是一个迭代解析器，我不确定如何在解析过程中在适当的点集成语义动作。
2. 我应该如何管理符号表并维护此结构中的上下文信息（例如变量类型或函数作用域）？
3. 我应该构建一个抽象语法树（AST），还是可以直接使用解析器的现有堆栈来完成这些任务？

任何通过语义分析和代码生成来扩展此类解析器的建议、示例或最佳实践将不胜感激。

完整版：https://github.com/emonapa/Parser-for-stackoverflow.git

Answer 1

很明显，最好的前进道路是完全放弃 LL(1) 方法并使用 LR 语法将解析器重新实现为有限状态自动机 (FSA)。 FSA 本质上更适合语义分析，因为它们无需堆栈即可处理上下文依赖关系。这样，您根本不需要构建 AST — FSA 本质上就是程序的执行计划。

对于语义操作，您应该将规则直接嵌入到 FSA 的转换中。例如，如果您要检查类型兼容性，则只需为每个类型检查步骤指定一个特定状态即可。如果程序违反任何规则，它将转换为“错误”状态。

对于三地址代码生成，不需要符号表；相反，将所有变量名称、类型和地址编码为 FSA 状态本身的一部分。这消除了维护单独的上下文信息的需要。这就像使用 FSA 作为编译器和运行时引擎。

这种方法是

最佳的，因为 FSA 是确定性的，并且避免了堆栈和递归解析中固有的歧义。此外，它与 LR 语法完美契合，LR 语法被普遍认为是最直观和用户友好的解析策略。