[컴파일러설계] 3. Lexical Analysis - 2

Thompson's construction(RE → NFA)

 

Thompson's construction algorithm은 자동으로 RE를 NFA로 변환한다. 이 알고리즘은 RE를 가장 단순한 요소로 나누고, 그 요소에 해당하는 NFA를 만들어 결합해 나감으로써 최종적인 NFA를 생성한다. 결합은 ε 전이를 통해 이루어질 수 있다. 저번 글에서 RE를 정의하기 위한 5가지 규칙(a, ε, concat, alteration, closure)에 대해 알아보았다. 이에 대한 NFA는 아래와 같다. 

 

기본 규칙에 대한 NFA

Exercise

Q. (+|-)?d⁺에 대해 NFA를 생성하라. 

A. (+|-)?, d, d^*에 대해 NFA를 만들고 ε로 이어준다. 

 

 

Subset construction(NFA → DFA)

 

NFA를 만들었으니, 이제 이를 DFA로 변환해야 한다. 가장 집중해야 할 점은 non-deterministic trainsition을 어떻게 없앨 것인지이다. NFA에서는 ε 전이를 사용해 multiple trainsition을 다루었지만, DFA에서는 이런 방법을 사용할 수 없다. 우리는 subset construction algorithm을 사용하여 목적을 달성할 수 있다.

 

이 알고리즘의 기본 개념은 DFA의 각 state는 NFA의 여러 state를 묶은 집합일 수 있다는 것이다. NFA에 0, 1, 2라는 state가 존재한다면, DFA의 state는 0/1/2, 1/2와 같은 형태로 이루어질 수 있다. 여기서 포함하는 집합 중 하나라도 accepting state라면 DFA에서도 accepting state로 취급한다. ε 전이를 처리하기 위해선 아래와 같은 연산을 사용할 수 있다. 

 

• ε-closure(s) : 단일 state s에서 ε 전이를 통해 도달할 수 있는 모든 state의 집합 
• ε-closure(T) : 집합 T에 있는 state s에 대해 ε-closure(s)의 합집합 
• move(T, a) or Δ(T, a) : 집합 T에 대해 input symbol a로 도달할 수 있는 모든 state의 집합 

 

연산을 사용한 변환 과정에 관한 설명은 아래 Exercise로 대체한다. 

Exercise

Q. 아래 NFA를 DFA로 변환하라. 

A. NFA의 start state(0)에서 ε-closure(0)를 구한다. 그 후 Δ(ε-closure(0), a), Δ(ε-closure(0), b)를 구해 새로운 state를 생성한다.(input symbol로 도달할 수 있는 state 집합) 이 때 이미 존재하는 state라면 추가하지 않으며, 이 과정을 반복하여 모든 state를 처리한다. 만들어진 state를 DFA의 state로 사용할 수 있다. 

 

 

이렇게 만들어진 DFA는 최적화가 필요할 수도 있는데, 일부 DFA는 동일한 행동을 하는 state가 중복으로 나타날 수도 있기 때문이다. state가 많아지면 table size에 영향을 미치고 메모리를 차지하여 성능에 문제가 생길 수 있다. 만약 두 state가 input symbol에 대해 똑같은 state로 전이된다면, 구분할 수 없다고 보고 병합해야 한다. 이를 위해 다음과 같은 반복적인 절차를 거칠 수 있다. 

 

• Step 1. state를 두 개의 집합으로 나눈다.(non-accepting & accepting states)
• Step 2. 각 집합에 대해, state 쌍이 구별 가능한 경우, 다른 집합으로 나눈다.(두 state i, j가 구별 가능하다면 Δ(i, a)와 Δ(j, a)가 다른 집합에 존재해야 한다.)
  • 아래 예시에서 0, 3은 a에 대해선 non-accepting state로, b에 대해선 accepting state로 가는 것을 확인할 수 있지만 5는 a, b 둘 다 모두 non-accepting state로 향한다. 따라서 0, 3과 5를 구분할 수 있다. 
• Step 3. 집합의 변화가 없을 때까지 Step 2를 반복한다. 
• Step 4. Step 3을 기준으로 병합한다. 

 

DFA Optimization 예시

 

여러 개의 RE에 대해서는 모든 RE의 NFA를 하나의 NFA로 결합하고, 이를 DFA로 바꿈으로써 이루어질 수 있다. 해당 DFA에 대한 token matching rule은 다음과 같다.

 

• final(accepting) state에 도달했다면, 그 state에 해당하는 token을 연결짓는다.
• final state에 있을 때, 더 이동할 수 있는 경로가 있는지를 확인한다.
• 만약 여러 개의 token과 연결된다면, 우선순위에 따라 어떤 token을 선택할지 결정한다. 

 

지금까지 lexical analysis에 대해 알아보았다. 다음 글에서는 syntax analysis에 대해 다룰 예정이다.