简介河南大学软件学院《编译原理》期末考点整理面向软件工程专业本科生及准备期末复习的同学系统梳理词法分析、语法分析、文法概念、语义优化等核心模块。文档以考点题型为主线选择填空侧重编译各阶段任务、输入输出及文法分类简答题归纳解释程序与编译程序区别、LL(1)与SLR概念对比大题围绕正则表达式转DFA、句柄识别、语法树构建等高频操作并标注“不考”范围与避坑提示。内容包括各阶段输入输出、FIRST与FOLLOW集合、消除左递归、LR(0)/SLR(1)判断等关键知识点并整理了题型分值分布选择10分、填空10分、简答20分、大题60分方便考生针对性复习复习时可先看考点框架再对照真题演练。压缩包内为1个docx文档仅13KB内容精炼便于打印。已有1232人学习使用是冲刺高分的实用复习资料。1. 一份考点文档怎么变成能落地的编译原理复习方案拿到《河南大学软件学院编译原理考点.docx》这类材料第一反应往往是“终于有范围了”但真正翻完会发现考点文档只做了两件事告诉你哪些理论要背哪些计算题要练。编译原理这门课最坑的地方在于背下来的名词如果不落到代码和推导上试卷里的五道大题依然无从下手。实际考试和实验考核的核心盯着的永远是三块词法分析、语法分析、语义分析与中间代码生成。本文就顺着这条主线把考点拆成能动手验证的知识点再给出一套用 Java 从零搭起的最小词法分析器和递归下降语法分析框架最后盘点那些让历届学生翻车的典型错误。无论你是为了应对期末考试还是想把编译原理实验做扎实都可以按这篇文章的路径走一遍。2. 编译原理考点全景拆解词法分析为什么是编译原理实验的第一道坎2.1 考点定位正则、DFA/NFA 与词法分析器的三种考察形式词法分析是编译原理课程里第一个真正需要“动手算”的模块考点文档里关于它的条目通常散落在三处正则表达式、有穷自动机、手写或工具生成词法分析器。考试最常见的第一大题是从一个正则表达式构造 NFA再把 NFA 转成 DFA最后做 DFA 最小化。这道题考的不是记忆而是三个步骤之间的转换关系NFA 的空串转移如何消除、子集构造法的闭包怎么求、最小化时如何划分等价状态。实验环节则更偏向第三种让你写一个能识别某门语言子集的词法分析器。这里有个普遍的误解以为用 flex 之类工具生成就算完成任务但课程考核往往要求在代码里能看到你理解“最长匹配”和“优先级”这两个概念。比如识别关键字if和标识符ifx时自动机必须保证读入尽可能多的字符才能正确处理边界。测试用例里最常见的翻车点恰恰是if后面紧跟字母或数字时分析器错误地把整个ifx拆成if和x。从备考角度看词法分析这一章应该掌握三个能力能手工写出简单语言的 token 正则定义能把小规模 NFA 转成 DFA 并做最小化能读明白一段词法分析代码的状态转移逻辑。第三点在试卷中常以“补全代码”或“描述算法流程”的形式出现如果你只背结论不做推导很容易在状态转移表上卡住。2.2 考点定位上下文无关文法、语法分析树与冲突处理语法分析是整张考卷里分值占比最高的部分考点文档对应部分几乎一定包含这些关键词文法二义性、左递归消除、提取左因子、FIRST 集与 FOLLOW 集、LL(1) 判定、LR 分析器构造。试卷里典型的大题是给一个文法让你先消除左递归再计算 FIRST 和 FOLLOW最后构造 LL(1) 分析表并判断是否为 LL(1) 文法。这里要分清楚LL(1) 是自顶向下分析依赖“看一个输入符号就能决定产生式”LR(1) 是自底向上分析通过移进-归约和状态栈来工作。多数院校考试以 LL(1) 为主实验课则要求用递归下降或预测分析实现一个计算器。理解两者差异有一个朴素的办法LL(1) 的问题在于“选择产生式时信息不够”LR 的问题在于“归约还是移进的决策做错”这两种冲突在试卷里会分别以“分析表出现多重入口”和“动作冲突”的形式出现。语法分析树的绘制也是高频考点。给定一个输入串画出它的分析树能直接检验你有没有真正理解推导过程。很多学生在这里失分原因是只背了“最左推导”和“最右推导”的定义却没意识到分析树的分支顺序对应推导选用的产生式顺序。建议复习时每做一道构造分析表的题顺手把输入串的推导过程写一遍两件事互相验证正确率会明显提高。2.3 考点定位语义分析、中间代码生成与代码优化的“计算题”过了语法分析考点文档指向的是语义分析和中间代码生成。这一部分在试卷里通常是给出一段代码或一个表达式要求写出三地址码、画出 DAG 或符号表内容。三地址码的考点非常具体临时变量如何分配、地址与运算符如何表达、控制流语句如何翻译成跳转指令。比如if (a b) c a; else c b;翻译成三地址码要注意条件跳转的标签位置和 else 分支的跳转顺序漏掉一条无条件跳转是常见错误。代码优化在本科阶段不会考太深但基本块划分、DAG 构造、公共子表达式提取这三个知识点出现频率很高。给你一段三地址码先划分基本块再构建 DAG最后看哪些计算可以复用这是标准题型。做这类题时注意“基本块的入口条件”和“出口条件”必须有依据不要凭感觉切分。语义分析和中间代码生成在实验课上往往和 Java 联系在一起。比如用 Java 写一个简单语言的翻译器输入计算表达式输出三地址码。这类编译原理实验不仅要求语法正确还要求临时变量的命名规律稳定便于后续优化阶段扫描。如果你在实验里临时变量随便编名后面做 DAG 优化时会发现自己根本分不清哪些表达式是相同的。从这个角度来看中间代码生成实验真正练的是“结构化表达”的能力而不只是翻译本身。3. 用 java编译原理 落地一个最小词法分析器可直接运行的实验框架3.1 最小词法分析器的结构与 Java 骨架代码词法分析器常见的实现形态是“一个状态机 一张关键字表”。这里给出一个适用于课堂实验的最小框架只识别五类 token关键字、标识符、整数、运算符、分隔符。代码不依赖任何第三方库复制到单个 Java 文件中就能跑。import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; /** * 最小词法分析器骨架。 * 使用逐字符扫描状态机只区分三种状态普通、数字、标识符。 */ public class Lexer { // 关键字表识别关键字需要查表比逐字判断更灵活 private static final MapString, TokenType KEYWORDS new HashMap(); static { KEYWORDS.put(if, TokenType.KW_IF); KEYWORDS.put(else, TokenType.KW_ELSE); KEYWORDS.put(while, TokenType.KW_WHILE); KEYWORDS.put(int, TokenType.KW_INT); KEYWORDS.put(return, TokenType.KW_RETURN); } // 单字符运算符映射 private static final MapCharacter, TokenType OPERATORS new HashMap(); static { OPERATORS.put(, TokenType.OP_ADD); OPERATORS.put(-, TokenType.OP_SUB); OPERATORS.put(*, TokenType.OP_MUL); OPERATORS.put(/, TokenType.OP_DIV); OPERATORS.put(, TokenType.OP_ASSIGN); } private final String source; private int pos; public Lexer(String source) { this.source source; this.pos 0; } public ListToken tokenize() { ListToken tokens new ArrayList(); while (pos source.length()) { char c source.charAt(pos); // 跳过空白字符注意 \r\n 在 Windows 下要一并处理 if (Character.isWhitespace(c)) { pos; continue; } // 数字开头进入数字扫描分支 if (Character.isDigit(c)) { tokens.add(scanNumber()); continue; } // 字母或下划线开头进入标识符扫描分支 if (Character.isLetter(c) || c _) { tokens.add(scanIdentifier()); continue; } // 运算符分支 if (OPERATORS.containsKey(c)) { tokens.add(new Token(OPERATORS.get(c), String.valueOf(c), pos)); pos; continue; } // 无法识别时抛出异常方便定位错误行 throw new RuntimeException(词法错误: 第 pos 个字符 c 无法识别); } tokens.add(new Token(TokenType.EOF, , pos)); return tokens; } private Token scanNumber() { int start pos; while (pos source.length() Character.isDigit(source.charAt(pos))) { pos; } return new Token(TokenType.INT, source.substring(start, pos), start); } private Token scanIdentifier() { int start pos; while (pos source.length() isIdentifierPart(source.charAt(pos))) { pos; } String word source.substring(start, pos); TokenType type KEYWORDS.getOrDefault(word, TokenType.IDENT); return new Token(type, word, start); } private boolean isIdentifierPart(char c) { return Character.isLetterOrDigit(c) || c _; } public static void main(String[] args) { String code int a 1 2; if (a 0) a a - 1;; Lexer lexer new Lexer(code); for (Token t : lexer.tokenize()) { System.out.println(t); } } } class Token { enum TokenType { KW_IF, KW_ELSE, KW_WHILE, KW_INT, KW_RETURN, IDENT, INT, OP_ADD, OP_SUB, OP_MUL, OP_DIV, OP_ASSIGN, EOF } TokenType type; String text; int position; Token(TokenType type, String text, int position) { this.type type; this.text text; this.position position; } Override public String toString() { return type [ text , pos position ]; } }代码逻辑分四段主循环根据当前字符决定进入数字、标识符还是运算符分支数字扫描只用Character.isDigit判断遇到第一个非数字字符就停止标识符扫描则允许字母、数字和下划线扫完再查关键字表确定类型所有无法识别的字符直接抛出 RuntimeException这在实验报告里能当作异常处理的说明点。3.2 测试用例与三个关键参数关键字表、空白符跳过、最长匹配这个框架里有三个参数决定了分析器的行为实验报告中必须写明你测了什么、改了什么。第一个参数是关键字表 KEYWORDS。它放在静态代码块里意味着所有 Lexer 实例共享同一张表运行时增删会影响所有实例。如果实验要求支持多语言关键字或者动态加载关键字就要把这张表变成实例字段。扩展时注意表的查询顺序没有优先级可言重复关键字后加入的会覆盖先加入的所以初始化时要避免冲突。第二个参数是空白符处理。这里用Character.isWhitespace(c)跳过了空格、换行、制表符。课堂实验这样写已经够用但有几个隐藏坑Java 的isWhitespace默认会把部分 Unicode 空格也算进来比如不换行空格如果你的待分析源码里有全角空格行为会和你预期不一致。更严格的写法是明确判断c || c \t || c \n || c \r这样每个参与实验的人看到的跳过逻辑都相同。第三个参数是标识符的判断范围。isIdentifierPart里使用了Character.isLetterOrDigit这意味着中文也可以作为标识符的一部分因为 Java 的Character.isLetter会返回 Unicode 中所有字母类字符。如果实验规定标识符只能包含英文字母和数字就必须改成(c a c z) || (c A c Z)。这个改动直接影响最长匹配的结果比如输入变量名时宽松版会把它识别为一个标识符严格版则会直接报错。3.3 失败时如何排查输出 Token 流并对照手工推导词法分析器出错时不要盯着源码看第一个动作是打印 Token 流。把输入串和输出 token 一行行并排看通常马上就能定位到是哪一类字符处理出了问题。比如输入12时预期应该是INT(1) OP_ADD INT(2)如果输出变成了INT(1) INT(2)说明数字扫描分支在遇到运算符时没有正确停止。这类问题多半出在循环边界上检查pos和循环退出条件即可。另一个有效的排查手段是准备一组“最小失败样例”。一个样例只服务一个目的测数字边界、测关键字边界、测空白处理。有个经典样例是int ifx 1;它考验的是if关键字后面紧跟x时扫描器能不能把整个ifx当标识符处理。如果你在实现时先查表再读后续字符这个样例就会失败因为它读到了if就返回了关键字 token。正确顺序必须是“先扫描完整词再查表定型”代码里的 scanIdentifier 就是先完整收集再用getOrDefault决定类型。4. LL(1) 分析表与递归下降语法分析从考点到可运行代码的完整路径4.1 手动构造 FIRST 与 FOLLOW 集合的步骤语法分析考点的核心计算题几乎都从 FIRST 集和 FOLLOW 集开始。这里用一个简单文法演示完整推导过程E - TE E - TE | ε T - FT T - *FT | ε F - (E) | id计算 FIRST 集时从终结符开始反向推理。F的产生式右部以(或id开头所以FIRST(F) {(, id}。T的产生式右部以F开头因此FIRST(T) FIRST(F) {(, id}。E同理FIRST(E) FIRST(T) {(, id}。处理带撇的产生式时E的第一个候选TE首字符是第二个候选是 ε所以FIRST(E) {, ε}。计算 FOLLOW 集时从开始符号开始。FOLLOW(E)必然包含$。看产生式F - (E)E后面紧跟右括号所以)要进FOLLOW(E)得到FOLLOW(E) {$, )}。接下来看E - TEE在右部末尾所以FOLLOW(E) FOLLOW(E) {$, )}。T后面跟着E把FIRST(E)中除 ε 的元素加入FOLLOW(T)同时因为E可推导出 εFOLLOW(E)也要并入FOLLOW(T)得到FOLLOW(T) {, $, )}。这个推导过程在考试里必须写清每一步的依据只写结果不给理由会被扣大半分。手工验证集合是否算对有一个笨但可靠的办法随便找一个包含某个非终结符的产生式看能不能用你已经算出的集合完成一次完整的推导。如果推到一半需要的符号不在集合里说明之前计算有遗漏通常是第二条带 ε 的产生式没有参与传播。4.2 分析表构造与冲突检查的实操要点有了 FIRST 和 FOLLOW 集LL(1) 分析表就按规则逐格填入对每个产生式A - α把A和FIRST(α)中的每个终结符对应起来填这个产生式如果α可推导出 ε再把FOLLOW(A)中的每个终结符对应起来填入。把上面的文法填完会得到一个二维表行列分别是非终结符和终结符。填表之后必须做冲突检查。如果某个表项出现两个产生式说明该文法不是 LL(1)。这时有两种常见修复路径一种是提取左因子把公共前缀拆出去比如E - TE | ε本身没有左因子问题但如果遇到A - ab | ac就应改为A - aB, B - b | c另一种是消除左递归考试里最常考的是直接左递归改写比如E - E T | T要改写成E - TE, E - TE | ε。这套改写规则必须熟练到不假思索因为后面几乎每一道大题都会用到。还有一个容易忽略的细节分析表里 ε 产生式的处理。很多学生在填E - ε时只记得往FOLLOW(E)里的$和)格填却忘了问自己“如果当前输入符号是该怎么办”。在真正的预测分析器里遇到时应该选择E - TE而ε产生式是留着处理输入串结束时用的。这个决策逻辑就是表驱动分析的灵魂。4.3 用 Java 实现递归下降分析器并验证输入串实验课更常要求的是递归下降分析而不是表驱动。递归下降的本质是把每个非终结符写成一个方法方法内部的判断依赖当前输入符号。这里给出一个能解析上述文法的最小实现识别类似id id * ( id id )的表达式import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * 递归下降语法分析器识别文法 E - TE; E - TE|ε; T - FT; T - *FT|ε; F - (E)|id */ public class RecursiveDescentParser { private ListString tokens; private int pos; public RecursiveDescentParser(ListString tokens) { this.tokens tokens; this.pos 0; } private String peek() { return pos tokens.size() ? tokens.get(pos) : $; } private void consume() { pos; } public void parse() { expression(); if (!peek().equals($)) { throw new RuntimeException(语法错误: 多余的输入 peek() ); } } private void expression() { term(); expressionPrime(); } private void expressionPrime() { if (peek().equals()) { consume(); term(); expressionPrime(); } // peek 不是 时对应 E - ε这里什么都不做 } private void term() { factor(); termPrime(); } private void termPrime() { if (peek().equals(*)) { consume(); factor(); termPrime(); } } private void factor() { if (peek().equals(id)) { consume(); } else if (peek().equals(()) { consume(); expression(); if (!peek().equals())) { throw new RuntimeException(语法错误: 缺少右括号); } consume(); } else { throw new RuntimeException(语法错误: 无法处理的符号 peek() ); } } public static void main(String[] args) { ListString input new ArrayList(Arrays.asList(id, , id, *, (, id, , id, ))); RecursiveDescentParser parser new RecursiveDescentParser(input); parser.parse(); System.out.println(语法分析通过输入串合法); } }这个分析器的手写逻辑很直观expression()对应E - TE先调用term()处理T再调用expressionPrime()处理EexpressionPrime()里如果当前符号是就消费掉它并继续解析右侧的T和E否则保持沉默这正是 ε 产生式的代码化。factor()是最底层的分支选择区分id和带括号的递归表达式。运行时如果输入串不合法则抛出带具体符号的异常定位很快。这段代码在课程实验中有一个重要的改进空间它没有为每个非终结符构造返回值和语法树节点只能判断“合法或不合法”。如果你想加分可以把expression()的返回值改成ExprNode形成 AST后续语义分析就是在遍历这棵树上做文章。这是从语法分析迈向中间代码生成的必经之路。5. 编译原理考点中的高频踩坑点五个翻车案例与规避方法5.1 现象词法分析器把关键字识别成标识符实验测试全部失败原因scanIdentifier在读入整个词之后没有先查关键字表而是取第一个字符就判断类型。比如ifx被扫描成if时就立刻返回关键字 token而测试预期是标识符。解决方法是严格区分“扫描”和“分类”两个阶段先把连续的字母数字下划线全部收集起来再查表分类。代码里scanIdentifier已经体现这一原则但很多人改造时会把查表逻辑提前属于典型的实验翻车点。另一个相关原因是关键字表没有包含全部必备词课程测试文件一旦出现return就被当作标识符处理后续语义分析阶段自然全错。5.2 现象计算 FIRST/FOLLOW 集时把 ε 丢掉递归推导符号不完整原因FOLLOW 集的传播规则里只有当A - αBβ且β可推导出 ε 时FOLLOW(A)中的符号才会并入FOLLOW(B)。很多学生漏掉这个传递条件只算了 FIRST 集里的显式字符。解决方法是计算 FOLLOW 时按步骤列表检查先看右部末尾的非终结符再看右部中间的非终结符后面跟的 FIRST 集最后检查是否存在 ε 链。每次推算完用一个包含 ε 的推导路径反向验证一遍。5.3 现象递归下降分析器把运算符优先级算错12*3的结果是9而不是7原因递归下降里没有为加减和乘除建立层级。常见错误是只写一个expression()方法里面循环匹配加法和乘法导致语法树扁平化。解决方法是严格按文法分层expression 处理加减term 处理乘除factor 处理括号和原子。本文 4.3 的代码结构就是一个范本expressionPrime只处理termPrime只处理*优先级天然成立。考试时如果让你画表达式12*3的语法树只要树的高度至少有三层才说明优先级体现出来了。5.4 现象LL(1) 分析表构造出来有多重表项却不知道去哪查冲突原因分析表冲突位置是有规律的它往往落在某个非终结符和某个终结符的交点上。最常见的是 FIRST 集冲突比如A - aB | aC中a同时出现在两个产生式的首部另一种是 ε 冲突A - B和A - ε在同一个表入口竞争。解决方法是拿到分析表之后做单遍扫描凡是格子里有超过一条产生式的就记录下来写进实验报告并说明修复策略。如果是公共前缀提取左因子如果是ε竞争检查是否文法本身存在二义性。调试时把 FIRST 和 FOLLOW 计算过程完整写出来通常是找到根因的最快路径。5.5 现象考试做翻译题时把正则和上下文无关文法混用原因有些表达式用正则描述不了比如括号配对。正则只能描述有限层嵌套而编译原理里的括号配对必须用上下文无关文法。考题里常见设计是让你写一个识别嵌套括号的文法如果你用正则去套必然写错。解决方法是拿到题目先做分类纯字符模式、固定长度字符串用正则递归结构、嵌套结构必须用文法。这个判断能力在实验设计阶段同样重要比如选择表达式语言的词法定义时用正则没问题但语法阶段再正则就捉襟见肘。6. 把考点文档变成复习闭环一个可长期复用的验证方法考点文档只是一张索引真正的复习要用“闭环验证”来做。我常用的方法很简单把文档里的每个考点条目摘出来翻译成一个可执行动作。比如“了解 DFA 最小化”翻译成“能手工对一个 5 状态 DFA 做最小化并写清划分步骤”“熟悉递归下降分析”翻译成“能在 30 分钟内实现一个含加减乘除和括号的递归下降分析器”。这个翻译过程逼着你看清自己到底懂没懂。验证时采用双通道第一通道是纸上推导把考试要考的计算步骤完整写一遍第二通道是代码实现用 Java 写最小可运行样例。两道都过关才算真正掌握。这里有一个技巧把自我验证的结果记录成一个简单表格日期、考点、纸上状态、代码状态每周回头检查一次。你会发现考试前两周能快速锁定薄弱项而不是从头看一遍笔记。到了冲刺阶段可以尝试更高阶的做法——把你写的词法分析器和递归下降分析器串成一个命令行工具输入一段源代码输出 token 流和语法分析结果。这其实就是编译原理实验的雏形。串起来之后再看考点文档里的“中间代码生成”就有明确的下手点你只需要在语法分析时构建 AST然后遍历 AST 输出三地址码。整个编译器的前端链条就打通了。这样做完一遍考试里的任何计算题在你眼里都会变成你早就做过的事情。我自己的习惯是保留每一次实验的失败记录尤其是那些“卡了两个小时发现是少了一个等号”的案例。考试前翻一遍这些记录比背十遍习题集管用。希望这一整套方法对你也有用祝你顺利拿下编译原理。本文还有配套的精品资源点击获取