Проверка входных данных с помощью Finite Automata на Java

1. Обзор

Если вы изучали CS, вы, несомненно, взяли курс о компиляторах или что-то подобное; в этих классах преподается концепция 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");
}

Мы говорим, что автомат “принимает” данный символ, если есть какие-либо стрелки происходит от текущего состояния, которое имеет символ на нем. Переключение состояний означает, что указатель следует и текущее состояние заменяется состоянием, на которое указывает стрелка.

Наконец, когда цикл закончен, мы проверяем, может ли автомат “остановиться” (текущее состояние дважды обведено) и что ввод исчерпан.

3. Пример

Давайте напишем простой валидатор для объекта JSON, чтобы увидеть алгоритм в действии. Вот автомат, который принимает объект:

Обратите внимание, что значение может быть одним из следующих: строка, интегратор, boolean, нулевой или другой объект 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();
}

Отношения между ними:

Государственная машина имеет один текущий Государственные и говорит нам, если он может остановиться или нет (если государство является окончательным или нет)
Государственные имеет список переходов, которые могут следовать (исходящие стрелки)
Переходный говорит нам, если символ принят и дает нам следующий государство

publi 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 . с (Переход) метод возвращает экземпляр после добавления перехода для беглости. Государственные также говорит нам, если это окончательный (двойной круг) или нет.

public class RtState implements State {

    private List 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));
    }

    // standard constructors
}

Вышеупомянутый код здесь . С помощью этой реализации вы должны быть в состоянии построить любую государственную машину. Алгоритм, описанный в начале, так же прост, как:

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. Заключение

Конечные автоматы являются отличными инструментами, которые можно использовать при проверке структурированных данных.

Тем не менее, они не широко известны, потому что они могут стать сложными, когда дело доходит до сложного ввода (так как переход может быть использован только для одного символа). Тем не менее, они велики, когда дело доходит до проверки простой набор правил.

Наконец, если вы хотите сделать более сложную работу с использованием машин конечного состояния, StatefulJ и белка две библиотеки стоит изсмотреть.

Вы можете проверить образцы кода на GitHub .