DFA 和 NFA 都只有有限状态。状态数量再多，也仍然是有限的。它们适合识别固定模式、分支和重复，但面对任意深度的嵌套结构时会遇到硬边界。

括号匹配就是最小例子。()、(())、(()()) 都合法，(()、())、)( 都非法。有限状态机可以识别“最多三层括号”“最多十层括号”，但只要深度没有上限，有限状态就不够用了。机器需要一种能随输入增长的记忆结构。

下推自动机（Pushdown Automaton，PDA）给有限状态机加了一只栈。状态仍然有限，但栈可以随着输入增长。读到左括号就压栈，读到右括号就弹栈；输入结束后，栈如果回到底部符号，括号就匹配完成。

栈解决的是后进先出问题

括号嵌套天然是后进先出结构。最近打开的左括号，必须最先被右括号关闭。

1
2
3
4
5
6
7
8
9
(()())
123456

1: push (
2: push (
3: pop  (
4: push (
5: pop  (
6: pop  (

第 2 个字符打开的括号，要在第 3 个字符关闭；第 4 个字符打开的括号，要在第 5 个字符关闭；第 1 个字符打开的括号最后关闭。这个顺序正好是栈。

有限状态机无法保存任意多个未关闭括号。状态机可以用 zero_open、one_open、two_open 表示前几层，但深度一旦超过预设状态数，就没有地方记录。PDA 把“多少个未关闭括号”放进栈，状态只负责控制规则。

模式提炼：有限控制加可增长存储

finite_state + growing_memory -> stronger machine

有限状态适合记录阶段，栈适合记录嵌套历史。两者组合后，机器仍然按有限规则运行，但可处理的输入结构明显变强。

场景 有限状态 可增长存储 解决的问题
PDA 当前控制状态 栈 嵌套结构
parser 解析阶段 语法栈 块、表达式、括号
函数调用 指令位置 调用栈 返回地址和局部上下文
XML / JSON 校验 解析阶段 标签 / 容器栈 层级匹配

听到“最近进入的结构要最先退出”时，栈通常是第一选择。

栈的最小实现

本文的栈用 tuple 表示，栈顶放在 tuple 的第一个位置。底部符号用 $ 表示，防止空栈和“已经匹配完”混在一起。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from dataclasses import dataclass


State = str
StackSymbol = str
STUCK_STATE = "stuck"


@dataclass(frozen=True)
class Stack:
    contents: tuple[StackSymbol, ...]

    @property
    def top(self) -> StackSymbol:
        return self.contents[0]

    def pop(self) -> "Stack":
        return Stack(self.contents[1:])

    def push(self, symbols: tuple[StackSymbol, ...]) -> "Stack":
        return Stack(symbols + self.contents)

规则应用时会先弹出栈顶，再把一组符号压回去。因此：

当前栈 操作 新栈
$ 读 (，弹 $，压 ( 和 $ ($
($ 读 (，弹 (，压 ( 和 ( (($
(($ 读 )，弹 (，不压任何符号 ($

这里把栈写成从左到右“栈顶到栈底”。(($ 表示栈顶是 (，底部是 $。

配置包含状态和栈

有限自动机的配置只有当前状态。PDA 的配置需要再加一只栈。

1
2
3
4
5
6
7
@dataclass(frozen=True)
class PDAConfiguration:
    state: State
    stack: Stack

    def stuck(self) -> "PDAConfiguration":
        return PDAConfiguration(STUCK_STATE, self.stack)

stuck 表示机器卡死。读到无法处理的字符时，机器进入 stuck 状态，后续结果必然拒绝。括号匹配里，最典型的卡死场景是栈顶已经是底部符号 $，却还读到了右括号 )。

规则多检查一个栈顶

DFA 的规则看 state + character。PDA 的规则要再看栈顶：

1
state + character + stack_top -> next_state + new_stack
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
@dataclass(frozen=True)
class PDARule:
    state: State
    character: str
    pop_character: StackSymbol
    next_state: State
    push_characters: tuple[StackSymbol, ...]

    def applies_to(self, configuration: PDAConfiguration, character: str) -> bool:
        return (
            self.state == configuration.state
            and self.pop_character == configuration.stack.top
            and self.character == character
        )

    def follow(self, configuration: PDAConfiguration) -> PDAConfiguration:
        return PDAConfiguration(self.next_state, self.next_stack(configuration.stack))

    def next_stack(self, stack: Stack) -> Stack:
        return stack.pop().push(self.push_characters)

括号匹配只需要三条规则：

1
2
3
reading + ( + $ -> reading + ($
reading + ( + ( -> reading + ((
reading + ) + ( -> reading + ε

第一条规则处理第一层左括号：栈顶是 $，读到 ( 后压入 ( 和 $。第二条规则处理更深一层左括号：栈顶是 (，再压入一个 (。第三条规则处理右括号：栈顶必须是 (，弹掉它。

如果栈顶是 $ 时读到 )，没有任何规则适用，机器卡死。

模式提炼：动作能否执行取决于局部上下文

state + event + local_context -> transition

PDA 比 DFA 多看的栈顶，就是一种局部上下文。很多工程状态机不能只看“当前状态 + 事件”，还要看一个最近上下文。

场景 state event local context
PDA 控制状态 输入字符 栈顶符号
parser 解析阶段 当前 token 栈顶语法符号
调用栈 执行位置 return 栈顶栈帧
事务补偿 流程状态 失败事件 最近执行的步骤

当一个事件是否合法取决于最近进入的结构时，单纯状态表往往不够，需要把局部上下文加入转移条件。

DPDA 规则表

本文实现确定性下推自动机（Deterministic Pushdown Automaton，DPDA）。确定性的要求是：同一个配置和输入字符最多只能命中一条规则。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class DPDARulebook:
    def __init__(self, rules: list[PDARule]) -> None:
        self.rules = rules

    def next_configuration(
        self,
        configuration: PDAConfiguration,
        character: str,
    ) -> PDAConfiguration:
        rule = self.rule_for(configuration, character)

        if rule is None:
            return configuration.stuck()

        return rule.follow(configuration)

    def rule_for(
        self,
        configuration: PDAConfiguration,
        character: str,
    ) -> PDARule | None:
        matches = [
            rule for rule in self.rules if rule.applies_to(configuration, character)
        ]

        if len(matches) > 1:
            raise ValueError("DPDA rulebook must be deterministic")

        return matches[0] if matches else None

这里没有实现空转移。PDA 可以有空转移，和 NFA 一样用于不消耗输入的移动；括号匹配不需要它，保留最小模型更清楚。

DPDA 的接受条件

形式理论里，PDA 常见两种接受方式：终态接受和空栈接受。本文使用一个适合代码演示的简化条件：机器没有卡死，并且输入读完后栈顶回到底部符号 $。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class DPDA:
    def __init__(
        self,
        current_configuration: PDAConfiguration,
        bottom_character: StackSymbol,
        rulebook: DPDARulebook,
    ) -> None:
        self.current_configuration = current_configuration
        self.bottom_character = bottom_character
        self.rulebook = rulebook

    def accepting(self) -> bool:
        return (
            self.current_configuration.state != STUCK_STATE
            and self.current_configuration.stack.top == self.bottom_character
        )

    def read_character(self, character: str) -> None:
        self.current_configuration = self.rulebook.next_configuration(
            self.current_configuration,
            character,
        )

    def read_string(self, text: str) -> None:
        for character in text:
            self.read_character(character)

和 DFA / NFA 一样，设计对象负责反复创建新的运行态机器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@dataclass(frozen=True)
class DPDADesign:
    start_state: State
    bottom_character: StackSymbol
    rulebook: DPDARulebook

    def to_dpda(self) -> DPDA:
        start_stack = Stack((self.bottom_character,))
        start_configuration = PDAConfiguration(self.start_state, start_stack)
        return DPDA(start_configuration, self.bottom_character, self.rulebook)

    def accepts(self, text: str) -> bool:
        dpda = self.to_dpda()
        dpda.read_string(text)
        return dpda.accepting()

完整示例

完整代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
from dataclasses import dataclass


State = str
StackSymbol = str
STUCK_STATE = "stuck"


@dataclass(frozen=True)
class Stack:
    contents: tuple[StackSymbol, ...]

    @property
    def top(self) -> StackSymbol:
        return self.contents[0]

    def pop(self) -> "Stack":
        return Stack(self.contents[1:])

    def push(self, symbols: tuple[StackSymbol, ...]) -> "Stack":
        return Stack(symbols + self.contents)


@dataclass(frozen=True)
class PDAConfiguration:
    state: State
    stack: Stack

    def stuck(self) -> "PDAConfiguration":
        return PDAConfiguration(STUCK_STATE, self.stack)


@dataclass(frozen=True)
class PDARule:
    state: State
    character: str
    pop_character: StackSymbol
    next_state: State
    push_characters: tuple[StackSymbol, ...]

    def applies_to(self, configuration: PDAConfiguration, character: str) -> bool:
        return (
            self.state == configuration.state
            and self.pop_character == configuration.stack.top
            and self.character == character
        )

    def follow(self, configuration: PDAConfiguration) -> PDAConfiguration:
        return PDAConfiguration(self.next_state, self.next_stack(configuration.stack))

    def next_stack(self, stack: Stack) -> Stack:
        return stack.pop().push(self.push_characters)


class DPDARulebook:
    def __init__(self, rules: list[PDARule]) -> None:
        self.rules = rules

    def next_configuration(
        self,
        configuration: PDAConfiguration,
        character: str,
    ) -> PDAConfiguration:
        rule = self.rule_for(configuration, character)

        if rule is None:
            return configuration.stuck()

        return rule.follow(configuration)

    def rule_for(
        self,
        configuration: PDAConfiguration,
        character: str,
    ) -> PDARule | None:
        matches = [
            rule for rule in self.rules if rule.applies_to(configuration, character)
        ]

        if len(matches) > 1:
            raise ValueError("DPDA rulebook must be deterministic")

        return matches[0] if matches else None


class DPDA:
    def __init__(
        self,
        current_configuration: PDAConfiguration,
        bottom_character: StackSymbol,
        rulebook: DPDARulebook,
    ) -> None:
        self.current_configuration = current_configuration
        self.bottom_character = bottom_character
        self.rulebook = rulebook

    def accepting(self) -> bool:
        return (
            self.current_configuration.state != STUCK_STATE
            and self.current_configuration.stack.top == self.bottom_character
        )

    def read_character(self, character: str) -> None:
        self.current_configuration = self.rulebook.next_configuration(
            self.current_configuration,
            character,
        )

    def read_string(self, text: str) -> None:
        for character in text:
            self.read_character(character)


@dataclass(frozen=True)
class DPDADesign:
    start_state: State
    bottom_character: StackSymbol
    rulebook: DPDARulebook

    def to_dpda(self) -> DPDA:
        start_stack = Stack((self.bottom_character,))
        start_configuration = PDAConfiguration(self.start_state, start_stack)
        return DPDA(start_configuration, self.bottom_character, self.rulebook)

    def accepts(self, text: str) -> bool:
        dpda = self.to_dpda()
        dpda.read_string(text)
        return dpda.accepting()


rulebook = DPDARulebook(
    [
        PDARule("reading", "(", "$", "reading", ("(", "$")),
        PDARule("reading", "(", "(", "reading", ("(", "(")),
        PDARule("reading", ")", "(", "reading", ()),
    ]
)

design = DPDADesign("reading", "$", rulebook)

for sample in ["", "()", "(())", "(()())", "(()", "())", ")("]:
    print(f"{sample!r:8} -> {design.accepts(sample)}")

运行结果：

1
2
3
4
5
6
7
''       -> True
'()'     -> True
'(())'   -> True
'(()())' -> True
'(()'    -> False
'())'    -> False
')('     -> False

空字符串被接受，因为没有未关闭括号。(() 被拒绝，因为输入结束时栈里还留着一个 (。()) 和 )( 被拒绝，因为读到多余右括号时机器卡死。

看一条栈轨迹

(()()) 的执行轨迹可以直接从栈看出来。

1
2
3
4
5
6
7
start: $
read (: ($
read (: (($
read ): ($
read (: (($
read ): ($
read ): $

栈在每个左括号处增长，在每个右括号处缩短。输入结束时回到底部符号 $，所以字符串被接受。

这种轨迹和真实 parser 的调试方式很接近。块结构、函数调用、XML 标签、JSON 容器都可以通过“输入事件 + 栈变化”观察。

Java 程序员的迁移表

Python 写法 Java 对照 作用
Stack Deque<Symbol> 保存未闭合结构
PDAConfiguration record Configuration(State, Deque<Symbol>) 运行时配置
PDARule record Rule(State, Token, Symbol, State, List<Symbol>) 一条栈转移规则
DPDARulebook 转移表 / 规则表 查找下一配置
STUCK_STATE 异常状态 / 错误状态 表示无法继续解析
DPDADesign parser 配置 / 工厂 复用规则，创建运行态

Java 里实现栈时，ArrayDeque 通常比旧的 Stack 类更合适。更重要的是语义：栈顶元素代表最近打开但尚未关闭的结构，读到关闭符号时只能匹配栈顶。

从 PDA 回到工程

PDA 不是为了让业务代码手写一台自动机。它提供的是一个判断：当输入语言需要任意深度嵌套时，有限状态不够，系统至少需要一只栈。

这条判断可以解释很多工程现象。正则表达式核心能力适合识别扁平模式；parser 需要栈来处理嵌套表达式和代码块；函数调用需要调用栈保存返回位置；JSON / XML 校验需要容器栈或标签栈。

下一步进入图灵机。PDA 的栈只能在一端读写，图灵机的纸带可以在任意位置读写并左右移动。存储结构一变，机器能力继续上升。

练习

第一，修改规则，让机器只接受非空括号串。提示：可以增加一个状态，读到第一个 ( 后再进入 reading。

第二，让机器同时识别 () 和 [] 两类括号。提示：栈里需要保存具体括号类型。

第三，增加 trace 函数，打印每读一个字符后的栈内容。

第四，把接受条件改成终态接受：输入结束且栈顶是 $ 时，通过一条空转移进入 accept 状态。

参考资料