introduction to compiler design

[주의] 의역과 직역을 통한 해석 + 지식수준으로 인해 정확성이 떨어질 수 있음 

• Regular Expression and Nondeterministic Finite Automata

 

단어를 인식하는 것에는 regular expression이 존재하지만 nondeterministic nature한 특성 때문에 real machines에 적용하기에는 아직 거리가 있다. 

예를 들어 ((x, y) | (x, z)) 라는 regular expression이 존재한다고 할 때 x라는 문자를 인식하고 다음 콤마(,) 문자를 인식하고 나서 다음 어떤 문자를 인식해야 할지 결정짓지 못하기 때문이다. 

 즉, 위 식은    x 뒤에 문자열을 입력하여 입력을 받아 들일 수 있는 방법은 2가지가 되기 때문이다. 

          , ⇨ y

    ⬀

x

      ⬂

            , ⇨ z

 

이러한 Nondeterministic Finite Automata를 Deterministic Finite Automata로 변경하는 것이 목표이다. 

 

Nondeterministic Finite Automata(이하 NFA)는 주로 UI적으로 설명된다. 

 

State와 Transition으로 이루어지는데 State에는 Initial State와 Accept State가 존재하고 입력에 따른 Transition이 존재한다. 

 

Initial State는 처음 시작의 State이고 Accept State는 입력이 끝났을 때 도달해야 하는 State이다. 

 

이러한 NFA는 successful path를 찾을때까지 Backtracking을 하거나 accept state에 도달하기 까지 transition할 수 있는 모든 경우의 수를 찾기 때문에 time-consuming측면에서 매우 크다 

 

그럼에도 불구하고 NFA는 regular expression에서 DFA의 stepping stone(디딤돌) 역할을 하며 

 

DFA로 변환하는 과정을 손쉽게 만든다. 그럼 이제 regular에서 nfa로의 변환과정에 대해 알아보자 

 

 

• Converting a regular expression to an NFA 

 

 

regular expression을 NFA로 정확하게 구성하기 위해서는 해당 regular expression의 subexpression의 내용을들을 각 각의 NFA(nfa fragment)로 변환한뒤 연결(결합)하면 완성된 NFA가 나오게 된다. 

 

각 각의 NFA Fragment는 State와 Transition으로 완전하지 않은 형태를 이루게 되는데 

 

하나의 State에 들어오는 transition과 나가는 transition이 있다면 들어오는 transition에 대해서는 Label되어 있지 않지만 나가는 transition에 대해서는 label이 되어있다(어떤 입력으로 transition이 되는지) 

 

이런식으로 subexpression에 대한 NFA Fragment를 만들고 전제 regular expression에 대해 NFA Fragment들을 결합하여 구성하면 된다. 

 

NFA는 여러개의 Accpeting State를 가지는 것을 허용한다. 

 

 

• Optimisations 

 

s+ 는 ss* , [0-9]는 0|1|2 ... |9의 shorthand한 것들이다. 이들을 shorthand하지 않고 그냥 쓴다면 엄청나게 큰 NFA를 맛볼 수 있기에 최적화된 몇 몇들을 사용한다. 

 

예를 들어 [0-9]+ 라는 regular expression이 있다. 이를 NFA로 나타내면 

 

 

 

 

• Deterministic finite automata 

지금 까지 언급한 NFA들은 the machine에 근접하지 않음을 언급했고 따라서 우리는 좀 더 제한된 형태의 Finite Automaton이 필요하다. 즉 Deterministic Finite Automaton임을 의미한다. 

DFA가 필요한 이유는 앞서말했듯이 lexical analyser의 과정 중 하나인 regular expression의 과정에서 regular expression은 Nondeterministc한 점을 언급했다. a*(a|b)의 형식의 regular expression이 존재한다고 할 때 이 regular expression은 

 

이렇게 나타낸다. 즉 2번 State에서 a의 입력에 따라 1번 State로 갈지 3번 State로 가서 Accept할지 컴터의 판단으로는 할 수 없다는 것이다. 그래서 이러한 Nondeterministic을 Deterministic으로 변경해야함을 의미한다. 

DFA를 NFA라고 부를 수는 있지만 몇가지의 제한 사항이 붙는다. 

1. 엡실론 전환(Epsilon-transition)이 존재하지 않는다. 

2. 하나의 State에 두개 이상의 동일한 transition이 이루어지면 안된다. 

위의 조건을 정리하자면 DFA는 하나의 State에 대해 하나의 입력이 주어진다면 이 입력에 대해 다음 State의 전환에 있어 하나의 선택이 주어짐을 의미한다. 즉, Deterministic하다는 뜻이다. 

State의 전환에 관계에 있어 종종 함수처럼 쓰이곤 한다. 

예를 들어 move(s,c)라는 함수가 있을 때 State s로부터 c라는 transition이 발생했음을 의미한다. 

NFA를 DFA로 바꿨을 때 그 결과는 지수적으로 증가할 수 있다. 하지만 대부분의 Lexical Analysers들이 dfa를 사용하는 이유는 그 증가량이 그렇게만은 크지 않기 때문이다. 

 

• Converting an NFA to a DFA 

 

DFA가 뭔지 알았으니 nfa를 dfa로 바꿔볼 것이다. ?

DFA는 NFA에서 모든 Transition이 도달 할 수 있는 집합 중 하나이다. 

NFA를 DFA로 바꾼다는 의미 자체는 어떤 input string이 나왔을 때 나올 수 있는 NFA의 요소들로 적절한 DFA의 State를 찾는다는 것이다. => Subset Construction Alogorithm

만약 Transition에 Epsilon이 포함되어 있다면 복잡해 지긴하지만 DFA를 구해낼 수 있다. 

일단 NFA에서 epsilon-transition만을 이용해서 각 각의 State들이 어떤 Set을 이루는지 확인할 필요가 있다. 그런다음 가능한 각 입력 기호를 넣어 도달 할 수 있는 State에대해 새로운 Set을 만든다. 

처음 epsilon transition을 이용하여 도달 가능한 State로 set을 구하는 것을 Epsilon-closure라고 정의한다. 

 

• Definition - Epsilon-closure
  

NFA State의 M이 주어진다면 우리는  ε-closure(M) 이라고 정의한다. 이는 집합 방정식의 해가 된다. 

ε-closure(M) = M∪{ t | s ∈ ε-closure(M) and s^ε t ∈ T  }

T는 NFA에서 transition할 수 있는 Set을 의미한다. 

즉, epsilon-closure는 세트의 M상태에서 임의의 epsilon transition으로부터 취할 수 있는 State의 Set을 의미한다. 

epsilon transition이 없는 NFA의 경우 δ(q,a)를 a로 표시된 transition을 취하여 q에서 도달 가능한다 State Set을 정의한다. 

 

어떤 사이트를 보면서 책의 내용들은 공식을 증명하기위해 좀 형식적인 내용이 많다고 한다. 실제로 epsilon-closure의 개념은 매우 간단하다...(어떠한 State에 있어서 epsilon transition으로 전환이 가능한 모든 State의 Set...)