[컴파일러 만들기] 2. 컴파일의 첫 번째 단계 - 어휘 분석

'컴파일러 만들기' 책을 참고하여 진행.
이번 포스팅은 컴파일의 첫 번째 단계인 어휘 분석에 대해 알아보고 어휘 분석 구현에 대해 다룬다.
 

컴파일 : 소스 코드를 목적 코드로 번역하는 과정
컴파일 단계 : 소스 코드 -> 어휘 분석 > 구문 분석 > 코드 생상 -> 목적 코드

 
+ 여기서 컴파일러는 c++ 을 사용해서 작성한다! 
 
 

어휘 분석 lexical analyze

---

어휘 분석은 프로그래밍 언어로 작성한 소스 코드의 문자열을 분석하는 과정이다.
 
 

💭 소스 코드 문자열은 무엇으로 구성되어 있을까? 

바로 어휘들이다! 소스 코드 문자열은 어휘들의 나열이다. 
어휘 분석은 곧 소스 코드의 문자열의 어휘 분석을 하는 것이다. 
 

💭 어휘에는 어떤 것들이 있을까?

• 키워드: for, if, function, return 등과 같이 프로그래밍 언어에서 특별하게 취급하는 어휘
• 식별자: 변수 이름, 함수 이름 등 사용자가 정의하는 어휘
• 연산자: +, - 와 같이 연산을 위한 기호 
• 구분자: 괄호 ( ), 세미콜론 ; 과 같이 어휘들을 구별하기 위한 기호
• 숫자 리터럴: 정수, 실수. -> 숫자로 시작해서 숫자로 끝남. 
• 문자열 리터럴: 'Hello World!'와 같이 따옴표에 둘러싸인 문자열 -> 따옴표로 시작해서 따옴표로 끝남.

 
 
그럼 어휘 분석을 위해서 우선적으로 해야할 것은 사용되는 어휘들을 정의해주는 것이다. 
 
 

1. 어휘 분석을 하기 전 - 어휘 정의하기  

---

어휘들을 정의하려면 > 어떻게 생긴 애가 무슨 어휘인지 < 알려줘야겠다. 
 
어떻게 생긴 애 -> 문자열
무슨 어휘인지 -> 종류
 
문자열은 "for", "if", ";", "+" 등 우리가 정의할 어휘이고, 종류는 각각  "For", "If", "Semicolon", "Add" 에 대응한다.
 
여기서 종류들을 매 어휘마다 새로 작성하지 않고, 따로 모든 종류들을 모아서 저장 해둔다. 
열거형 자료구조를 이용해서 모든 종류들을 저장해둔다면 상수로 접근 가능해진다. 
이름은 Kind로 했다.

enum class Kind {
	Unknown, EndOfList,
    
	Comma, Colon, Semicolon
};

이런식으로 어휘의 종류들을 저장해둔다.  
 
그리고 map 자료구조를 이용해서 문자열과 종류를 매칭시킨다. key: string, value: Kind
각 문자열이 Kind 열거형에서 어떤 멤버에 대응하는지 연관시킨다.

static map<string, Kind> stringToKind = {
	{"#Unknown",	Kind::Unknown},
    	{"#EndOfList",	Kind::EndOfList},
    
	{",",		Kind::Comma},
    	{":",		Kind::Colon},
	{";",		Kind::Semicolon},
}

',' 은 Comma라는 종류의 어휘이고, ':'은 Colon이라는 종류라는 것을 정의했다는 것을 볼 수 있다.
여기서 ',' 라는 문자열은 열거형 Kind에 의해서 2 라는 상수에 대응된다!  (Kind::Unknown부터 0~ )
 
이렇게 정리해서 어휘를 정의한다.  
 

💭 그런데 어디에 어휘의 종류 (enum Kind) 를 정의할까?

형을 정의하는 것이기 때문에 헤더파일에 작성해준다~ 
 
+) c/c++ 에서 형을 알리는 코드들 

#define, enum, struct 헤더, class 선언, 함수 형

 
 

2. 어휘 분석의 결과 - 토큰

---

어휘 분석의 결과는
소스 코드 문자열의 어휘들을 분석해서 어떤 어휘들이 있는지 (어떤 문자열과 어떤 종류인지)에 대한 정보다.
 
어휘의 문자열과 종류를 묶어서 토큰이라고 하면, 결국 어휘 분석의 결과는 토큰의 리스트다. 
 
-> 토큰은 분석된 어휘의 문자열과 종류의 쌍을 의미한다.
예를 들어, 구분자 ; 의 토큰의 문자열은 ';' 이고 종류는 Semicolon 이다. 
 
 
토큰은 다음과 같이 정의한다. 구조체 선언이니까 헤더 파일로 작성

struct Token{
	Kind kind = Kind::Unknown;
    	string string;
}

 
 

3. 어휘 분석기 lexical analyzer or Scanner

---

이제 본격적으로 소스 코드 문자열을 분석해서 토큰 리스트를 만들 차례
 
어휘 분석기
소스 코드의 문자열을 분석하는 어휘 분석 프로그램
 
 
어휘 분석을 하는 함수의 이름은 scan 
어휘 분석의 결과인 토큰 리스트를 이쁘게 출력해줄 함수의 이름은 printTokenList()
 
main 함수를 실행  -> 우리가 컴파일하려는 소스 코드를 scan 함수에 인자로 넘겨 어휘 분석을 할 거다

auto main() -> void {
    
    //R"""" ( 여기 사이에 있는 문자열이 어휘 분석을 할 소스 코드다. )""""
    string sourceCode = R""""(
        function main() {
            printLine 'Hello, World!';
            printLine 1 + 2 * 3;
        }
    )"""";


    // scan이라는 어휘 분석 함수를 호출하고 결과로 받은 토큰 리스트를 변수에 저장
    auto tokenList = scan(sourceCode);
    // 따로 정의한 토큰리스트를 이쁘게 출력해주는 함수를 이용해서 출력 ㄱ ㄱ
    printTokenList(tokenList);
}

 
 
scan() 함수가 소스 코드 문자열을 문자 단위로 순회하고 토큰 리스트를 반환하는데, 이 때 마지막에는 토큰 리스트의 끝을 나타내는 EndOfList 토큰을 추가해 주어야 한다. 
-> 소스 코드 문자열 (string) 맨뒤에 문자열의 끝을 나타내는 '\0' 추가 하고 반복문 돌며 어휘 분석해서 토큰 추가하고 다 돌고나면 EndOfList 토큰을 추가해준다. 
 
 

3-1 어휘의 시작 문자를 이용해서 어휘 분류하기 

scan()은 문자열을 문자 단위로 순회한다. 
따라서 우선 어휘의 시작 문자를 가지고 종류를 알아낸다음, 그 중 해당하는 토큰을 생성한다. 
 
어휘의 종류는 크게 { 키워드, 식별자, 연산자, 구분자, 숫자 리터럴, 문자 리터럴 } 이 있었다. 
 
하지만 항상 여기에 속하는 어휘만 들어오는 것이 아니다. 사용할 수 없는 문자들이 들어올 수도 있고, 공백, 탭, 개행 등의 문자도 입력으로 들어온다. 이것들도 다 분류를 해주어야 한다. 
 
문자 리터럴은 따옴표로 시작하기 때문에 따로 구별이 되지만, 식별자와 키워드는 그냥 알파벳으로 시작한다. 그래서  식별자와 키워드는 같이 묶어서 분류한다. 
 
또 연산자와 구별자는 모두 특수 문자로 시작되기 때문에 이 둘도 묶어서 분류한다. 
 
정리하면 어휘를 다음과 같이 분류하면 된다
 

1. 사용할 수 없는 문자
2. 공백, 탭, 개행
3. 숫자 리터럴
4. 문자 리터럴
5. 식별자, 키워드
6. 연산자, 구분자

 
예를 들어, 시작 문자가 '<' 또는 '[' 라면 6번 분류에 속하고,
" (따옴표) 라면 4번일 것이고 아무것에도 속하지 못하면 1번에 속할 것이다.
 
이렇게 시작 문자를 분석해서 어휘의 분류를 반환하는 getCharType() 함수를 만들자!
 
 
시작 문자만 가지고 그 문자가 진짜 숫자 리터럴인지, 문자 리터럴인지 알 수 없다. 만약 숫자로 시작해서 문자로 끝나면 아무것도 아니게 된다.  따라서 분류에 맞춰 검사하고 토큰을 생성해야 겠다.
 

3-2 분류에 따라 문자열 분석하기 - 토큰 추가하기

시작 문자를 분석해서 얻은 분류가 정말 맞는지 검사하는 isCharType() 함수를 작성하자!
 
True를 반환한다면 토큰리스트에 토큰을 추가하자. 
 

💭 토큰을 새로 생성하려면 ?

// stringToToken 의 형태 - map(<sting, Kind>)

{"#unknown",	Kind::Unknown},
{"#EndOfList",	Kind::EndOfList},

{",",	Kind::Comma},
...

내가 가지고 있는 문자열의 정보는 string. 이걸 이용해서 Kind를 알아내야 한다. 

stringToToken.at(string);

map의 at 함수를 이용해서 key값을 넘겨서 string에 해당하는 Kind를 반환 받을 수 있다. string, Kind 를 모두 알게 되었으니 Token 생성하면 된다!