앞에서 언어의 문법을 표현하는 수학적 표현(수식)을 보았다. 마찬가지로 단어의 Pattern(무늬)를 표현하는 수식을 만들 수 있다. 이름하여 거창하게 Regular Expression!(정규/정식/표준 수식)이라고 부르지만 우린 용어에 관심이 없으니 무시하고, 그냥 단어 표현 수식이라고 한다. 이런 수식이 만능은 아니다. 괄호와 같이 앞뒤에 짝으로 나타나는 글자가 있는 경우는 표현할 수가 없다. 또한 If ~ then ~ else ~ 같은 것도 3개 단어가 짝을 이룬다. 이런 것은 표현할 수 없다. 이런 것을 처리하려면 기억 능력이 있어야 하지만, 정규식 수식으론 기억능력을 표현하기 어렵다.(^^) 그러니까 중첩이 되어 여러 번 나타나는 가변적인 상황에 대한 대응이 되지 않는다. 그냥 고정적으로 한 번 나타나는 경우는 표현할 수가 있다. 왜 이런 수식을 쓰냐 하면 사람들이 생각을 명확하게 하는데 도움이 되기 때문이다. 그래서 항상 설명할 때는 <수식-그림-코드> 이렇게 3 가지가 쌍으로 나온다. 우린 항상 구체적 예제와 그림과 실제 코드 3가지를 분석해서 공부한다. 그것이 가장 쉽다. 설명을 읽으면 시간도 많이 소모되고 이상하게 미궁 속에 빠져든다. 정규식과 문맥 자유 문법의 정확한 차이가 뭘까? 겉으로 보면 모두 비슷한 모양을 하고 있다. 왼쪽은 문형의 이름이고, 화살표가 중간에 하나 있고, 우측은 구체적인 문형의 나열이다. 중첩 구조를 표현할 때는 우측에 좌측 문형 이름이 반복되어 나타나면 된다. 그래서 정규식과 문맥자유문법의 구분을 하지 않겠다. 이렇게 하면 문맥 자유 문법은 중첩 괄호를 처리할 수 있는데 정규식은 안 된다는 약간 이상한 설명을 하지 않아도 될 것 같다. 불가능은 없다. 모두 섞자!
드디어 상태변화도가 나왔다. 튜링 머신에 대한 설명을 해야 하겠지만 생략한다. 간단하게 설명하면 상태 변화도란 교차로를 말한다. 어떤 교차로에 들어가서 어느 길로 갈지를 주사위를 던져 결정한다고 하자! 그럼 그 결과에 따라 다음 교차로로 진입한다. 바로 이와 같은 것이다. 여기서 주사위를 던져 나오는 숫자는 입력되는 글자나 단어이다. 그 글자와 단어에 따라 다음 교차로인 다음 상태로 진입한다. 각 상태를 이동하면서 결국 최종 종착점에 도달하는데 그 종착점을 보고 어떤 문형인지 결론을 내리는 것이다. 이와 같이 상태를 이동하면서 뭔가를 처리하는 기계, 즉 현재 상태만 기억하는 복잡한 상태 이동 도로망으로 되어 있는 기계를 튜링 머신이라고 부른다. 이런 상태 변화도를 이용하면 상당히 복잡한 프로그램도 쉽게 작성할 수 있다. 좋은 아이디어이니 깊이 기억한다.
앞에서 설명한 바와 같이 <수식-그림-코드> 순으로 단어 분석이 어떤 것인지 간단하게 소개를 한 것이다. 수식이나 그림이 눈에 익지 않았다면 코드를 바로 분석하면 더 감각이 확실하게 생길 것이다. 이 글자 다음엔 요 글자, 요 글자 다음엔 저 글자, 저 글자 다음에 그 글자. 이런 식으로 계속 상태를 바꾸면서 Pattern(무늬)를 찾는 것이다. 이런 능력은 특히 숫자를 분석하는 부분에서 특별하게 강력하다.(^^) Ch2에서도 문맥 자유 문법이라는 수식 같이 생긴 것에서 분석 나무 그림을 그렸었다. 그리고 코드를 작성하였다. 같은 방식의 설명이다. 여기까지 내용으로도 단어 분석의 기본 개념은 잡은 것이다. 상태를 이동하는 개념을 코드로 어떻게 구현했는지 보라! 이 방법만 있는 것은 아니다.
그 다음 내용에 보면 단어 분석기를 만들어주는 프로그램 언어가 있다고 한다. 즉, 기계로 기계를 만들 듯이 프로그램으로 프로그램을 만든다. 컴퓨터 언어로 컴퓨터 언어를 만드는 것이다. 이 언어에 대한 설명이 나오는데 시간 많으면 읽어 봐라. 기본 개념만 이해하고 넘어가려고 해도 시간이 없어서 이것은 뺀다. 아무리 어려운 게임과 응용프로그램이 있더라도 모두 도구가 있기 때문에 쉽게 만들 수 있는 것이다. 전문 분야에서 전문가에게 전문 도구 사용법을 교육 받아서 만들면 된다. 비행기/배/자동차 만드는데 망치와 톱으로만 만들 수는 없지 않은가?
다음에 아주 일반적인(수학적인) 방법이 설명되는데 다시 말해서 비구체적이라 어떤 언어와도 무관한 내용이다.(^^) 단지 앞의 상태 변화 그림을 처리하는 기계적인 방법을 설명하는 것이다. 여기 Automata[어타~머터](자동기계)라는 단어가 나온다. 상태 변화 그림 그 자체가 바로 Automata[어타~머터]다. 한국에선 한자를 써야 개 폼이 나듯이 영어 권에선 라틴어를 써야 똥 폼이 난다. 이런 단어를 써도 그 뜻은 그냥 자동 처리 기계란 뜻이다. 어떤 문법에 대한 상태 변화 그림을 그려서 완성했다면 바로 자동 기계(컴퓨터 프로그램)가 완성된 것이기 때문이다. 다른 말로 말하면 구체적인 절차와 방법이 만들어지면 자동기계로 만드는 것은 쉽다. 이제부터는 약간 어려워진다. 정신 차리자!
명칭 NFA, DFA에서 앞의 N/D는 미래(결과)가 결정되느냐 애매모호하냐에 따라 붙인 이름이다. 아무 입력이 없어도 이리 갔다 저리 갔다 할 수 있고, 같은 입력이라도 이쪽으로 갈지 저쪽으로 갈지 모르니까 비결정적이라고 표현한 것이다. 중간에 Finite(유한하다)가 붙은 이유는 모르겠다. 무한한 것도 있나 보지? 아마도 도로망의 크기가 유한하다는 뜻일 것이다. 요점은 문법을 나타내는 수식에서 바로 상태 변화 그림(자동 기계 동작 흐름도)을 그리고 이것에서 애매모호함을 제거하는 것이다. 다음 설명에는 애매모호함을 제거하는 방법이 나온다. 상태 변화 그림은 사람이 볼 때는 그림이지만 컴퓨터가 볼 때는 표가 된다. 그래서 배열을 처리하는 프로그램으로 상태 변화를 추적하는 것을 할 수 있다. 상태 변화도를 구현하는 방법은 많다. 함수, 다중 선택문, 배열(표) 검색 등 다양하다. 창조성을 발휘해 보도록! 히히!
예) 다음 상태 = 함수 (현재 상태, 입력 값)
예) 다음 상태 = 배열 (현재 상태, 입력 값)
책에는 설명이 좀 어려운 것 같다. 위의 그림을 잘 보면 쉽게 이해가 될 것이다. 이 NFA에서 DFA 변환 과정을 컴퓨터 프로그램으로 작성해서 찾아 내게 된다. 이 상태 변화 그림은 바로 표와 같다. 표는 바로 배열과 같다. 배열에서 (Row, Column) 또는 (X, Y)가 들어오면, 즉 (현재상태, 입력문자)가 들어오면 Z값(다음 상태)을 찾아서 추적하는 프로그램을 작성하면 된다. 이것은 아주 쉬운 것이라 설명하지 않겠다. 이렇게 하여 임의의 어떤 문법이 주어지더라도 자동 처리하는 절차를 완성할 수 있게 되었다. 정규식(단어 표현식)에서 NFA를 구성하는 법은 책의 설명이 좀 어렵다. 추상적인 규칙 설명보다는 구체적인 예제를 보는 것이 더 쉽다. 책의 예제는 앞에 그림과 동일하다. 일단 정규식에서 이 중간단계의 NFA가 만들어지면 여기서 DFA로 바꾸면 된다. 책의 내용에 NFA로 프로그램을 작성하면 기억장소는 적게 필요하나 처리 시간이 늘어나고, DFA로 프로그램을 작성하면 기억장소가 많이 필요하지만 처리 시간은 짧아진다고 한다. 당연한 얘기다. NFA는 “저쪽이다” 하고 가 보니 “아니네” 하고 다시 뒤로 돌아오는 과정이 필수적으로 들어간다. DFA는 선택할 것이 없이 확실하다. 그림을 보면 알겠지만 정규식이 And, Or 형태로 분석할 수 있고, Or 형태는 NFA의 병렬로, And 형태는 NFA의 직렬로 표현된다. 책에서는 설명을 위해서 이런 이상한 정규식을 만든 것 같은데 실제 우리가 사용하는 컴퓨터 언어에서 이런 경우를 만날 수 있을까? 현실성에서 아주 많이 벗어난 예제 같다는 생각이 든다. 예를 들어 시작은 a~z까지의 문자가 마구 섞여 나타나다가 마지막에는 abb라는 접미사로 끝나는 단어라고 하자! 위의 예제는 이와 같은 것을 나타낸다. 그러나 이런 식의 단어는 컴퓨터 언어에선 거의 사용하지 않는다. 그리고 설사 이런 단어를 사용하더라도 그냥 단어의 끝부분부터 거꾸로 3글자만 해석하면 답이 나온다. 단어를 첫 글자부터 순서에 따라 판독하라는 법은 없으니까! 방법이 하나만 있는 것은 아니다. 여하튼 개념은 뭔지 알 것이다.
이 그림에는 단어 분석기의 구조와 정규식에서 NFA를 구성하고 NFA를 이용해서 단어를 검색하는 과정과 NFA에서 DFA로 바꾸는 과정이 모두 나와 있다. 앞의 그림들과 같지만 표기가 좀 다른 것뿐이다. NFA나 DFA 모두 상태 변화 표를 만들어서 검색하는 것이 실제 프로그램으로 구현하는 방법이다. 이 그림을 잘 이해하면 내용을 모두 이해했다고 할 수 있다. 대부분 실제 컴퓨터 언어에선 단어(ID)란 영문자로 시작하고 그 다음은 영문자나 숫자 조합이며 길이가 정해져 있다. 그래서 이렇게 복잡한 방법으로 단어 분석기를 작성할 필요가 없다. 이런 기술은 문서 편집기에서 사용된다. 다음 내용은 좀 어려운 설명이 나온다. 위의 그림을 보면 NFA의 경우는 일치하는 후보 상태가 여럿이 있다. 그래서 입력을 보고 이 중에 어떤 상태인지 점차 좁혀 나가는 형태를 하고 있다. 즉, 여긴가? 아니네! 이런 식으로 찾아 가는 것이다. 이를 피하려면 NFA를 DFA로 바꾸어야 한다. 포트란의 경우는 옛날에 공백을 사용하지 않았다고 한다. 그러니 IF가 하나의 독립된 단어인지 다른 단어의 접두사로 시작하는 부분인지 구분해야 할 필요가 있었다. IF 다음에 괄호 같은 이질적인 것이 나타나면 이 놈은 IF이지만 계속 영문 글자로 이어지면 그냥 보통 단어일 수도 있는 것이다. 이 문제를 해결하는 쉬운 방법은 띄어 쓰기를 하면 되도록 문법을 고치는 것이다. 아주 쉽다. 그냥 문법을 고치면 된다.(^^)
앞에서 본 바와 같이 NFA를 DFA로 만드는 방법이 비슷하나 약간 다르다. 먼저 정규식에서 나무그림을 그린다. 이것은 Ch2에서 본 바와 같이 정규식을 수식으로 보고 그리면 된다. 이렇게 하면 상태 변화 그림에서 중요한 부분이 숫자로 표현되고 이것을 중심으로 DFA로 변환하면 된다. 어찌해서 이렇게 되는지는 설명하지 못 하겠다. 내가 그린 것이지만 나도 잘 이해가 안 된다. 그림을 보고 계속 연구하면 답을 얻을 수 있을 것이다. 앞에서도 말 했지만 실제 컴퓨터 언어에서 사용하는 단어는 접미사를 사용하지 않는다. 접미사를 구분할 필요가 없어서 이런 문법 사용하지 않을 것이다. 오히려 사람들이 사용하는 단어에서 이런 접미사를 볼 수 있겠으나 사람들이 사용하는 단어에서는 띄어 쓰기를 하기 때문에 이런 복잡한 문법이 필요 없을 것이다. 영어를 띄어 쓰기 하지 않으면 어떻게 문장을 읽고 어떻게 단어를 구분하겠는가! 사람도 하기 힘들 것이다. 멍청한 컴퓨터가 어떻게 하겠는가!
이 그림도 앞과 매우 비슷하다. 일단 정규식에서 나무그림을 그린 다음 위치번호를 주는 것은 같다. 그 다음 각 위치번호에서 가장 앞에 올 수 있는 위치번호와 가장 뒤에 올 수 있는 위치 번호들을 구한다. 그리고 각자의 바로 다음에 올 수 있는 위치번호를 구한다. 그리고 이 위치 번호들을 모아서 바로 DFA를 그리는 방법이다. 정규식 나무그림의 가장 뿌리 부분을 보면 가장 처음과 가장 끝의 위치 번호들이 나온다. 시작과 끝이 나온 것이다. 그 다음 중간은 각자의 바로 다음에 나올 위치 번호들을 이용해서 만들어가는 것이다. 나도 원리는 잘 이해되지 않는데 그림을 보고 자꾸 연구하면 알 수 있지 않을까? 앞에서 예측 문법 다룰 때 구체적인 첫 단어 조사하는 것과 비슷한 것 같다. 즉, 처음에 나타날 수 있는 것과 마지막이 될 수 있는 것과 중간의 상태를 그 다음에 나타날 것들을 서로 연결한 것인데 충분히 상상할 수 있는 방법이다.
앞의 것과 역시 비슷한 내용으로, 정규식에서 NFA를 그리고 NFA에서 DFA를 만들고 여기서 DFA를 줄이는 방법이다. 책의 설명이 약간 난잡하고 어려워서 예제 그림을 보고 이해하자. 원리는 잘 모르겠다. 설명이 상당히 애매모호하다.(^^) 내가 머리가 나쁜 것인가? 상태들을 구분하는 기준이 명확하게 이해되지 않는다. 처음엔 종료상태와 그렇지 않은 것을 구분한다. 그 다음은 어떤 문자가 들어왔을 때 다른 상태들과 구분되는 상태를 찾는 것인데 그 구분하는 기준이 좀 어렵다.(^^) 그림을 보고 그냥 직관적으로 이해하기 바란다. 이렇게 어렵게 설명하는 책은 별로 많이 본 적 없다. 좋은 책이 아니다. 계속 NFA와 DFA를 가지고 놀고 있다. 이론적인 관심과 현실은 많이 다를 것인데? 그냥 바로 DFA를 직관적으로 만드는 것이 낫겠다. 설명이 어렵다. 허허! 다시 볼 일 없었으면 좋겠군!
상태 변화도는 바로 상태 변화표이다. 상태변화표는 바로 2차원 배열로 구현할 수 있다. 그런데 이렇게 하면 배열이 너무 커진다. 영문자, 숫자, 기호 합하면 128개 정도 된다. 거기에 상태가 10개만 되어도 1천 개의 공간이 필요하다. 그래서 좀 더 현실적이게 만드는 방법이라고 저자가 소개한 것이다. 1차원 배열 2개를 이용하는 방법이다. 먼저 현재 상태에서 주소를 찾고 그 주소에 입력 문자를 더하면 다음 상태의 위치가 나온다. 아주 간단하니 이해는 쉬울 것이다. 여기 방법 말고도 다른 방법 많이 만들 수 있을 것이다. 이것은 어려운 것이 아니고, NFA에서 DFA 만드는 것이 어렵군!
이렇게 하여 단어 분석기 만드는 이론을 끝낸다. 생각보다는 매우 복잡하고 단어 분석기 만들려면 전문적으로 이것을 만들어주는 도구인 컴파일러가 필요하다. 즉, 프로그램을 프로그램으로 만드는 것이다. 그러니 원리만 알아두고 실전에선 단어분석기 컴파일러 사용법을 배워야 한다.(^^) 그리고 이론은 이론이고 실전은 실전이다. 이런 이론을 사용하지 않고 무작정 하는 방법도 있다. 보통 문자를 구분할 수 있는 기준이 영문자, 숫자, 기호가 될 것이다. 영문자는 다시 대문자, 소문자로 구분된다. 또는 모음과 자음으로 구분할 수도 있다. 이렇게 문자들을 구분한 기준으로 단어를 파악하는 것이 패턴(무늬)이다. 단어 분석기란 바로 패턴 검색기다.
출처 : http://blog.daum.net/jty71/
댓글