[Compiler] Finite Automata

 이전 포스트에서 계속 다룬 내용은 Compiler 의 동작 수행시 가장 먼저 이뤄지는 Lexical Analysis 이 뭔지를 살펴보고, Regular Expression을 통해서 코드 상의  string을 뽑아낼 수 있는 것을 보았다. 이렇게 살펴보면 사람이 작성한 코드는 무척이나 많은 요소들로 구성되어 있는 것을 알 수 있다. 먼저 alphabet들이 있을 것이고, 그 alphabet으로 구성된 string이 있을 것이다. 그 중 의미를 지닌 keword도 들어갈 수 있다. 또는 어떤 연산을 위한 Number도 들어가 있고, Operator, Bracket, Whitespace 등등이 사람이 작성한 코드에 적어도 하나씩 포함되어 있다. 그러면 이전 포스트에서 말한 Regular Expression 방법을 적용해보면 코드상에서 뽑아낼 수 있는 단어는 분명 위에서 언급한 요소들 중에 하나라고 할 수 있고, 각각 Regular Expression의 Union에는 포함되어 있을 것이다. 

Regular Expression L(R) = L(Keyword) | L(Number) | L(Identifier) | L(Operator) | ....

 그러면 우리가 만약 else라는 단어를 위의 Union으로부터 찾으려면 어떻게 해야 될까? 가장 쉬운 방법은 첫글자부터 하나씩 Regular Expression으로 부터 찾아내는 것이다. 즉, else의 "e" 부터 찾아내고 찾아낸 다음 부터는 "e"를 삭제하고 다음글자인 "l"을 찾아가게끔 할 것이다. 그러면 특정 pattern속에는 else가 나타내는 의미가 정의된 부분이 있을 것이고, 이부분을 parse할 수 있도록 넘겨주는게 여기서 할 수 있는 역할일 듯 하다. 하지만 이 과정이 "단순하게" 생각해서 적용가능한 것이지 실제로는 조금더 생각해봐야 한다. 만약 elsewhere 라는 단어를 Regular Expression을 통해서 찾으려면 어떻게 해야 될까..

 여기서 ambiguity가 발생한다. 분명 else를 찾는 과정은 똑같은데 문제는 뒤에 있는 where에 대한 처리는 어떻게 하냐는 것이다. 컴파일러의 Lexical Analysis가 잘못되면 이걸 조건문의 Keyword로 인지할 수 있고, 또는 사용자가 임의로 정의한 identifier로 인지할 수 있을 것이다. 이런 경우는 몇가지 예시를 찾아볼 수 있다.

- Identifier vs Identifier ex) tmp / tmp1

- Keyword vs Identifier ex) else / elsewhere

- operator vs operator ex) = / ==

사실 Lexical Analysis 의 알고리즘에선 이런 Ambiguity를 해결하는 몇가지 규칙들이 정의되어 있다. 그중 두가지만 소개해보자면 첫번째는 longest match이다. Dragon book에는 Maximal munch라는 이름으로 소개되어 있는데 이방법은 그냥 간단하게 갈때까지 가보는 것이다. else와 elsewhere는 else 뒤에 Empty String이 나오는지 안나오는지의 차이에 따라 구분할 수 있다. 그냥 else만 찾았다고 해당 구문을 parse 하는게 아니라 뒤에 나오는 alphabet에 대한 검색도 계속 진행되는 것이다. 물론 elsewhere라는 string이 따로 keyword로 지정되지 않았다면 그냥 Identifier로 구분될 것이다. 즉, 분석을 최대한 해보자는 게 Maximal Munch의 취지이다. 

 다른 방법은 Priority Ordering을 지정하는 것이다. 나는 개인적으로 이걸 계층적 트리로 놓고 보면 어떨까 하는 생각을 해본다. 

먼저 else라는 단어는 찾고나면 분석하다가 가장 ordering이 높은 Expression에 의미를 부여하는 것이다.

이런식으로 몇가지 방법을 적용해보면 Lexical Analysis 시에 발생할 수 있는 모호성을 조금이나마 해결할 수 있다. 물론 이런 규칙이 있음에도 해당되지 않는 구문이 있다면 컴파일러는 인지하지 못할 것이다. 우리가 보통 프로그래밍할 때도 왠만한 string은 keyword나 Identifier로 분류하겠지만, 진짜로 생뚱맞은 @$AB_2131ksf 같은 string은 변수로도 삽입하지 못하고 컴파일러는 에러를 출력할 것이다. 물론 이걸 표현하는 컴파일러의 반응은 제각각일 수 있다. 쿨하게 error 메세지를 출력할 수도 있겠지만, 진짜 꼼꼼한 컴파일러라면 이런 상황도 분석을 하고 해당 rule을 정의했을 수도 있다. 하지만 흔하지는 않은 경우이기에 앞에서 언급한 Priority Ordering과 겹치지 않게 가장 후순위에 정의가 되어 있을 것이다.

 자 지금까지 lexeme를 분리하고 처리하는 방법을 소개해봤다. 이걸 코드로 구현해보라고 하면 감이 잡힐까? 적어도 나는 아직도 이해가 가지 않는다. 프로그래밍도 어차피 사람이 만든 이상 사람의 readability를 고려해서 만들어졌을 것이고, 그러면 기본적으로 사람의 언어와 비슷한 형식을 갖출 것이다. 요즘도 국립국어원에서도 매년 신조어에 대한 발표를 하다시피 언어는 조합해서 만들수도 있고, 그 표현 방식이 정말로 무궁무진하다. 이걸 과연 코드로 일일히 구연할 수 있을까? 하는게 내가 가진 궁금증이었다. 

 사실 이걸 이해하는 기본적인 전제가 바로 모든 string이 Finite하다는 것이다. 물론 사람에 따라서는 string을 괴상망측하게 나열할 수 있겠지만, 그런 특수한 경우를 제외하면 모든 string이 Finite 하다는 전제하에 분석하는 것이다. 당연히 어떤 Pattern을 사전에 정의하고 기기의 힘을 빌어 분석하면 기기의 컴파일러는 state에 따라서 string을 추출할 수 있을 것이다. 일일이 case를 나눌 필요가 없이 말이다. 이런 방식을 Finite (state) Automata 라고 하는 거 같다. 

FA의 수행 방식에 따라서 DFA냐 NFA로 나눌 수 있는데 이 부분은 다음 포스트에서 정리해본다.

PS0: Automata를 부르는 말이 참 많다. 나도 처음 일본말인 줄인데 알고보니까 라틴어에서 파생되었다..

PS1: 왜 우리나라 번역서는 굳이 번역하기 힘든 단어를 한자로 억지로 번역하는지 모르겠다. 처음에 결정식 유한 자동자라고 해서 뭔가 했는데 Deterministic Finite Automata를 번역한 것이었다. 오히려 원문 그대로 표현하면 조금더 이해하기 쉽지 않았을까 하는데...