简介2022年华东理工大学编译原理词法分析与语法分析实验报告主要面向编译原理课程学习者、需要完成类似实验的高校学生以及想了解PL/0词法分析实现与改造的入门读者。资源共5个文件打包大小274KB包含2份实验报告文档、2个C源文件和1个PL测试用例报告覆盖词法分析与语法分析的完整实验流程源码提供PL0Compiler、PL1Compiler等可参考实现PL文件是配套的PL/0或PL/1测试源程序。内容按照实验要求展示了从编写测试源程序、识别单词并输出单词序号/字符串/类型/值到将PL/0标识符组成规则修改为C语言规则并定义PL/1语言的全过程可帮助读者理解词法分析程序中数据结构和变量变化的原因以及语法分析实验的设计思路。已有721人学习下载适合作为实验报告撰写、代码调试和课程设计的重要参考。 说实话编译原理课的词法分析语法分析实验是我大学阶段做过的最劝退也最上头的课程作业。很多人一开始以为就是写个程序判断句子对不对结果真正动手才发现前面连着的是状态机、文法和递归下降后面接着的是符号表、中间代码生成一个实验就把整门课的核心串起来了。这篇就拿2022年华东理工大学编译原理这门课的词法分析语法分析实验作为切入点把从文法设计、词法解析、语法解析到联调测试的完整链路重新走一遍。不管你是正在被实验报告折磨的学生还是想自学编译器前端的开发者这篇文章都能让你少踩几个实打实的坑。1. 拿到实验要求的第一次拆解先别写代码先把交付物想清楚1.1 词法分析和语法分析在一台编译器里到底扮演什么角色先说个容易忽略的背景。一个C语言程序从源码到可执行文件中间要经过词法分析、语法分析、语义分析、中间代码生成、优化、目标代码生成多个阶段。词法分析管的是字符流变成单词流语法分析管的是单词流变成语法树。你做这个实验本质上是在手搓一台迷你编译器的前端。很多同学把这两个实验当成两个独立的小任务这是最大的误区。词法分析器输出的Token类型怎么定义直接决定语法分析器写起来是舒心还是痛苦。我见过有人把intreturn这类关键字跟普通标识符混在一起处理结果语法分析阶段为了区分类型写了一大堆if判断代码丑到没法看。正确顺序应该是先想清楚词法阶段要产出哪些Token类别再设计文法最后才动手写词法分析器的代码。数据结构的风格先行而不是功能先行。1.2 用BNF把目标语言子集写清楚是唯一靠谱的起点以这份实验为例要求里通常会给一个简化版的类C语言子集支持int、char或者void类型的变量声明、赋值语句、if/else、while、for、函数定义与调用、算术/关系表达式、注释以及最基本的括号和分号。第一步永远是用BNF巴科斯范式把文法写出来。比如表达式部分常见的写法是expr → term | expr term | expr - term term → factor | term * factor | term / factor factor → number | ident | ( expr )然后你会发现文法里藏着左递归。左递归对递归下降分析器是致命的因为parseExpr()一进来就调用parseExpr()直接无限递归。所以后面必须花时间做消除左递归和提取左公因子。这个步骤如果在写代码之前完成后面会顺畅得多。1.3 技术栈选型C还是Python取决于你要不要硬核到底做这类实验主流是三条路线技术栈优点缺点适合场景C/C贴近底层指针操作直观状态机代码清晰字符串处理繁琐调试成本高学校实验环境固定、需要交C报告Python开发快调试容易列表和字符串切片好用性能无所谓但代码风格容易散想快速验证编译原理思路Java工程结构清晰异常处理机制完善代码量偏大类设计容易过度设计熟悉Java生态、后续想做完整编译器我当时选的是C原因是实验环境里给的是C/C模板而且后续实验符号表、中间代码都是在同一套代码上扩展换语言等于重写。选C还有一个隐形好处指针和引用在实现语法树节点时特别好用new一个节点塞进树里和书上讲的逻辑完全对应学起来理解的更透。如果你只是为了交差Python三天就能搞定。但如果你后面想继续做中间代码生成和优化实验或者想在简历上写独立实现编译器前端我建议用C硬啃一遍收获完全不在一个量级。2. 词法分析器实现手写DFA状态机的那点事2.1 状态转换图先画在纸上再翻译成代码词法分析器的本质是一个简化版DFA确定性有限自动机。你会读入一个个字符根据当前状态和输入字符决定转移到哪个新状态。很多人上手就写代码写完发现一坨 if-else自己都看不懂。正确做法是先画状态转换图。以这份实验的类C子集为例我当时画的图大概是这样的起始状态跳过空白、换行、Tab字母/下划线 → 进入标识符状态持续读入字母、数字、下划线直到遇到非这些字符然后查保留字表决定是关键字还是普通标识符数字 → 进入数字状态连续读入数字注意只支持整数所以读到小数点可以直接报错或者按浮点数扩展处理、-、*、/、(、)、{、}、;、,→ 单字符运算符/分隔符直接生成对应Token→ 单独处理因为要区分和!、、→ 同理区分!、、和单字符版本/→ 还要再看下一个字符如果是/就是单行注释如果是*就是块注释否则是除号把这些画出来之后代码就变成了状态的转移表逻辑非常直白。2.2 核心循环读一个字符、走一步状态、超出边界就回退词法分析器的主循环大概是这样的结构Token getNextToken() { skipWhitespaceAndComments(); if (isalpha(ch) || ch _) { std::string lexeme ; while (isalnum(ch) || ch _) { lexeme ch; ch getChar(); } TokenType type isKeyword(lexeme) ? KEYWORD : IDENTIFIER; return Token(type, lexeme, line, col); } if (isdigit(ch)) { std::string lexeme ; while (isdigit(ch)) { lexeme ch; ch getChar(); } return Token(CONSTANT, lexeme, line, col); } switch (ch) { case : advance(); return Token(PLUS, , line, col); case -: advance(); return Token(MINUS, -, line, col); case *: advance(); return Token(STAR, *, line, col); case : advance(); if (ch ) { advance(); return Token(EQ, , line, col); } return Token(ASSIGN, , line, col); // ... 其他符号类似 } // 到达这里说明是非法字符 error(unexpected character: std::string(1, ch)); advance(); return getNextToken(); }这段代码里最容易出问题的操作是回退。比如读数字时while (isdigit(ch))会把下一个非数字字符也读进来但那个字符不属于当前Token必须回退到输入流里否则下一个Token就丢了。C里可以维护一个pushbackChar标志Python里用ungetc类似思路。这个细节不处理好词法模块单测没问题一接上语法分析就疯狂出错。2.3 保留字与标识符先按标识符读完整串再查表判关键字因为这段代码要反复强调我就单独拿出来说。判断关键字时千万不要边读边判断前三个字母是不是int这种写法会把无数个以int开头的标识符误判成关键字。正确做法是不管三七二十一先按标识符规则读入完整字符串然后查一张预置的保留字表。bool isKeyword(const std::string s) { static std::setstd::string keywords { int, void, char, if, else, while, for, return, break, continue }; return keywords.count(s) 0; }这样intx能正确识别成标识符int能识别成关键字逻辑清爽不容易出幺蛾子。2.4 词法错误处理报错要报在行号列号上词法分析器的容错要看实验要求的严格程度。最低要求是遇到非法字符比如、#时报错并跳过。稍微好一点的做法是记录出现错误的位置行号、列号统一汇总输出。最容易被忽略的是注释未闭合和字符串未闭合。拿注释来说处理/*时一直读到*/才算结束如果文件结束了还没读到*/要能报出未闭合注释错误。我当时就是因为没处理这个验收测试里专门有一条用例挂掉了。3. 语法分析器实现递归下降与LL(1)的实战选择3.1 为什么实验几乎都要求手写递归下降而不是用Yacc很多教材会把语法分析的重点放在LR分析器、SLR、LALR这些表格驱动的算法上但实际上课程实验普遍要求手写递归下降分析器。原因很简单递归下降代码直观能和文法一一对应而且错误恢复逻辑可以写得非常细。Yacc/Bison这类工具生成的是查表代码报错信息往往不人性化调试体验也差。递归下降的核心思想是为每一个非终结符写一个解析函数函数体里按照该非终结符的产生式去匹配终结符和调用其他非终结符函数。比如表达式的文法写成代码就是这样void parseExpr() { parseTerm(); while (lookahead.type PLUS || lookahead.type MINUS) { advance(); parseTerm(); } } void parseTerm() { parseFactor(); while (lookahead.type STAR || lookahead.type SLASH) { advance(); parseFactor(); } } void parseFactor() { if (lookahead.type NUMBER || lookahead.type IDENTIFIER) { advance(); } else if (lookahead.type LPAREN) { advance(); parseExpr(); expect(RPAREN); } else { error(unexpected token in factor); } }这里while循环处理的就是左递归消除之后的E → T E与E → T E | ε用迭代替代递归。明白这一点代码和文法之间的对应关系就清清楚楚了。3.2 消除左递归与提取左公因子是实验报告中必须写清楚的内容写实验报告时消除左递归和提取左公因子是必考知识点老师一眼就能看出你懂不懂。左递归消除的标准方法假设有产生式A → A α | β可以改写为A → β A A → α A | ε比如前面提到的算术表达式文法消除左递归之后是这个样子expr → term expr_tail expr_tail → term expr_tail | - term expr_tail | ε term → factor term_tail term_tail → * factor term_tail | / factor term_tail | ε factor → number | ident | ( expr )提取左公因子的典型案例是if语句因为if (condition) stmt和if (condition) stmt else stmt有共同前缀if (condition) stmt。不提取公因子递归下降时读到if后推进到语句末尾再看见else就不知所措。处理办法是解析完then分支后向前看一个Token如果是else就走else分支。这种向前看在LL(1)里本质上是FIRST/FOLLOW集的应用报告里可以顺带把FIRST和FOLLOW算一遍会显得你很有体系。3.3 Token输入缓冲处理好向前看一个Token递归下降分析器最常见的问题是Token读取时机不一致。每个解析函数都要知道自己当前看到的Token是什么而且经常需要看下一个Token来决定走哪个分支。所以词法分析器不能变成一次性吐出一整串Token而要设计成流式接口语法分析器维护一个当前Token和前瞻Token的缓冲区。我当时用的结构很简单class Parser { Lexer lexer; Token currentToken; Token lookaheadToken; // 如果需要向前看两个Token再加一个 void advance() { currentToken lookaheadToken; lookaheadToken lexer.nextToken(); } };判断else分支时看一下lookaheadToken.type ELSE就行。这个设计配合expect(type)函数代码写起来非常顺手。3.4 语法错误恢复panic mode是性价比最高的策略语法分析不可能只处理合法输入。实验评测一定会给错误用例比如少了一个分号、括号不匹配、赋值语句左边不是左值等。如果你在处理第一个错误后就立刻崩溃退出评测印象分就会打折扣。性价比最高的错误恢复是panic mode惊慌模式发现错误后输出错误信息包含行号和期望类型然后不断丢弃Token直到遇到一个同步符号比如分号、右花括号再恢复解析。它能保证一个输入的多个错误都能被检测出来而且实现简单。我在实现时用了一个辅助函数void synchronize() { while (lookahead.type ! SEMI lookahead.type ! RBRACE lookahead.type ! EOF) { advance(); } }注意同步时不要把同步符号本身丢掉否则恢复后语义会错位。这里也是个经典的隐蔽bug建议实验报告里可以专门写一段错误恢复设计是个加分项。4. 词法和语法衔接Token结构体是整条链的接口协议4.1 Token结构体设计里的三个字段缺一个都难受词法分析器传给语法分析器的Token结构我建议至少包含三个字段类型、值、位置。enum class TokenType { IDENTIFIER, KEYWORD, NUMBER, PLUS, MINUS, STAR, SLASH, ASSIGN, EQ, NEQ, LT, LE, GT, GE, LPAREN, RPAREN, LBRACE, RBRACE, SEMI, COMMA, IF, ELSE, WHILE, FOR, RETURN, INT, VOID, CHAR, END_OF_FILE }; struct Token { TokenType type; std::string lexeme; int line; int col; };type是语法分析的判断依据lexeme是报错信息和符号表里的原始字符串line/col是定位错误位置的关键。很多同学只保留type和lexeme一但程序有错误报错信息没办法提示第几行第几列调试起来像无头苍蝇。4.2 语法分析时别提前把Token流全部缓存我见过一种很天真的写法词法分析先把整个文件的所有Token读进vectorToken再交给语法分析器遍历。问题在于语法分析报错后想做错误恢复很麻烦因为数组的遍历位置不好回退。更重要的是你的内存模型和真实编译器不一致后续如果要加符号表作用域管理、中间代码生成流式处理会让你少改很多代码。我推荐的做法是语法分析器持有词法分析器的引用按需调用nextToken()自己缓存当前Token和前瞻Token。这样既灵活又能模拟边扫描边分析的真实流程。4.3 联调时最常见的翻车点位置信息错位和EOF处理联调阶段我踩过两个坑说出来给大家提个醒。第一个是报错位置错位。比如语法分析器发现parseExpr()里期望RPAREN但来的是SEMI这时候报错位置应该用当前Token的位置而不是语法分析器自己的某个计数器。我就犯过用tokenIndex当行号的错误结果所有报错都指向同一行查了好久。第二个是EOF处理。程序读到文件末尾词法分析器要返回一个EOF类型的Token不能返回空或者抛异常。语法分析器在表达式的循环里看到EOF要能正常退出否则文件结束时会崩。这个测试不写到位报告答辩的时候容易出洋相。5. 测试与验收怎么让代码经得起老师抛来的各种刁钻输入5.1 三个维度的测试用例合法程序、边界情况、错误输入我做这类实验总结出一套测试矩阵三个维度缺一不可合法程序覆盖所有语法结构的组合。比如嵌套循环、多层括号、函数调用、多变量声明。这类用例保证功能正确性。边界情况空程序、仅注释、连续多个空行、超长标识符、数字为0、while(1)但不加大括号。这类用例最容易暴露缓冲区溢出和空指针问题。错误输入缺分号、括号不匹配、非法字符、数字后跟字母、关键字拼写错误、if的条件里没有括号。这类用例用来验证错误恢复能力。推荐用目录文件的方式管理测试用例每个文件对应一个独立场景。验收前把目录里每个in文件跑一遍对照预期输出检查比临时乱敲半天的效率高多了。5.2 答辩时老师最常问的五个问题提前准备好答案根据我自己的答辩经历老师翻实验报告时最爱问这几类问题你的文法是怎么消除左递归的这个问题要求你能在白板上写出A → A α | β到A → β A的转换过程并且能对照你自己的文法现场推导一遍。if-else的悬空else问题怎么处理的你要能说出else和最近未匹配的if绑定这个规则并指出你的递归下降代码里是哪个分支实现的。遇到语法错误你的分析器做了什么不能只说输出错误要能讲清楚错误恢复策略是什么同步符号选了什么、为什么选它。Token的line和col是怎么维护的小细节但很容易被问因为很多人的位置信息是假的。如果数字溢出怎么办这个很坑。如果你只支持整数但输入的数值超过int范围你的词法分析器怎么处理报错、截断还是转成更大类型实验要求一般不会细说但要提前想好并且写进报告。5.3 从这次实验里总结出的三条早该早知道的教训最后分享三条我个人的血泪经验也是我后来安利给学弟学妹的话第一文法永远先于代码。我在语法分析阶段返工过一次就是因为一开始没处理好左递归和if的else悬空写了两百行代码后发现还要回头改文法。在纸上花两小时整理文法能省下两天的调试时间。第二Token的接口设计是所有实验的基石。不光这个实验后面的语义分析、中间代码生成全都依赖一个稳定、清晰的Token接口。哪怕课程不要求我也建议你把Token设计得稍微冗余一点比如为后续符号表预留symbolIndex字段后面会很舒服。第三测试用例从一开始就要维护。不要等代码写完再补测试每实现一个功能点就加一条用例这样出bug时能很快定位到是哪次改动引入的问题。这也是一种很小成本的版本管理习惯。这个实验做完之后回头再看编译原理课本的第六章语法分析、第七章语义分析你会发现自己不再是被动地看公式而是能主动把概念对上自己写的代码。这才是这门实验真正的价值所在。本文还有配套的精品资源点击获取 编译原理实验指南：词法分析器与递归下降语法分析器手写全攻略
简介2022年华东理工大学编译原理词法分析与语法分析实验报告主要面向编译原理课程学习者、需要完成类似实验的高校学生以及想了解PL/0词法分析实现与改造的入门读者。资源共5个文件打包大小274KB包含2份实验报告文档、2个C源文件和1个PL测试用例报告覆盖词法分析与语法分析的完整实验流程源码提供PL0Compiler、PL1Compiler等可参考实现PL文件是配套的PL/0或PL/1测试源程序。内容按照实验要求展示了从编写测试源程序、识别单词并输出单词序号/字符串/类型/值到将PL/0标识符组成规则修改为C语言规则并定义PL/1语言的全过程可帮助读者理解词法分析程序中数据结构和变量变化的原因以及语法分析实验的设计思路。已有721人学习下载适合作为实验报告撰写、代码调试和课程设计的重要参考。 说实话编译原理课的词法分析语法分析实验是我大学阶段做过的最劝退也最上头的课程作业。很多人一开始以为就是写个程序判断句子对不对结果真正动手才发现前面连着的是状态机、文法和递归下降后面接着的是符号表、中间代码生成一个实验就把整门课的核心串起来了。这篇就拿2022年华东理工大学编译原理这门课的词法分析语法分析实验作为切入点把从文法设计、词法解析、语法解析到联调测试的完整链路重新走一遍。不管你是正在被实验报告折磨的学生还是想自学编译器前端的开发者这篇文章都能让你少踩几个实打实的坑。1. 拿到实验要求的第一次拆解先别写代码先把交付物想清楚1.1 词法分析和语法分析在一台编译器里到底扮演什么角色先说个容易忽略的背景。一个C语言程序从源码到可执行文件中间要经过词法分析、语法分析、语义分析、中间代码生成、优化、目标代码生成多个阶段。词法分析管的是字符流变成单词流语法分析管的是单词流变成语法树。你做这个实验本质上是在手搓一台迷你编译器的前端。很多同学把这两个实验当成两个独立的小任务这是最大的误区。词法分析器输出的Token类型怎么定义直接决定语法分析器写起来是舒心还是痛苦。我见过有人把intreturn这类关键字跟普通标识符混在一起处理结果语法分析阶段为了区分类型写了一大堆if判断代码丑到没法看。正确顺序应该是先想清楚词法阶段要产出哪些Token类别再设计文法最后才动手写词法分析器的代码。数据结构的风格先行而不是功能先行。1.2 用BNF把目标语言子集写清楚是唯一靠谱的起点以这份实验为例要求里通常会给一个简化版的类C语言子集支持int、char或者void类型的变量声明、赋值语句、if/else、while、for、函数定义与调用、算术/关系表达式、注释以及最基本的括号和分号。第一步永远是用BNF巴科斯范式把文法写出来。比如表达式部分常见的写法是expr → term | expr term | expr - term term → factor | term * factor | term / factor factor → number | ident | ( expr )然后你会发现文法里藏着左递归。左递归对递归下降分析器是致命的因为parseExpr()一进来就调用parseExpr()直接无限递归。所以后面必须花时间做消除左递归和提取左公因子。这个步骤如果在写代码之前完成后面会顺畅得多。1.3 技术栈选型C还是Python取决于你要不要硬核到底做这类实验主流是三条路线技术栈优点缺点适合场景C/C贴近底层指针操作直观状态机代码清晰字符串处理繁琐调试成本高学校实验环境固定、需要交C报告Python开发快调试容易列表和字符串切片好用性能无所谓但代码风格容易散想快速验证编译原理思路Java工程结构清晰异常处理机制完善代码量偏大类设计容易过度设计熟悉Java生态、后续想做完整编译器我当时选的是C原因是实验环境里给的是C/C模板而且后续实验符号表、中间代码都是在同一套代码上扩展换语言等于重写。选C还有一个隐形好处指针和引用在实现语法树节点时特别好用new一个节点塞进树里和书上讲的逻辑完全对应学起来理解的更透。如果你只是为了交差Python三天就能搞定。但如果你后面想继续做中间代码生成和优化实验或者想在简历上写独立实现编译器前端我建议用C硬啃一遍收获完全不在一个量级。2. 词法分析器实现手写DFA状态机的那点事2.1 状态转换图先画在纸上再翻译成代码词法分析器的本质是一个简化版DFA确定性有限自动机。你会读入一个个字符根据当前状态和输入字符决定转移到哪个新状态。很多人上手就写代码写完发现一坨 if-else自己都看不懂。正确做法是先画状态转换图。以这份实验的类C子集为例我当时画的图大概是这样的起始状态跳过空白、换行、Tab字母/下划线 → 进入标识符状态持续读入字母、数字、下划线直到遇到非这些字符然后查保留字表决定是关键字还是普通标识符数字 → 进入数字状态连续读入数字注意只支持整数所以读到小数点可以直接报错或者按浮点数扩展处理、-、*、/、(、)、{、}、;、,→ 单字符运算符/分隔符直接生成对应Token→ 单独处理因为要区分和!、、→ 同理区分!、、和单字符版本/→ 还要再看下一个字符如果是/就是单行注释如果是*就是块注释否则是除号把这些画出来之后代码就变成了状态的转移表逻辑非常直白。2.2 核心循环读一个字符、走一步状态、超出边界就回退词法分析器的主循环大概是这样的结构Token getNextToken() { skipWhitespaceAndComments(); if (isalpha(ch) || ch _) { std::string lexeme ; while (isalnum(ch) || ch _) { lexeme ch; ch getChar(); } TokenType type isKeyword(lexeme) ? KEYWORD : IDENTIFIER; return Token(type, lexeme, line, col); } if (isdigit(ch)) { std::string lexeme ; while (isdigit(ch)) { lexeme ch; ch getChar(); } return Token(CONSTANT, lexeme, line, col); } switch (ch) { case : advance(); return Token(PLUS, , line, col); case -: advance(); return Token(MINUS, -, line, col); case *: advance(); return Token(STAR, *, line, col); case : advance(); if (ch ) { advance(); return Token(EQ, , line, col); } return Token(ASSIGN, , line, col); // ... 其他符号类似 } // 到达这里说明是非法字符 error(unexpected character: std::string(1, ch)); advance(); return getNextToken(); }这段代码里最容易出问题的操作是回退。比如读数字时while (isdigit(ch))会把下一个非数字字符也读进来但那个字符不属于当前Token必须回退到输入流里否则下一个Token就丢了。C里可以维护一个pushbackChar标志Python里用ungetc类似思路。这个细节不处理好词法模块单测没问题一接上语法分析就疯狂出错。2.3 保留字与标识符先按标识符读完整串再查表判关键字因为这段代码要反复强调我就单独拿出来说。判断关键字时千万不要边读边判断前三个字母是不是int这种写法会把无数个以int开头的标识符误判成关键字。正确做法是不管三七二十一先按标识符规则读入完整字符串然后查一张预置的保留字表。bool isKeyword(const std::string s) { static std::setstd::string keywords { int, void, char, if, else, while, for, return, break, continue }; return keywords.count(s) 0; }这样intx能正确识别成标识符int能识别成关键字逻辑清爽不容易出幺蛾子。2.4 词法错误处理报错要报在行号列号上词法分析器的容错要看实验要求的严格程度。最低要求是遇到非法字符比如、#时报错并跳过。稍微好一点的做法是记录出现错误的位置行号、列号统一汇总输出。最容易被忽略的是注释未闭合和字符串未闭合。拿注释来说处理/*时一直读到*/才算结束如果文件结束了还没读到*/要能报出未闭合注释错误。我当时就是因为没处理这个验收测试里专门有一条用例挂掉了。3. 语法分析器实现递归下降与LL(1)的实战选择3.1 为什么实验几乎都要求手写递归下降而不是用Yacc很多教材会把语法分析的重点放在LR分析器、SLR、LALR这些表格驱动的算法上但实际上课程实验普遍要求手写递归下降分析器。原因很简单递归下降代码直观能和文法一一对应而且错误恢复逻辑可以写得非常细。Yacc/Bison这类工具生成的是查表代码报错信息往往不人性化调试体验也差。递归下降的核心思想是为每一个非终结符写一个解析函数函数体里按照该非终结符的产生式去匹配终结符和调用其他非终结符函数。比如表达式的文法写成代码就是这样void parseExpr() { parseTerm(); while (lookahead.type PLUS || lookahead.type MINUS) { advance(); parseTerm(); } } void parseTerm() { parseFactor(); while (lookahead.type STAR || lookahead.type SLASH) { advance(); parseFactor(); } } void parseFactor() { if (lookahead.type NUMBER || lookahead.type IDENTIFIER) { advance(); } else if (lookahead.type LPAREN) { advance(); parseExpr(); expect(RPAREN); } else { error(unexpected token in factor); } }这里while循环处理的就是左递归消除之后的E → T E与E → T E | ε用迭代替代递归。明白这一点代码和文法之间的对应关系就清清楚楚了。3.2 消除左递归与提取左公因子是实验报告中必须写清楚的内容写实验报告时消除左递归和提取左公因子是必考知识点老师一眼就能看出你懂不懂。左递归消除的标准方法假设有产生式A → A α | β可以改写为A → β A A → α A | ε比如前面提到的算术表达式文法消除左递归之后是这个样子expr → term expr_tail expr_tail → term expr_tail | - term expr_tail | ε term → factor term_tail term_tail → * factor term_tail | / factor term_tail | ε factor → number | ident | ( expr )提取左公因子的典型案例是if语句因为if (condition) stmt和if (condition) stmt else stmt有共同前缀if (condition) stmt。不提取公因子递归下降时读到if后推进到语句末尾再看见else就不知所措。处理办法是解析完then分支后向前看一个Token如果是else就走else分支。这种向前看在LL(1)里本质上是FIRST/FOLLOW集的应用报告里可以顺带把FIRST和FOLLOW算一遍会显得你很有体系。3.3 Token输入缓冲处理好向前看一个Token递归下降分析器最常见的问题是Token读取时机不一致。每个解析函数都要知道自己当前看到的Token是什么而且经常需要看下一个Token来决定走哪个分支。所以词法分析器不能变成一次性吐出一整串Token而要设计成流式接口语法分析器维护一个当前Token和前瞻Token的缓冲区。我当时用的结构很简单class Parser { Lexer lexer; Token currentToken; Token lookaheadToken; // 如果需要向前看两个Token再加一个 void advance() { currentToken lookaheadToken; lookaheadToken lexer.nextToken(); } };判断else分支时看一下lookaheadToken.type ELSE就行。这个设计配合expect(type)函数代码写起来非常顺手。3.4 语法错误恢复panic mode是性价比最高的策略语法分析不可能只处理合法输入。实验评测一定会给错误用例比如少了一个分号、括号不匹配、赋值语句左边不是左值等。如果你在处理第一个错误后就立刻崩溃退出评测印象分就会打折扣。性价比最高的错误恢复是panic mode惊慌模式发现错误后输出错误信息包含行号和期望类型然后不断丢弃Token直到遇到一个同步符号比如分号、右花括号再恢复解析。它能保证一个输入的多个错误都能被检测出来而且实现简单。我在实现时用了一个辅助函数void synchronize() { while (lookahead.type ! SEMI lookahead.type ! RBRACE lookahead.type ! EOF) { advance(); } }注意同步时不要把同步符号本身丢掉否则恢复后语义会错位。这里也是个经典的隐蔽bug建议实验报告里可以专门写一段错误恢复设计是个加分项。4. 词法和语法衔接Token结构体是整条链的接口协议4.1 Token结构体设计里的三个字段缺一个都难受词法分析器传给语法分析器的Token结构我建议至少包含三个字段类型、值、位置。enum class TokenType { IDENTIFIER, KEYWORD, NUMBER, PLUS, MINUS, STAR, SLASH, ASSIGN, EQ, NEQ, LT, LE, GT, GE, LPAREN, RPAREN, LBRACE, RBRACE, SEMI, COMMA, IF, ELSE, WHILE, FOR, RETURN, INT, VOID, CHAR, END_OF_FILE }; struct Token { TokenType type; std::string lexeme; int line; int col; };type是语法分析的判断依据lexeme是报错信息和符号表里的原始字符串line/col是定位错误位置的关键。很多同学只保留type和lexeme一但程序有错误报错信息没办法提示第几行第几列调试起来像无头苍蝇。4.2 语法分析时别提前把Token流全部缓存我见过一种很天真的写法词法分析先把整个文件的所有Token读进vectorToken再交给语法分析器遍历。问题在于语法分析报错后想做错误恢复很麻烦因为数组的遍历位置不好回退。更重要的是你的内存模型和真实编译器不一致后续如果要加符号表作用域管理、中间代码生成流式处理会让你少改很多代码。我推荐的做法是语法分析器持有词法分析器的引用按需调用nextToken()自己缓存当前Token和前瞻Token。这样既灵活又能模拟边扫描边分析的真实流程。4.3 联调时最常见的翻车点位置信息错位和EOF处理联调阶段我踩过两个坑说出来给大家提个醒。第一个是报错位置错位。比如语法分析器发现parseExpr()里期望RPAREN但来的是SEMI这时候报错位置应该用当前Token的位置而不是语法分析器自己的某个计数器。我就犯过用tokenIndex当行号的错误结果所有报错都指向同一行查了好久。第二个是EOF处理。程序读到文件末尾词法分析器要返回一个EOF类型的Token不能返回空或者抛异常。语法分析器在表达式的循环里看到EOF要能正常退出否则文件结束时会崩。这个测试不写到位报告答辩的时候容易出洋相。5. 测试与验收怎么让代码经得起老师抛来的各种刁钻输入5.1 三个维度的测试用例合法程序、边界情况、错误输入我做这类实验总结出一套测试矩阵三个维度缺一不可合法程序覆盖所有语法结构的组合。比如嵌套循环、多层括号、函数调用、多变量声明。这类用例保证功能正确性。边界情况空程序、仅注释、连续多个空行、超长标识符、数字为0、while(1)但不加大括号。这类用例最容易暴露缓冲区溢出和空指针问题。错误输入缺分号、括号不匹配、非法字符、数字后跟字母、关键字拼写错误、if的条件里没有括号。这类用例用来验证错误恢复能力。推荐用目录文件的方式管理测试用例每个文件对应一个独立场景。验收前把目录里每个in文件跑一遍对照预期输出检查比临时乱敲半天的效率高多了。5.2 答辩时老师最常问的五个问题提前准备好答案根据我自己的答辩经历老师翻实验报告时最爱问这几类问题你的文法是怎么消除左递归的这个问题要求你能在白板上写出A → A α | β到A → β A的转换过程并且能对照你自己的文法现场推导一遍。if-else的悬空else问题怎么处理的你要能说出else和最近未匹配的if绑定这个规则并指出你的递归下降代码里是哪个分支实现的。遇到语法错误你的分析器做了什么不能只说输出错误要能讲清楚错误恢复策略是什么同步符号选了什么、为什么选它。Token的line和col是怎么维护的小细节但很容易被问因为很多人的位置信息是假的。如果数字溢出怎么办这个很坑。如果你只支持整数但输入的数值超过int范围你的词法分析器怎么处理报错、截断还是转成更大类型实验要求一般不会细说但要提前想好并且写进报告。5.3 从这次实验里总结出的三条早该早知道的教训最后分享三条我个人的血泪经验也是我后来安利给学弟学妹的话第一文法永远先于代码。我在语法分析阶段返工过一次就是因为一开始没处理好左递归和if的else悬空写了两百行代码后发现还要回头改文法。在纸上花两小时整理文法能省下两天的调试时间。第二Token的接口设计是所有实验的基石。不光这个实验后面的语义分析、中间代码生成全都依赖一个稳定、清晰的Token接口。哪怕课程不要求我也建议你把Token设计得稍微冗余一点比如为后续符号表预留symbolIndex字段后面会很舒服。第三测试用例从一开始就要维护。不要等代码写完再补测试每实现一个功能点就加一条用例这样出bug时能很快定位到是哪次改动引入的问题。这也是一种很小成本的版本管理习惯。这个实验做完之后回头再看编译原理课本的第六章语法分析、第七章语义分析你会发现自己不再是被动地看公式而是能主动把概念对上自己写的代码。这才是这门实验真正的价值所在。本文还有配套的精品资源点击获取