编译原理实验：词法状态图到LL(1)预测分析表的C++实现

简介这是一份编译原理课程中词法分析与语法分析实验的完整实验报告面向计算机科学与技术等专业本科生及正在学习编译原理的开发者。报告基于Windows操作系统和Visual C集成环境系统讲解了词法分析阶段如何依据状态图设计scan()函数识别标识符、关键字、十进制整数以及运算符与分隔符语法分析阶段则针对含、*运算的算术表达式文法E→TEE→TE|ε等详细说明FIRST、FOLLOW集合与LL(1)分析表的构造步骤并完成非递归预测分析程序。压缩包内含1个doc文档约220KB正文包含实验目的、实验内容、实验原理、程序源代码、实验步骤及结论并附有状态图和预测分析表代码逻辑清晰、注释完整可直接复制到编译器中测试运行。已有2570人学习下载无论是作为课程实验报告模板还是用于备战编译原理考试或课程设计都具有较好的参考价值。1. 卡住的不是算法是状态图到 C 代码的落地编译原理这门课有两道坎一是词法分析怎么从正规式变成能跑的scan()函数二是 LL(1) 的预测分析表怎么变成栈驱动的匹配程序。这份实验报告把两段都覆盖了——从标识符、十进制整数、运算符的正规式画状态图写出逐字符读入的关键字查表函数再对只含、*的算术表达式文法构造 FIRST/FOLLOW 与预测分析表最后用 C 栈模拟最右推导完成idid*id的语法检查。适合正在肝编译原理实验的本科生也适合想把书上算法落到能调试代码的开发者。下面我把 token 编码、fseek回退、分析表查表几个关键点拆开讲顺带指出这套代码里几处一跑就翻车的细节。2. 词法分析从五个正规式到 scan() 函数2.1 先画状态图再写代码正规式的落地顺序词法分析的本质是有限状态机。实验要求识别五类单词但正规式只有四条标识符、关键字、十进制整数、运算符和分隔符。为什么关键字单列因为关键字也是以字母开头的字母数字串状态机在读到完整单词之前无法区分关键字和普通标识符。常见做法是把它们统一按标识符合法形式识别拿到完整词之后查关键字表这就是lookup(TOKEN)干的事说白了就是一张极简的符号表查询——先查关键字表查不到就当普通标识符处理。于是状态图只需要三个状态初始态、标识符态、整数态。状态 0 读字母进状态 1状态 1 读字母或数字留在状态 1读到其它符号就回退并输出 token数字同理。运算符和分隔符因为都是单字符或双字符直接在switch里处理不单独建状态。这样画出的状态图三张就覆盖全部需求很多同学卡在关键字 if 的状态图箭头怎么画其实不用画查表是更简单的路径。2.2 scan() 主循环逐字符读入、回退与关键字表先看核心代码这是整个词法分析的骨架struct key_word { char *word; int id; }; key_word keyword[] { {if, 1}, {then, 2}, {else, 3}, {while, 4}, {do, 5}, {integer, 16} }; void scan(FILE *ftp) { char temp_char; int i, c; while (!feof(ftp)) { temp_char fgetc(ftp); if (isalpha(temp_char)) { // 字母开头可能是标识符或关键字 TOKEN[0] temp_char; temp_char fgetc(ftp); i 1; while (isalnum(temp_char)) { // 连续读字母/数字构成完整单词 TOKEN[i] temp_char; i; temp_char fgetc(ftp); } TOKEN[i] \0; fseek(ftp, -1, 1); // 多读的那个分隔符回退下次继续用 c lookup(TOKEN); // 查关键字表0 表示普通标识符 if (c 0) out(ID, TOKEN); else out(c, ); } else if (isdigit(temp_char)) { TOKEN[0] temp_char; temp_char fgetc(ftp); i 1; while (isdigit(temp_char)) { // 只收数字遇到字母或运算符就停 TOKEN[i] temp_char; i; temp_char fgetc(ftp); } TOKEN[i] \0; fseek(ftp, -1, 1); // 同样的回退逻辑 out(INT, TOKEN); } } }代码逻辑不复杂isalpha判断首字符进入标识符分支isalnum循环读直到卡在非字母数字边界。此时多读了一个分隔符fseek(ftp, -1, 1)回退一位保证主循环下一次能接着处理这个字符。整数分支结构完全对称。lookup返回 0 则按标识符 ID 输出返回非 0 就是关键字编号。注意两个细节。第一关键字表里的 id 编码是自定义的integer编码 16和前 5 个关键字之间留了间隔这个编码理论上要和后续语法分析的终结符编号对应自己写的时候保持一套编码体系别混。第二fseek第三个参数 1 对应SEEK_CUR意思是相对当前文件位置回退 1 字节在 Windows VC6 下能跑但换个平台最好用ungetc代替原因后面避坑章细说。2.3 运算符与分隔符双字符符号和注释处理运算符部分最有意思的是对、:、/的处理因为它们可能构成双字符符号switch (temp_char) { case : temp_char fgetc(ftp); if (temp_char ) out(LE, ); else if (temp_char ) out(NE, ); else { fseek(ftp, -1, 1); out(LT, ); } break; case :: temp_char fgetc(ftp); if (temp_char ) out(FZ, ); else { fseek(ftp, -1, 1); report_error(temp_char); } break; case /: temp_char fgetc(ftp); if (temp_char /) { do { temp_char fgetc(ftp); } while (temp_char ! \n); graphnum; // 统计行数 } else { fseek(ftp, -1, 1); out(DEV, ); } break; }处理套路是一致的单字符运算符直接输出可能双字符的先读第二个字符再决定//注释直接吞到换行符为止。这里有三个容易忽略的点。一是每个else分支都要fseek回退否则当前字符会被丢掉二是注释分支不加回退因为换行符被消耗是故意的同时graphnum做了行数统计三是实验要求里其实没有//注释和:赋值符但代码里都处理了说明实现时做了功能延伸交作业保留即可。报告里out函数的第二参数传空格是因为 token 类型已经编码进第一参数词法分析阶段的输出是一个二元组token 类型属性值。这个设计虽然粗糙但足够让语法分析阶段拿 token 类型做匹配。3. 语法分析LL(1) 的 FIRST/FOLLOW 与分析表构造3.1 为什么必须先消左递归实验给出的文法E → TE′、E′ → TE′|ε是改造后的形式。大家最初熟悉的是E → ET | T这种文法叫左递归文法直接用于 LL(1) 时最左推导会无限循环——每次想推导 E第一个符号又是 E。所以必须先把左递归消掉变成E → TE′再用T → FT′、T′ → *FT′|ε处理乘法和因子。LL(1) 里的1表示每次决策只看当前栈顶非终结符和输入串头一个终结符产生式右部的第一个符号必须能唯一决定下一步。如果文法带左递归这个唯一性就保证不了。这个前置条件不做后面分析表填出来也是错的。很多同学拿着文法直接填表填到M[E, i]时发现有两个产生式都匹配就是因为没消左递归。3.2 手工算 FIRST 和 FOLLOW别跳过这一步FIRST(α) 是 α 能推导出的第一个终结符集合FOLLOW(A) 是可能紧跟 A 之后的终结符集合。这两个集合直接决定分析表格子填什么。计算步骤归纳如下先算 FIRST。对每个非终结符看产生式右部首符号终结符直接入集非终结符递归展开能推出空串就把 ε 也放进去。再算 FOLLOW。开始符号的 FOLLOW 先放#输入结束符对形如A → αBβ的产生式把 FIRST(β) 中除 ε 的元素并入 FOLLOW(B)若 β 可以推出 ε把 FOLLOW(A) 并入 FOLLOW(B)。我给这组文法手算过一次结果如下非终结符FIRSTFOLLOWE{id, (}{), #}E′{, ε}{), #}T{id, (}{, ), #}T′{*, ε}{, ), #}F{id, (}{*, , ), #}这里有一个高频易错点FOLLOW 集合里永远不会出现 ε因为 FOLLOW 描述的是紧跟在这个非终结符后面的终结符不可能是空。还有代码里 id 统一记作i输入结束符记作#分析表里出现的$实际代表 ε这三套符号别混。3.3 预测分析表一个格子一个产生式构造规则在报告里写得很清楚三条对产生式A → α对 FIRST(α) 中的每个终结符 a把A → α填入M[A, a]。如果 ε 在 FIRST(α) 中对 FOLLOW(A) 中的每个终结符 b把A → α填入M[A, b]。如果 ε 在 FIRST(α) 中且#在 FOLLOW(A) 中把A → α填入M[A, #]。剩下的格子全部置 error。按这个规则填出来的表长这样只列非空项非终结符id*()#EE→TE′E→TE′E′E′→TE′E′→εE′→εTT→FT′T→FT′T′T′→εT′→*FT′T′→εT′→εFF→idF→(E)这张表就是后面查表程序的全部数据来源。验证方法很简单拿idid*id从头推导一遍每个非终结符扩展时看一眼当前输入符号对应表格哪一列能完整走到#结束就说明表没填错。这一步千万不要省后面程序跑不出来九成是表填错了而不是代码写错了。4. 非递归预测分析程序栈驱动的表驱动实现4.1 栈结构用尾插尾出的链表模拟分析栈LL(1) 的预测分析程序核心是一个分析栈初始状态栈底是#栈顶是开始符号E。分析过程循环做三件事看栈顶符号 X看输入串当前符号 a查分析表M[X, a]。如果 X 是终结符和 a 比较相等就消费输入如果 X 是非终结符用表项里的产生式右部替换 X如果表项是 ε直接弹栈不压入。原代码用链表实现栈Stack_Push尾插、Stack_Pop尾出等价于栈顶在链表尾部。教学版可以写成这样typedef struct node { char ch; struct node *next; } Node, *Stack; Stack initStack() { Stack s (Stack)malloc(sizeof(Node)); s-next NULL; return s; } void push(Stack s, char ch) { Node *tail s; while (tail-next) tail tail-next; // 走到尾节点 Node *n (Node*)malloc(sizeof(Node)); n-ch ch; n-next NULL; tail-next n; // 尾插新节点成为栈顶 } char pop(Stack s) { if (s-next NULL) { /* 报错栈空 */ } Node *pre s, *cur s-next; while (cur-next) { // 找到倒数第二个节点 pre cur; cur cur-next; } char ch cur-ch; pre-next NULL; free(cur); return ch; }逻辑说明initStack创建头节点头节点不存数据push每次遍历到链表尾部再挂新节点保证新压入的元素在栈顶pop找到倒数第二个节点把尾节点解下来返回。这套组合的语义和数组栈相反——数组栈是头插头出链表栈是尾插尾出但效果一致。参数说明push的ch是单个字符可能是一个终结符也可能是非终结符的代号。原代码把E′存成A、T′存成B就是为了让每个符号只占一个char。这个映射在调试时特别容易看懵建议在文件开头写一行注释/* EA, TB */。还有链表实现的push每次都要 O(n) 找尾部实验规模无所谓但你要是想做成通用组件直接换成固定大小数组栈更省心。4.2 查表GetMatrixValue 的字符串匹配char *GetMatrixValue(char NT, char TE) { char nt[2], te[2]; nt[0] NT; nt[1] \0; te[0] TE; te[1] \0; for (int i 0; i MAXSYMBOL; i) { if (strcmp(nt, analysisTable[i][0]) 0 // 匹配行非终结符 strcmp(te, analysisTable[i][1]) 0 // 匹配列终结符 analysisTable[i][2][0] ! \0) { // 跳过空产生式 return analysisTable[i][2]; // 返回产生式右部 } } return ; // 表项为空上报 error }这个函数做的事就是查M[X, a]。逻辑说明analysisTable是一个 30 行 3 列的二维数组30 正好是 5 个非终结符乘 6 个终结符的笛卡尔积每行存{非终结符, 终结符, 产生式右部}。GetMatrixValue逐行扫行列都匹配且右部非空就返回右部字符串。把单个字符先转成带\0的字符串再strcmp效率不高但好处是调试时能把表项直接打印出来。参数说明NT是非终结符代号TE是当前输入符号。返回值有四种情况产生式右部字符串、error、$实际上代表 ε需要调用方特判。原代码里$和是两套约定前者要跳过不压栈后者要报错返回 false这个区分是整个查表程序的命门。4.3 主循环IsCorrectSentence 与完整匹配过程bool IsCorrectSentence(char str[]) { int pos 0; char X; char *pro; Stack s initStack(); push(s, #); // 输入结束标志 push(s, E); // 开始符号 while (true) { X pop(s); if (是终结符(X)) { if (X str[pos]) pos; // 匹配则消费输入 else return false; } else if (X #) { return X str[pos]; // 栈底与输入串尾对齐才算成功 } else if ((pro GetMatrixValue(X, str[pos])) ! ) { if (pro 是 ε) continue; // ε 产生式弹栈即可 for (int j strlen(pro) - 1; j 0; j--) push(s, pro[j]); // 逆序压栈右部第一个符号在栈顶 } else { return false; // 查表失败语法错误 } } }主循环的流程就是前面说的三步。关键在压栈顺序产生式右部TE′要保证T先被弹出所以必须先压E′再压T代码里从strlen(pro)-1往前遍历正好实现这一点。拿idid*id走一遍完整推导。为了和代码对应输入串记作ii*i结束符#额外追加初始栈# E输入i i * i #。查M[E, i]得E→TE′压栈后栈内容# E′ T栈顶T。查M[T, i]得T→FT′压栈后栈内容# E′ T′ F栈顶F。查M[F, i]得F→i压栈后栈顶就是i和输入i匹配消费。此时栈内容# E′ T′输入 i * i #。查M[T′, ]得T′→ε弹栈不压栈内容# E′。查M[E′, ]得E′→TE′压栈后栈顶匹配输入消费。之后T展开匹配iT′遇到*用T′→*FT′最后栈内容回到# E′输入只剩#查M[E′, #]得E′→ε弹栈栈顶#与输入#对齐accept。这一套走完整个 LL(1) 的闭环就通了。代码里把E′写成A、T′写成B你在对照上表追踪时记住这个映射就行。5. 避坑五处容易翻车的地方5.1 fseek 回退在文件末尾会出诡异问题现象输入文件最后一行是数字或标识符没有结尾换行符程序跑完输出正常但再跑一次就死循环或丢字符。原因fgetc读到文件末尾返回EOF即 -1但feof(ftp)在循环顶部判断意味着最后一次fgetc已经返回 -1 后循环体还会执行一次。标识符分支里fseek(ftp, -1, 1)回退 1 字节如果fgetc已经越过了文件末尾回退位置不确定。解决不用feof做循环条件改成先读后判断或者把fseek(ftp, -1, 1)换成ungetc(temp_char, ftp)。ungetc把读出的字符塞回流语义上就是多读一位再还回去比手工算文件偏移量安全得多。5.2 分析表里 E′ 写成 A、T′ 写成 B对照文法时全懵现象对着报告里的文法E′→TE′去查代码里的analysisTable发现整张表没有一行写E′只有一堆A和B手算的 FIRST/FOLLOW 完全对不上。原因为了用单个char表示非终结符代码把带撇号的E′、T′映射成了A、B。实验报告里没写这层映射直接看代码就产生黑匣子效应。解决在代码文件头写注释说明映射关系或者自己重构时直接用字符串E存非终结符名把表结构从char*[30][3]改成结构体数组可读性立刻上一个台阶。5.3 GetMatrixValue 用 strcmp 比较单字符初始化不全就崩现象照着代码抄到自己工程里运行到某个特定输入符号时查表失败返回空串导致误报语法错误。原因analysisTable如果用char *analysisTable[MAXSYMBOL][3]声明只有部分行被初始化未初始化的行是野指针。原报告里所有 30 行都手工填满了字符串所以没炸但你精简表结构时很容易漏行。解决全部表项用const char*统一初始化空项显式写成不要依赖默认值。或者把表从指针数组改成char analysisTable[30][3][8]这种二维定长数组内存布局确定strcmp不会读到越界数据。5.4 ε 用$表示、结束符用#表示两个特殊字符混用现象调试时在IsCorrectSentence里看到$不压栈以为遇到输入结束直接 return结果该匹配的id没消费整个分析提前结束。原因原代码把$当作 ε 的记号#才是输入结束标志。两个都是特殊符号语义完全不同但肉眼看起来就是两个普通字符很容易把判断条件写混。解决在代码里定义两个宏#define EPSILON $和#define END_MARK #所有比较都用宏名。改完之后代码读起来就是如果产生式是 EPSILON 就不压栈不会再把两者搞混。5.5 词法输出没有行号多行输入出错时没法定位现象输入 20 行代码语法分析报错在第 19 行但词法分析输出的 token 列表没有行号根本不知道是哪个单词触发的错误。原因实验要求只输出 token 序列out函数没有设计行列信息。这个在单行表达式上没影响一旦换真实代码就非常痛苦。解决给out函数加一个全局行号参数scan里遇到\n时行号自增输出格式改成行号: token类型 token值。这个改动很小但排错体验会好非常多。6. 从这份实验到你的工具验证技巧与两个实用重构6.1 用一个用例验证分析表没填错分析表是不是填错了靠肉眼扫很难发现最笨但最有效的验证方式是手工追踪一个用例。把idid*id的过程做成一张表每一步记录栈内容、输入位置、查表结果和动作步骤栈内容栈底→栈顶输入串查表结果动作1# Eidid*id#M[E,id]E→TE′弹 E压 E′T2# E′ Tidid*id#M[T,id]T→FT′弹 T压 T′F3# E′ T′ Fidid*id#M[F,id]F→id弹 F压 id4# E′ T′id*id#M[T′,]T′→ε弹 T′5# E′id*id#M[E′,]E′→TE′弹 E′压 E′T6………继续到 # 对齐表格不要求写满每一步重点是前五步能确认查表逻辑和压栈顺序对不对。我从第一次实验得到的教训是分析表一定要先手工推完整推导再写代码。代码跑出来结果不对九成是表的问题表和代码同时出错的概率非常低。6.2 两个能立刻受益的重构第一个重构是把analysisTable从二维数组改成结构体数组。原来的 30 行字符串在查表时要逐行strcmp改成下标索引后查找时间是 O(1)代码也更接近教科书上的定义typedef struct { char nonTerminal; // 非终结符代号 char terminal; // 终结符 char *production; // 产生式右部 表示 errorEPSILON 表示 ε } Production; Production table[5][6]; // 按 非终结符×终结符 索引 // 初始化示例 table[E][ID] {E, id, TE}; table[E][LPAREN] {E, (, TE};第二个重构是给词法分析的out函数加行号。原报告里graphnum已经在统计行数了但out没把它带出来。接上之后语法分析报错时能直接定位到源文件第几行调试成本直线下降。从那以后我每次做和编译相关的实验都强制自己先画状态图、手算一遍 FIRST/FOLLOW、再把生成的分析表对着一个用例模拟完整推导三步走完基本就不翻车了。这份实验报告也是这么一套完整链路按这个顺序复现能少走不少弯路希望帮到你。本文还有配套的精品资源点击获取