简介本资源是北京邮电大学计算机学院《编译原理》课程配套的词法与语法分析器实践项目面向高校计算机专业学生及编译技术初学者聚焦编译前端核心能力训练——从源码中识别token并构建抽象语法树。压缩包共12个文件含4个C/C实现源码.cpp/.c、3份Markdown文档含设计说明与实验报告、4个文本文件含文法定义、测试样例与词法规范整体仅27KB轻量精炼便于快速导入IDE调试学习。已有200人下载学习适合作为课程实验参考或自主复现编译器前端的入门范例。读者可直接运行Word_analysis.cpp和LL/LR分析器代码结合Grammar.txt与test.cpp理解自顶向下/自底向上分析流程并通过report.md掌握实验设计逻辑与常见错误处理思路。1. 北邮编译原理实验包实测词法分析器能跑通 sample.c但 LR 分析器默认不支持左递归——这是给真正在写实验报告的人准备的落地笔记上周帮实验室师弟调试一份“北邮计算机学院编译原理词法、语法分析器.zip”他卡在Word_analysis.cpp编译报错整整两天最后发现是 VS2022 默认启用了/permissive-严苛模式而原代码里用了 C11 前的gets()和未声明的string::substr()重载。这不是理论课 PPT这是你明天就要交的实验压缩包它包含 3 套完整可运行的分析器LL(1)、LR(0)、手写词法配套Grammar.txt文法定义、sample.c测试源码、两份report.md实验报告模板甚至还有demo.txt逐行执行日志。它不教你怎么推导 FIRST/FOLLOW 集而是直接给你能g -o lexer Word_analysis.cpp出来、能读入sample.c并输出 token 流的 C 可执行体。适合正在赶编译原理实验 deadline 的本科生、想快速复现经典分析器结构的考研党以及需要嵌入式场景下轻量级语法校验模块的嵌入式工程师——别被“北邮”二字唬住这包里没用任何私有库纯标准 C11Windows/WSL/macOS 全平台可编译唯一门槛是你得知道g怎么加-stdc11。2. 词法分析器核心从 sample.c 到 token 流的四步拆解与正则映射表2.1 词法分析器工作流预处理 → 字符缓冲 → 状态机匹配 → token 输出Word_analysis.cpp是整个包里最稳定、最接近工业级实现的模块。它不依赖 Flex/Bison而是用纯 C 手写状态机流程清晰到可以画成一张纸预处理读取sample.c全文到std::string buffer预扫描剔除//行注释和/* */块注释注意/* */不支持嵌套字符缓冲用size_t pos 0作为游标在buffer上滑动每次buffer[pos]取单字符状态机匹配进入while (pos buffer.length())主循环根据当前字符跳转到不同switch分支如a-z进入标识符识别0-9进入数字识别token 输出每识别一个完整 token如int、123、调用addToken(type, lexeme, line)将类型、字面值、行号存入全局vectorToken最终遍历打印。这个设计规避了正则引擎的黑盒性——你改一行if (c / buffer[pos1] *)就能关掉块注释支持比改.l文件再flex生成快十倍。2.2 正则规则硬编码表为什么关键字必须前置匹配Word_analysis.cpp中最关键的不是算法而是isKeyword()函数里的字符串数组const string keywords[] { auto, break, case, char, const, continue, default, do, double, else, enum, extern, float, for, goto, if, int, long, register, return, short, signed, sizeof, static, struct, switch, typedef, union, unsigned, void, volatile, while };提示这个数组顺序不能乱isKeyword()用的是线性查找for (int i0; i32; i) if (s keywords[i]) return true;。如果把int放在integer后面虽然本包没integer而输入是integer就会先匹配到int导致截断错误。这是手写词法分析器的典型玄学——关键字必须按最长前缀优先排序实际项目中建议改成unordered_setstring哈希查找O(1) 时间且无序依赖。2.3 Token 结构体定义与行号追踪机制Token类型定义在Word_analysis.cpp开头struct Token { int type; // 1: KEYWORD, 2: IDENTIFIER, 3: NUMBER, 4: OPERATOR, 5: DELIMITER string lexeme; // 原始字面值如 while、i、123 int line; // 行号从 1 开始计数 };行号不是靠\n计数器简单累加——那样会漏掉 Windows 的\r\n和 macOS 的\r。真实逻辑在skipWhitespace()函数里void skipWhitespace() { while (pos buffer.length()) { char c buffer[pos]; if (c \n) line; // 每遇到 \n 行号1 else if (c \r) { if (pos 1 buffer.length() buffer[pos 1] \n) { line; pos; // 跳过 \r\n 的 \n 部分 } else line; // 单独 \r 也视为换行兼容旧 Mac } else if (isspace(c)) { pos; continue; } break; } }这段代码解释了为什么sample.c里混用\n和\r\n时行号依然准确它显式处理了三种换行符组合。如果你的测试文件是 Linux 生成的纯\n这段逻辑完全冗余但一旦拿到 Windows 下编辑过的 C 源码这就是救命逻辑。2.4 标识符与数字的边界判定下划线、科学计数法、十六进制的取舍标识符识别函数parseIdentifier()的终止条件是while (pos buffer.length()) { char c buffer[pos]; if (isalnum(c) || c _) { lexeme c; pos; } else break; // 遇到空格、运算符、分号等即停止 }注意它允许下划线符合 C 标准但不检查首字符是否为字母或下划线_abc会被识别为 IDENTIFIER而非 ERROR。这是教学简化——工业级词法器需在parseIdentifier()前加首字符校验if (!isalpha(c) c ! _) return ERROR;。数字识别更激进parseNumber()只支持十进制整数123、带小数点的浮点数3.14、科学计数法1.23e-4但明确拒绝十六进制0x1A和八进制0123。证据在Grammar.txt的词法规则部分digit → 0|1|...|9 number → digit | digit . digit* | digit . digit e (|-) digit没有0x前缀定义。这意味着若你在sample.c里写int x 0xFF;词法器会把0当作 NUMBERx当作 IDENTIFIERFF当作 IDENTIFIER全程无报错——因为文法没定义十六进制它就当普通标识符处理。这是教学包的合理取舍聚焦核心概念不堆砌边缘语法。3. 语法分析器双轨制LL(1) 递归下降 vs LR(0) 表驱动——选哪个看你的 Grammar.txt3.1 LL(1) 分析器递归下降 预测分析表适合教学推演LL.cpp实现的是典型的 LL(1) 递归下降分析器结构极其清晰每个非终结符对应一个函数parseProgram(),parseDeclaration(),parseStatement()函数内用lookahead当前 token 类型决定调用哪个产生式。核心逻辑在predictTable二维数组// predictTable[nonterminal][terminal] production_index // nonterminal: 0PROGRAM, 1DECLARATION, 2STATEMENT... // terminal: 0KEYWORD_int, 1IDENTIFIER, 2NUMBER, 3SEMICOLON... int predictTable[10][20] { {1, -1, -1, 0, ...}, // PROGRAM - DECLARATION PROGRAM | ε {2, -1, -1, -1, ...}, // DECLARATION - KEYWORD_int IDENTIFIER SEMICOLON ... };parseProgram()的伪代码void parseProgram() { int la lookahead.type; int prod predictTable[0][la]; // 0PROGRAM 行 if (prod 1) { // PROGRAM - DECLARATION PROGRAM parseDeclaration(); parseProgram(); } else if (prod 0) { // PROGRAM - ε什么也不做 return; } else error(unexpected token); }这种写法的好处是你能一眼看出语法树怎么长。parseDeclaration()调用parseStatement()parseStatement()调用parseExpression()调用栈就是 AST 的深度优先遍历路径。缺点也很明显predictTable必须手工填写且要求文法满足 LL(1) 条件无左递归、FIRST/FOLLOW 不相交。Grammar.txt里E → E T | T这种左递归规则在LL.cpp里已被改写为E → T E和E → T E | ε——这是你写实验报告时必须展示的改写步骤。3.2 LR(0) 分析器DFA 状态图 ACTION/GOTO 表贴近真实编译器LR.cpp是本包的技术高点。它不手写递归函数而是先读取Grammar.txt构建 LR(0) 项目集规范族Canonical Collection再生成 ACTION 和 GOTO 表最后用栈模拟 DFA 运行。主循环只有 20 行stackint stateStack; // 存状态编号 stackToken symbolStack; // 存已移进的符号 stateStack.push(0); // 初始状态 while (true) { int s stateStack.top(); int a lookahead.type; int action actionTable[s][a]; // 查 ACTION 表 if (action 0) { // 移进压入新状态 stateStack.push(action); symbolStack.push(lookahead); lookahead nextToken(); // 读下一个 token } else if (action 0) { // 归约查 GOTO 表 int prodLen -action; // 归约长度 for (int i0; iprodLen; i) { stateStack.pop(); symbolStack.pop(); } int lhs getLHS(prodLen); // 获取产生式左部非终结符 int gotoState gotoTable[stateStack.top()][lhs]; stateStack.push(gotoState); symbolStack.push(Token(lhs, , 0)); // 压入非终结符占位符 } else if (action 0) { // 接受 cout Parse success! endl; break; } else error(syntax error at line to_string(lookahead.line)); }actionTable和gotoTable由buildTables()函数生成该函数实现了标准的 LR(0) 构造算法闭包Closure、转移Goto、项目集规范族构建。Grammar.txt的文法必须是上下文无关文法CFG且LR.cpp对文法无改写要求——E → E T这种左递归可以直接用LR 自动处理。这是它比 LL 更强大的地方无需人工消除左递归更贴近 Yacc/Bison 的工作方式。3.3 Grammar.txt 文法格式详解终结符、非终结符、产生式书写规范Grammar.txt是所有分析器的共同输入格式严格遵循教学惯例# 终结符列表必须以 TERM 开头 TERM int, char, float, if, else, while, return, ;, , , -, *, /, (, ), {, }, ,, ID, NUM # 非终结符列表必须以 NONTERM 开头 NONTERM program, declaration, statement, expression, term, factor # 产生式列表→ 表示推导| 表示或 program → declaration program | ε declaration → int ID ; statement → expression ; | while ( expression ) statement | { statement* } expression → term expression expression → term expression | - term expression | ε term → factor term term → * factor term | / factor term | ε factor → ID | NUM | ( expression )关键约束ε表示空产生式不能写成epsilon或ID和NUM是预定义终结符对应词法器输出的IDENTIFIER和NUMBER类型statement*表示零个或多个statement这是LR.cpp特有的简写LL.cpp不识别需手动展开为statements → statement statements | ε。注意LR.cpp的buildTables()函数会将Grammar.txt解析为内存中的 CFG 结构但不验证文法是否符合 LR(0) 要求。如果你写了二义性文法如if E then S1 else S2的悬空 elsebuildTables()仍会生成表但运行时在冲突状态报错。这是教学包的刻意设计让你亲手撞墙理解冲突本质。3.4 两套分析器的性能与适用边界对比维度LL(1) (LL.cpp)LR(0) (LR.cpp)文法支持需消除左递归、提取左公因子仅支持 LL(1) 文法支持任意 CFG含左递归但可能有移进-归约/归约-归约冲突实现复杂度低手写函数逻辑直白高需实现项目集规范族、ACTION/GOTO 表构造调试难度低函数调用栈即 ASTcout打印即可定位高需打印状态栈、符号栈、输入剩余序列三元组错误恢复中可跳过 token 直到同步记号如;弱冲突时直接报错无内置恢复机制编译速度快无表构造开销纯函数调用慢首次运行需 200ms 构造表对sample.c约 50 行结论写实验报告选 LL研究编译器原理选 LR。LL.cpp的report.md里有完整的 FIRST/FOLLOW 集计算过程LR.cpp的report.md则展示了状态 0 的项目集{ [S→•S], [S→•A], [A→•aA], [A→•b] }如何通过 Goto 得到状态 1。两者互补不是替代。4. 避坑编译、运行、调试三大环节的 5 个血泪经验4.1 编译失败C11 标准缺失导致to_string、auto报错现象g Word_analysis.cpp -o lexer报错‘to_string’ was not declared in this scope或‘auto’ does not name a type。原因GCC 4.7 才完全支持 C11而Word_analysis.cpp大量使用to_string()第 89 行、auto第 142 行、unordered_map第 201 行。老版本 GCC 默认用 C98 标准。解决强制指定标准g -stdc11 -o lexer Word_analysis.cpp。Windows 下用 MinGW-w64 时还需加-D_GLIBCXX_USE_CXX11_ABI0兼容旧 ABI。4.2 运行崩溃sample.c中文注释触发buffer[pos]越界现象程序运行到while (pos buffer.length())时Segmentation fault。原因sample.c里有 UTF-8 中文注释如// 初始化变量UTF-8 中文占 3 字节但buffer[pos]按字节取当pos指向中文第二个字节时c是非法字节如0xA6后续isalnum(c)返回 false但skipWhitespace()未处理此情况pos未递增陷入死循环直至越界。解决在skipWhitespace()开头加 UTF-8 字节校验// 在 while 循环内字符处理前插入 if ((c 0x80) 0x80) { // 可能是 UTF-8 多字节开头 if ((c 0xE0) 0xC0 pos 1 buffer.length() (buffer[pos1] 0xC0) 0x80) pos 2; // 2字节 else if ((c 0xF0) 0xE0 pos 2 buffer.length() (buffer[pos1] 0xC0) 0x80 (buffer[pos2] 0xC0) 0x80) pos 3; // 3字节 else pos; // 无效字节跳过 continue; }4.3 语法分析失败Grammar.txt缺少TERM声明导致LL.cpp读取崩溃现象./parser_ll运行后立即Segmentation faultGDB 显示崩溃在readGrammar()函数的getline()调用处。原因LL.cpp的readGrammar()假设Grammar.txt严格按TERM→NONTERM→PRODUCTION顺序书写。若你删掉了TERM行如只留NONTERM和产生式readGrammar()会把第一行当作TERM列表解析stringstream ss(line)分割出空 vector后续ss token读取时ss.fail()为 true但代码未检查直接访问tokens[0]越界。解决确保Grammar.txt以TERM开头且每行末尾无空格。可用sed -i s/[[:space:]]*$// Grammar.txt清理。4.4 LR 分析器卡死sample.c末尾缺;导致归约链断裂现象./parser_lr读完sample.c最后一个 token 后状态栈停在state 5不再推进程序假死。原因Grammar.txt中statement → expression ;要求每个语句以分号结束。sample.c若写int a 1无分号词法器输出KEYWORD_intIDENTIFIER_aOPERATOR_NUMBER_1LR 分析器在NUMBER_1后尝试归约factor → NUM再归约term → factor但无法归约expression因缺少;触发归约最终卡在等待;的状态。解决sample.c必须是合法 C 子集所有语句以;结尾。或修改Grammar.txt添加statement → expression产生式但会引入冲突。4.5 报告生成失败report.md模板中 MathJax 公式渲染异常现象report.md用 Typora 打开$FIRST(A) \{a, b\}$公式显示为原始 LaTeX 代码。原因Typora 默认关闭 MathJax需手动启用。解决Typora 设置 → Markdown → 数学公式 → 勾选 “Inline math” 和 “Block math”。VS Code 用户需安装 “Markdown Preview Enhanced” 插件并启用mathjax选项。5. 实战技巧用 demo.txt 日志反向调试 LR 分析器状态机5.1demo.txt的真实价值它不是示例而是状态机执行轨迹快照demo.txt看似只是sample.c的运行结果实则是LR.cpp在DEBUG模式下打印的完整状态机轨迹。打开它你会看到类似Step 0: Stack[0], Input[KEYWORD_int, IDENTIFIER_a, OPERATOR_, NUMBER_1, SEMICOLON, ...] Step 1: Shift to state 3, Stack[0,3], Input[IDENTIFIER_a, OPERATOR_, NUMBER_1, SEMICOLON, ...] Step 2: Shift to state 5, Stack[0,3,5], Input[OPERATOR_, NUMBER_1, SEMICOLON, ...] Step 3: Reduce by production 2: factor → ID, Stack[0,3], Input[OPERATOR_, NUMBER_1, SEMICOLON, ...] Step 4: Goto state 7, Stack[0,3,7], Input[OPERATOR_, NUMBER_1, SEMICOLON, ...] ...这不是静态输出而是LR.cpp中debugPrint()函数在每次移进/归约后调用的结果。它的价值在于当你修改Grammar.txt后分析失败不必重跑程序直接对比demo.txt与你的预期轨迹。例如若你新增产生式declaration → char ID ;期望在KEYWORD_char后进入状态 4但demo.txt显示它进了状态 3则说明GOTO表计算有误问题出在buildTables()的closure()函数。5.2 三步法精确定位 LR 表构造错误当LR.cpp运行报错conflict in state X按此流程排查定位冲突状态在buildTables()中cout Conflict in state i endl;加日志运行获知X导出状态项目集修改printItemSet(int i)函数使其输出state X的全部项目如[A→α•β]对照demo.txt验证查看demo.txt中Step N: Stack[..., X]时的Input前几个 token代入项目集判断若存在[A→α•aβ]和[B→γ•]且a在FOLLOW(B)中则是归约-归约冲突。我曾用此法发现Grammar.txt中expression → ε的FOLLOW(expression)错误包含了;应为)和$导致state 10对;既想移进又想归约。修正FOLLOW集后冲突消失。5.3 用test.cpp快速验证词法器边界 casetest.cpp是包里最易被忽略的宝藏。它不分析语法只做一件事穷举所有词法单元类型验证Word_analysis.cpp的健壮性。内容节选// 测试用例关键字、标识符、数字、运算符、分隔符、注释 string cases[] { int, while, return, // 关键字 abc, _123, a_b_c, // 标识符 123, 3.14, 1.23e-4, // 数字 , -, *, /, , , // 运算符 ;, (, ), {, }, [, ], // 分隔符 // comment, /* block comment */ // 注释 };运行./lexer test.cpp输出应严格匹配KEYWORD_int KEYWORD_while KEYWORD_return IDENTIFIER_abc IDENTIFIER__123 IDENTIFIER_a_b_c NUMBER_123 NUMBER_3.14 NUMBER_1.23e-4 OPERATOR_ ...若某项输出为ERROR说明词法器对该类型识别失败。例如若1.23e-4输出ERROR则parseNumber()中科学计数法分支有 bug若/* block comment */未被剔除则skipBlockComment()函数未被调用。这是比sample.c更细粒度的验证手段。5.4 从report.md模板提取可复用的实验报告框架两份report.md不是摆设。LL/report.md的结构可直接用于你的实验报告## 一、文法改写过程 原始文法E → E T | T 消除左递归后 E → T E E → T E | ε ## 二、FIRST/FOLLOW 集计算 - FIRST(E) FIRST(T) {int, (} - FOLLOW(E) FOLLOW(E) {), $} ## 三、预测分析表 | | int | ( | | ) | $ | |------|-----|-----|-----|-----|-----| | E | 1 | 1 | | | | | E | | | 2 | 3 | 3 | ## 四、测试结果 输入 int a 1;输出 token 流正确语法树生成成功。LR/report.md则提供状态图绘制方法用graphviz将buildTables()输出的状态转移关系转为 PNG# 在 buildTables() 末尾添加 ofstream dot(lr_states.dot); dot digraph LR_States {\n; for (int i0; inumStates; i) { dot state i [label\State i \\n getItemSetString(i) \];\n; for (int j0; jnumTerminals; j) { if (actionTable[i][j] 0) { dot state i - state actionTable[i][j] [label\ terminalName[j] /S\];\n; } } } dot };然后dot -Tpng lr_states.dot -o lr_states.png。这张图就是你报告里的核心插图。从那以后我每次改Grammar.txt都强制走一遍test.cpp验证词法、demo.txt对齐状态、report.md更新表格三步流程。省下的调试时间够我多啃两章《Compilers: Principles, Techniques, and Tools》。希望帮到你。本文还有配套的精品资源点击获取
