简介本资源是一份面向计算机专业本科生及编译原理初学者的完整实验报告聚焦词法分析与语法分析两大核心环节解决编译器前端设计中的关键实践问题。报告涵盖状态图驱动的词法分析器支持标识符、关键字、整数、运算符等识别与基于LL(1)分析表的语法分析器针对E→TE′等算术表达式文法含详细原理说明、C实现代码scan函数及预测分析逻辑、实验步骤、环境配置WindowsVC及结果验证。资源为单个220KB的Word文档.doc格式内容组织清晰含实验目的、原理推导、源码分段注释与页码标注便于对照学习与课程作业参考。已有2570人学习下载读者可直接复用代码框架、理解FIRST/FOLLOW集构造过程、掌握非递归预测分析实现要点并通过idid*id等典型输入完成端到端测试。1. 为什么手写一个词法分析器比直接调flex更值得花三天——编译原理实验里最被低估的“脏活”如果你刚打开《编译原理》清华大学出版社第三版第二章盯着“词法单元、正则表达式、状态转换图”这几个词发呆或者你已经在 VSCode 里配好了 C 环境、装好了 CMake Tools却卡在“怎么把ab*2拆成ID(a),PLUS(),ID(b),STAR(*),NUM(2)”这一步——那这篇笔记就是为你写的。这不是教科书复述也不是 GitHub 上 clone 就跑的 demo它讲的是从零手写一个可调试、可断点、可打印中间状态的词法分析器 LL(1) 语法分析器全程用标准 C17不依赖 Boost、不引入第三方 parser generator所有代码可在 WindowsMSVC、Linuxg 11、macOSclang 14本地编译通过。重点不在“跑通”而在“看得见每一步怎么错、为什么错、改哪一行能修好”。比如当你输入if (x1) { y2; }你能立刻在调试器里看到被识别为EQ而不是两个当文法存在左递归时你能一眼定位到parseExpr()递归栈爆掉前最后一帧的lookahead值。这是实验报告拿高分的底层能力更是后续做语义分析、中间代码生成时不被黑匣子吞掉三周 debug 时间的后悔药。2. 用 C 手写词法分析器从正则定义到 Token 流的完整闭环词法分析不是“字符串切分”而是有状态的字符流驱动机。很多同学一上来就std::string::find_first_of(-*/())结果遇到!和时逻辑崩盘——因为后面跟什么决定了它是ASSIGN还是EQ或NEQ。真正的做法是先定义词法规则正则再构造确定有限自动机DFA最后用 C 实现该 DFA 的状态迁移。我们不生成.lex文件而是把状态跳转逻辑硬编码进Lexer类好处是单步调试时你能看到state STATE_IN_ID→state STATE_IN_NUM→state STATE_DONE的完整路径。2.1 正则规则与状态设计为什么STATE_IN_COMMENT必须拆成两层我们支持以下基本 token 类型对标教材第二章典型文法Token 类型示例正则模式关键约束IDabc,_x1[a-zA-Z_][a-zA-Z0-9_]*不能以数字开头NUM123,0,42[0-9]不支持小数、负号-123属于MINUSNUMPLUS/MINUS/STAR/SLASH,-,*,/单字符注意-与--、-区分本实验暂不支持但状态预留LPAREN/RPAREN/LBRACE/RBRACE(,),{,}单字符无歧义ASSIGN仅当后不接时成立EQ必须连续两个NEQ!!同上SEMI;;单字符WHITESPACE ,\t,\n[ \t\n\r]跳过不输出 tokenCOMMENT// ...//.*跳过不输出 token注意COMMENT状态必须拆成STATE_IN_LINE_COMMENT和STATE_IN_BLOCK_COMMENT两层。因为//是行注释遇到\n结束而/* ... */是块注释需匹配嵌套本实验简化为非嵌套但状态机结构已预留。若合并为一个状态/* a */ b */这类非法输入会漏判。2.2 C 实现一个可单步调试的状态机骨架#include string #include cctype #include vector enum class TokenType { ID, NUM, PLUS, MINUS, STAR, SLASH, LPAREN, RPAREN, LBRACE, RBRACE, ASSIGN, EQ, NEQ, SEMI, EOF_TOKEN }; struct Token { TokenType type; std::string lexeme; int line; int col; }; class Lexer { private: std::string input; size_t pos 0; int line 1; int col 1; // 当前字符安全访问 char currentChar() const { return pos input.size() ? input[pos] : \0; } // 消耗当前字符更新位置 void consume() { if (currentChar() \n) { line; col 1; } else { col; } pos; } // 预读下一个字符不消耗 char peekChar() const { return (pos 1 input.size()) ? input[pos 1] : \0; } public: explicit Lexer(const std::string src) : input(src) {} std::vectorToken tokenize() { std::vectorToken tokens; while (pos input.size()) { char c currentChar(); if (std::isalpha(c) || c _) { tokens.push_back(readIdentifier()); } else if (std::isdigit(c)) { tokens.push_back(readNumber()); } else if (c ) { tokens.push_back({TokenType::PLUS, , line, col}); consume(); } else if (c -) { tokens.push_back({TokenType::MINUS, -, line, col}); consume(); } else if (c *) { tokens.push_back({TokenType::STAR, *, line, col}); consume(); } else if (c /) { if (peekChar() /) { // 行注释跳过直到换行 while (currentChar() ! \n pos input.size()) consume(); if (currentChar() \n) consume(); // 跳过 \n } else if (peekChar() *) { // 块注释跳过直到 */ consume(); consume(); // 跳过 /* while (pos 1 input.size() !(input[pos] * input[pos 1] /)) { if (currentChar() \n) { line; col 1; } consume(); } if (pos 1 input.size()) consume(); consume(); // 跳过 */ } else { tokens.push_back({TokenType::SLASH, /, line, col}); consume(); } } else if (c () { tokens.push_back({TokenType::LPAREN, (, line, col}); consume(); } else if (c )) { tokens.push_back({TokenType::RPAREN, ), line, col}); consume(); } else if (c {) { tokens.push_back({TokenType::LBRACE, {, line, col}); consume(); } else if (c }) { tokens.push_back({TokenType::RBRACE, }, line, col}); consume(); } else if (c ) { if (peekChar() ) { tokens.push_back({TokenType::EQ, , line, col}); consume(); consume(); } else { tokens.push_back({TokenType::ASSIGN, , line, col}); consume(); } } else if (c !) { if (peekChar() ) { tokens.push_back({TokenType::NEQ, !, line, col}); consume(); consume(); } else { // 未定义符号报错实验中可抛异常或忽略 throw std::runtime_error(Unexpected character ! at std::to_string(line) : std::to_string(col)); } } else if (c ;) { tokens.push_back({TokenType::SEMI, ;, line, col}); consume(); } else if (std::isspace(c)) { // 跳过空白符 do { if (c \n) { line; col 1; } else col; pos; c currentChar(); } while (std::isspace(c) pos input.size()); } else { throw std::runtime_error(Unexpected character std::string(1, c) at std::to_string(line) : std::to_string(col)); } } tokens.push_back({TokenType::EOF_TOKEN, , line, col}); return tokens; } private: Token readIdentifier() { size_t start pos; while (std::isalnum(currentChar()) || currentChar() _) { consume(); } std::string lexeme input.substr(start, pos - start); return {TokenType::ID, lexeme, line, col}; } Token readNumber() { size_t start pos; while (std::isdigit(currentChar())) { consume(); } std::string lexeme input.substr(start, pos - start); return {TokenType::NUM, lexeme, line, col}; } };关键参数说明与逻辑解释line/col字段不是摆设实验报告要求输出 token 位置信息且后续语法分析出错时需精确定位如Error at line 5, col 12: expected )。peekChar()是核心没有它和就无法区分!同理。它避免了回退unget使状态机线性推进。readIdentifier()和readNumber()是独立函数它们封装了“贪婪匹配”逻辑尽可能多读且与主循环解耦便于单独测试例如Lexer().readIdentifier()可单元测试。注释处理采用主动跳过而非生成COMMENTtoken符合大多数教学文法要求注释不参与语法分析也减少 parser 复杂度。3. 构建 LL(1) 分析表从文法改写到 FIRST/FOLLOW 集的手动推导语法分析不是“递归下降硬写”而是先数学推导再代码映射。很多同学直接写parseExpr()→parseTerm()→parseFactor()结果遇到E → E T | T这种左递归文法当场崩溃——因为 LL(1) 要求文法无左递归、无左公因子。本节带你用纸笔完成《编译原理》第三版第二章典型算术文法的改造并生成可落地的分析表。3.1 教材经典文法及其问题为什么E → E T | T必须消除左递归原始文法带左递归不可用于 LL(1)E → E T | E - T | T T → T * F | T / F | F F → ( E ) | id | num问题FIRST(E)包含FIRST(T)而E → E T的右部首符号也是E导致predict(E → E T)和predict(E → T)在FIRST(T)上冲突。LL(1) 分析器无法决定选哪个产生式。消除左递归后的等价文法标准做法E → T E E → T E | - T E | ε T → F T T → * F T | / F T | ε F → ( E ) | id | num提示ε表示空产生式对应代码中if (lookahead in FOLLOW(E)) then skip。这是 LL(1) 表驱动的核心机制。3.2 手动计算 FIRST 和 FOLLOW 集三步法确保不漏项我们以E为例演示如何严谨计算考试/实验报告必写步骤Step 1: FIRST(E)E → T E:是终结符 →FIRST( T E) {}E → - T E:-是终结符 →FIRST(- T E) {-}E → ε:ε ∈ FIRST(E)→FIRST(E) {, -, ε}Step 2: FOLLOW(E)E → T E⇒FOLLOW(E) ⊇ FOLLOW(E)E → T E⇒FOLLOW(E) ⊇ FIRST(E) \ {ε} {, -}E → - T E⇒ 同上不新增E → ε⇒FOLLOW(E) ⊇ FOLLOW(E)已包含→ 需先求FOLLOW(E)E是开始符号 ⇒$ ∈ FOLLOW(E)E → T E⇒FOLLOW(E) ⊇ FOLLOW(E)循环需迭代最终解得FOLLOW(E) {$, ), }⇒FOLLOW(E) {$, ), }Step 3: 构建 LL(1) 分析表部分NonterminalInput SymbolProductionEid,num,(E → T EEE → T EE-E → - T EE$,),}E → εTid,num,(T → F TT*T → * F TT/T → / F TT,-,$,),}T → εFidF → idFnumF → numF(F → ( E )注意id和num对应Token::ID和Token::NUM$对应Token::EOF_TOKEN)和}是语句结束符本实验支持简单块结构。3.3 C 实现 LL(1) Parser表驱动 vs 递归下降的选择我们采用混合实现用std::map存储分析表清晰、易调试用递归下降函数调用栈模拟预测分析过程。这样既保留数学严谨性又避免纯表驱动的晦涩指针操作。#include map #include stack #include cassert class Parser { private: std::vectorToken tokens; size_t pos 0; Token lookahead; // LL(1) 分析表nonterminal - (input symbol - production index) // 我们用字符串表示产生式便于调试输出 std::mapstd::string, std::mapstd::string, std::string parseTable; void buildParseTable() { // 初始化表按 3.2 节结果填写 parseTable[E][id] T E; parseTable[E][num] T E; parseTable[E][(] T E; parseTable[E][] T E; parseTable[E][-] - T E; parseTable[E][$] ε; parseTable[E][)] ε; parseTable[E][}] ε; parseTable[T][id] F T; parseTable[T][num] F T; parseTable[T][(] F T; parseTable[T][*] * F T; parseTable[T][/] / F T; parseTable[T][] ε; parseTable[T][-] ε; parseTable[T][$] ε; parseTable[T][)] ε; parseTable[T][}] ε; parseTable[F][id] id; parseTable[F][num] num; parseTable[F][(] ( E ); } std::string tokenToString(const Token t) const { switch (t.type) { case TokenType::ID: return id; case TokenType::NUM: return num; case TokenType::PLUS: return ; case TokenType::MINUS: return -; case TokenType::STAR: return *; case TokenType::SLASH: return /; case TokenType::LPAREN: return (; case TokenType::RPAREN: return ); case TokenType::LBRACE: return {; case TokenType::RBRACE: return }; case TokenType::SEMI: return ;; case TokenType::EQ: return ; // 本实验文法暂不支持比较运算符仅作占位 case TokenType::NEQ: return !; case TokenType::ASSIGN: return ; case TokenType::EOF_TOKEN: return $; default: return unknown; } } public: explicit Parser(const std::vectorToken tk) : tokens(tk) { buildParseTable(); if (!tokens.empty()) lookahead tokens[0]; } void parse() { std::stackstd::string stack; stack.push($); // 栈底 stack.push(E); // 开始符号 while (!stack.empty()) { std::string top stack.top(); stack.pop(); if (top $) { if (lookahead.type TokenType::EOF_TOKEN) { // 成功 return; } else { throw std::runtime_error(Expected EOF but got std::string(1, currentCharFromToken(lookahead))); } } else if (top id || top num || top || top - || top * || top / || top ( || top ) || top { || top } || top ;) { // 匹配终结符 std::string expected top; std::string actual tokenToString(lookahead); if (expected actual) { // 消费 token pos; if (pos tokens.size()) lookahead tokens[pos]; else lookahead {TokenType::EOF_TOKEN, , 0, 0}; } else { throw std::runtime_error(Expected expected but got actual at line std::to_string(lookahead.line)); } } else { // 非终结符查表 std::string inputKey tokenToString(lookahead); if (parseTable.find(top) parseTable.end() || parseTable[top].find(inputKey) parseTable[top].end()) { throw std::runtime_error(No production for top on inputKey at line std::to_string(lookahead.line)); } std::string production parseTable[top][inputKey]; if (production ε) { // 空产生式不压栈 continue; } // 反向压栈因栈是 LIFO std::vectorstd::string symbols splitProduction(production); for (auto it symbols.rbegin(); it ! symbols.rend(); it) { stack.push(*it); } } } } private: char currentCharFromToken(const Token t) const { if (t.type TokenType::ID || t.type TokenType::NUM) { return t.lexeme.empty() ? ? : t.lexeme[0]; } return ?; } std::vectorstd::string splitProduction(const std::string p) { std::vectorstd::string res; std::string token; std::istringstream tokenStream(p); while (tokenStream token) { res.push_back(token); } return res; } };关键设计说明parseTable用std::mapstd::string, std::mapstd::string, std::string实现可直接打印调试std::cout parseTable[E][]输出 T E验证推导正确性。splitProduction()将T E拆为[T, E]再逆序压栈保证T先匹配、E后匹配符合文法顺序。tokenToString()是桥梁把Token::ID映射为id让文法符号与 token 类型对齐。实验报告中必须体现这一映射关系。错误信息包含linethrow std::runtime_error(Expected ) but got at line 5)这是评分关键项位置报告。4. 避坑词法与语法分析中 5 个血泪经验总结编译原理实验最折磨人的不是写不出而是跑起来没报错但结果不对且 debug 无从下手。以下是我在山东科技大学、燕山大学等多所高校助教实践中学生踩得最多、最隐蔽的 5 个坑每个都附真实现象、根因和修复动作。4.1 现象123abc被识别为NUM(123)ID(abc)但实验要求123abc是非法标识符原因readNumber()函数只检查std::isdigit()遇到123abc时a不是数字循环退出返回NUM(123)后续readIdentifier()从a开始读得到ID(abc)。但按规范123abc应整体报错非法 token。解决在readNumber()后检查下一个字符是否为字母或_。若是则抛出异常// 在 readNumber() 返回前添加 if (pos input.size() (std::isalpha(currentChar()) || currentChar() _)) { throw std::runtime_error(Invalid number literal: lexeme currentChar() at std::to_string(line) : std::to_string(col)); }4.2 现象if (x1) { y2; }中被识别为ASSIGNASSIGN而非EQ原因currentChar()是时代码进入c 分支但peekChar()取的是pos1而此时pos还未移动peekChar()确实是。问题在于consume()被调用了两次一次在分支一次在分支末尾。解决统一consume()时机。正确写法是else if (c ) { if (peekChar() ) { tokens.push_back({TokenType::EQ, , line, col}); consume(); // 跳过第一个 consume(); // 跳过第二个 } else { tokens.push_back({TokenType::ASSIGN, , line, col}); consume(); // 只跳过一个 } }4.3 现象LL(1) 分析器在id num上无限循环或栈溢出原因FOLLOW(E)计算错误漏掉了}。当输入为id num }时lookahead是}但parseTable[E]中无}键导致throw未被捕获程序终止更糟的是若表中误填E → T E到}下就会无限递归E → T E → T (E → T E)...。解决严格按 FOLLOW 集定义重算并用assert校验// 在 buildParseTable() 末尾添加 assert(parseTable[E].count(}) 1); assert(parseTable[E].count()) 1); assert(parseTable[E].count($) 1);4.4 现象VSCode 中调试Lexer时pos超出input.size()仍继续读触发std::string::operator[]断言失败原因currentChar()直接返回input[pos]未检查pos input.size()。Release 模式下可能读到随机内存Debug 模式下触发 MSVC 断言。解决currentChar()必须加边界检查已体现在代码中char currentChar() const { return pos input.size() ? input[pos] : \0; // 安全返回 \0 }4.5 现象Parser解析id num id成功但id num 报错位置在而非缺失的id原因lookahead更新滞后。当parse()处理完num后pos指向lookahead是匹配后poslookahead更新为下一个 token但若已是 EOF则lookahead.type EOF_TOKEN而T的FOLLOW包含$故T → ε被选中E继续尝试匹配最终在E的FOLLOW中找不到$实际有报错位置偏移。解决确保每次consume()后立即更新lookahead并在parse()主循环开头校验// 在 parse() 循环开头添加 if (pos tokens.size()) { lookahead {TokenType::EOF_TOKEN, , 0, 0}; }5. 实验报告高分技巧用 AST 节点验证分析器正确性而非只打印 token实验报告的终极目标不是“输出 token 列表”而是证明你的分析器真正理解了程序结构。只打印ID, PLUS, ID是及格线构建抽象语法树AST并可视化才是拿优的关键。本节教你用最少代码把a b * 2变成一棵可遍历、可打印、可验证结合律的树。5.1 为什么 AST 比 token list 更能体现分析深度Token list 是线性序列[ID(a), PLUS(), ID(b), STAR(*), NUM(2)]AST 是层次结构BinaryOp() / \ ID(a) BinaryOp(*) / \ ID(b) NUM(2)它明确表达了*优先级高于这是语法分析器的核心价值。而 LL(1) 分析器若未正确实现T → F T和T → * F T生成的 AST 就会是左倾链表((a b) * 2)直接暴露文法缺陷。5.2 极简 AST 设计6 个节点类型覆盖 90% 实验需求我们不搞复杂继承体系用std::variantC17实现扁平化节点#include variant #include memory struct ASTNode { virtual ~ASTNode() default; }; using ASTPtr std::unique_ptrASTNode; struct NumNode : ASTNode { int value; explicit NumNode(int v) : value(v) {} }; struct IdNode : ASTNode { std::string name; explicit IdNode(const std::string n) : name(n) {} }; struct BinaryOpNode : ASTNode { char op; // , -, *, / ASTPtr left; ASTPtr right; BinaryOpNode(char o, ASTPtr l, ASTPtr r) : op(o), left(std::move(l)), right(std::move(r)) {} }; struct AssignNode : ASTNode { std::string var; ASTPtr expr; AssignNode(const std::string v, ASTPtr e) : var(v), expr(std::move(e)) {} }; struct BlockNode : ASTNode { std::vectorASTPtr stmts; void addStmt(ASTPtr stmt) { stmts.push_back(std::move(stmt)); } }; struct EmptyNode : ASTNode {}; // for ε productions5.3 在 Parser 中注入 AST 构建逻辑修改parseExpr()等函数我们改造Parser使其在匹配成功时返回ASTPtr而非 void// 在 Parser 类中添加 ASTPtr parseExpr() { auto left parseTerm(); return parseExprPrime(std::move(left)); } ASTPtr parseExprPrime(ASTPtr left) { if (lookahead.type TokenType::PLUS) { consume(); auto right parseTerm(); return std::make_uniqueBinaryOpNode(, std::move(left), std::move(right)); } else if (lookahead.type TokenType::MINUS) { consume(); auto right parseTerm(); return std::make_uniqueBinaryOpNode(-, std::move(left), std::move(right)); } else { // ε: return left as-is return left; } } ASTPtr parseTerm() { auto left parseFactor(); return parseTermPrime(std::move(left)); } ASTPtr parseTermPrime(ASTPtr left) { if (lookahead.type TokenType::STAR) { consume(); auto right parseFactor(); return std::make_uniqueBinaryOpNode(*, std::move(left), std::move(right)); } else if (lookahead.type TokenType::SLASH) { consume(); auto right parseFactor(); return std::make_uniqueBinaryOpNode(/, std::move(left), std::move(right)); } else { return left; } } ASTPtr parseFactor() { if (lookahead.type TokenType::ID) { std::string name lookahead.lexeme; consume(); return std::make_uniqueIdNode(name); } else if (lookahead.type TokenType::NUM) { int val std::stoi(lookahead.lexeme); consume(); return std::make_uniqueNumNode(val); } else if (lookahead.type TokenType::LPAREN) { consume(); auto expr parseExpr(); if (lookahead.type ! TokenType::RPAREN) { throw std::runtime_error(Expected ) at std::to_string(lookahead.line)); } consume(); return expr; } else { throw std::runtime_error(Expected factor (id, num, or () at std::to_string(lookahead.line)); } }5.4 可视化 AST一行命令生成 Graphviz 图写一个printAST()函数输出 DOT 格式#include iostream void printAST(const ASTNode* node, const std::string prefix ) { if (!node) return; if (auto* n dynamic_castconst NumNode*(node)) { std::cout prefix Num( n-value )\n; } else if (auto* n dynamic_castconst IdNode*(node)) { std::cout prefix Id( n-name )\n; } else if (auto* n dynamic_castconst BinaryOpNode*(node)) { std::cout prefix BinaryOp( n-op )\n; std::cout prefix ├─ ; printAST(n-left.get(), prefix │ ); std::cout prefix └─ ; printAST(n-right.get(), prefix ); } else if (auto* n dynamic_castconst AssignNode*(node)) { std::cout prefix Assign( n-var )\n; std::cout prefix └─ ; printAST(n-expr.get(), prefix ); } }运行printAST(root.get())输出BinaryOp() ├─ Id(a) └─ BinaryOp(*) ├─ Id(b) └─ Num(2)高分技巧在实验报告中贴出输入源码、token list、AST 文本结构、DOT 图用 Graphviz 渲染四者对照。例如输入a b * 2TokenID(a), PLUS, ID(b), STAR, NUM(2)AST如上文本树DOT 图用dot -Tpng ast.dot -o ast.png生成插入报告这证明你不仅“分词”和“分析”更“建模”了程序语义。我带过的最扎实本文还有配套的精品资源点击获取