企业官网建设流程全解析

简介：这份常州工学院编译原理试卷A（doc格式，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 为什么编译器不喜欢中缀表达式

我们平时写的A+B*(C-D)+E/(C-D)叫中缀表达式，运算符在操作数中间。人类读起来自然，但机器处理起来麻烦——你得处理优先级（乘除高于加减）、括号嵌套、结合性（左结合还是右结合）。编译器不想每次都做这套复杂判断，所以它会把中缀表达式转成一种更“扁平”的形式。

逆波兰表示（也叫后缀表达式）就是其中一种。规则很简单：操作数直接写，运算符写在它两个操作数后面。A+B变成AB+，A+B*C变成ABC*+。试卷里那个表达式转换后是：

ABCD-*+ECD-/+

拆开看：C-D先转成CD-，然后B*(C-D)变成BCD-*，接着A+...变成ABCD-*+，右边E/(C-D)变成ECD-/，最后两部分相加得到ABCD-*+ECD-/+。

逆波兰表示的好处是不需要括号，也不需要优先级规则。计算时用一个栈，遇到操作数就压栈，遇到运算符就弹出两个操作数计算再把结果压回去。整个过程机械、确定，不会产生歧义。

3.2 四元式：更接近目标代码的中间形式

逆波兰表示适合做表达式求值，但编译器还需要一种能表达赋值、跳转、函数调用等操作的中间形式。四元式就是最常用的一种，它把每个操作拆成四个部分：(运算符, 操作数1, 操作数2, 结果)。

比如A+B*(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 从表达式到四元式的翻译思路

翻译过程本质上是对语法树做一次后序遍历。以A+B*(C-D)为例，语法树根节点是+，左子节点是A，右子节点是*，*的左子节点是B，右子节点是-，-下面才是C和D。后序遍历的顺序是：先处理C-D生成四元式，再处理B*T1，最后处理A+T2。

试卷第五题考的是把if x>0 y>0 then z:=x+y else begin x:=x+2; y:=y+3 end翻译成四元式。这里涉及条件跳转，需要用到“跳转目标”这个概念。通常的做法是：先计算条件，根据条件真假跳转到不同分支，每个分支执行完后跳转到整个 if 语句的出口。四元式里会用(j>, x, 0, 标号)表示“如果 x>0 则跳到标号处”，用(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到底匹配哪个if？C 语言用“else 匹配最近的未匹配 if”这条规则来消除二义性，但这本质上是在文法之外打补丁。

4.2 First 集和 Follow 集：LL(1) 分析的两块基石

LL(1) 文法是一类适合自顶向下语法分析的文法。LL 的意思是：从左到右扫描输入（第一个 L），产生最左推导（第二个 L），每次只看一个输入符号就能决定用哪条产生式（1）。要判断一个文法是不是 LL(1)，必须先算两个集合：First 集和 Follow 集。

First 集：对于某个符号串 α，First(α) 是 α 能推导出的所有可能的开头终结符的集合。如果 α 能推导出空串 ε，那么 ε 也在 First(α) 里。通俗地说，First 集回答的是“这个语法成分可能以什么字符开头”。

Follow 集：对于某个非终结符 A，Follow(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) 考的是语法分析。把这五类题搞懂，你就有了理解编译器前端的基础。

从那以后我每次遇到“解析一个文本格式”的需求，都会先问自己三个问题：这个词法层面能不能用正规表达式描述？语法层面有没有二义性？需不需要生成中间表示？这三个问题问完，方案基本就清楚了。希望帮到你。

本文还有配套的精品资源，点击获取