扫码获取 VIP 码
添加管理员微信获取 VIP 码
在软件设计师考试的上午综合知识部分，编译原理相关的选择题每年至少出现两到三道，在满分七十五分的卷面中稳定占据约百分之五的分值。其中正规式、有限自动机和乔姆斯基文法体系是命题密度最高的考点群，几乎逢考必出。不少考生对这块内容的第一印象是抽象难懂，符号多公式多，读题就卡壳。其实拨开形式化的外壳，这三个概念之间的逻辑关系非常清晰：正规式是一种写法的约定，有限自动机是同一种语言规则的另一种表达形式，而上下文无关文法则在前两者的基础上扩展了描述能力的疆界。本文从正规式语法规则入手，延伸到有限自动机的构造与化简方法，再展开乔姆斯基四类文法的层级关系，把软设历年真题中反复出现的命题模式逐一拆解透彻，让考生不仅会做题，更能理解编译原理底层的形式语言思想。
正规式也称为正则表达式，是用代数符号精确描述字符串集合的语言工具。它的核心思想是用少数几个基本运算符，组合出无穷多种字符串模式。正规式定义的字符串集合统称为正规集，正规集就是正则语言。正规式的运算符只有三种：连接运算、选择运算和闭包运算。连接运算表示两个子模式首尾相接，比如正规式"ab"表示先出现字符a紧接着出现字符b。选择运算用竖线符号表示，读作"或"，正规式"a竖线b"表示要么匹配a要么匹配b。闭包运算用星号表示，读作"零次或多次重复"，正规式"a星号"表示空字符串、一个a、两个a连续等任意长度的a串。这三种运算的组合表达力极强，正规式"a竖线b星号c"表示以单个a开头或者以任意多个b后跟一个c结尾的字符串，涵盖了a、c、bc、bbc等多种情况。理解正规式的关键在于识别运算符的优先级和结合性：星号闭包优先级最高，连接运算次之，选择运算最低，所有二元运算都是左结合。正规式的运算满足一些代数定律，比如选择运算满足交换律和结合律，连接运算对选择运算满足分配律，这些定律在等价变换和化简时频繁使用。软设考试中正规式的题型比较固定，一种题型是给出正规式让考生判断某个字符串是否属于该正规集，另一种是给出字符串集合的描述让考生选出等价的正规式。后一种题型常设陷阱：两个正规式看起来不同但描述的语言完全相同。比如正规式"a括号b竖线c括号星号"要求每个a后面必须跟b或c的重复，而正规式"括号a星号b星号c星号括号星号"允许任意穿插，两者完全不等价。判断两个正规式是否等价没有通用的自动化方法，需要考生从语言描述的视角去比对，这也是命题人最喜欢的区分度来源。
正规式的表达能力有明确上限：无法描述需要"计数"的语言。典型例子是左右括号配对，正规式无法表达"任意数量左括号后跟同样数量右括号"，因为它没有记忆能力记录左括号次数。这引出一个核心理论结果：正规式等价于有限自动机，而自动机只有有限个状态，无法实现任意精度计数。另一个超边界语言是回文串，正读反读相同的字符串也需要比较前后对应位置字符，本质上是计数配对。理解这个边界对软设有两层意义：做题时快速排除明显超正规式能力范围的选项，以及理解为何需要上下文无关文法这类更强工具。
有限自动机是用状态和状态之间的转移来描述字符串规则的数学模型。它像一张带箭头的图，圆圈代表状态，箭头代表在读到某个字符时从一个状态转移到另一个状态。有限自动机分为确定型有限自动机和不确定型有限自动机两类。确定型有限自动机简称DFA，要求每个状态针对字母表中的每个字符恰好有一条出边，也就是说在当前状态下读到某个字符时，下一步去哪个状态是唯一确定的。不确定型有限自动机简称NFA，允许一个状态针对同一个字符有多条出边，也允许不消耗任何字符的空转移。从表达能力上看，DFA和NFA完全等价，任何一个NFA都可以通过子集构造法转换为等价的DFA。这个等价性定理是形式语言理论的核心结论之一。在软设考试中，有限自动机的题型通常有三种：第一种是给出一张状态转换图，判断该自动机接受哪个字符串或者拒绝哪个字符串；第二种是给出语言描述，推导出对应的状态转换图；第三种是正规式和自动机之间的相互转换。一个字符串被有限自动机接受的判定规则非常明确：从初始状态开始，沿着与字符串字符序列对应的转移边走，如果走完整条字符串后停留在一个终态上，该字符串就被接受。终态在图中通常用双圈表示。这个判定过程本质上是一个逐步消耗输入的过程，每读一个字符就走一步，全部读完后检查落点是否合法。设计有限自动机有一个实用技巧：先确定要识别的语言特征，然后为每个特征阶段设置一个状态。比如要识别正规式"a括号b竖线c括号星号"，可以先设计一个初始状态，读到a之后进入下一个状态，然后在这个状态下读到b或c都回到自身表示重复，最后把这个循环状态标为终态即可。
子集构造法是把不确定自动机等价转为确定自动机的标准算法，软设考过多次。核心是把NFA同时可能处于的多个状态打包成一个集合，把这个集合当作DFA的一个状态。初态是原NFA初态经所有空转移能到达的状态集合。对此集合中每个元素，考虑读入某字符后能到达哪些NFA状态，再经空转移扩展形成新状态集合，即DFA读入该字符后的目标状态。重复直至无新集合产生。所有包含原NFA终态的集合都是DFA终态。子集构造法最坏情况下产生指数级状态数，但实际远少于此。软设常见考法是给NFA状态图问转换后DFA状态数，或问某状态下读某字符转到哪个状态。核心不在机械执行算法步骤，而在掌握"集合即状态"的思维转换。很多考生做错是把NFA单状态与DFA集合状态混淆，在脑中仍用单状态思考转移关系。
确定型有限自动机的最小化是编译原理中的经典优化步骤，考查频率中等但难度偏大。化简的目标是在不改变接受语言的前提下把DFA的状态数减到最少。基本方法是将所有状态划分为终态组和非终态组两个初始等价类，然后反复检查每个等价类内部的状态是否针对所有输入字符都转移到同一个等价类中。如果某个状态对某个字符的转移目标落入了不同的等价类，就需要把该状态从当前等价类中分离出来形成新的等价类。重复这个过程直到等价类不再变化，最终每个等价类对应化简后DFA的一个状态。软设中关于DFA化简的题目通常给一张不太复杂的状态转换图让考生判断化简后有几个状态，或者判断哪两个状态是等价的。一个常见的得分技巧是观察"镜像"状态，即两个状态对所有输入字符的转移目标完全相同，或者互为对方的镜像，那么它们可以合并。但要注意的是，即使转移目标不同，只要转移目标也属于同一个等价类，两个状态仍然可以合并。真正的判断标准是后续所有可能路径的一致性，而不是一步转移的简单比对。
上下文无关文法在乔姆斯基文法体系中位于第二层，是正规语言描述能力的直接扩展。它的产生式规则形如"A右箭头α"，其中A是单个非终结符，α是由终结符和非终结符组成的任意字符串。这个定义的"上下文无关"体现在：无论在什么上下文中遇到非终结符A，都可以用α来替换A，替换不依赖于A的左右邻居。上下文无关文法的描述能力比正规式强出一个数量级，它可以描述嵌套结构、配对结构、递归结构。典型例子是程序设计语言中表达式语法的括号配对，正规式无法描述任意深度的括号嵌套，上下文无关文法只需要一条规则"S右箭头左括号S右括号竖线空"就可以精确捕获。程序设计语言的大多数语法结
本篇完！