编译原理课的语法分析器实验我前后大概磨了两个星期才把它彻底打通。词法分析器阶段还没什么压力照着正则表达式逐个匹配即可到了语法分析这一环情况突然变得不一样要对着文法手算FIRST集和FOLLOW集要把左递归文法改写成LL(1)形式要填一张动不动就冲突的预测分析表最后才是写驱动代码把整条流程跑通。很多人就卡在“理论看得懂、实验写不出”这道坎上。这篇文章把我实现语法分析器的完整过程捋一遍从文法分析到接口设计从表构建到代码骨架再到调试踩坑全部摊开来讲希望能让正在做这个实验的同学少走点弯路。1. 动手前的关键选择先弄懂你要做的是哪一类语法分析器1.1 自顶向下与自底向上两个流派的核心差异语法分析器在整个编译流程里管的是“结构”。词法分析器把源代码切成一个个Token语法分析器则要判断这串Token是否符合文法并且隐式或显式地还原出层次结构。按推导方向语法分析分成自顶向下和自底向上两大家族它们的原理和适用场景差别很大。LL(1)是自顶向下家族的代表从开始符号出发做最左推导反复用产生式右部替换当前最左边的非终结符。名字里的两个L分别表示“从左到右扫描输入”和“最左推导”数字1代表每次决策只需要向前看一个Token。它的优点在于决策路径短、表结构直观、出错定位方便缺点也很明显能处理的文法范围有限遇到左递归和无公共前缀的文法必须先改写否则推导过程会陷入死循环或者无从选择。LR系列是自底向上家族从输入左端开始“移进-规约”把Token逐渐合并成更大的语法单元直到栈里只剩开始符号。LR(1)、LALR(1)的能力明显强于LL(1)很多带左递归和复杂运算符优先级的文法不用大改就能直接用但它们的状态机庞大抽象程度高如果不借助Yacc、Bison这类工具辅助手写实现的工作量和调试难度都会成倍增加。我选LL(1)的原因很简单课程要求手写实现而且实验给的表达式文法经过改写可以变成LL(1)文法。LL(1)的每个关键环节——文法改写、集合计算、表构建、驱动循环——都能在纸上先推演清楚代码量也能控制在一个可接受的范围内。对第一次接触编译原理实验的人来说这是一个性价比很高的选择。1.2 拿到实验题目后的第一件事判断文法是不是LL(1)课程实验通常会给一个四则运算表达式文法长这样E - E T | T T - T * F | F F - (E) | id我拿到题目的第一反应不是打开编辑器而是把这个文法抄到纸上逐条做LL(1)判定。这个文法有两个致命问题直接左递归和公共左因子。E - E T这条规则使得最左非终结符永远是E推导永远没有尽头如果程序按“遇到左递归就展开”的思路走就会无限循环。另外T - T * F也同理。消除左递归的标准做法是把左递归变成右递归也就是引入新的非终结符来承载递归尾部。对于E - E T | T可以改写成 E - T EE - T E | εT同理T - F TT - * F T | ε。F的产生式本身没有左递归保留原样。改写后还需要做一遍LL(1)检验每个非终结符的各候选式FIRST集两两不相交且如果某个候选式能推导出ε它的FIRST集与对应非终结符的FOLLOW集不能相交。两个条件都满足才能保证预测分析表无冲突。这一环节最常见的失误是有人写完了改写后的文法却跳过了检验直接去算FIRST/FOLLOW并填表。结果表里冲突一大堆又查不出哪里错。其实“左递归改右递归”只是让文法具备成为LL(1)文法的可能性它未必真的就是LL(1)文法。必须通过计算和检验确认不能想当然。2. 从词法到语法的接口Token流是语法分析的命根子2.1 Token类型定义与编号映射语法分析器消费的是Token流不是字符流。如果你的词法分析器和语法分析器要分成两个独立模块接口约定就特别重要。我在实现里用结构体表示Token字段有类型、原文、行号、列号。类型用枚举每个终结符一个值。以C语言为例typedef enum { TOKEN_ID, TOKEN_NUM, TOKEN_PLUS, TOKEN_MINUS, TOKEN_STAR, TOKEN_SLASH, TOKEN_LPAREN, TOKEN_RPAREN, TOKEN_EOF, TOKEN_ERROR } TokenType; typedef struct { TokenType type; char lexeme[64]; int line; int col; } Token;语法分析器里预测分析表的列标号必须和词法分析器产出的TokenType使用同一套编号这是容易被忽略但极其关键的约束。我调试中遇到过的情况是文法里把编号成3词法分析器里把TOKEN_PLUS定义成5两边不统一分析器一查表就得到错误动作整个解析过程从第一个Token起就是错的。解决方案是让两个模块共享同一个头文件从同一个枚举里取值。人肉维护两套编号表必然出错别问我是怎么知道的。2.2 栈底$与词法EOF看似相同的终结符其实不是一回事LL(1)分析表里会用到句子结束符$词法分析器跑到文件末尾也会返回一个EOF类型的Token。$和EOF虽然在很多实现里都用同一个值表示但语义上有区别$是文法层的“输入串结束标记”EOF是词法层的“文件读取完毕”信号。最好在语法分析器入口处做一次显式映射把词法EOF转换成SP_END再送入分析逻辑。别图省事直接把EOF当$用也别把$当EOF用。我吃过一次亏把栈底初始化的$和输入结束的EOF编成了同一个值结果输入串末尾尚未被消费完驱动循环就判断“收到$分析成功”几条合法输入全部误判成功。这个问题非常隐蔽因为程序不崩、不死循环只是在最后一步悄悄放行。如果发现“合法输入竟然通过了但多出来的Token没被消费”优先检查这里。2.3 报错与错误恢复不只输出一句“错误”就完事课程实验如果只要求判断“输入是否合法”遇到第一个错误可以直接停下。但大部分实验会要求报错信息包含位置和期望内容有的还要求错误恢复能力。我的做法是采用panic mode当分析表查不到动作时输出包含行号和列号的错误提示然后丢弃当前Token直到遇到某个同步终结符比如右括号再恢复分析。同步终结符的选择根据文法结构决定通常选那些在语言中天然起分隔作用的符号。这个策略虽然简单但足以在表达式文法上支撑起多错误检测的效果。词法Token携带行号列号这件事从词法分析器实验时就该做好。如果没有位置信息语法报错只能告诉你“某个地方错了”排查体验会非常糟糕。当时我们班有个同学的报错信息永远是“syntax error”加一个全局计数器定位问题时得靠数Token数量效率极低。3. 构建LL(1)预测分析表的完整实操3.1 改写后的文法长什么样什么时候不能无脑提左因子改写后的表达式文法如下E - T E E - T E | ε T - F T T - * F T | ε F - (E) | id用这个文法能表达加法和乘法的优先级吗能。原理是优先级分层括号和因子在F层乘法在T层加法在E层每往上一层运算符的结合力就弱一级。改写过程中很多人会犯一个错误把E - T E写成了E - E T等于又把左递归装了回来。每写完一个产生式我都习惯用一个简单句子手工推导一遍确认推导顺序和预期一致。还要提醒一点提取左公因子并非万能。有些文法提取左公因子反而会让结构混乱比如某些语言的函数调用和数组下标都以标识符开头硬提取会把上下文信息打散增加后续语义分析的困难。实验给的表达式文法实际上不需要提取左公因子因为左递归消除之后左右两个分支的首符号天然不同了。这一步如果没必要就别多此一举少改一个地方就少一个出错点。3.2 FIRST集与FOLLOW集手算顺序和不动点实现计算FIRST集有明确的递推顺序。先把所有终结符的FIRST置为自身然后反复扫描产生式对于 A - X1 X2 ... Xn先把FIRST(X1)的非ε元素加入FIRST(A)如果X1能推导出ε再关注FIRST(X2)以此类推若所有X都能推导出ε就把ε加入FIRST(A)。这个“逐符号往后看”的过程正好对应了产生式右部的空串推导能力。FOLLOW集的计算顺序则不同。第一步是固定的把$加入开始符号的FOLLOW。然后反复扫描产生式对形如 A - αBβ 的产生式把FIRST(β)中的非ε成员加入FOLLOW(B)如果β存在且能推导出ε或者β根本不存在再把FOLLOW(A)加入FOLLOW(B)。这里最容易漏的就是“β根本不存在”的情况许多嵌套递归文法FOLLOW集要靠这条规则一层层传递下去。用程序计算时我会用不动点迭代把所有集合初始化成空集仅开始符号有$然后循环扫描全部产生式按照上述规则更新集合直到某一次完整扫描后没有任何集合变化为止。不动点迭代看起来朴笨但正确性容易保证也方便调试时打印中间结果。不要试图用“聪明”的递归算法一步算完一旦有环状依赖递归实现很容易算错或写崩。3.3 填表规则三句话但每一句背后都有坑LL(1)预测分析表的填表规则其实只有三条对于产生式 A - α先把α的FIRST集中每个终结符a对应的表项M[A, a]填上该产生式如果α可以推导出ε再对FOLLOW(A)中每个终结符b把M[A, b]填上该产生式其余表项保持空白表示语法错误。任何表项如果同时被两条产生式命中就是冲突文法不满足LL(1)。这三句话里最容易被忽略的是第二条。ε产生式的表项位置完全由FOLLOW集决定很多人填完FIRST部分就把ε产生式忘记了导致分析器在遇到应该用ε跳过的场景时无路可走。反过来如果FOLLOW集多算了一个终结符则会在本不该出现ε的位置插入动作产生虚假的“二义性冲突”或错误接受。我在调试时判断冲突性质的方法打印出每个非终结符的FIRST、FOLLOW集合和最终分析表和手算结果逐一对照。绝大多数冲突在集合层面就能看出根因不用一行行查驱动代码。如果你发现自己对着代码发呆超过半小时不如回头查集合。3.4 把示例文法的集合和分析表完整算一遍以改写后的文法为例手算结果如下FIRST(E) { (, id } FIRST(E) { , ε } FIRST(T) { (, id } FIRST(T) { *, ε } FIRST(F) { (, id } FOLLOW(E) { $, ) } FOLLOW(E) { $, ) } FOLLOW(T) { , $, ) } FOLLOW(T) { , $, ) } FOLLOW(F) { , *, $, ) }这里FOLLOW(F)包含和*是沿着 F - (E) 这条规则以及后续的 T、E 推导链一层层传递得到的。预测分析表中最容易让人疑惑的表项是M[E, $]E - ε 之所以能对$生效正是因为FOLLOW(E)含有$。同理M[E, )]也是ε产生式。其余如M[E, (]对应E - T EM[E, ]对应E - T E全部由FIRST集直接得出。有了这张表剩下的工作就是把每个格子翻译成代码里的跳转。这也是表驱动分析器的精髓文法变了只改表和产生式列表驱动代码基本不动。4. 核心代码实现表驱动LL(1)分析器的骨架4.1 数据结构产生式、编号体系、预测表C语言实现中我为非终结符、终结符、$符号各维护一套整数编号。非终结符用负数终结符用正数$用特殊值0这样栈里的“符号身份”一眼就能区分。这是我在踩了编号混用的坑之后总结出的约定。#define MAX_PRODS 32 #define MAX_NONTERMS 16 #define MAX_TERMS 16 typedef struct { int lhs; // 产生式左部非终结符编号 int rhs[8]; // 右部符号序列 int rhs_len; // 右部长度 int is_epsilon; // 是否为ε产生式 } Production; Production g_prods[MAX_PRODS]; int g_table[MAX_NONTERMS][MAX_TERMS]; // 值为产生式下标-1表示错误预测分析表用二维数组足以应对课程实验不需要用哈希表。如果你用的是Python用字典嵌套也可以但要注意查表时的默认值处理别让缺键异常把整个程序带崩。我当时用字典实现时就因为没有处理缺省情况程序在合法输入上反而抛了一堆KeyError那场面真是又好笑又好气。4.2 驱动主循环先弹栈再看是终结符还是非终结符表驱动分析器的核心是一个栈和一个循环逻辑大致如下初始化时栈底压入$再压入开始符号每次循环先弹出栈顶符号X如果X等于$且输入也处于结束状态分析成功如果X是终结符就要求它和当前输入Token匹配否则报错如果X是非终结符就查表g_table[X][curToken]得到产生式后把右部符号从后往前依次压栈ε产生式什么都不压。void parse(Token *tokens, int n) { int stk[64], top 0; stk[top] SP_END; stk[top] START_SYMBOL; int pos 0; while (1) { int X stk[--top]; if (X SP_END) { if (pos n) return; // 正常结束 error_at(pos, 输入串过早结束); return; } if (X 0) { // 终结符 if (pos n X tokens[pos].type) { pos; } else { error_at(pos, 期望终结符 %s, sym_name(X)); recover(pos); // 错误恢复 } } else { // 非终结符 int a (pos n) ? tokens[pos].type : SP_END; int prod_idx g_table[-X][a]; if (prod_idx -1) { error_at(pos, 无法匹配非终结符 %s, sym_name(X)); recover(pos); } else { push_rhs(stk, top, prod_idx); } } } }注意压栈顺序产生式右部的符号序列在栈中是后进先出所以压栈时要从右往左压。比如E - T E右部是[PLUS, T, E]压栈顺序是E、T、PLUS这样弹出时依次得到PLUS、T、E恰好和推导顺序一致。把压栈顺序写反是新手最容易犯的错后果是程序各种乱序疯狂报错。4.3 手工演算验证逻辑id id * id我建议在写完驱动代码后先不急着跑程序而是拿一个简单输入串在纸上把栈的变化写出来作为后续对照的“标准答案”。以 id id * id $ 为例初始栈是[$ E]查表得到E - T E弹E压入E T栈变为[$ E T]。此时栈顶T是非终结符匹配当前输入id查M[T, id]得到T - F T弹T压入T F栈变为[$ E T F]。F再匹配id压入id并弹出继续分析加号……整个过程中栈顶总是当前需要展开或匹配的符号输入指针只在匹配终结符时前进。如果程序运行结果和手工演算在某一帧不一致问题十有八九出在FIRST/FOLLOW集合、表项填写或压栈顺序上。优先检查这三处不要急着改主循环代码。主循环代码很简单真的。5. 调试验证与常见问题速查5.1 合法输入也报错先检查集合计算这是我在课程答疑时见到最多的一类问题。程序能跑但随便拿一条合法输入进来第一步就报错。排查路径很简单打印出每个符号的FIRST/FOLLOW集合和手算结果对比。大多数情况的根因是FOLLOW集少算了一个元素导致ε产生式对应的表项缺失或错位。不要一上来就怀疑驱动循环驱动循环通常是所有环节里最简单、最不容易写错的。5.2 表项冲突堆积在某个非终结符多半是ε推导链有问题如果预测分析表里某个非终结符有大量表项被多个产生式同时填满先别慌也不建议直接“人工选一个优先级”。正确做法是回头检验该非终结符是否有候选式能推导出ε。如果有ε候选式的表项来自FOLLOW集其他候选式的表项来自FIRST集只要存在交集就是文法不满足LL(1)条件。要嘛改文法要嘛换更宽松的分析方法硬填表只会掩盖问题让后面的实验越走越偏。5.3 匹配不上空格或换行先回头看词法分析器语法分析器只消费Token它永远不会替你忽略空格。如果你在词法分析器里没有跳过空白符那么输入 id id 会被切成[ID, BLANK, PLUS, BLANK, ID]语法分析器一碰到BLANK类型的Token就直接报错。这个锅不在语法分析器解决办法有两个在词法分析器扫描时跳过空白或者给空白符号定义成一个在任何上下文都不参与匹配的终结符。前一种做法是主流也符合大多数语言的定义。5.4 常见问题速查表我把调试中遇到的典型问题整理成一张表建议收藏现象可能原因排查方法合法输入第一次Token就报错终结符编号不统一、FIRST集缺失打印集合与分析表对比报错位置永远在最后EOF与$的处理混淆提前判成功单独处理词法EOF显式映射为SP_END分析过程死循环左递归未清除或压栈顺序写反检查文法无左递归右部从右往左压栈表项大面积冲突文法不满足LL(1)条件修改文法或改用LR系分析输入串末尾多一个Token没消费栈底$与SP_END编号冲突划分独立编号区段带空产生式的非终结符无法匹配忘记给ε产生式按FOLLOW集填表复查FOLLOW集和ε表项5.5 调试神器打开“栈轨迹”开关从实验第一天开始我给驱动循环加了一个DEBUG开关打开后每次迭代都打印当前栈内容、当前输入Token、使用的产生式和压栈动作。打印出来的轨迹可以和手工演算逐行对照定位问题非常快。这个习惯后来被我带到了工作里凡是写递归下降解析器我都会预留这个trace选项关键时刻能救急。实现方式很简单在parse函数里加一个全局布尔变量每次循环结束时按条件打印。输出格式尽量和手工演算的习惯一致比如stack: [$ E] input: id这样。有人觉得打印日志麻烦但和对着断点单步调试相比这种方式能让你一眼看到整个推导过程的全貌。6. 从实验到真实工程一点扩展思考6.1 LL(1)实验做完离真实编译器前端还差什么课程实验的表达式文法毕竟是一个玩具没有类型、没有作用域、没有运算符优先级之外的语法结构。真实语言前端里递归下降加运算符优先级解析Pratt解析是更常见的组合因为它比表驱动更好维护、报错更可控。但LL(1)表的构建思路并没有浪费你学会的FIRST/FOLLOW计算、文法等价变换、冲突分析能力在手工编写解析器时依然每天都用得上。6.2 为什么工程中常见LR(1)和LALR(1)如果未来接触编译器生成器会看到Yacc/Bison这类工具内部主要采用LALR(1)分析。LR族能处理更多文法特别是左递归和需要“推迟决策”的语法结构。理解LL(1)之后再去接触LR差的只是状态机的构造方法本质思路一致都是“查表决定下一步动作”。课程实验如果要求扩展把LL(1)换成SLR(1)是个不错的跳板——SLR(1)在LR(0)项目集的基础上利用FOLLOW集解决部分冲突算法复杂度可以接受也和本实验的知识点衔接最紧密。6.3 一个小建议写完实验后保留你的文法文档最后再分享一个我自己的习惯。无论代码写得多急我都会留一份可打印的文档里面是这个文法的产生式、FIRST/FOLLOW集、预测分析表以及两三组手工推演的栈轨迹。这份文档的价值在于它是调试时逐行对照的基准也是提交实验报告时最扎实的素材。在我之后写更复杂的词法语法模块时这个习惯也一直在帮我。语法分析器这个实验虽然看起来只是课程中的一环但它第一次让人理解“文法是语言的灵魂”这句话的含义值得认真对待。