使用有限自动机在Java中进行输入验证

1. 概述

如果你学过计算机科学，肯定上过编译原理这类课程；在这些课程里会教授有限自动机（Finite Automaton，也叫有限状态机）的概念。这是一种形式化语言语法规则的方法。

想深入了解这个主题可以参考这里和这里。

那么这个看似过时的概念，对我们这些不需要构建新编译器的高级程序员有什么用呢？

实际上，有限自动机可以简化很多业务场景，为我们提供处理复杂逻辑的工具。举个简单例子：我们甚至可以不用第三方库，直接用它来验证输入格式。

2. 核心算法

简单来说，有限自动机通过定义状态和状态转换规则来工作。当输入流通过它时，可以用以下算法验证格式（伪代码）：

for (char c in input) {
    if (automaton.accepts(c)) {
        automaton.switchState(c);
        input.pop(c);
    } else {
        break;
    }
}
if (automaton.canStop() && input.isEmpty()) {
    print("Valid");
} else {
    print("Invalid");
}

算法逻辑说明：

当自动机"接受"某个字符时（即存在从当前状态出发、标记该字符的转换箭头），就执行状态切换
状态切换意味着沿着箭头移动，将当前状态更新为箭头指向的状态
循环结束后，检查两个条件：
1. 自动机能否停止（当前状态是双圈表示的终止状态）
2. 输入是否已完全消耗

3. 实战案例

我们来实现一个简单的JSON对象验证器，看看算法如何运作。这是接受JSON对象的自动机：

⚠️ 注意：value可以是字符串、整数、布尔值、null或嵌套JSON对象。为简化示例，我们只处理字符串类型。

3.1 代码实现

实现有限状态机其实很直接。核心接口设计如下：

public interface FiniteStateMachine {
    FiniteStateMachine switchState(CharSequence c);
    boolean canStop();
}
 
interface State {
    State with(Transition tr);
    State transit(CharSequence c);
    boolean isFinal();
}
 
interface Transition {
    boolean isPossible(CharSequence c);
    State state();
}

接口关系说明：

状态机维护一个当前State，并告知能否停止（即状态是否为终止态）
State包含可执行的转换列表（出向箭头）
Transition判断字符是否被接受，并提供下一个State

public class RtFiniteStateMachine implements FiniteStateMachine {

    private State current;

    public RtFiniteStateMachine(State initial) {
        this.current = initial;
    }

    public FiniteStateMachine switchState(CharSequence c) {
        return new RtFiniteStateMachine(this.current.transit(c));
    }

    public boolean canStop() {
        return this.current.isFinal();
    }
}

✅ 关键点：FiniteStateMachine实现是不可变的。这主要是为了让单例能被多次复用。

接下来是RtState实现。with(Transition)方法采用流式设计，添加转换后返回自身。State还负责判断是否为终止态（双圈状态）：

public class RtState implements State {

    private List<Transition> transitions;
    private boolean isFinal;

    public RtState() {
        this(false);
    }
    
    public RtState(boolean isFinal) {
        this.transitions = new ArrayList<>();
        this.isFinal = isFinal;
    }

    public State transit(CharSequence c) {
        return transitions
          .stream()
          .filter(t -> t.isPossible(c))
          .map(Transition::state)
          .findAny()
          .orElseThrow(() -> new IllegalArgumentException("Input not accepted: " + c));
    }

    public boolean isFinal() {
        return this.isFinal;
    }

    @Override
    public State with(Transition tr) {
        this.transitions.add(tr);
        return this;
    }
}

最后是RtTransition，负责检查转换规则并提供下一状态：

public class RtTransition implements Transition {

    private String rule;
    private State next;
    public State state() {
        return this.next;
    }

    public boolean isPossible(CharSequence c) {
        return this.rule.equalsIgnoreCase(String.valueOf(c));
    }

    // 标准构造方法
}

基于这套实现，你可以构建任何状态机。前文描述的算法用起来很简单粗暴：

String json = "{\"key\":\"value\"}";
FiniteStateMachine machine = this.buildJsonStateMachine();
for (int i = 0; i < json.length(); i++) {
    machine = machine.switchState(String.valueOf(json.charAt(i)));
}
 
assertTrue(machine.canStop());

完整实现参考测试类RtFiniteStateMachineTest中的*buildJsonStateMachine()*方法。⚠️ 注意实际实现比上图多了几个状态，用于正确处理字符串两端的引号。

4. 总结

有限自动机是验证结构化数据的利器。虽然它因处理复杂输入时容易变得繁琐（一个转换只能处理单个字符）而不太流行，但在检查简单规则集时依然高效。

如果需要更复杂的状态机操作，推荐两个库：

完整代码示例见GitHub仓库。

Persistence

REST

Security

1. 概述

2. 核心算法

3. 实战案例

3.1 代码实现

4. 总结