여기까지 왔다면 어휘분석기 구성의 중간단계까지 온 것이다.
먼저 패턴을 전이도라 불리는 정형화된 순서로 변환하는 것이 필요하다. 그리고 변환하는 과정에서 State 와 Transition라 불리우는 두가지의 개념으로 분해된다. 그렇기에 먼저, State(상태) 와 Transition(전이)가 무엇인지 살펴보도록 하자.
State (상태)
2개의 포인터를 사용해 어휘항목의 시작과 끝을 찾아낸다.
State 란 해당 그림에서 보여지는 상황처럼 LexemeBegin 포인터와 Forward 포인터 사이에 있는 문자들에 관해서 알아야 할 모든 것을 요약하는 것으로 생각할 수 있다.
State는 3가지의 형태로 구분되는데 Start Accepting Final 들이 존재한다.
Start: 분석의 시작점으로, 입력이 시작되기 전 상태이다.
Accepting: 어떠한 문자를 하나 이상 읽은 상태이다. 이 상태에서는Accepting State를 유지하거나,Final State로 전이할 수 있다.
Final: 패턴 매칭이 종료된 상태로, 패턴을 만족하는 입력이 완료되었음을 나타낸다. 또한 입력이 패턴 규칙을 벗어난 경우에도 해당된다.
Transition (전이)
State 변화의 동작또는 개념적 과정으로써 입력 조건에 따라 다른 상태로 이동하는 동작을 의미한다. Transition은 보통 Edge 와 Transition Condition을 결합한 논리적 개념으로 State가 Transition Condition 에 따라 다른 State으로 이동하는 동작이다.
Transition은 글로만 표현하기에는 어려우니 아래 시각적으로 표현한 전이도와 함께 설명하겠다.
전이도의 시각적 표현
전이도의 기본적인 해석
해당 그림은 토큰 𝑟𝑒𝑙𝑜𝑝 에 부합하는 어휘항목을 인식하는 전이도이다.
- 상태 0은 모든 입력의 시작점으로, 모든 토큰에 대한 공통적인 초기 상태 역할을 합니다. 하지만, 상태 0 자체는 입력을 분류하는 데 중점을 두며, 실제로 입력을 인식하고 반환하는 작업은 이후 상태들(예: 상태 1, 5, 6 등)에서 수행됩니다
- 어떤 상태는
AcceptingorFinal상태라고 불린다. 이 상태들은 실제로 𝐿𝑒𝑥𝑒𝑚𝑒𝐵𝑒𝑔𝑖𝑛 and 𝐹𝑜𝑟𝑤𝑎𝑟𝑑 포인터 사이의 모든 위치로 구성되지 않을지라도 어휘항목이 발견되었다는 것을 나타낸다. 항상Accepting State는 이중 원으로 나타내며, 만약 수행할 동작(전형적으로 토큰과 속성 값을 파서에 반환하는 동작 ==return( relop ,??))이 있다면 그 동작을 수락 상태에 부여한다.
여기서Accepting과Final상태의 관계의 혼동이 올 수 있는데 조금 더 디테일하게 설명해보자면,
Final State: 입력 스트림이 특정 패턴을 만족하여 입력 처리가 논리적으로 종료되는 상태를 의미한다. 이 상태는 입력 매칭이 끝난 상태이지만, 반드시 어떤 동작(예:return)이 이루어진다고 보장하지 않는다.Accepting State:Accepting State는Final State의 하위 집합이라고 볼 수 있으며, 패턴 인식 완료 후, 추가 동작(return등)이 명시적으로 수행되는 상태이다.
즉 모든Accepting State는Final State이지만, 모든Final State는Accepting State가 아니다. 토큰과 속성 값을 반환하는 구체적인 동작은Accepting State에서 이루어진다.
- 만약 𝐹𝑜𝑟𝑤𝑎𝑟𝑑 포인터를 한 위치 뒤로 물리는 것이 필요하다면(어휘항목이 수락 상태로 전이하게 했던 기호를 포함하지 않는다)수락 상태 옆에 *를 부가적으로 놓는다. 한 위치 뒤로 물리는 것이 결코 필요하지 않지만 만약 필요하다면 임의의 개수의 *를 수락 상태에 붙일 수 있다.(보통 ** 를 2개 이상 사용하는 것은 비효율적이라 잘 사용하지 않는다.)
State 1
첫 입력 기호로서 < 를 본다면, 𝑟𝑒𝑙𝑜𝑝 의 패턴에 부합하는 어휘항목 중에서 <, <> 또는<= 만 볼 것이다. 그러므로 State 1으로 진행하며 다음 문자를 본다. 그 문자가 =라면 어휘항목<=를 인식하고 State 2으로 진행하며, 속성 LE(특정 비교 연산자를 나타내는 기호 상수)를 갖는 토큰 𝑟𝑒𝑙𝑜𝑝 을 반환하게 된다.
만약 State 1 에서, 다음 문자가 > 라면 어휘항목 <>를 인식하고 State 3으로 들어가서 비동등 연산자가 발견되었다는 표시를 반환한다. 다른 문자에 대해서는 어휘항목 < 를 그대로 반환한다. 허나 State 4는 입력을 한 위치 뒤로 물려야 한다는 것을 나타내는 *를 갖고 있다는 것에 유의하여야 한다.
State 5
첫 입력 기호로서 =를 본다면, 이 문자가 바로 어휘항목이어야 하며 즉시 State 5로 이동하여 이 정보를 반환한다.
State 6
𝑟𝑒𝑙𝑜𝑝의 토큰에서의 마지막 가능성은 첫 문자가 > 인 경우가 남았다. 이 경우에서는 State 6으로 진입하며 다음 문자에 기초하여 어휘항목이>= 또는 단지 > 인가를 결정한다.
Except this...
만약 State 0 에서 < = 또는 > 이외의 문자를 본다면 𝑟𝑒𝑙𝑜𝑝 토큰의 어휘항목을 본다는 것은 불가능하다. 따라서 이 전이도가 아니라 다른 전이도가 사용 되어야 한다.
