编译原理实战：用Python模拟下推自动机（PDA）识别0^n1^n语言

编译原理实战用Python模拟下推自动机PDA识别0^n1^n语言很多计算机科学的学生和自学者在初次接触编译原理时都会觉得理论部分抽象难懂。那些关于上下文无关文法Context-free Grammar和下推自动机Push-down Automata的数学定义常常让人望而生畏。然而这些理论并非空中楼阁它们是构建编译器、解释器乃至许多复杂文本处理工具的基石。理解它们最好的方式莫过于亲手将其实现出来。今天我们就抛开复杂的数学符号直接从工程实践的角度出发用Python代码来模拟一个下推自动机让它去识别经典的、非正则的语言——{0^n1^n | n 0}。这个语言简单明了由任意数量n个的0后跟完全相同数量n个的1组成。你会发现通过一个简单的栈结构我们就能将抽象的计算模型转化为清晰、可运行的逻辑这远比单纯阅读定义要深刻得多。1. 从理论到代码理解PDA的核心构件在动手写代码之前我们需要先厘清下推自动机的几个核心组成部分。一个PDA可以看作是一个加强版的有限状态自动机FSM它多了一个无限容量的栈Stack作为辅助存储器。正是这个“下推”Push-down的栈赋予了它超越正则语言的处理能力。一个标准的PDA通常由以下几个部分形式化定义状态集合Q机器可能处于的有限个状态。输入字母表Σ输入字符串中可以出现的字符集合例如我们这里的{0, 1}。栈字母表Γ可以压入栈中的符号集合通常包含输入符号和一些特殊的栈底标记。转移函数δ这是PDA的“大脑”决定了在特定状态下根据当前输入字符和栈顶符号机器下一步该做什么。其输出通常是一个新的状态和对栈的操作压入、弹出或替换。起始状态q₀机器开始运行时的状态。接受状态F当输入字符串全部处理完毕后若机器处于这些状态之一则接受该字符串。对于我们要识别的0^n1^n语言其核心思路是利用栈来计数。基本算法流程可以这样描述初始状态栈为空或有一个栈底标记。读取输入字符串只要读到0就将其压入栈中。这相当于用栈来“记住”我们读到了多少个0。当读到第一个1时进入一个新的阶段。之后每读到一个1就从栈顶弹出一个0。这相当于用1来“抵消”之前记录的0。输入字符串读取完毕时检查栈是否为空。如果栈为空说明0和1的数量相等接受该字符串否则拒绝。这个过程中栈充当了一个完美的计数器。下面这个表格对比了PDA与更简单的有限自动机在处理0^n1^n语言时的本质区别特性有限自动机 (DFA/NFA)下推自动机 (PDA)存储能力仅有有限个状态无额外存储。拥有一个无限容量的栈作为辅助存储。可识别语言正则语言。上下文无关语言CFL是正则语言的超集。处理0^n1^n无法识别。因为需要记住0的数量n而n可以是任意大的有限状态无法记忆。可以识别。利用栈存储0数量不受限。核心操作状态转移。状态转移 栈操作push/pop。理解了这些我们就可以开始用Python的类Class来具象化这些抽象概念了。2. 构建PDA的Python骨架状态、栈与转移我们将采用面向对象的方式来构建我们的PDA模拟器。这样结构清晰也便于后续扩展。首先我们定义PDA的状态。为了直观我们使用字符串来标识状态例如q0,q1,q_accept。栈的实现我们直接使用Python的列表List将其视为一个栈列表的末尾作为栈顶。这非常方便因为list.append()就是压栈pushlist.pop()就是弹栈pop。最核心的部分是转移函数的设计。我们将用一个嵌套字典或字典列表来模拟非确定性转移函数但为了首次实现的清晰性我们先实现一个确定性的下推自动机DPDA。转移规则可以定义为在某个状态下面对特定的输入字符和栈顶符号应该转移到哪个新状态并对栈执行什么操作序列。让我们先搭建起这个PDA类的基本框架class PushdownAutomaton: 一个下推自动机PDA的Python模拟实现。 本实现侧重于展示PDA识别上下文无关语言的核心逻辑。 def __init__(self, states, input_alphabet, stack_alphabet, transitions, start_state, start_stack_symbol, accept_states): 初始化PDA。 :param states: 集合所有状态的集合。 :param input_alphabet: 集合输入符号表。 :param stack_alphabet: 集合栈符号表。 :param transitions: 字典转移函数。格式为 {(state, input_char, stack_top): (new_state, stack_operation_list)} :param start_state: 字符串起始状态。 :param start_stack_symbol: 字符串初始时栈底的符号。 :param accept_states: 集合接受状态集合。 self.states states self.input_alphabet input_alphabet self.stack_alphabet stack_alphabet self.transitions transitions # 转移函数 self.start_state start_state self.start_stack_symbol start_stack_symbol self.accept_states accept_states self.stack [] # 使用Python列表作为栈 self.current_state None def reset(self): 重置PDA到初始配置。 self.stack [self.start_stack_symbol] # 栈底放入初始符号 self.current_state self.start_state def _get_stack_top(self): 获取栈顶符号。如果栈为空返回特殊符号如None或ε。 return self.stack[-1] if self.stack else None def _apply_stack_operation(self, operation): 应用一个栈操作。 :param operation: 字符串如 push:X 或 pop 或 replace:Y。 if operation.startswith(push:): symbol operation.split(:)[1] self.stack.append(symbol) elif operation pop: if self.stack: self.stack.pop() else: raise RuntimeError(Attempted to pop from an empty stack.) elif operation.startswith(replace:): # 先弹出栈顶再压入新符号 if self.stack: self.stack.pop() symbol operation.split(:)[1] self.stack.append(symbol) # 可以扩展其他操作如 noop无操作 def step(self, input_char): 执行一步转移。 :param input_char: 当前输入的字符可以是 表示空转移ε。 :return: 布尔值表示这一步转移是否成功找到并执行了规则。 stack_top self._get_stack_top() # 构造查找键。注意输入字符为 时代表空转移ε移动。 key (self.current_state, input_char, stack_top) if key in self.transitions: new_state, operations self.transitions[key] self.current_state new_state for op in operations: self._apply_stack_operation(op) return True # 如果没有找到精确匹配的转移尝试空转移ε epsilon_key (self.current_state, , stack_top) if epsilon_key in self.transitions: new_state, operations self.transitions[epsilon_key] self.current_state new_state for op in operations: self._apply_stack_operation(op) return True return False # 没有可用的转移输入被拒绝这个PushdownAutomaton类已经具备了PDA的核心运行机制。reset方法用于初始化step方法根据当前配置执行一步转移。转移规则transitions是这个类的灵魂它定义了机器的所有行为逻辑。接下来我们就用这个框架来专门构造识别0^n1^n的PDA。3. 实战为0^n1^n语言配置专属PDA现在我们来具体配置一个能够识别0^n1^n语言的确定性下推自动机。我们需要设计状态和转移规则。状态设计q0: 起始状态负责处理开头的0序列。q1: 过渡状态在遇到第一个1后进入负责处理1序列并弹出栈中的0。q_accept: 接受状态。当输入读完且栈中只剩下栈底符号$时进入。栈符号设计0: 用于计数。$: 栈底标记用于判断栈是否“空”实际上只剩$。转移规则设计δ函数在q0状态读入0栈顶为$或0将0压入栈并保持在q0状态。这记录了0的数量。在q0状态读入1栈顶为0不压入任何东西直接弹出栈顶的0并转移到q1状态。这标志着从记录0切换到消耗0的阶段。在q1状态读入1栈顶为0弹出栈顶的0保持在q1状态。继续消耗0。在q1状态读入输入结束我们用空字符串模拟栈顶为$转移到接受状态q_accept。这表示所有1都消耗完毕且栈已“空”只剩$匹配成功。其他所有未明确列出的情况如在q0读入1但栈顶是$或在q1读入0均意味着输入字符串不合法PDA将因找不到转移规则而拒绝。让我们用代码来定义这个PDAdef create_0n1n_pda(): 创建并返回一个识别 0^n1^n 语言的PDA实例。 states {q0, q1, q_accept} input_alphabet {0, 1} stack_alphabet {0, $} start_state q0 start_stack_symbol $ # 栈底标记 accept_states {q_accept} # 定义转移函数 # 格式: (当前状态, 输入字符, 栈顶) - (新状态, [操作列表]) transitions { # 规则1: 在q0读0压0入栈 (q0, 0, $): (q0, [push:0]), (q0, 0, 0): (q0, [push:0]), # 规则2: 在q0读第一个1弹出栈顶0进入q1 (q0, 1, 0): (q1, [pop]), # 规则3: 在q1读1弹出栈顶0 (q1, 1, 0): (q1, [pop]), # 规则4: 在q1输入结束且栈顶为$进入接受状态空转移 (q1, , $): (q_accept, []), # ε-move } pda PushdownAutomaton( states, input_alphabet, stack_alphabet, transitions, start_state, start_stack_symbol, accept_states ) return pda注意在我们的模拟中输入结束是通过调用一个特殊的方法如下文的run来触发的而不是通过读入一个字符。因此规则4使用了空输入来代表“输入已读完可以检查栈并决定是否接受”这个动作。这是一种常见的处理方式。现在我们需要一个run方法来驱动整个PDA处理完整的输入字符串class PushdownAutomaton(PushdownAutomaton): # 假设这是原类的延续 def run(self, input_string): 运行PDA处理给定的输入字符串。 :param input_string: 待识别的字符串。 :return: 布尔值True表示接受False表示拒绝。 self.reset() print(f开始处理输入: {input_string}) print(f初始状态: {self.current_state}, 初始栈: {self.stack}) # 逐个字符处理输入 for i, char in enumerate(input_string): print(f\n步骤 {i1}: 读入字符 {char}) if char not in self.input_alphabet: print(f 错误字符 {char} 不在输入字母表 {self.input_alphabet} 中。) return False if not self.step(char): print(f 在状态 {self.current_state}, 栈顶 {self._get_stack_top()} 下没有针对输入 {char} 的转移规则。输入被拒绝。) return False print(f 新状态: {self.current_state}, 栈: {self.stack}) # 输入字符串处理完毕尝试通过空转移进入接受状态 print(f\n输入字符串处理完毕。当前状态: {self.current_state}, 栈: {self.stack}) if self.step(): # 尝试ε转移 print(f 成功通过空转移进入状态: {self.current_state}) else: print(f 无法从当前状态通过空转移进入接受状态。) # 判断是否处于接受状态 if self.current_state in self.accept_states: print(f✓ 字符串 {input_string} 被接受。) return True else: print(f✗ 字符串 {input_string} 被拒绝。) return False4. 测试与调试让PDA真正跑起来理论设计和代码实现完成后最重要的环节就是测试。我们需要用各种边界情况和典型用例来验证我们的PDA是否正确工作。让我们创建一个测试函数def test_0n1n_pda(): 测试识别0^n1^n语言的PDA。 pda create_0n1n_pda() test_cases [ (, True), # n0空字符串应该被接受 (01, True), # n1 (0011, True), # n2 (000111, True), # n3 (1, False), # 没有0只有1 (0, False), # 没有1只有0 (10, False), # 顺序错误 (001, False), # 0比1多 (00111, False),# 1比0多 (0101, False), # 交替出现不符合0^n1^n模式 (000, False), # 只有0 (111, False), # 只有1 ] print(*50) print(开始测试 0^n1^n 语言识别器) print(*50) all_passed True for input_str, expected in test_cases: print(f\n{*30}) result pda.run(input_str) if result expected: print(f测试通过: {input_str} - 期望 {expected}, 得到 {result}) else: print(f**测试失败**: {input_str} - 期望 {expected}, 得到 {result}) all_passed False print(f\n{*50}) if all_passed: print(所有测试用例通过) else: print(部分测试用例失败请检查PDA配置。) return all_passed if __name__ __main__: test_0n1n_pda()运行这个测试脚本你会看到PDA一步步处理每个输入字符串打印出状态和栈的变化。对于空字符串PDA从q0开始由于没有输入字符直接尝试空转移。根据规则4在q0状态、栈顶为$时并没有定义空转移所以step()失败最终状态是q0不在接受集中被拒绝。等等这似乎不对空字符串0^0 1^0应该是属于0^n1^n语言的。这里暴露了我们设计的一个小缺陷我们的PDA没有处理n0的情况。修正方法很简单增加一条从起始状态直接通过空转移进入接受状态的规则前提是栈里只有$。我们可以在transitions字典里增加一条规则(q0, , $): (q_accept, []), # 接受空字符串增加这条规则后再运行测试空字符串就应该被正确接受了。这个调试过程非常典型它展示了如何通过测试用例来完善和验证自动机的设计。通过观察控制台输出你能清晰地看到PDA的内部运作如何用栈记录0如何在遇到第一个1时切换状态并开始弹栈以及最终如何根据栈是否“空”来决定接受或拒绝。这种透明性对于学习理解至关重要。5. 超越确定性探索非确定性PDANPDA的模拟我们目前实现的是一个确定性的下推自动机DPDA。对于0^n1^n语言DPDA足以胜任。但上下文无关文法CFG的等价机器是非确定性的下推自动机NPDA。NPDA在某个配置下可能有多个选择即转移函数输出一个状态和操作的集合而非单一结果只要存在一条选择路径能最终导致接受整个输入就被接受。模拟NPDA比DPDA稍微复杂一些因为我们需要管理多个并行的“计算分支”。一种经典的模拟方法是使用“广度优先搜索”BFS或“深度优先搜索”DFS来探索所有可能的路径。我们可以扩展我们的PDA类使其能够处理非确定性转移。首先我们需要修改转移函数的定义使其能返回多个可能的(新状态, 操作列表)对。然后run方法不再跟踪单一配置(状态, 栈, 输入位置)而是跟踪一个配置集合。class NondeterministicPDA: 模拟非确定性下推自动机NPDA。 def __init__(self, states, input_alphabet, stack_alphabet, transitions, start_state, start_stack_symbol, accept_states): # ... 初始化部分与DPDA类似 ... # 但transitions的value应该是一个列表包含多个(next_state, operations)元组 self.transitions transitions def run(self, input_string): 使用BFS模拟NPDA。 from collections import deque # 每个配置是一个元组(当前状态, 栈列表的元组, 当前输入位置) start_config (self.start_state, tuple([self.start_stack_symbol]), 0) queue deque([start_config]) visited set() # 用于剪枝避免重复探索相同配置 while queue: current_state, stack_tuple, pos queue.popleft() if (current_state, stack_tuple, pos) in visited: continue visited.add((current_state, stack_tuple, pos)) stack list(stack_tuple) input_char input_string[pos] if pos len(input_string) else # 获取可能的转移 possible_transitions [] stack_top stack[-1] if stack else None # 1. 尝试基于当前输入字符的转移 key (current_state, input_char, stack_top) if key in self.transitions: possible_transitions.extend(self.transitions[key]) # 2. 尝试空转移ε epsilon_key (current_state, , stack_top) if epsilon_key in self.transitions: possible_transitions.extend(self.transitions[epsilon_key]) for next_state, operations in possible_transitions: new_stack stack.copy() # 应用栈操作 for op in operations: # ... 应用操作同前 ... pass new_pos pos (1 if input_char ! else 0) # 如果消耗了输入字符位置1 # 检查是否到达接受条件 if next_state in self.accept_states and new_pos len(input_string): return True # 找到一条接受路径 # 将新配置加入队列 queue.append((next_state, tuple(new_stack), new_pos)) return False # 所有路径都探索完毕没有找到接受路径为了展示NPDA的能力我们可以考虑一个稍微复杂的语言例如回文语言{ w w^R | w ∈ {0,1}* }即一个字符串后接其反转。这个语言用DPDA是无法识别的因为机器无法确定哪里是字符串的中间点即w的结束和w^R的开始。但NPDA可以“猜测”中间点并通过非确定性选择一条正确的路径。实现这样一个NPDA是很好的进阶练习它能让你更深刻地理解非确定性在计算理论中的力量和意义。6. 从PDA到解析器理论到工程的桥梁实现一个PDA模拟器不仅仅是完成一个课堂作业它为我们打开了一扇窗让我们窥见编译器前端工作的核心。一个PDA本质上就是一个语法解析器的雏形。在编译原理中我们经常使用下推自动机来实现对上下文无关文法的语法分析。考虑一个简单的算术表达式文法E - E T | T T - T * F | F F - ( E ) | id这个文法不是LL(1)文法存在左递归但我们可以构造一个NPDA来识别它。PDA的栈可以用来存放文法符号非终结符和终结符状态转移模拟了推导过程。虽然现代编译器更常用LR或LL系列等更高效的确定性算法但其思想根源与PDA一脉相承。动手实验扩展你的PDA你可以尝试用我们构建的PDA框架去模拟一个识别简单平衡括号语言{(^n )^n | n 0}的自动机。这几乎和0^n1^n一模一样只是符号换成了(和)。更进一步可以尝试识别嵌套的括号如{ (^i )^i (^j )^j | i, j 0 }这需要更精巧的状态设计。另一个有趣的扩展是可视化。为你的PDA类添加图形输出功能使用graphviz库绘制状态转移图。或者在run方法中生成更详细的日志甚至制作一个简单的动画实时展示栈的 push 和 pop 操作。这种视觉反馈能极大地加深理解。最后将PDA与上下文无关文法CFG联系起来。尝试为你实现的PDA编写一个等价的CFG。对于0^n1^n其CFG非常简单S - 0 S 1 | ε这个文法产生的语言正是0^n1^n。理解PDA和CFG之间的等价性即两者都能描述上下文无关语言是编译原理课程中的一个关键里程碑。通过代码实现这个抽象等价关系变得触手可及。