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

1. Обзор

Если вы изучали CS, вы, несомненно, прошли курс по компиляторам или что-то подобное; на этих занятиях преподается концепция конечного автомата (также известного как конечный автомат). Это способ формализации правил грамматики языков.

Подробнее о теме можно прочитать здесь и здесь .

Так как же эта забытая концепция может быть полезна нам, программистам высокого уровня, которым не нужно беспокоиться о создании нового компилятора?

Что ж, оказывается, эта концепция может упростить множество бизнес-сценариев и дать нам инструменты для рассуждений о сложной логике.

В качестве быстрого примера мы также можем проверить ввод без внешней сторонней библиотеки.

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, чтобы увидеть алгоритм в действии. Вот автомат, который принимает объект:

Обратите внимание, что значение может быть одним из следующих: строка, целое число, логическое значение, нуль или другой объект 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 . Метод with(Transition) возвращает экземпляр после добавления перехода для беглости. Состояние также сообщает нам , является ли оно окончательным (обведено двойным кружком) или нет.

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

    // 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 и squirrel .

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