简介这份常州工学院编译原理试卷Adoc格式55KB共1个文件面向计算机专业学生及备考编译原理的学习者用于检验和巩固课程核心知识点。试卷内容覆盖正规表达式与有限自动机、逆波兰表示、文法二义性证明、LL(1)文法与预测分析表构造以及if-then-else语句的四元式翻译等典型题型并配有班级、姓名、学号等标准答题栏便于模拟真实考试环境。通过练习可系统梳理词法分析、语法分析、语义分析与代码生成各阶段的关键方法掌握First集、Follow集计算及最简DFA构造等解题思路。目前已有391人学习下载适合作为期末复习、自测与查漏补缺的参考材料。1. 编译原理到底在学什么从一份试卷的五大题型说起很多人第一次听到“编译原理”脑子里浮现的是满屏的代码和看不懂的符号。其实它研究的事情特别朴素你写下一行a b c计算机怎么把它变成能跑起来的指令这中间要经过词法分析、语法分析、语义分析、代码生成等一连串步骤每一步都有严格的形式化方法在支撑。打个比方编译原理就像教一个只懂机器语言的外星人学会读人类写的高级语言——你得先教它认字词法再教它断句和理解语法语法然后搞懂句子的意思语义最后翻译成它能执行的命令代码生成。这份试卷把这条链路里最核心的五个知识点抽出来考正规表达式与有限自动机、逆波兰表示、文法的二义性、LL(1)文法与预测分析表、四元式序列。搞懂它们你就摸到了编译器设计的骨架。2. 正规表达式与有限自动机怎么让机器“看懂”字符串模式2.1 正规表达式到底在描述什么正规表达式Regular Expression这个词你可能在写代码时天天见用\d匹配数字、用.*匹配任意字符。但它的理论根基来自形式语言与自动机理论描述的是一类特定字符串集合的模式。通俗地说它是一套“字符串配方”告诉你一个合法的字符串长什么样由哪些字符、以什么顺序、重复多少次组成。试卷第一题给了两个具体任务。第一个是在字母表 {0,1} 上构造所有“不以 0 开头但以 11 结尾”的字符串的正规表达式。拆解一下这个描述——不以 0 开头意味着第一个字符必须是 1以 11 结尾意味着最后两个字符固定是 11中间可以穿插任意 0 和 1 的组合。所以正规表达式可以写成1(0|1)*11。这里(0|1)*表示“零个或多个 0 或 1”|是选择操作*是闭包操作。第二个任务是包含子串 01 的所有字符串。这个更直接只要字符串里出现过一次连续的 01 就行前后可以是任意字符。正规表达式为(0|1)*01(0|1)*。2.2 从正规表达式到最简 DFA 的转换逻辑有了正规表达式下一步是构造与之等价的确定性有限自动机DFA。DFA 你可以理解为一台“状态机”它从初始状态出发每读一个字符就跳到一个确定的下一个状态读完所有字符后如果停在接受状态就说明这个字符串符合模式。为什么需要 DFA因为正规表达式是“声明式”的描述而 DFA 是“可执行”的模型。编译器里的词法分析器本质上就是一个 DFA它逐字符扫描源代码判断当前读到的是标识符、数字还是运算符。从正规表达式到 DFA 的标准路径是正规表达式 → NFA非确定性有限自动机→ DFA → 最简 DFA。NFA 允许一个状态在同一个输入下有多个去向甚至不读字符就能跳转DFA 则要求每个状态对每个输入符号最多只有一个去向。把 NFA 确定化子集构造法得到 DFA再用等价状态合并的方法最小化就得到最简 DFA。注意考试里常考的“最简 DFA”要求状态数最少合并的原则是两个状态如果对所有输入字符串的接受行为完全一致就可以合并成一个。这部分知识在真实工程中的价值在于你用的grep、sed、各种 IDE 的语法高亮底层都跑着 DFA。理解了它你就知道为什么有些正则匹配快、有些慢——状态数越多匹配时跳转越复杂。3. 逆波兰表示与四元式编译器眼里的表达式长什么样3.1 为什么编译器不喜欢中缀表达式我们平时写的AB*(C-D)E/(C-D)叫中缀表达式运算符在操作数中间。人类读起来自然但机器处理起来麻烦——你得处理优先级乘除高于加减、括号嵌套、结合性左结合还是右结合。编译器不想每次都做这套复杂判断所以它会把中缀表达式转成一种更“扁平”的形式。逆波兰表示也叫后缀表达式就是其中一种。规则很简单操作数直接写运算符写在它两个操作数后面。AB变成ABAB*C变成ABC*。试卷里那个表达式转换后是ABCD-*ECD-/拆开看C-D先转成CD-然后B*(C-D)变成BCD-*接着A...变成ABCD-*右边E/(C-D)变成ECD-/最后两部分相加得到ABCD-*ECD-/。逆波兰表示的好处是不需要括号也不需要优先级规则。计算时用一个栈遇到操作数就压栈遇到运算符就弹出两个操作数计算再把结果压回去。整个过程机械、确定不会产生歧义。3.2 四元式更接近目标代码的中间形式逆波兰表示适合做表达式求值但编译器还需要一种能表达赋值、跳转、函数调用等操作的中间形式。四元式就是最常用的一种它把每个操作拆成四个部分(运算符, 操作数1, 操作数2, 结果)。比如AB*(C-D)E/(C-D)的四元式序列大致是这样的( - , C , D , T1 ) ( * , B , T1 , T2 ) ( , A , T2 , T3 ) ( - , C , D , T4 ) ( / , E , T4 , T5 ) ( , T3 , T5 , T6 )每一行只做一件事临时变量 T1 到 T6 用来存中间结果。这种形式的好处是每个四元式都对应一条或几条机器指令代码生成阶段只需要逐条翻译就行不用再解析复杂表达式。提示四元式里的“结果”不一定非得是变量也可以是临时变量。临时变量的数量反映了表达式的计算复杂度。3.3 从表达式到四元式的翻译思路翻译过程本质上是对语法树做一次后序遍历。以AB*(C-D)为例语法树根节点是左子节点是A右子节点是**的左子节点是B右子节点是--下面才是C和D。后序遍历的顺序是先处理C-D生成四元式再处理B*T1最后处理AT2。试卷第五题考的是把if x0 y0 then z:xy else begin x:x2; y:y3 end翻译成四元式。这里涉及条件跳转需要用到“跳转目标”这个概念。通常的做法是先计算条件根据条件真假跳转到不同分支每个分支执行完后跳转到整个 if 语句的出口。四元式里会用(j, x, 0, 标号)表示“如果 x0 则跳到标号处”用(j, -, -, 标号)表示无条件跳转。这部分知识在真实编译器里的位置是“中间代码生成”。前端做完语法分析和语义分析后生成中间代码后端再把中间代码优化并翻译成目标机器的汇编。四元式因为结构规整特别适合做优化——比如常量折叠、公共子表达式消除都是在四元式层面做的。4. 文法、二义性与 LL(1)语法分析的核心概念4.1 文法是什么二义性为什么是个问题文法Grammar是描述一门语言语法结构的规则集合。它由四部分组成终结符就是实际的字符或记号、非终结符表示语法范畴的占位符、产生式形如A → α的替换规则、开始符号。试卷第三题给出的文法 G 以 N 为开始符号产生式包括N→SE|E、S→SD|D、E→0|2|4|6|8|10、D→0|1|2|3|4|5|6|7|8|9。二义性指的是同一个字符串可以被同一文法生成两棵不同的语法分析树。换句话说文法没有唯一确定字符串的结构。这在编程语言里是灾难——同一个表达式如果有两种解析方式编译器就不知道该生成哪种代码。试卷要求证明文法 G 有二义性。证明方法通常是找到某个字符串它能对应两棵不同的推导树。比如对于这个文法字符串0既可以通过N→SE→DE→0推导出来也可以通过N→E→0推导出来两条路径对应不同的语法结构所以文法有二义性。二义性在真实语言设计中是要极力避免的。C 语言里著名的“悬空 else”问题就是二义性的经典案例if a then if b then s1 else s2里的else到底匹配哪个ifC 语言用“else 匹配最近的未匹配 if”这条规则来消除二义性但这本质上是在文法之外打补丁。4.2 First 集和 Follow 集LL(1) 分析的两块基石LL(1) 文法是一类适合自顶向下语法分析的文法。LL 的意思是从左到右扫描输入第一个 L产生最左推导第二个 L每次只看一个输入符号就能决定用哪条产生式1。要判断一个文法是不是 LL(1)必须先算两个集合First 集和 Follow 集。First 集对于某个符号串 αFirst(α) 是 α 能推导出的所有可能的开头终结符的集合。如果 α 能推导出空串 ε那么 ε 也在 First(α) 里。通俗地说First 集回答的是“这个语法成分可能以什么字符开头”。Follow 集对于某个非终结符 AFollow(A) 是所有可能紧跟在 A 后面的终结符的集合。它回答的是“这个语法成分后面可能跟什么字符”。Follow 集的计算需要用到 First 集并且开始符号的 Follow 集里要加入结束符$。试卷第四题给出的文法 G 包含E→TE、E→E|ε、T→FT、T→T|ε、F→PF、F→*F|ε、P→(E)|^|a|b。计算 First 和 Follow 集是构造预测分析表的前置步骤。4.3 预测分析表怎么构造LL(1) 怎么证明预测分析表是一个二维表格行是非终结符列是终结符包括结束符$。表格的每个单元格告诉分析器当栈顶是非终结符 A、当前输入符号是 a 时应该用哪条产生式替换 A。构造规则是对于每条产生式A→α如果 a 在 First(α) 里就把A→α填到M[A, a]如果 α 能推导出 ε那么对于 Follow(A) 里的每个符号 b也把A→α填到M[A, b]。证明文法是 LL(1) 的条件是预测分析表里每个单元格最多只有一条产生式。如果某个单元格里出现了两条或更多产生式就说明分析器在面对某个输入时无法唯一决定用哪条规则这个文法就不是 LL(1)。注意LL(1) 文法的能力有限很多自然语言的语法和复杂编程语言的语法都不是 LL(1)。但它的分析过程简单高效适合手写递归下降分析器也适合教学理解语法分析的基本原理。这部分知识在工程中的对应物是ANTLR、JavaCC 这类解析器生成工具它们支持 LL(*) 或类似的自顶向下分析策略。理解 First 集、Follow 集和预测分析表你就能看懂这些工具生成的代码在干什么也能在语法报错时判断是文法设计的问题还是输入的问题。5. 这些概念容易混五个初学者最常踩的坑5.1 正规表达式和 DFA 是一回事吗易混点很多人觉得正规表达式和 DFA 是同一个东西的两种写法。为什么混它们确实描述同一类语言正规语言而且可以互相转换考试里也经常放在一起考。怎么区分正规表达式是声明式的描述像一份配方告诉你字符串长什么样DFA 是操作式的模型像一台机器告诉你逐字符读入时怎么跳转。正规表达式适合人写DFA 适合机器执行。编译器里词法分析器最终跑的是 DFA但设计阶段可能先用正规表达式描述模式。5.2 逆波兰表示和四元式都是中间代码有什么区别易混点两者都是中缀表达式的转换结果都用于编译器中间阶段。为什么混它们确实都在“中间代码”这个大类里而且试卷里同时考了。怎么区分逆波兰表示只适合表达式求值它没有变量赋值、没有跳转、没有函数调用就是一个纯粹的计算序列。四元式是通用中间表示能表达赋值、条件跳转、无条件跳转、数组访问、函数调用等几乎所有操作。逆波兰表示更像一个计算器的输入四元式更像汇编语言的雏形。5.3 文法的二义性和语法分析器的冲突是一回事吗易混点二义性文法会导致分析冲突所以有人觉得二义性就是分析冲突。为什么混两者确实相关——二义性文法在构造分析表时通常会出现冲突。怎么区分二义性是文法本身的属性跟用什么分析方法无关。一个文法有二义性意味着存在某个字符串有两棵不同的语法树。分析冲突是分析方法和文法共同作用的结果——同一个非二义性文法用 LL(1) 分析可能冲突用 LR(1) 分析就不冲突。二义性是“语言结构不唯一”冲突是“分析器无法决策”。5.4 First 集和 Follow 集到底谁是谁易混点两个集合都是终结符的集合名字又抽象初学者经常搞反。为什么混它们总是一起出现计算过程也互相依赖。怎么区分First 集看开头——某个符号串能推导出的第一个终结符有哪些。Follow 集看后面——某个非终结符后面可能紧跟哪些终结符。一个记忆口诀First 管“生出来的第一个”Follow 管“后面跟着的”。计算 Follow 集时要用到 First 集但反过来不成立。5.5 LL(1) 和 LR(1) 只是方向不同吗易混点LL 和 LR 都有 L 和 R看起来只是扫描方向不同。为什么混名字确实只差一个字母而且都是语法分析方法。怎么区分LL(1) 是自顶向下分析从开始符号出发试图推导出输入串LR(1) 是自底向上分析从输入串出发试图归约到开始符号。LL(1) 的分析栈里存的是还没匹配的语法成分LR(1) 的分析栈里存的是已经识别出的语法成分。LL(1) 文法范围窄LR(1) 文法范围宽得多几乎所有编程语言的语法都能用 LR(1) 或它的变体LALR(1)描述。真实编译器里GCC、Clang 用的都是自底向上的分析。6. 什么时候该用这些知识什么时候别硬套学编译原理的人常有一个困惑我又不去写编译器学这些干嘛这个问题值得认真回答。该用的场景当你需要处理任何“结构化文本”时这些知识就直接派上用场。写一个配置文件解析器你需要词法分析正规表达式 DFA和语法分析文法 递归下降。做一个查询语言你需要定义文法、消除二义性、设计分析器。甚至写一个简单的计算器逆波兰表示和四元式的思路都能帮你把表达式求值逻辑理清楚。更不用说面试里问“正则表达式为什么可能很慢”答案就在 NFA 到 DFA 的转换过程里。不该硬套的场景不是所有文本处理都需要完整编译技术。如果你只是从日志里提取几个字段用字符串分割或简单正则就够了没必要上 DFA。如果你只是解析一个固定格式的 JSON用现成的库就行没必要自己写文法。编译原理的价值在于理解原理而不是手写每一个分析器。知道什么时候用工具、什么时候自己动手比会背 First 集和 Follow 集的计算步骤更重要。一个具体例子假设你要做一个简单的表达式计算器支持加减乘除和括号。你可以用正规表达式提取数字和运算符用递归下降法写一个分析器本质上是 LL(1) 的手写版本生成四元式序列然后逐条解释执行。整个过程不到两百行代码但覆盖了词法分析、语法分析、中间代码生成、解释执行四个阶段。这就是编译原理最直接的应用——不是造一个完整的编译器而是用编译器的思维拆解问题。提示试卷里的题目都是这些知识的“最小可考单元”。正规表达式和 DFA 考的是词法分析的核心逆波兰表示和四元式考的是中间代码生成文法和 LL(1) 考的是语法分析。把这五类题搞懂你就有了理解编译器前端的基础。从那以后我每次遇到“解析一个文本格式”的需求都会先问自己三个问题这个词法层面能不能用正规表达式描述语法层面有没有二义性需不需要生成中间表示这三个问题问完方案基本就清楚了。希望帮到你。本文还有配套的精品资源点击获取