SLR(1)分析表实战：C++实现小型编译器，输出四元式与汇编代码

SLR(1)分析表实战C实现小型编译器输出四元式与汇编代码1. 编译器前端架构设计现代编译器通常采用分层架构设计我们将实现一个包含完整前端流程的编译器graph LR A[源代码] -- B[词法分析器] B -- C[记号流] C -- D[语法分析器] D -- E[抽象语法树] E -- F[语义分析器] F -- G[中间代码]核心数据结构定义// 记号类型枚举 enum TokenType { TOKEN_KEYWORD, // if/while等 TOKEN_OPERATOR, // - * / TOKEN_IDENT, // 标识符 TOKEN_NUM, // 数字 TOKEN_EOF // 结束标记 }; // 四元式结构 struct Quadruple { string op; string arg1; string arg2; string result; };2. SLR(1)分析表实现2.1 文法定义与冲突处理我们采用以下简化文法(0) S → E (1) E → E T (2) E → T (3) T → T * F (4) T → F (5) F → ( E ) (6) F → idSLR(1)分析表构造算法计算所有非终结符的FOLLOW集构建LR(0)项目集规范族对于每个项目集I和终结符a若[A→α·aβ]∈I且GO(I,a)J则ACTION[I,a]移进J若[A→α·]∈I则对所有a∈FOLLOW(A)ACTION[I,a]按A→α归约若[S→S·]∈I则ACTION[I,#]接受2.2 C实现核心逻辑class SLR1Parser { public: void parse(vectorToken tokens) { stackint stateStack; stackSymbol symbolStack; stateStack.push(0); for (auto it tokens.begin(); it ! tokens.end(); ) { int state stateStack.top(); Token token *it; Action action getAction(state, token); if (action.type SHIFT) { stateStack.push(action.value); symbolStack.push(token); it; } else if (action.type REDUCE) { Production prod productions[action.value]; // 执行语义动作 executeSemanticAction(prod); // 弹出右部符号 for (int i 0; i prod.rhs.size(); i) { stateStack.pop(); symbolStack.pop(); } // 压入左部符号 symbolStack.push(prod.lhs); stateStack.push(getGoto(stateStack.top(), prod.lhs)); } else if (action.type ACCEPT) { cout Parse successfully! endl; return; } else { cerr Syntax error at line token.line endl; return; } } } };3. 四元式生成策略3.1 语义动作设计针对不同产生式设计语义动作void handleProduction(Production prod) { switch (prod.id) { case 1: // E → E T genQuad(, prod.rhs[0].val, prod.rhs[2].val, newTemp()); break; case 3: // T → T * F genQuad(*, prod.rhs[0].val, prod.rhs[2].val, newTemp()); break; case 5: // F → ( E ) prod.lhs.val prod.rhs[1].val; break; // ...其他产生式处理 } }3.2 临时变量管理class TempManager { int counter 0; public: string newTemp() { return t to_string(counter); } void reset() { counter 0; } };示例输出输入表达式a b * c 生成四元式 1. (*, b, c, t1) 2. (, a, t1, t2)4. 目标代码生成4.1 汇编代码模板; 加法模板 mov eax, [arg1] add eax, [arg2] mov [result], eax ; 乘法模板 mov eax, [arg1] mul dword [arg2] mov [result], eax4.2 寄存器分配算法class RegisterAllocator { enum { EAX, EBX, ECX, EDX }; bool used[4] {false}; public: int allocate() { for (int i 0; i 4; i) { if (!used[i]) { used[i] true; return i; } } return -1; // 需要溢出到内存 } void free(int reg) { used[reg] false; } };5. 测试用例验证5.1 测试文法覆盖设计测试用例验证各种语法结构vectorstring testCases { a b * c, // 常规表达式 (a b) * c, // 括号优先级 a : b c, // 赋值语句 if x 0 then a : b else a : c, // 条件语句 while i 10 do i : i 1 // 循环语句 };5.2 调试技巧LR分析调试输出状态栈: 0 5 3 8 符号栈: # E T 输入: *id# 动作: 移进进入状态76. 性能优化实践6.1 分析表压缩采用稀疏矩阵存储分析表class ActionTable { unordered_mapint, unordered_mapTokenType, Action table; public: void addAction(int state, TokenType token, Action action) { table[state][token] action; } Action getAction(int state, TokenType token) { return table[state][token]; } };6.2 内存管理优化使用对象池管理语法树节点class ASTNodePool { vectorunique_ptrASTNode pool; public: templatetypename T, typename... Args T* create(Args... args) { auto ptr make_uniqueT(forwardArgs(args)...); pool.push_back(move(ptr)); return static_castT*(pool.back().get()); } };7. 工程实践建议模块化设计词法分析独立为Scanner类语法分析实现为Parser类代码生成封装为CodeGen类错误恢复机制void errorRecovery(Token token) { // 跳过直到遇到同步记号 while (!isSyncToken(token)) { token getNextToken(); } // 弹出栈直到找到能转移的状态 while (!canRecover(stateStack.top(), token)) { stateStack.pop(); } }可视化调试输出语法树图形化表示生成分析过程动画完整项目应包含Makefile构建系统和单元测试框架推荐采用CMake管理项目结构。对于工业级实现可以考虑集成LLVM框架替代手写后端代码生成。