简介面向编译原理课程设计与实验场景这份资源聚焦TINY语言词法分析器的手工构造适合正在学习编译器前端、需要完成类似实验的本专科生及自学者。内容围绕C/C实现展开涵盖TINY词法规则识别、Token类型定义、确定有限状态自动机DFA设计与状态转移逻辑帮助读者从零搭建可运行的分析程序。压缩包共10个文件核心是C源代码、Dev-C工程文件与实验报告另有TINY测试样例、可执行文件等辅助材料整体仅779KB便于快速下载与本地验证。目前已有1330人学习下载。通过源码阅读与报告对照可以掌握词法分析器的模块划分、数据结构如枚举标记类型、结构体存储Token信息及排错思路同时体会DFA在真实编译器中的应用适合作为课程设计参考、期末复习或入门编译原理的动手实践。1. 手工构造TINY词法分析器这个课设到底要你交付什么期末周的编译原理实验里手工构造TINY语言的词法分析器几乎是点名率最高的题目。你从课程平台下载的那个zip里通常是一份源码骨架、几个测试样例和一份实验报告模板真正要交付的核心只有一件事把TINY源码逐字符读进来按词法规则切成带行号、带类型的Token流。TINY是为教学裁剪出来的语言没有数组、没有浮点、没有字符串字面量Token类型两只手数得过来所以手工构造完全可行。它也是理解编译器前端第一站的最小样本——很多同学第一次体会“把黑匣子打开自己造一个”就是从这个题目开始的。下面按“先定规则、再写扫描器、最后做驱动和测试”的顺序把从解压到跑通的完整路径讲清楚适合正在做这门课设、以及想补编译器前端基础的人照着做。2. 先把TINY词法规则拆成三张表字符集、Token类型与判定顺序拿到题目别急着写代码。词法分析器本质上是把“字符流”变成“Token流”的转换器你心里没有一张准确的词法规则表写出来的扫描器一定漏Token、错分Token。TINY不是标准语言每个学校的实验指导书对特殊符号的定义都可能微调所以第一步是把手边能确认的规则固定下来而不是抄网上的正则。2.1 TINY语言的字符集与Token种类比C语言少了什么TINY的字符集很小大小写字母、十进制数字、空白字符以及一组特殊符号。它没有字符串字面量没有浮点数注释用花括号包裹注释内容不产生任何Token。下表是经典TINY的Token种类清单请对着你自己的实验指导书核对一遍再动手。Token 类型词法形式说明标识符letter (letter | digit)*变量名如 n、fact数字digit只支持十进制整数保留字if then else end repeat until read write同样是字母串但优先识别特殊符号 - * / ( ) ; :: 是赋值 是相等比较文件结束EOF不是文件里的字符是合成Token和C语言对比TINY少了字符串、数组、位运算、自增自减、比较符和!唯一的双字符特殊符号是:。这意味着词法分析器在特殊符号分支里只有一个“需要预读一位”的场景复杂度被压得很低。也正因为它足够小手工构造才比用Lex/Flex更划算为了一棵小树去架一套生成工具反而把实验重点从“理解词法规则”变成了“学会调用工具”。这里有个常见的认知误区把保留字当成独立的Token类型。我自己的习惯是保留字用专门的类型但很多课设代码把所有字母串都先当标识符扫描出来再查保留字表决定是否改类型。这两种做法结果一样区别只在代码组织。还有一点要提前确认你的实验要求里是否支持、这类扩展符号。经典TINY不支持但不少指导书会加进去这个决定影响符号表的条目数量和switch分支个数一定要在写代码前定死不要边写边猜。2.2 保留字、特殊符号与标识符的判定顺序最长匹配与预读词法规则本质上是一组正则表达式标识符是letter(letter|digit)*数字是digit特殊符号是显式枚举。手工词法分析器做的事情可以理解成一个确定有限自动机的状态转移初始状态读到一个字母就进入“标识符状态”读到一个数字就进入“数字状态”读到特殊符号就进入对应符号分支。直接扫描的写法不会真的定义一张状态转移表而是把这些状态藏在分支判断里。判定顺序比分支本身更重要。我的扫描循环是这样组织的跳过空白和花括号注释遇到换行时行号加一看当前位置的字符属于哪一类字母、数字、符号、其他字母开头就连续吸收字母和数字直到遇到既非字母也非数字的字符才停停下来的那个字符不能丢它就是下一个Token的开头数字开头就连续吸收数字直到遇到非数字才停同样不能把这个字符丢掉符号分支里先判断是不是双字符:是则一次吸收两个字符否则只吸收一个。第3步和第4步里“停下来但不要越过”的做法在编译原理里叫最长匹配。为什么一定要最长匹配因为标识符fact1不能拆成fact和1数字123不能拆成12和3词法层必须一次吃掉最长的合法串。实现上不需要真正把字符“退回”输入流只要控制好游标位置让循环结束时游标停在下一个待处理字符上即可。保留字的处理顺序是“先按标识符吸收再查表改类型”而不是“先判断是不是保留字再决定吸收到哪里”。因为ifx是完全合法的标识符如果先在字符层试探if就会把ifx错误地切成if和x。正确逻辑是吸收整个字母数字串得到word之后查保留字表表里有它就是保留字没有它就是标识符。这个顺序反了是新手第一批翻车点。双字符:的预读也属于判定顺序的一部分。读到:时不能立即输出必须看下一个字符是不是。这里有个边界如果:是源码的最后一个字符预读就会越过字符串末尾。所以预读前必须先判断pos1 src.length()否则会抛越界异常。这个问题我在第5章会作为踩坑单列出来。三张表定下来之后词法分析器的骨架其实已经出来了一张Token类型表、一张保留字表、一张特殊符号表。后面的代码只是把这三张表按顺序翻译成扫描逻辑。3. 用Java手工实现词法扫描核心代码与符号表设计规则定完就进入编码。这一章给出一个最小可跑的Java实现包含Token定义、Lexer扫描循环、符号表三部分。代码是可以直接抄进Eclipse或IDEA跑起来的但更重要的是看懂每个游标和边界检查在防什么。3.1 状态机还是直接扫描为什么选Java做手工实现写词法分析器有两条路显式状态机和直接扫描。显式状态机需要先定义状态枚举再维护一张“当前状态×输入字符→下一状态”的转移表优点是逻辑和状态完全分离适合自动生成器缺点是Token一多转移表变成一张巨大的黑匣子出问题时很难人工排查。直接扫描则是手工构造的首选每遇到一类字符走一个分支状态变化摊在代码结构上代码量小、断点好打、第几行出错一眼就能看出。给编译原理实验做课设我一般选直接扫描。用Java而不是C主要是为了省掉样板代码。Java的Character.isLetter()和Character.isDigit()可以直接做字符分类HashMap用来存保留字StringBuilder拼单词如果用C光是字符分类判断和字符串比较就要多写几十行实验的核心反而被淹没了。这也是搜索“java编译原理”时课设代码特别多的原因——Java的处理字符串能力让词法层代码更接近“读起来像规则”的状态。如果实验平台只接受C思路完全一样把下面代码里的字符分类函数换成手写的ASCII范围判断即可。如果实验报告要求画状态图也不用改代码。在报告里按start、in_id、in_num、done几个状态画一个状态转移图再把“吸收字母数字串”和“预读:”画成自环和条件转移跟上面的直接扫描代码并不冲突。状态图是给评审看设计的直接扫描是给自己省事的两者讲的是同一套规则。3.2 核心扫描循环代码Token定义与Lexer主循环先定义Token类型。我用常量编号而不是枚举因为实验报告里通常要求“Token种类表”常量编号可以一一对应表格行号打印时也直观。// TokenType.java public class TokenType { public static final int ID 1; // 标识符 public static final int NUM 2; // 数字常量 public static final int KW 3; // 保留字 public static final int PLUS 4; // public static final int MINUS 5; // - public static final int TIMES 6; // * public static final int OVER 7; // / public static final int ASSIGN 8; // : public static final int EQ 9; // public static final int LT 10; // public static final int LPAREN 11; // ( public static final int RPAREN 12; // ) public static final int SEMI 13; // ; public static final int EOFTOK 14; // 文件结束 }这里把文件结束Token也作为一种类型原因后面会讲。如果你用枚举就把枚举常量一一映射到表格里的编号效果相同。Token对象携带三样信息类型、原文、行号。行号是词法分析器的基本素养没有行号的Token流在语法分析报错时完全无法定位。// Token.java public class Token { public int type; // TokenType里的编号 public String text; // 原始字符串 public int line; // 所在行号 public Token(int type, String text, int line) { this.type type; this.text text; this.line line; } Override public String toString() { return line line : type type text text ; } }然后是核心的Lexer。下面这个nextToken()方法每调用一次返回一个Token它的结构就是2.2节判定顺序的直译// Lexer.java import java.util.HashMap; import java.util.Map; public class Lexer { private String src; // 整个源码字符串 private int pos 0; // 当前游标位置 private int line 1; // 当前行号 private MapString, Integer reserved new HashMap(); private SymbolTable symbols new SymbolTable(); // 符号表3.3节会讲 public Lexer(String src) { this.src src; // 保留字表单词本身 - TokenType.KW String[] words {if, then, else, end, repeat, until, read, write}; for (String w : words) { reserved.put(w, TokenType.KW); } } // 跳过空白和 { } 注释换行时更新行号 private void skipWhitespaceAndComments() { while (pos src.length()) { char c src.charAt(pos); if (c \n) { line; // 只有换行才加行号 pos; } else if (Character.isWhitespace(c)) { pos; // 空格、制表符直接跳过 } else if (c {) { pos; // 注释一直读到右花括号未闭合时自然走到文件末尾 while (pos src.length() src.charAt(pos) ! }) { if (src.charAt(pos) \n) line; pos; } if (pos src.length()) pos; // 吃掉右花括号 } else { break; // 遇到有效字符跳出循环开始分析 } } } // 读一个Token遇到文件结尾返回EOFTOK public Token nextToken() { skipWhitespaceAndComments(); if (pos src.length()) { return new Token(TokenType.EOFTOK, EOF, line); } char c src.charAt(pos); // 标识符或保留字letter (letter | digit)* if (Character.isLetter(c)) { StringBuilder sb new StringBuilder(); while (pos src.length() Character.isLetterOrDigit(src.charAt(pos))) { sb.append(src.charAt(pos)); pos; } String word sb.toString(); int type reserved.getOrDefault(word, TokenType.ID); if (type TokenType.ID) { symbols.add(word, line); // 首次出现登记符号表 } return new Token(type, word, line); } // 数字digit if (Character.isDigit(c)) { StringBuilder sb new StringBuilder(); while (pos src.length() Character.isDigit(src.charAt(pos))) { sb.append(src.charAt(pos)); pos; } return new Token(TokenType.NUM, sb.toString(), line); } // 特殊符号只有一个双字符 : 需要预读 switch (c) { case : pos; return new Token(TokenType.PLUS, , line); case -: pos; return new Token(TokenType.MINUS, -, line); case *: pos; return new Token(TokenType.TIMES, *, line); case /: pos; return new Token(TokenType.OVER, /, line); case (: pos; return new Token(TokenType.LPAREN, (, line); case ): pos; return new Token(TokenType.RPAREN, ), line); case ;: pos; return new Token(TokenType.SEMI, ;, line); case : pos; return new Token(TokenType.EQ, , line); case : pos; return new Token(TokenType.LT, , line); case :: // 预读下一个字符决定是 : 还是非法冒号 if (pos 1 src.length() src.charAt(pos 1) ) { pos 2; return new Token(TokenType.ASSIGN, :, line); } System.err.println(line line : 非法字符 :); pos; return nextToken(); // 错误恢复跳过非法字符继续 default: // 未知字符统一报错并跳过核心是pos必须前进 System.err.println(line line : 非法字符 c ); pos; return nextToken(); } } }这段代码有几个设计要点。第一pos游标只前进不后退双字符:靠“预读pos1”来识别不需要实现真正的字符回溯缓冲区预读前先检查pos1 src.length()防止:在文件末尾时越界。第二标识符循环里的条件是isLetterOrDigit数字循环里是isDigit这两个条件不能混用一旦数字分支也接受字母123abc就会被识别成一个非法的数字串这是5.1节会展开的坑。第三错误恢复直接用return nextToken()递归非法字符多时可能会把栈打深我给出的方案是课设里最简的写法如果测试文件里故意放几千个非法字符建议改成第5.4节的大循环版本。关于游标和行号skipWhitespaceAndComments()在每次nextToken()开头调用所以空白和注释永远不会到达扫描主逻辑。换行只在字符是\n时加行号如果你处理Windows下的\r\n\r会被当成普通空白跳过行号仍只由\n驱动这一点在跨平台测试时要留意。3.3 符号表与错误恢复两个必写的辅助结构很多课设只要求输出Token流但实验报告里会问“符号表如何组织”。符号表不是保留字表它的本职工作是记录用户自定义标识符的首次出现位置方便后续语义分析查重和类型登记。用HashMap就可以// SymbolTable.java import java.util.HashMap; import java.util.Map; public class SymbolTable { private MapString, Integer table new HashMap(); // 首次登记返回true重复出现返回false public boolean add(String name, int line) { if (table.containsKey(name)) { return false; } table.put(name, line); return true; } public int getLine(String name) { return table.getOrDefault(name, -1); } }add()的调用时机在Lexer的标识符分支里见3.2节代码中的symbols.add(word, line)。这样每个标识符第一次出现时被记入符号表后续重复出现只查不改。如果你希望报告里能输出“标识符出现的所有行号”把MapString, Integer改成MapString, ListInteger即可add()里改成追加行号逻辑量不大。错误恢复策略要在写代码前决定常见做法有两种。第一种是报错后跳过非法字符继续扫描适合课设验收“要求指出所有词法错误”的场景但要注意pos必须前进否则会死循环。第二种是遇到第一个错误就停止只要在nextToken()的错误分支里返回null或抛出异常并在主循环检测即可代码更简单。我一般推荐第一种因为编译器的真实行为也是“尽量恢复一次报出多个错误”而且课堂演示效果更好。提示位置信息只记到行号语法分析报错时只能说“第几行附近”定位不够精确。建议在Lexer里再加一个int col字段遇到换行置为0其余情况每消费一个字符加一多字符Token返回时列号要加上text.length()而不是加一。这个字段加进Token对象里后面调试语法分析器能省一半力气。4. 用驱动与测试把词法分析器打疼最小主程序与边界用例词法分析器的本体写完还差一个入口和一个能证明它没毛病的测试方案。很多课设代码跑一个写死的字符串就交差一旦换文件、换编码、换换行符立刻露馅。这一章把驱动主程序和测试用例补齐让词法分析器面对真正的源码文件能撑住。4.1 最小驱动主程序从文件读源码并打印Token流驱动只需要做三件事读文件、循环调nextToken()、打印Token直到EOFTOK。我把输出里带了行号和类型编号后面写语法分析器时这串输出就是调试依据。// Main.java import java.nio.charset.StandardCharsets; import java.nio.file.Files; import java.nio.file.Paths; public class Main { public static void main(String[] args) throws Exception { if (args.length 1) { System.err.println(用法: java Main 源文件路径); return; } // 按UTF-8读取源码避免中文环境下默认编码不一致 String src new String(Files.readAllBytes(Paths.get(args[0])), StandardCharsets.UTF_8); Lexer lexer new Lexer(src); Token t; int tokenCount 0; while ((t lexer.nextToken()).type ! TokenType.EOFTOK) { System.out.println(t); tokenCount; } System.out.println(词法分析完成共输出 tokenCount 个Token不含EOF); } }编译和运行的命令很直接javac Main.java Lexer.java Token.java TokenType.java SymbolTable.java java Main test.tinyargs[0]是源码文件路径相对路径直接写文件名即可。如果你不想每次敲命令行参数也可以在main里把args[0]换成一个硬编码文件名但那样换测试文件时要改代码重新编译不推荐。读取时显式指定StandardCharsets.UTF_8这样源码文件只要存成UTF-8编码在Linux和Windows上行为就一致如果省略这个参数new String(bytes)会按平台默认编码解析中文Windows下的GBK环境很容易读出一堆乱码。这里有一个命令行的经典坑如果只编译Main.javajavac会自动去查找Lexer.java等依赖文件绝大多数情况下能编过但手动指定全部文件更稳避免“找不到符号”这类因为没编最新改动而出现的怪问题。运行时报“找不到或无法加载主类”时先看当前目录里有没有.class文件多半是编译阶段就失败了不是运行配置的问题。文件读取用Files.readAllBytes()一次性读入适合TINY这种小文件如果换成一个几十MB的测试文件应该用Reader配合字符缓冲流每个字符处理完再读下一个。不过课设规模用不着那么重一次读入反而让pos游标逻辑更简单。4.2 测试用例设计合法、非法、边界三类样本驱动写好后真正的考验在测试样本。我习惯按三类准备测试文件完全合法的样例、含词法错误的样例、专门戳边界的样例。下面这个文件覆盖了TINY的大部分Token类型可以直接存成test.tiny运行{ 计算阶乘的示例 } read n; fact : 1; if n 1 then repeat fact : fact * n; n : n - 1 until n 1 end; write fact注意这个符号在经典TINY里并不存在如果你的指导书要求支持在TokenType.java中加一个GT常量在Lexer的switch里补一个分支case : pos; return new Token(TokenType.GT, , line);这只是加一个case的事正好说明词法分析器的可扩展性规则表加一行扫描逻辑加一个分支。边界用例的价值超过想象我一般用下面这些样本做回归样本内容期望结果它在测什么空文件直接输出EOFTOK跳过空白后游标越界判断只有空格和换行只输出EOFTOK空白的整体跳过{注释}read n只识别read、n注释不产生Token123abcNUM(123) 然后 ID(abc)数字和标识符相邻时的边界a:1ID(a) ASSIGN(:) NUM(1)双字符预读a : 1报错并跳过:随后识别出EQ单冒号非法且错误恢复表格里a : 1这一行特别容易翻车:后面跟的是空格而不是按2.2节的预读逻辑它不会误判成:而是报非法字符并跳过随后把识别成EQ。如果你的实现把“预读下一个字符不是”当成普通冒号Token输出就违反了TINY词法规则验收时会被问住。还有三个位置需要单独测试注释不闭合、文件以:结尾、连续多个非法字符。注释不闭合时skipWhitespaceAndComments()里的内层while会在pos src.length()条件失效后正常退出整个文件被当成注释吞掉行为是安全的但如果你忘了边界条件会直接抛StringIndexOutOfBoundsException。文件以:结尾时预读条件pos 1 src.length()为假代码走非法字符分支pos后安全退出。连续几百个符号则考验错误恢复的写法递归版的nextToken()在极端情况下会爆栈见5.4节。注意词法分析器只负责切Token不做语法合法性判断。比如if read n这类序列在词法层是合法的KW、KW、ID要到语法分析器才会报错。如果测试时看到这类输出就怀疑自己写错了先想清楚这层边界。5. 手工构造中的典型踩坑五个现象与对应修复下面是手工构造词法分析器最常遇到的五个问题按“现象→原因→解决”记录。这些坑我基本都踩过一遍对照你的代码逐个排查能省很多调试时间。5.1 数字后紧跟字母被整体识别成一个Token现象输入123abc输出NUM(123abc)或者直接报“非法字符”。原因数字分支的循环条件误用了Character.isLetterOrDigit()。这个函数同时接受字母和数字导致数字串把后续字母也吸收干净破坏了词法规则中“数字digit”的定义。解决数字循环里只用Character.isDigit()判断字母只能由标识符分支吸收。把3.2节代码里数字分支的while条件改回来即可。顺手再用123abc单独跑一遍确认输出是NUM(123)加ID(abc)两个Token。5.2 注释不闭合导致越界异常现象源码文件里只有{没有}运行时抛StringIndexOutOfBoundsException。原因跳过注释的while循环只判断了src.charAt(pos) ! }忘了在条件里写pos src.length()。游标走到字符串末尾后还继续取字符自然越界。解决所有内层扫描循环都要在条件最前面加pos src.length()注释、数字、标识符三个循环一个都不能漏。3.2节里的写法是标准姿势先问游标合法再取字符判断。把这个边界检查写成肌肉记忆词法层很多崩溃都能从根源上挡住。5.3:只识别出冒号赋值号变成非法字符现象输入a:1输出ID(a)、报“非法字符:”、输出EQ等赋值号没出现。原因特殊符号分支里把:当成单字符处理读到一个冒号就pos并返回没有预读下一个字符。还有一种变体写了预读但没判断pos1是否越界文件末尾的:直接把程序炸掉。解决无论哪种情况都按2.2节的预读方案走先确认pos1还没越界再判断下一个字符是不是是则pos 2否则按非法字符处理。写完后用a:1和a: 1两个样本分别测试前者应产出ASSIGN后者应报非法冒号且程序不崩溃。5.4 错误恢复用递归导致栈溢出现象测试文件里有连续大量非法字符比如几百个运行时抛StackOverflowError。原因nextToken()在错误分支里用return nextToken()实现“跳过非法字符继续”本质上是一次递归调用。非法字符少时没问题量一大就把调用栈打穿。解决把错误恢复从递归改成循环。常见做法是把整个扫描主逻辑包进while(true)非法字符分支用continue跳过并回到循环开头也可以保留递归版本但在外层main里用循环驱动让每次非法字符都从主循环重新进nextToken()。我倾向第一种因为它把游标前进和错误恢复放在同一个方法里逻辑最直观。下面这个片段是改造后的骨架public Token nextToken() { while (true) { skipWhitespaceAndComments(); if (pos src.length()) { return new Token(TokenType.EOFTOK, EOF, line); } char c src.charAt(pos); // 原标识符、数字、符号分支…… // 非法字符分支 System.err.println(line line : 非法字符 c ); pos; continue; // 回到循环开头而不是递归 } }5.5 保留字表没生效所有字母串全变成标识符现象if、read、write全被识别成IDToken流里一个KW都看不到。原因常见的有两种。一是保留字表初始化代码写在了构造方法外面reserved在用到时还是空的二是getOrDefault(word, TokenType.ID)里的默认值写反查出保留字时反而返回了ID。解决把reserved的初始化集中到构造方法或静态初始化块然后在nextToken()识别出字母串后立即查表。写完后先跑一个只含保留字的文件确认每个保留字输出KW再跑一个ifx样本确认它输出ID而不是KW。这两个样本一正一反能同时验证查表和默认值两条路径。6. 进阶把词法分析器接到语法分析器之前词法分析器交付之后下一步通常是递归下降语法分析器。这时候你要做的是把词法层包成一个干净接口而不是把pos、line这些字段直接暴露给上层。最常见做法是只提供nextToken()配合一个lookahead做单Token前瞻// Parser.java 里的一段接口约定 public class Parser { private Lexer lexer; private Token lookahead; public Parser(Lexer lexer) { this.lexer lexer; lookahead lexer.nextToken(); // 预读第一个Token } public void advance() { lookahead lexer.nextToken(); } }这种“一个Token前瞻”的结构对词法分析器的要求只有一个nextToken()能稳定地返回下一个Token并且在文件结束时一直返回EOFTOK。词法层一旦满足这个契约语法层就可以通过lookahead.type判断接下来的语法结构不用关心Token文本怎么切出来的。反过来如果词法层的行号、类型、原文任何一处不稳定语法层查出来的错全都会变成“玄学”——错误堆栈指向语法层病根却在词法层。验证词法分析器是否真的合格我建议做三件事。第一把Token流完整输出成文件和人工手写的预期Token序列逐行diff这一步能抓到绝大多数类型编号和文本错误。第二测试文件按场景单独命名比如test-ok-01.tiny、test-err-01.tiny这样回归时看文件名就能知道哪个场景挂了而不是对着一个混着正常和报错的大文件发呆。第三先验证空文件和纯注释文件再验证边界用例最后再跑整个语法样例顺序反了出错时你会分不清是驱动的问题还是扫描循环的问题。我之前做这个课设时就是在写语法分析器之前先花了一晚上把Token流打印出来对齐后来调试时遇到的所有报错都直接定位到语法层词法层几乎没有回来返工。词法分析器是编译器的起点它不牢靠后面所有工作都在沙子上盖楼。希望帮到你。本文还有配套的精品资源点击获取