简介一份编译原理词法分析与语法分析实验报告面向计算机专业本科生及考研复习者用于系统理解编译器前端词法分析、语法分析两大核心阶段。报告从词法分析状态图设计讲起说明如何识别标识符、关键字、十进制整数以及 - * / ( ) ;等运算符和分隔符并给出C实现的scan()函数代码支持、、、:等多字符运算符的判定也包含注释跳过与错误报告处理。语法分析部分围绕E→TE、T→FT等LL(1)文法详细说明FIRST集、FOLLOW集以及预测分析表的构造过程并给出非递归预测分析程序的实现思路以idid*id为例帮助理解。压缩包内为1个Word文档大小约220KB内容包含实验目的、实验步骤、实验原理、程序源代码和实验结论等完整模块可直接参考或对照编写自己的实验报告。已有2570人学习下载对需要完成编译原理实验或准备期末考试的读者具有实用价值。1. 编译原理词法分析与语法分析实验报告这题不只是交代码是在交“证明”编译原理词法分析与语法分析实验报告看起来是课程作业但做下去你就知道它是把《编译原理》教材里正规式、有限自动机、上下文无关文法、LL/LR 分析这四章硬生生串成的一道综合题。很多同学交上去的报告只有代码和一句“运行成功”等老师追问“为什么这个 token 会识别错”“你的文法哪里有冲突”当场翻车。这份报告真正要回答的只有两个问题你凭什么这么设计以及你怎么证明它是对的。适合正在跟编译原理实验课、需要交一份能讲清来龙去脉的本科生也适合带实验想给学生一份可参照范本的助教。下面按词法分析、语法分析、冲突排查、踩坑记录、报告验证的顺序把这条线走完。2. 编译原理实验的第一关词法分析的三种写法和一份可复用的 Flex 规则词法分析实验的核心就是把标识符、关键字、数字、运算符这些 token 的识别规则翻译成代码。常见做法有三条路手写状态机、用正则库硬切、用 Flex 这类生成器把正则编译成 DFA。三条路在实验报告里对分数的影响差别很大因为老师看的不是“能不能跑”而是你有没有把输入字符流映射成 (token 名, 属性值, 行号) 这个标准三元组以及你能不能讲清楚歧义是怎么消解的。2.1 手写状态机适合搞懂原理但不适合撑起整份报告手写状态机的思路很朴素给每个状态编号读一个字符跳一个状态碰到终态就吐出一个 token。核心结构就是一个二维状态转移表加一个循环。#define START 0 #define IN_ID 1 #define IN_NUM 2 int state START; while ((c getchar()) ! EOF) { switch (state) { case START: if (isalpha(c)) state IN_ID; else if (isdigit(c)) state IN_NUM; else if (c || c \n) /* 忽略空白 */; else { /* 生成运算符 token状态回到 START */ } break; case IN_ID: if (!isalnum(c) c ! _) { /* 回退一个字符生成 ID token */ state START; } break; case IN_NUM: if (!isdigit(c)) { /* 回退生成 NUM token */ state START; } break; } }这段逻辑里最容易被忽略的是“回退一个字符”。当你读到标识符后面的空格这个空格已经用掉了如果不把它塞回输入流下一个 token 的开头就丢了。手写方案的好处是状态和转移一清二楚报告里能画出状态图坏处是关键字、注释、字符串这些模式一多状态矩阵膨胀到没人看得懂而且很容易在某个边界字符上翻车。我一般建议状态机代码只作为“原理说明”放在报告前面真正交付的词法器另用一个可控的方案。2.2 用 Flex 把正则编译成 DFA最小可运行模板Flex 的原理是把你写的每条正则先转成 NFA再子集化构造成 DFA最后做等价类最小化。你不需要自己写 Thompson 构造法和子集构造法但要理解它的匹配规则Flex 按“最长匹配优先同长则规则靠前者优先”决定走哪条规则。%{ #include stdio.h #include y.tab.h /* 语法分析器生成的 token 宏 */ int yylval; /* 传给语法分析器的属性值 */ %} %option noyywrap %% [ \t\n] { /* 跳过空白不产生 token */ } if|else|while|return { yylval 0; return IF; } [a-zA-Z_][a-zA-Z0-9_]* { yylval 1; return ID; } [0-9] { yylval atoi(yytext); return NUM; } |!|| { return RELOP; } |-|*|/ { return yytext[0]; } . { fprintf(stderr, lexical error at line %d: %s\n, yylineno, yytext); } %%几个参数要说明白%option noyywrap表示输入流只有一个文件不调用 yywrapyylval是词法分析器与语法分析器之间的信道识别出 NUM 时把整数值放进去语法分析器在$1里取到return IF而不是return yytext[0]是为了让语法分析器拿到一个明确的 token 编号而不是裸字符。关键字规则必须写在标识符规则前面这一点很容易踩坑后面避坑章会单独展开。Flex 生成了 C 文件之后主程序只要不断调用yylex()直到它返回 0就能拿到整个 token 流。2.3 报告必填项token 类型表与 DFA 最小化过程一份能拿高分的词法分析实验报告不能只贴 .l 文件。老师最想看到的是下面这张表把每条正则可接受的字符串集合写清楚token 名模式正规式属性值示例IFif无ifID[a-zA-Z_][a-zA-Z0-9_]*符号表索引count, _tmpNUM[0-9]整数值1024RELOP!运算符编号ADDSUB-无DFA 最小化这一节很多报告直接抄教材结论“划分等价类”没有过程。其实只要写一个三步走先按接受态与非接受态分成两组再对每组按每个输入符号的后继状态是否落在同一组细分重复到分组不再变化。表格比文字好讲比如一个识别a(b|c)*的 DFA最小化前 4 个状态最小化后变 3 个每一轮划分写一行。老师看到这个表就知道你是真的把子集构造法跑过一遍而不是只会敲 flex 命令。2.4 符号表与属性值词法和语法之间的传话人编译原理符号表不是选做题是词法分析实验里最容易问倒人的地方。标识符的 yylval 不能只放 1要放进符号表得到一个索引这个索引在语法分析阶段被用来区分不同的变量名。符号表要紧盯这里变量声明和引用的登记时机不同同一个名字可能在不同作用域出现两次如果符号表设计成一张全局哈希表同名遮蔽关系根本表现不出来。常见做法是用作用域链每进一个新作用域压入一层退出弹出一层查找时从当前层一路往上。词法阶段只负责“首次遇到时登记”谁负责“出作用域时删除”要在报告里写清楚否则会被当成设计缺漏。3. 语法分析的选型关口LL(1) 递归下降还是 LALR(1) 工具链词法分析解决的是“这是什么单词”语法分析解决的是“这些单词按什么结构组织起来”。这一步的选型比写代码更影响报告质量。多数编译原理实验给的是表达式加赋值语句的文法而表达式文法天然带左递归这一条就卡住了 LL(1) 的路线。你需要先把手上的文法归类再决定用哪种分析方法。3.1 先给你的文法定个位LL 还是 LR别混着用LL(1) 要求文法无左递归、无公共左因子判断条件是每个非终结符的候选首符号集合两两不相交LR 类分析SLR(1)、LR(1)、LALR(1)则对左递归和右递归都能处理只要求没有冲突。实验题目里常见的算术表达式文法E - E T | T T - T * F | F F - (E) | num这是典型的左递归文法直接拿到递归下降里会死循环。要么手动消除左递归改成 LL(1) 形式要么换 LR 类分析器。两条路都有人走我帮你把判断条件摆出来维度递归下降LL(1)Bison / YaccLALR(1)文法要求消除左递归、提左公因子无左递归要求但需无冲突实现成本每个非终结符一个函数写文法规则即可生成解析器错误定位好函数名就是出错位置冲突报告需费劲解读工具链纯手写零依赖flex bison 配合适合场景文法小、要讲原理文法略复杂、要快速稳定你要是用 java 编译原理那条路线对应的是 JFlex JavaCC思路完全一样只是生成器换了个名字。3.2 递归下降手写示例一个能跑的表达式解析器消除左递归后的表达式文法长这样E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | num每个非终结符对应一个函数核心代码在 E 和 T 那里因为要处理左结合函数里用 while 而不是 if。/* expr : term ( term)* */ int expr(void) { int left term(); while (lookahead || lookahead -) { int op lookahead; lookahead next_token(); int right term(); left (op ) ? left right : left - right; } return left; }lookahead是全局的当前 tokennext_token()负责推进遇到语法错误时lookahead停在错误位置错误定位非常精确。这里最关键的是循环结构表面上文法写的是右递归形式但因为每次循环先取右操作数算完立即累加到 left实际结合方向是左的。这个细节在报告里值得用一页 PPT 讲清楚。递归下降的缺点也明显如果实验文法里有很多运算符层级函数数量会膨胀每个函数都要自己维护同步集合代码量不小。3.3 用 Bison 声明优先级二义性文法的“后悔药”很多同学的实验文法直接照着教材写成了二义性文法expr - expr expr expr - expr * expr expr - ( expr ) expr - NUM这种文法既左递归又二义性理论上进不了 LL(1)也进不了 LALR(1)。但 Bison 给了你一个后悔药运算符优先级声明。你用 %left 声明同层运算符左结合声明顺序从上到下优先级递增Bison 会据此给冲突的产生式配优先级自动消解 shift/reduce 冲突。%token NUM %left - %left * / %% expr : expr expr { $$ $1 $3; } | expr - expr { $$ $1 - $3; } | expr * expr { $$ $1 * $3; } | expr / expr { $$ $1 / $3; } | ( expr ) { $$ $2; } | NUM { $$ $1; } ; %%$$是左部非终结符的属性值$1、$3是右部符号的属性值语义动作跟在每个候选式后面。这个方案的优点是文法与二进制表达式本身一致不用改写报告里只用解释清楚“为什么乘除的优先级声明写在加减后面”。代价是如果实验文法里出现了相同优先级但结合方向不同的运算符比如赋值语句与比较表达式搅在一起优先级声明也会兜不住还是要回到改写文法这条路。3.4 什么时候上 Parser Generator什么时候手写我自己的判断标准是看实验报告要你“证明什么”。如果实验要求展示语法树的构建过程、错误的定位与恢复机制那适合手写递归下降因为每一步都看得到如果实验要求写一个能处理主流语法子集的小编译器再用递归下降写运算符优先级会写到手指发麻这时上 Bison 是正解。还有第三类实验用了别人的中间代码生成框架只要求你填文法文件那直接用 Bison。选型没有绝对对错报告里写清楚“我选它的三个理由”比选什么更重要。一个反向教训是有人 Flex 生成了 tokenBison 却没声明对应 token 类型结果词法返回的编号对不上文法的期望运行起来全部输入都报 syntax error这种黑匣子问题最浪费时间。4. 语法分析的深水区LR 冲突怎么定位与改写如果你打算用 Bison 或 Yacc 做语法分析这一章几乎必看。写好的 .y 文件编译时蹦出的 conflicts 提示对新手来说像天书但它是实验报告里最能体现你能力的素材。冲突有两种shift/reduce 冲突和 reduce/reduce 冲突。前者是可消解的后者多半是文法设计有重叠必须动手改写。4.1 先看懂 Bison 的冲突报告shift/reduce 不是玄学Bison 编译时加-v会生成一个 .output 文件里面写着每个状态的分析表。冲突报告长这样state 5 stmt - IF expr stmt . (reduce) stmt - IF expr stmt . ELSE stmt (shift) ELSE shift, and go to state 7 ELSE [reduce using rule 4 (stmt)] State 5 contains 1 shift/reduce conflict圆点表示当前分析位置。在圆点后面如果既存在归约的产生式又存在可以移进的后继符号就产生了 shift/reduce 冲突。新手不需要读懂整张表只要抓住三列状态编号、冲突的产生式、冲突符号。课上讲的是“按语法分析表驱动”实验里则是把这个报告当作调试线索。不要凭感觉去改 .y 文件每改一次就跑一次bison -v冲突数从几次减到 0 的过程要记录在实验报告里这个就是你排错能力的证据。4.2 悬空 else 的 shift/reduce 冲突默认 shift 为什么是对的最经典的 shift/reduce 冲突来源就是悬空 else。文法写%token IF ELSE STMT %% stmt : IF expr stmt | IF expr stmt ELSE stmt | STMT ;遇到IF expr stmt . ELSE时分析器可以按第一条产生式简化也可以把 ELSE 移进。如果你是 C 系语言的 if-else正确语义是让 else 匹配最近的 if也就是“继续移进”而 Bison 的默认决策正是 shift 优先。这里不需要改文法保留 Bison 默认行为即可。但报告里要写一句默认 shift 使 else 与最近的 if 结合符合 C 语言语义。如果你做的是 Pascal 那类 else 必须匹配最远 if 的语言才需要改写文法结构。这一条能说清老师就知道你理解了这个冲突的本质而不是碰巧过了。4.3 reduce/reduce 冲突提左公因子改写文法reduce/reduce 冲突比 shift/reduce 严重得多因为它通常意味着文法的同一段输入可以被两种不同的产生式归纳为不同结果。典型例子%% A : id ; B : id ;A和B都以id为右部当分析器读入 id 后不知道该归约成 A 还是 B。解决办法是提左公因子先把公共部分提到一个新的非终结符 C 里再让 A、B 分别指向 C。%% C : id ; A : C ; B : C ;注意这样改后语言本身没变但分析表不再是二义选择。实际实验里更常见的是中途改了文法导致某个非终结符的候选式与另一个候选式出现相同前缀。排查时先看 .output 报告里冲突状态的候选式把相同前缀的产生式提取出来逐条对照找到重叠根因再动手。最忌讳是不看报告在 .y 文件里删一行加一行瞎试试十次不如读一次表。4.4 改了文法记得重跑回归用例冲突清零不代表语法正确。修改文法会连带影响语法树的形状、运算符优先级、甚至 token 的消化速度。我给自己的规矩是每改一次文法强制跑一遍全部测试用例一个都不许跳。测试输入不能只有正确程序要包含缺少分号的、括号不匹配的、运算符写错的观察这些错误输入报告的出错位置是否合理。因为冲突消解过程可能让分析器走了歧义分支正确的程序还算正常错误的程序可能直接死循环或二次崩溃。把“改前冲突数”“改后冲突数”“测试通过率”这张表写进实验报告比任何描述都有说服力。5. 避坑词法边界、符号表与错误恢复的 5 条实战记录这几条不是原理问题是动手跑实验时最容易翻车的细节。我按“现象 → 原因 → 解决”记录每一本文还有配套的精品资源点击获取