[Compiler] Lexical Analysis

다른 포스트에서도 이야기 했었지만 compiler가 하는 가장 기본적인 역할은 사용자가 특정 목적에 의해서 만든 코드를 컴퓨터가 알아먹을 수 있게끔 컴퓨터의 언어로 번역해주는 것이다. 그런데 참 신기하지 않은가? 우리가 ">>" 라고 작성하면 대부분의 사람은 오른쪽으로 shift 하는 걸로 생각하지만 만약 <Tmp<int>> 에 들어있는 >> 는 우리가 생각하는 그런 의미를 담지 않는다. 단지 parentheses 일 뿐이다. 그런데 컴파일러가 설치되어 있는 컴퓨터는 i>>2 와 <Tmp<int>> 에 들어있는 >>를 잘 구분한다. 여기서 컴파일러에 대해서 전혀 모르는 사람이라도 컴퓨터 내부에 이런 어휘나 규칙을 정해놓은 무언가가 있을 거라는 짐작을 할 수 있을 것이다. 보통 이런 걸 구분하는 요소를 Lexeme (어휘소) 라고 하고, 컴파일러가 가장 기본적으로 수행하는 작업 중 하나가 이런 어휘를 분석해서 분별하는 Lexical Analysis인 것이다.

앞에서도 언급했지만 뭔가가 신기하다 분명 프로그래밍 언어에도 문법이 있는 것이고, 그 문법 덕택에 사용자가 코드를 보더라도 readability가 보장된다. 간단한 예시를 보자.

#include <stdio.h> 

int main(int argc, char* argv[])

{

printf("Hello, World!\n");

return 0;

}

 

보통 이런 문장을 하나의 Stream 이라고 하고, 이런 stream이 사용자가 일상에서 사용하는 문법과 비슷하기 때문에 읽기가 쉬운 것이다. 하지만 다들 알다시피 컴퓨터가 이 code Stream을 그대로 이해할 수 없다. 컴퓨터는 컴퓨터만의 언어인 binary code가 있을 것이고, 위의 코드도 컴퓨터가 처리하기 위해서는 어떤 과정을 거쳐서  binary로 변환되어야 할 것이다. 하지만 일단 각 Stream이 whitespace로 인해서 띄워쓰기가 되어 있는 것을 알 수 있기 때문에 이걸 기반으로 단어별로 자르는 작업을 거치게 된다. 이 잘라진 단어가 Token 인데 이걸 뽑아내는 것이 Lexical Analysis의 최종 목적이 되는 것이다. 

 일단 위의 코드를 컴퓨터는 먼저 이렇게 읽게 된다.

뭔가 아까의 정형화되었던 것과는 다르게 복잡해졌지만, 잘 보면 아까와 똑같은 구문이다. 여기서 Token을 뽑아내야 한다. 앞에서 언급한대로 whitespace에 따라 구분해보면 대략적으로 "include", "<", "stdio.h", ">" .. 와 같이 구분할 수 있다. 여기서 특정 부류의 token으로 분류할 수 있게 된다. 사전에 정의된 Token의 부류는 다음과 같다.

 - identifier

 - keywords

 - integer

 - operator

 - separators

 - whitespace

 - etc...

 이렇게 사전에 identifier 다 keyword 다 라는 것을 정해놓은 규칙이 바로 pattern이 되는 것이고, 이를 토대로 lexeme를 뽑아낼 수 있게 되는 것이다. 드래곤 책(Compilers : Principles, techniques & tools)에는 이 둘의 정의를 다음과 같이 하고 있다.

 - Pattern : rule defining the possible lexemes of a token

 - Lexeme : sequence of characters that match the pattern for a token

위의 정보를 활용하면 각각의 lexeme 정보를 담은 Token을 뽑아낼 수 있게 되는데, 보통 Token의 형식은 다음과 같이 이뤄진다.

<token의 이름,  token과 관련한 정보>

 자 그럼 일단은 위의 예시중 출력 구문에 대한 부분인 printf("Hello, World!\n"); 중에서 token들을 분석해보면 다음과 같이 할 수 있다.

<id, printf> <punctuation, ( > <literal, "Hello, World!\n"> <punctuation, ) > <punctuation, ; >

어떻게 보면 literal에 속해있는 " , Hello, , ,World!, \n, " 이런 것들도 하나의 identifier로 묶어져야 하는 게 아닐까 할 수도 있지만 사전에 " " 안에 들은 문자들은 전부 literal로 구분하게 하자는 pattern이 있기 때문에 이와 같이 분류가 된것이다. 이렇게 분류된 Token들은 하나의 Symbol Table로 정의되어 이 Lexical Analysis 후에 이뤄지는 Syntax Analysis의 Parser 가 사용할 수 있게 된다. 그러면 Parser는 printf 같은 구문을 발견하게 되면 그에 해당되는 기능을 수행하게 하는 것이다.

 그러니까 결론적으로 말하면 Lexical Analysis의 진정한 의미는 코드를 구동하게 하는 본역할이 아닌, 구동이 원활하게 이뤄지게끔 사전에 어휘들을 분류해주는 보조의 역할이라고 본다. 물론 Lexical Analysis 가 없는 것에 비해선(없는 걸 본적이 없지만..) Compiler의 구동 효율에 도움을 줄 수 있는게 이 Lexical Analysis의 의미가 아닐까 되집어 본다. 

 아무튼... 그런데 지나쳐 오면서 궁금증이 생길 수 있다. 맨앞에서 언급했던 내용인데 같은 문자열이 나오면 어떻게 구분하냐는 것이다. 예를 들어 else 라는 lexeme는 분명 if 다음에 나오는 "그렇지 않으면" 이라는 의미를 가진다. 그런데 문득 사용자가 elsewhere 라는 단어를 사용하면 그 두개를 어떻게 구분할 수 있을까? 이렇게 구분하는 요소를 lookahead라고 하는데 앞의 hello world 예제에서는 임의로 whitespace를 lookahead로 정의하고 각각의 lexeme를 구분했다. 분명 그런식으로도 구분할 수도 있는데 포트란이나  PL/1같은 언어에서는 lookahead가 다른 식으로 정의된다. 이렇게 각각의 경우를 따져보고 이에 따른 lookahead가 지정되어야 한다. 이것도 어떻게 보면 하나의 pattern이라고 볼 수 있을 듯 하다. 

 이처럼 특정 문구를 보고 원하는 pattern을 추출해내는 능력이 요구되는데 많은 방법들이 있다. 그 중 가장 대표적인 방법이 바로 Regular Expression( 정규표현식 ) 방식이다. 줄여서는 Regex라고 하고, 이를 추출해주는 프로그램이 Lex나 Fast Lex 같은게 있다. 이 부분은 다음 글에서 조금 더 정리해보고자 한다.