1. 개요
CS를 공부했다면 의심할 여지 없이 컴파일러나 이와 유사한 과정을 수강했을 것입니다. 이 수업에서는 Finite Automaton(Finite State Machine이라고도 함)의 개념을 가르칩니다. 이것은 언어의 문법 규칙을 공식화하는 방법입니다.
여기 와 여기 에서 주제 에 대해 자세히 읽을 수 있습니다 .
그렇다면 이 잊혀진 개념이 새로운 컴파일러 구축에 대해 걱정할 필요가 없는 고급 프로그래머에게 어떻게 도움이 될 수 있습니까?
이 개념은 많은 비즈니스 시나리오를 단순화하고 복잡한 논리를 추론할 수 있는 도구를 제공합니다.
빠른 예로 외부 타사 라이브러리 없이 입력을 확인할 수도 있습니다.
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 개체에 대한 간단한 유효성 검사기를 작성해 보겠습니다. 다음은 객체를 받아들이는 자동 장치입니다.
값은 문자열, 정수, 부울, 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();
}
그들 사이의 관계는 다음과 같습니다.
- 상태 머신은 하나의 현재 상태를 가지며 중지할 수 있는지 여부를 알려줍니다(상태가 최종인지 여부).
- 상태 에는 따를 수 있는 전환 List이 있습니다(나가는 화살표).
- 전환 은 캐릭터가 승인되었는지 알려주고 다음 상태를 알려줍니다.
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) 메서드는 유창함을 위해 전환이 추가된 후 인스턴스를 반환합니다. 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;
}
}마지막으로 전환 규칙을 확인하고 다음 State를 제공할 수 있는 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 에서 코드 샘플을 확인할 수 있습니다 .
