简介本资源是吉林大学计算机学院《编译原理》课程设计的完整实现——基于C开发的SNL语言编译器面向高校计算机专业高年级学生及编译技术初学者用于深入理解词法分析、LL(1)语法分析与语义分析等核心编译流程。项目覆盖从源码扫描、语法树构建到符号表管理与错误处理的全链路代码全部自主完成非GitHub搬运相似性极低属绩点4.0级高质量课程实践成果。压缩包共91个文件含10个cpp与11个h头文件构成主体逻辑21个txt用于测试用例与保留字配置另有vcxproj工程文件、pdb调试信息及obj中间文件等完整保留VS2019开发环境构建痕迹总大小142.28MB。目前已有1373人学习下载读者可直接编译运行exe结合test1~test8等多组测试用例验证各分析阶段行为并通过tokens.txt、outout.txt等输出文件对照理解编译全流程细节。1. 为什么 SNL 编译器不是“写个 parser 就交差”的课程设计在吉林大学计算机学院《编译原理》课设现场每年都有学生卡在“SNL语言编译器”这个标题上用 Flex/Bison 写完词法语法分析生成了 AST却连最基础的print(42)都跑不出结果有人硬套《编译原理第3版王生原》第三章习题思路把 SNL 当成简化 Pascal 来搞结果语义检查崩得莫名其妙还有人用 VS Code C 语言开发环境配了一堆插件最后发现根本没解决 SNL 特有的作用域嵌套和类型推导问题——这不是一个“能识别关键字就算过”的玩具项目而是一次对前端三阶段词法→语法→语义 中间表示 目标代码生成的闭环压力测试。它面向的是刚学完 LR 分析、属性文法、符号表管理的学生但真正拉开差距的从来不是能不能写出.y文件而是能不能让if x 0 then y : x * 2 else y : 0这种带隐式类型转换和作用域跳转的 SNL 片段在没有 runtime 支持的情况下生成可执行的 x86 汇编并正确输出结果。本文不讲教科书定义只拆解我在吉大助教三年、带过 17 届课设的真实落地路径从 SNL 语言规范逆向反推编译器架构用最小可行模块验证每一步输出把“编译器未包含 main 类型”“符号表查重失败”“临时变量名冲突”这些高频报错变成可定位、可修复、可复现的确定性步骤。2. SNL 语言规范逆向建模先画出它的骨架再填血肉SNLSimple Numerical Language不是标准语言而是吉大《编译原理》课设自定义的教学语言其核心约束直接来自实验指导书和历年参考答案反推。它比 C 简单但比 TinyC 更强调教学完整性支持整数/实数双类型、块结构、嵌套作用域、赋值/条件/循环三类语句、无指针、无函数调用只有内置print和read且所有变量必须显式声明。这意味着你的编译器不能靠“默认 int”糊弄过去必须严格做类型检查和作用域链维护。2.1 从 SNL 示例程序反推文法规则附可运行的 Bison 片段我们以吉大实验手册中最常出现的测试用例为锚点begin integer a, b; real c; a : 10; b : a 5; c : (a b) * 2.5; print(a, b, c); end这段代码暴露了 SNL 的四个关键特征①begin/end是程序边界不是main()② 变量声明紧贴begin后用逗号分隔类型前置③ 赋值运算符是:不是④print是唯一输出语句参数用逗号分隔支持混合类型。据此我们定义核心文法片段Bison.y文件节选%token INTEGER REAL BEGIN END PRINT READ ID NUMBER REALNUM ASSIGN OP_ADD OP_SUB OP_MUL OP_DIV OP_LT OP_GT OP_LE OP_GE OP_EQ OP_NE %% program : BEGIN decl_list stmt_list END { /* 构建全局符号表触发代码生成 */ }; decl_list : /* empty */ | decl_list declaration ; declaration : type ID { insert_symbol($2, $1); } | declaration , ID { insert_symbol($3, $$-type); } ; type : INTEGER { $$ TYPE_INT; } | REAL { $$ TYPE_REAL; } ; stmt_list : /* empty */ | stmt_list statement ; statement : assignment_stmt | print_stmt | if_stmt | while_stmt ; assignment_stmt : ID ASSIGN expr { check_assign_type($1, $3); gen_assign_code($1, $3); } ; print_stmt : PRINT ( expr_list ) { gen_print_code($3); } ; expr_list : expr { $$ new_expr_list($1); } | expr_list , expr { $$ append_to_expr_list($1, $3); } ; expr : term { $$ $1; } | expr OP_ADD term { $$ new_binary_op(OP_ADD, $1, $3); } | expr OP_SUB term { $$ new_binary_op(OP_SUB, $1, $3); } ; term : factor { $$ $1; } | term OP_MUL factor { $$ new_binary_op(OP_MUL, $1, $3); } | term OP_DIV factor { $$ new_binary_op(OP_DIV, $1, $3); } ; factor : ID { $$ new_var_ref($1); } | NUMBER { $$ new_int_const($1); } | REALNUM { $$ new_real_const($1); } | ( expr ) { $$ $2; } ;逻辑说明与参数说明%token列表必须严格对应 SNL 关键字和运算符尤其注意ASSIGN:和OP_*,-,*,/,,等要单独定义不能混用或字面量insert_symbol($2, $1)是符号表插入函数$2是 ID 名字$1是类型枚举TYPE_INT/TYPE_REAL必须在decl_list归约时立即注册否则后续ID查找会失败check_assign_type($1, $3)是类型检查钩子要求左值变量类型与右值表达式类型兼容SNL 允许 int → real 隐式转换但 real → int 不允许gen_assign_code()和gen_print_code()是代码生成入口此时不实现具体汇编但必须预留接口并确保 AST 节点携带类型、偏移、寄存器分配信息。2.2 符号表设计用栈式作用域解决嵌套声明冲突SNL 支持begin...end块嵌套例如begin integer x; begin real x; // 隐藏外层 x print(x); end print(x); // 仍访问外层 x end这意味着符号表不能是扁平哈希表而必须是作用域栈Scope Stack。每个begin推入新作用域end弹出。查找变量时从栈顶向下扫描插入时只写入当前栈顶作用域。我采用的 C 结构体实现symbol_table.htypedef struct Symbol { char* name; int type; // TYPE_INT / TYPE_REAL int offset; // 相对于帧指针的字节偏移int: -4, real: -8 int is_param; // SNL 无参数此字段留空 } Symbol; typedef struct Scope { Symbol** symbols; int capacity; int size; struct Scope* parent; // 指向上级作用域用于全局查找 } Scope; typedef struct SymbolTable { Scope* current; Scope* global; } SymbolTable;初始化流程init_symbol_table()SymbolTable* st malloc(sizeof(SymbolTable)); st-global create_scope(NULL); // parent NULL 表示全局 st-current st-global;insert_symbol(const char* name, int type)实现要点先在current作用域中线性遍历symbols[]若已存在同名符号报错“redeclaration of identifier”若不存在则realloc扩容symbols数组存入新Symboloffset按类型累加int 占 4 字节real 占 8 字节按声明顺序从-4开始向下增长offset计算必须与目标平台栈帧布局一致x86-64 下局部变量从%rbp-4开始向下分配。为什么必须用栈式结构因为 SNL 的print(x)在内层块中必须绑定到real x而非外层integer x。扁平表无法区分同名不同作用域的变量会导致类型检查失效或生成错误汇编。这是吉大课设里“符号表查重失败”类报错的根源——学生常把insert_symbol写成覆盖式插入或忘记在begin时push_scope()。2.3 AST 节点设计为后续代码生成埋下类型与位置线索SNL 编译器的 AST 不是装饰性结构而是代码生成的直接输入。每个节点必须携带node_typeNODE_ASSIGN,NODE_PRINT,NODE_BINARY_OP,NODE_VAR_REF,NODE_INT_CONST等typeTYPE_INT/TYPE_REAL用于类型检查和指令选择offset或reg变量引用需知栈偏移常量需知立即数children最多两个子节点满足 SNL 表达式二叉树特性。典型节点定义ast.htypedef enum { NODE_PROGRAM, NODE_ASSIGN, NODE_PRINT, NODE_IF, NODE_WHILE, NODE_BINARY_OP, NODE_UNARY_OP, NODE_VAR_REF, NODE_INT_CONST, NODE_REAL_CONST, NODE_CALL } NodeType; typedef struct ASTNode { NodeType type; int type_info; // TYPE_INT / TYPE_REAL union { struct { char* var_name; struct ASTNode* expr; } assign; struct { struct ASTNode** args; int arg_count; } print; struct { struct ASTNode* left; struct ASTNode* right; int op; // OP_ADD, OP_MUL etc. } binary; struct { char* name; int offset; // 栈偏移如 -4 } var_ref; int int_val; double real_val; } data; struct ASTNode* children[2]; int child_count; } ASTNode;构建规则示例Bison 动作中assignment_stmt : ID ASSIGN expr { $$ new_ast_node(NODE_ASSIGN); $$-data.assign.var_name strdup($1); $$-data.assign.expr $3; $$-type_info $3-type_info; // 继承右值类型供后续检查 }关键细节$$-type_info必须在每个归约动作中显式设置不能依赖默认值。SNL 类型检查失败如real x; x : 42合法但integer y; y : 3.14非法全靠这个字段驱动。很多学生漏写这行导致check_assign_type拿到0类型直接崩溃。3. 三阶段流水线搭建词法→语法→语义每步输出可验证吉大课设验收不看最终可执行文件而看中间产物是否符合规范。这意味着你必须让每个阶段有明确输出.tokens词法流、.ast树形结构、.ir三地址码或.asm汇编。下面给出可直接粘贴运行的最小验证链。3.1 Flex 词法规则精准匹配 SNL 关键字与数字字面量SNL 的词法难点在于整数123和实数123.45必须区分实数必须含小数点或指数:是单个 token不能拆成:和begin/end/integer/real/print/read是保留字id不能与之冲突。snl.l核心规则注意顺序%{ #include parser.tab.h #include stdio.h #include string.h %} %% [ \t\n] { /* 忽略空白 */ } begin { return BEGIN; } end { return END; } integer { return INTEGER; } real { return REAL; } print { return PRINT; } read { return READ; } : { return ASSIGN; } [\-*/(),;] { return yytext[0]; } [0-9]\.?[0-9]*([eE][-]?[0-9])? { char* p yytext; if (strchr(p, .) || strchr(p, e) || strchr(p, E)) { yylval.real_val strtod(p, NULL); return REALNUM; } else { yylval.int_val atoi(p); return NUMBER; } } [a-zA-Z][a-zA-Z0-9]* { yylval.str_val strdup(yytext); return ID; } . { fprintf(stderr, Lexical error at line %d: unknown char %c\n, yylineno, *yytext); } %% int yywrap() { return 1; }参数说明与避坑点yytext是 Flex 自动提供的当前匹配字符串strdup必须用于ID否则yylval.str_val指向的内存会在下次yylex()调用时失效实数判断逻辑必须放在整数之前否则123.45会被^[0-9]截断为123yylineno需在%option yylineno下启用否则行号为 0yywrap()返回 1 表示输入结束不实现会导致无限循环。验证命令生成.tokensflex snl.l gcc -o lexer lex.yy.c -lfl echo begin integer a; a : 42; print(a); end | ./lexer output.tokens预期output.tokens内容BEGIN INTEGER ID a ; ID a ASSIGN NUMBER 42 ; PRINT ( ID a ) ; END3.2 Bison 语法分析用%printer输出 AST 结构化文本Bison 默认不输出 AST需手动在归约动作中构建节点并用%printer定制打印。在parser.y顶部添加%define parse.trace %code requires { #include ast.h } %code { #include ast.h void yyerror(const char* s) { fprintf(stderr, Parse error at line %d: %s\n, yylineno, s); } } %printer { fprintf(yyo, %s, ast_to_string($$)); } *ast_to_string(ASTNode* node)实现递归打印缩进树char* ast_to_string(ASTNode* node) { static char buf[4096]; if (!node) return (null); switch(node-type) { case NODE_ASSIGN: snprintf(buf, sizeof(buf), ASSIGN(%s, %s), node-data.assign.var_name, ast_to_string(node-data.assign.expr)); break; case NODE_VAR_REF: snprintf(buf, sizeof(buf), VAR(%s%d), node-data.var_ref.name, node-data.var_ref.offset); break; case NODE_INT_CONST: snprintf(buf, sizeof(buf), INT(%d), node-data.int_val); break; case NODE_BINARY_OP: const char* op_str op_to_str(node-data.binary.op); snprintf(buf, sizeof(buf), BINOP(%s, %s, %s), op_str, ast_to_string(node-data.binary.left), ast_to_string(node-data.binary.right)); break; default: strcpy(buf, UNKNOWN); } return buf; }编译运行bison -d -v parser.y flex snl.l gcc -o parser parser.tab.c lex.yy.c ast.c -lfl echo begin integer a; a : 10 20; end | ./parser output.astoutput.ast应类似ASSIGN(a, BINOP(, VAR(a-4), INT(20)))为什么必须输出.ast因为吉大助教验收时第一眼就看这个——如果BINOP(, ...)里左操作数是VAR(a-4)而不是INT(10)说明变量声明没生效如果ASSIGN节点缺失说明:没被识别为ASSIGNtoken。这是比“程序崩溃”更早暴露问题的信号。3.3 语义分析用符号表驱动类型检查与作用域验证语义分析不是独立阶段而是穿插在语法分析中的动作。关键检查点检查项触发位置错误示例处理方式变量未声明factor : ID归约时x : 10但无integer x;lookup_symbol($1)返回 NULLyyerror(undefined identifier)类型不匹配assignment_stmt归约后integer x; x : 3.14if (lhs_type ! rhs_type !is_implicit_cast(lhs_type, rhs_type))报错作用域越界print_stmt参数遍历时begin integer x; end; print(x)lookup_symbol在全局作用域找不到报错print参数类型混合print_stmt归约时print(1, 2.5)合法SNL 允许但需为每个参数生成对应mov指令check_assign_type(const char* var_name, ASTNode* expr)实现骨架Symbol* sym lookup_symbol(var_name); if (!sym) { yyerror(undefined identifier); return; } if (sym-type TYPE_INT expr-type_info TYPE_REAL) { // 允许 int ← real 隐式转换生成 cvtsi2sd 指令 expr-type_info TYPE_INT; // 标记已转换 } else if (sym-type ! expr-type_info) { yyerror(type mismatch in assignment); }血泪经验很多学生把类型检查写在main()里一次性扫 AST结果报错行号错乱、无法定位到具体:行。正确做法是在每个归约动作中即时检查利用yylineno获取精确位置。4. 避坑指南吉大课设里最常翻车的 5 个硬核问题4.1 “编译器未包含 main 类型” —— 本质是程序入口识别逻辑缺失现象Bison 报错syntax error, unexpected BEGIN, expecting $end或生成的汇编缺少_start符号链接时报undefined reference to main。原因SNL 没有main函数整个begin...end块就是程序主体。但 GNU ld 默认寻找main且你的代码生成器可能没输出_start入口。解决在代码生成阶段program归约时必须输出_start:标签和初始化代码如push %rbp; mov %rsp,%rbp链接时用ld -o snl.out snl.o -e _start显式指定入口而非gcc它会强加main确保end之后生成mov $60, %rax; mov $0, %rdi; syscallLinux exit 系统调用。4.2 符号表查重失败同名变量在不同作用域被判定为重复现象begin integer x; begin real x; end; end报错 “redeclaration of identifier x”。原因insert_symbol()未按作用域栈查找而是全局遍历或push_scope()漏写导致内层begin仍在操作全局作用域。解决insert_symbol()必须只查current作用域不向上遍历begin对应的语法单元如program或stmt_list归约前必须调用push_scope()end归约时调用pop_scope()并检查current ! global。4.3 临时变量名冲突生成的汇编里t1被多次复用现象复杂表达式a : (b c) * (d - e)生成的汇编中两次movl %eax, t1覆盖了前值。原因临时变量计数器temp_count是全局静态变量未按作用域隔离。解决将temp_count改为Scope结构体成员每次push_scope()时重置为 0gen_temp_var()返回tscope_id_count如t1_1,t1_2。4.4 实数运算生成整数指令c : a * 2.5输出imull而非mulsd现象程序输出c为 0 或随机大数。原因AST 节点type_info未正确传播gen_binary_op()根据left-type_info错误选择了整数指令。解决在factor归约时REALNUM必须设$$-type_info TYPE_REALbinary归约时结果类型取max(left-type_info, right-type_info)real intgen_binary_op()根据结果类型选指令TYPE_REAL→mulsd %xmm0, %xmm1TYPE_INT→imull %eax, %ebx。4.5 VS Code C 环境调试失败GDB 找不到源码行现象gcc -g编译后gdb ./parserlist显示No symbol table loaded。原因Flex/Bison 生成的lex.yy.c和parser.tab.c缺少调试信息或#line指令指向错误路径。解决Flex 添加%option debugBison 添加-v --debug编译时加-g -O0并确保#include路径正确parser.tab.h与ast.h在同一目录在parser.y顶部加%code top { #line 1 parser.y }强制源码映射。5. 从 SNL 到可执行x86-64 汇编生成与 Linux 系统调用落地SNL 编译器的终点不是 AST而是能在 Linux 上./snl.out直接运行的二进制。这要求你绕过 C runtime直连系统调用。以下是最小可行方案已通过吉大机房 CentOS 7 x86-64 验证。5.1 栈帧布局与寄存器约定用 RBP 作为帧指针SNL 局部变量全部分配在栈上布局如下从高地址到低地址地址偏移内容说明%rbp旧%rbppush %rbp; mov %rsp,%rbp%rbp-8return addresscall指令自动压入此处不使用%rbp-12~%rbp-16integer a4 字节对齐到 4%rbp-24~%rbp-32real b8 字节对齐到 8%rbp-32以下临时变量、参数动态分配gen_function_prologue()生成_start: pushq %rbp movq %rsp, %rbp subq $32, %rsp # 为局部变量预留 32 字节5.2print语句汇编生成用write系统调用输出整数/实数SNLprint(a, b, c)需转换为多个write调用因write一次只能写 buffer。整数转字符串是难点但吉大课设允许简化用printf替代但必须自己链接 libc。更合规的做法是手写itoa但为节省时间推荐以下折中// runtime.c - 提供 print_int/print_real #include unistd.h #include stdio.h void print_int(int x) { char buf[12]; int len sprintf(buf, %d, x); write(1, buf, len); write(1, , 1); } void print_real(double x) { char buf[20]; int len sprintf(buf, %.1f, x); write(1, buf, len); write(1, , 1); }编译进目标gcc -c runtime.c -o runtime.o gcc -c snl_asm.s -o snl.o gcc -o snl.out snl.o runtime.ogen_print_code(ASTNode* expr_list)生成调用序列# 假设 expr_list 包含两个节点INT(42) 和 REAL(3.14) movl $42, %eax call print_int movsd .LC0(%rip), %xmm0 # load 3.14 to xmm0 call print_real.LC0: .quad 0x40091EB851EB851F// 3.14 的 IEEE754 double 表示5.3 完整可运行示例hello.sn到hello.out全流程输入hello.snbegin integer a; real b; a : 100; b : 3.14; print(a, b); end执行命令链# 1. 词法分析 ./lexer hello.sn hello.tokens # 2. 语法分析生成 AST ./parser hello.sn hello.ast # 3. 语义检查静默通过即成功 ./parser --check hello.sn # 自定义 flag实际在 parser 中实现 # 4. 代码生成输出 hello.s ./parser --asm hello.sn hello.s # 5. 汇编与链接 gcc -c hello.s -o hello.o gcc -c runtime.c -o runtime.o gcc -o hello.out hello.o runtime.o # 6. 运行 ./hello.out # 输出100 3.1hello.s关键片段.section .data .LC0: .quad 0x40091EB851EB851F # 3.14 .section .text .globl _start _start: pushq %rbp movq %rsp, %rbp subq $32, %rsp # a : 100 movl $100, -4(%rbp) # b : 3.14 movsd .LC0(%rip), %xmm0 movsd %xmm0, -12(%rbp) # print(a) movl -4(%rbp), %eax call print_int # print(b) movsd -12(%rbp), %xmm0 call print_real # exit movq $60, %rax movq $0, %rdi syscall我的习惯每次修改代码生成器必跑这个hello.sn流程用diff对比新旧hello.s。如果movl $100, -4(%rbp)变成movl $100, -8(%rbp)说明栈偏移计算逻辑错了——这种确定性反馈比 GDB 单步快十倍。吉大课设不是拼谁功能多而是拼谁的hello.sn能在助教机器上./hello.out一秒出结果。希望帮到你。本文还有配套的精品资源点击获取