文法的C++子集编译器前端实现：词法、语法与语义分析)
1. 从一段“能跑就行”的代码说起为什么我要手写一个C子集编译器很多人第一次接触编译原理都是在期末前两周对着龙书或者课堂PPT硬啃。老师讲FIRST集、FOLLOW集、预测分析表考试考一道“判断该文法是否为LL(1)文法”然后这门课就结束了。我当时也是这么过来的直到有一次需要把一个自定义的配置脚本转换成C代码才发现自己连一个像样的词法分析器都写不利索。这个实验的核心目标很明确用LL(1)文法实现一个能处理C语言子集的编译器前端。注意我说的是“子集”不是完整的C。完整的C标准有上千页光是模板推导和重载决议就够写一本书了。但如果你把范围收窄到变量声明、算术表达式、赋值语句、if-else分支、while循环和基本的输入输出整个编译器的骨架就清晰了。我选择LL(1)而不是LR或者LALR原因很实际。LL(1)是自顶向下分析里最直观的一种你只需要会算FIRST集和FOLLOW集就能手工构造预测分析表。对于教学实验来说手工构造的过程本身就是最好的学习方式。LR虽然能处理更多文法但状态机的手工推导容易让人迷失在Item集里。而且LL(1)的递归下降实现非常自然每个非终结符对应一个函数代码结构几乎就是文法结构的镜像。这个编译器能做什么它能把一段符合C子集语法的源代码经过词法分析、语法分析、语义检查最终生成三地址码或者简单的中间表示。适合谁来参考如果你正在做编译原理课程设计或者想自己动手写一个DSL的解析器又或者你单纯好奇“编译器到底怎么把代码变成可执行逻辑的”这篇文章会给你一条能走通的路。我踩过的坑包括但不限于左递归导致递归下降无限循环、FIRST集计算时遗漏空串产生式、符号表作用域嵌套处理错误、类型检查时忘记处理隐式转换。这些坑我都会在后面的章节里逐一拆解让你少走弯路。2. 文法设计哪些C特性必须砍掉哪些必须保留2.1 子集边界的划定逻辑设计LL(1)文法的第一步不是写产生式而是决定“砍什么”。C里有很多特性天生不适合LL(1)分析比如函数重载、模板、运算符重载、多重继承。这些特性的语法需要符号表在解析阶段就参与决策而LL(1)是纯语法驱动的只能看一个前瞻符号。我最终保留的核心构造包括基本类型int、float、bool、char。不保留double和long因为浮点精度和类型提升规则会让语义分析复杂化。变量声明与初始化int a 5;这种形式。不支持多变量同时声明比如int a, b, c;因为逗号分隔的声明列表会让文法产生式数量翻倍。算术与逻辑表达式加减乘除、取模、比较运算、逻辑与或非。运算符优先级通过文法层级自然体现。赋值语句a b c * d;这种。控制流if-else、while。不支持for和switch因为for的语法糖可以手动展开成whileswitch的跳转表生成属于后端优化。输入输出用input(a);和output(a);代替cin/cout避免处理流操作符的重载。语句块用花括号包裹的复合语句。砍掉这些之后文法规模控制在30条产生式左右手工计算FIRST和FOLLOW集完全可行。2.2 消除左递归与提取左公因子原始C文法里表达式通常是左递归的Expr - Expr Term | Term这种形式在递归下降分析器里会导致无限递归因为解析Expr时会先调用Expr。必须改写成右递归形式Expr - Term Expr Expr - Term Expr | ε这个变换的代价是引入了一个新的非终结符Expr但换来的是递归下降可以正常工作。类似地赋值语句的文法也要注意Stmt - Id Expr ; | ...这里Id和Expr的开头都是标识符如果不提取左公因子预测分析表里会有冲突。我的做法是在语法分析阶段用更细粒度的非终结符区分比如把赋值语句单独归为一类在解析到标识符后先看下一个符号是不是等号。注意消除左递归时ε产生式的FOLLOW集计算容易出错。我建议先用一个小例子手工验证比如A - B C | ε确认FOLLOW(A)包含了哪些符号。2.3 最终采用的文法产生式集合经过反复调整我最终确定的文法如下用EBNF风格描述实际代码里会展开Program - StmtList StmtList - Stmt StmtList | ε Stmt - DeclStmt | AssignStmt | IfStmt | WhileStmt | Block | IOStmt DeclStmt - Type Id InitOpt ; InitOpt - Expr | ε AssignStmt - Id Expr ; IfStmt - if ( Expr ) Stmt ElseOpt ElseOpt - else Stmt | ε WhileStmt - while ( Expr ) Stmt Block - { StmtList } IOStmt - input ( Id ) ; | output ( Expr ) ; Expr - OrExpr OrExpr - AndExpr OrExpr OrExpr - || AndExpr OrExpr | ε AndExpr - RelExpr AndExpr AndExpr - RelExpr AndExpr | ε RelExpr - AddExpr RelExpr RelExpr - AddExpr | AddExpr | AddExpr | ! AddExpr | ε AddExpr - MulExpr AddExpr AddExpr - MulExpr AddExpr | - MulExpr AddExpr | ε MulExpr - UnaryExpr MulExpr MulExpr - * UnaryExpr MulExpr | / UnaryExpr MulExpr | % UnaryExpr MulExpr | ε UnaryExpr - ! UnaryExpr | - UnaryExpr | Primary Primary - Id | Num | ( Expr ) | true | false Type - int | float | bool | char这套文法满足LL(1)条件我用手工计算验证过每个非终结符的FIRST集和FOLLOW集没有冲突。实际编码时我把OrExpr、AndExpr这些带撇的非终结符直接映射成递归函数里的循环这样代码更紧凑。3. 词法分析器别小看这个“切词”的活3.1 Token类型设计与正则匹配策略词法分析器的任务是把字符流切分成有意义的Token序列。我定义了以下几类TokenToken类型示例说明KEYWORDif, while, int保留字IDmyVar, count标识符NUM123, 3.14数字字面量OP, -, *, /, , , , 运算符DELIM(, ), {, }, ;分隔符EOF文件结束结束标记匹配策略上我采用最长匹配原则。比如遇到先看下一个字符是不是如果是就返回否则返回。对于标识符和关键字先按标识符规则匹配完整字符串再查关键字表决定是ID还是KEYWORD。数字的处理稍微麻烦一点。我支持整数和浮点数浮点数用[0-9].[0-9]匹配。注意不要用[0-9](.[0-9])?这种写法因为123.会被误判为浮点数而C里123.是合法的但我的子集不支持所以直接要求小数点后必须有数字。3.2 手写词法分析器的状态机实现我没有用Lex或者Flex而是手写了一个基于状态转移的分析器。核心逻辑是一个nextToken()函数每次调用返回下一个Token。内部维护一个字符缓冲区和一个位置指针。Token Lexer::nextToken() { skipWhitespaceAndComments(); if (isAtEnd()) return Token(TOKEN_EOF, ); char c peek(); if (isalpha(c) || c _) return identifier(); if (isdigit(c)) return number(); if (isOperatorStart(c)) return opOrDelim(); error(Unexpected character: string(1, c)); }skipWhitespaceAndComments()要处理空格、制表符、换行以及//和/* */两种注释。这里有个坑/* */注释不支持嵌套如果源码里写了/* /* */ */第二个*/会被当作普通字符。我的处理是遇到第一个*/就结束注释这是C标准的行为但很多人会误以为支持嵌套。3.3 错误恢复与位置追踪词法错误主要有两类非法字符和未闭合的字符串/注释。我的做法是遇到非法字符时记录错误位置然后跳过该字符继续分析这样一次编译能报出多个错误而不是遇到第一个就退出。位置追踪方面我维护了行号和列号。每次读取换行符时行号加一列号归零。报错时输出line X, column Y方便定位。这个功能在调试语法分析器时特别有用因为语法错误往往需要结合上下文才能判断。提示词法分析阶段不要急着做类型检查。比如int a hello;这种错误应该留给语义分析阶段词法分析器只负责把hello识别为字符串字面量Token即可。4. 语法分析递归下降与预测分析表的双轨实现4.1 FIRST集和FOLLOW集的手工计算过程在写代码之前我先把所有非终结符的FIRST集和FOLLOW集算了一遍。以表达式部分为例FIRST(Expr) FIRST(OrExpr) FIRST(AndExpr) ... FIRST(Primary) { Id, Num, (, true, false, !, - }FOLLOW(Expr) { ), ;, ,, then, else, EOF } 等计算FOLLOW集时我遵循三条规则把EOF加入起始符号的FOLLOW集。如果存在产生式A - αBβ把FIRST(β)中除ε外的符号加入FOLLOW(B)。如果存在产生式A - αB或A - αBβ且β能推导出ε把FOLLOW(A)加入FOLLOW(B)。手工计算时我用了一张大表每个非终结符一行逐条产生式扫描。这个过程很枯燥但能帮你发现文法里的隐藏冲突。比如我最初写的Stmt - Id Expr ; | Id ( Args ) ;就有问题因为两个产生式的FIRST集都包含IdLL(1)分析表里会有多重入口。4.2 递归下降分析器的代码骨架递归下降的核心思想是每个非终结符对应一个函数函数体根据当前Token决定走哪条产生式。以parseStmt()为例void Parser::parseStmt() { Token t peek(); if (t.type KEYWORD) { if (t.value int || t.value float || t.value bool || t.value char) { parseDeclStmt(); } else if (t.value if) { parseIfStmt(); } else if (t.value while) { parseWhileStmt(); } else if (t.value input || t.value output) { parseIOStmt(); } else { error(Unexpected keyword: t.value); } } else if (t.type ID) { parseAssignStmt(); } else if (t.type DELIM t.value {) { parseBlock(); } else { error(Unexpected token: t.value); } }这种写法的好处是逻辑清晰每个分支对应一条产生式。坏处是当文法复杂时函数调用层次会很深。我的做法是把表达式部分的递归下降改成循环比如parseAddExpr()里用一个while循环处理连续的和-而不是递归调用parseAddExpr()。4.3 预测分析表驱动的非递归版本除了递归下降我还实现了一个基于栈的预测分析器。这个版本用一张二维表驱动表的行为非终结符列为终结符单元格里是产生式编号。非终结符idnum*();$ExprExpr-Term ExprExpr-Term ExprExpr-Term ExprExprExpr-Term ExprExpr-εExpr-εExpr-εTermTerm-Factor TermTerm-Factor TermTerm-Factor TermTermTerm-εTerm-*Factor TermTerm-εTerm-εTerm-ε分析时栈里初始放$和起始符号。每次看栈顶和当前输入符号查表决定展开哪条产生式。如果栈顶是终结符且与输入匹配就弹出并读下一个Token。这个版本的好处是你能直观看到分析过程每一步栈的变化都能打印出来。我在调试文法冲突时就是靠打印分析栈发现某个单元格有多个候选产生式的。4.4 语法错误恢复的两种策略语法错误恢复是编译器实用性的关键。我的策略是恐慌模式恢复遇到错误时跳过Token直到遇到一个“同步符号”比如分号、右花括号或者EOF。同步符号的选择依据是FOLLOW集。短语级恢复对于缺少分号这种常见错误直接插入一个虚拟分号然后继续。比如解析int a 5时缺少分号分析器会在表达式解析完后发现下一个Token不是分号此时报错并“假装”有一个分号继续解析下一条语句。这样一次编译能报出多个错误而不是遇到第一个就停。5. 语义分析符号表、类型检查与作用域链5.1 符号表的数据结构选型符号表我用了栈式结构每个作用域对应一个哈希表。进入块时压入新表退出块时弹出。查找变量时从栈顶往下逐层查找这样自然实现了作用域遮蔽。class SymbolTable { vectorunordered_mapstring, Symbol scopes; public: void enterScope() { scopes.push_back({}); } void exitScope() { scopes.pop_back(); } bool declare(const string name, Symbol sym) { auto current scopes.back(); if (current.count(name)) return false; // 重复声明 current[name] sym; return true; } Symbol* lookup(const string name) { for (auto it scopes.rbegin(); it ! scopes.rend(); it) { if (it-count(name)) return (*it)[name]; } return nullptr; } };这里有个细节C允许内层作用域声明同名变量遮蔽外层变量所以declare只在当前作用域检查重复lookup则从内向外查找。5.2 类型检查规则与隐式转换我的类型系统支持int、float、bool、char四种基本类型。类型检查规则如下算术运算int和float可以混合运算结果提升为float。bool和char参与算术运算时先转成int。赋值运算右值类型必须能隐式转换成左值类型。int可以赋给float但float赋给int需要显式转换我的子集里不支持强制类型转换所以直接报错。条件表达式if和while的条件必须是bool类型。这里我做了简化不允许int隐式转bool避免if (x)这种写法带来的歧义。类型检查在语法分析过程中同步进行每个表达式节点都有一个type属性。比如解析a b时先查符号表得到a和b的类型然后根据类型提升规则计算结果的类型。5.3 作用域嵌套与变量生命周期作用域嵌套的典型场景是if语句块和while循环体。我的处理是进入{时调用enterScope()。退出}时调用exitScope()。if和while的条件表达式在外层作用域求值循环体内部是新作用域。这里有个容易忽略的点while循环体里声明的变量每次迭代都会重新声明。如果符号表用栈式结构退出循环体时弹出作用域下次进入时重新压入自然实现了这个语义。注意函数参数的作用域和函数体作用域是分开的。虽然我的子集不支持函数定义但如果你要扩展记得参数列表和函数体之间要有一个作用域边界。6. 中间代码生成从语法树到三地址码6.1 三地址码的指令集设计我选择三地址码作为中间表示因为它足够简单又足够表达计算逻辑。指令格式为result arg1 op arg2支持的指令包括算术指令ADD, SUB, MUL, DIV, MOD赋值指令ASSIGN比较指令LT, GT, EQ, NEQ逻辑指令AND, OR, NOT跳转指令JMP, JZ条件为假时跳转输入输出INPUT, OUTPUT每条指令对应一个四元式(op, arg1, arg2, result)。比如a b c生成(ADD, b, c, t1)和(ASSIGN, t1, -, a)。6.2 表达式求值的临时变量分配表达式求值时每个中间结果分配一个临时变量。我用一个计数器tempCount每次需要新临时变量时生成t1、t2这样的名字。string newTemp() { return t to_string(tempCount); }对于a b c * d生成的指令序列是t1 c * d t2 b t1 a t2这里体现了运算符优先级乘法先于加法。递归下降分析器天然保证了这一点因为parseMulExpr()在parseAddExpr()的下一层。6.3 控制流语句的回填技术if和while语句需要生成跳转指令但跳转目标地址在生成指令时还不知道这就是回填技术的用武之地。以if (cond) stmt1 else stmt2为例生成cond的求值指令结果在t1。生成JZ t1, ?目标地址待填。生成stmt1的指令。生成JMP ?跳过stmt2。回填第2步的JZ目标为stmt2的起始地址。生成stmt2的指令。回填第4步的JMP目标为stmt2结束后的地址。我用一个跳转指令列表来管理待回填的指令每次生成跳转时把指令索引压入列表回填时弹出并修改目标地址。6.4 一个完整的代码生成示例输入代码int a 5; int b 10; int c; if (a b) { c a b; } else { c b - a; } output(c);生成的三地址码a 5 b 10 t1 a b JZ t1, L1 t2 a b c t2 JMP L2 L1: t3 b - a c t3 L2: OUTPUT c这个例子涵盖了声明、赋值、条件判断、跳转和输出基本能验证编译器的核心功能。7. 实测中的坑与修复那些文档不会告诉你的细节7.1 左递归消除后的FOLLOW集变化消除左递归时我最初只改了产生式忘了重新计算FOLLOW集。结果预测分析表里某个单元格出现了两个候选产生式分析器不知道该走哪条路。后来发现是Expr的FOLLOW集没有包含Expr的FOLLOW集因为Expr - Term Expr这条产生式里Expr后面可以跟ε所以FOLLOW(Expr)要包含FOLLOW(Expr)。修复方法每次修改文法后重新手工计算一遍FIRST和FOLLOW集或者写一个小脚本自动计算。我后来写了一个Python脚本输入产生式集合输出FIRST和FOLLOW集省了不少时间。7.2 符号表作用域弹出时机错误我最初在解析完if语句的then分支后就弹出了作用域结果else分支里的变量查找失败。正确的做法是then分支和else分支各自有独立的作用域但if语句整体不引入新作用域。也就是说进入then的{时压栈退出}时弹栈else同理。这个bug的表现是在else分支里引用then分支声明的变量时报“未声明标识符”。虽然C里then分支的变量在else分支不可见但我的错误实现导致连外层变量都找不到了。7.3 类型提升规则遗漏导致的运行时错误我的类型检查最初只处理了同类型运算忘了int和float混合的情况。结果float x 1 2.5;被错误地报为类型不匹配。修复方案是在二元运算的类型检查里加入提升规则如果任一操作数是float结果提升为float。如果任一操作数是bool或char先转成int再参与运算。这个规则要递归应用因为表达式可以嵌套。比如1 2.5 * 3里2.5 * 3先提升为float然后1 float再提升。7.4 跳转目标地址回填的顺序问题回填跳转地址时我犯过一个错误先生成了JMP指令然后才生成JZ指令导致回填时地址顺序错乱。正确的顺序是生成条件求值指令。生成JZ指令记录待回填位置。生成then分支指令。生成JMP指令记录待回填位置。回填JZ目标为else分支起始。生成else分支指令。回填JMP目标为else分支结束。这个顺序保证了跳转逻辑的正确性。如果顺序错了程序会跳转到错误的地址表现为死循环或者跳过某些语句。8. 从实验到实用这个编译器还能怎么扩展8.1 加入函数定义与调用我的子集里没有函数但扩展起来并不复杂。需要做三件事文法里加入FuncDef - Type Id ( ParamList ) Block。符号表里增加函数符号记录参数类型和返回类型。代码生成时函数调用生成CALL指令函数定义生成标签和RET指令。难点在于参数传递和返回值处理。简单做法是用全局变量传递参数但这样不支持递归。更好的做法是用栈帧但那就涉及到运行时环境的设计了。8.2 支持数组与指针数组的语法是Type Id [ Num ]类型检查时要记录数组长度。代码生成时数组访问a[i]需要计算地址偏移。指针更复杂涉及到取地址和解引用而且LL(1)文法里*既可能是乘法也可能是解引用需要根据上下文区分。8.3 生成真正的目标代码三地址码只是中间表示要生成可执行文件还需要经过指令选择、寄存器分配、指令调度等后端步骤。一个简化的路径是把三地址码翻译成x86汇编然后用汇编器生成目标文件。寄存器分配可以用简单的图着色算法或者更简单的线性扫描。8.4 错误信息的友好化改进目前的错误信息只包含行号和列号以及一个简短的描述。更友好的做法是显示错误行源代码用^标记错误位置。提供修复建议比如“缺少分号”或“变量未声明是否想使用xxx”。支持多个错误同时报告而不是遇到第一个就退出。这些改进不需要改动核心算法只需要在错误处理模块里增加逻辑。9. 一些个人体会这个实验我前前后后做了三周中间推翻重来了两次。第一次是因为文法设计得太复杂LL(1)分析表里全是冲突第二次是因为符号表的作用域管理写错了调试了一整天才发现问题。最大的体会是编译原理不是“看懂”就会的必须动手写。你看书的时候觉得FIRST集和FOLLOW集很简单但真正手工计算一个30条产生式的文法时很容易漏掉某个ε产生式的影响。你看递归下降的代码觉得逻辑清晰但真正写的时候会发现左递归、回溯、错误恢复这些问题一个都躲不掉。另一个体会是测试用例要覆盖边界情况。我最初只测了正常的表达式和语句后来发现空语句块{}、嵌套if-else、连续赋值a b c这些情况都会触发bug。建议你写一个测试脚本把各种边界情况都跑一遍。最后如果你也在做这个实验我的建议是先把文法设计好手工验证LL(1)条件再动手写代码。文法改一行代码可能要改十行。前期多花时间在纸上推演后期能省下大量调试时间。
