[컴파일러 이론] Tokenizer, Lexer, Parser

[컴파일러 이론] Tokenizer, Lexer, Parser

컴파일러는 소스코드를 기계어로 바꿔주는 역할을 합니다.

이 때 구문분석 -> 최적화 -> 코드생성 -> 링킹 의 과정이 진행됩니다.

구문분석 과정에서 소스코드는 Tokenizer, Lexer, Parser 를 차례대로 지나가며 구문분석을 진행하게 되는데, 오늘은 이 부분에 대해 알아보도록 하겠습니다.

Tokenizer

Tokenizer 는 말 그대로 어떤 구문을 토큰화 하는 역할을 합니다.

여기서 토큰이란 어휘 분석의 단위를 뜻하며 단어, 단어구, 문자열 등 의미있는 단위로 정해집니다.

토큰은 어떤 요소들을 구조적으로 표현할 수 있도록 도와줍니다.

Lexer

Lexer 는 Tokenizer 로 인해 쪼개진 토큰들의 의미를 분석하는 역할을 합니다.

Tokenizer 를 거치며 의미있는 단위로 쪼개지고, Lexer 를 거치며 그 결과의 의미를 분석하는 과정을 통틀어 Lexical Analyze 라고 합니다.

return 이라는 명령어를 분석하는 과정을 예로 들어보겠습니다.

ex) return 명령어 분석

- return 이라는 단어에서 r, e, t, u, r, n 은 각각 따로놓고 보면 아무 의미도 가지지 않음
- Tokenizer 를 거치며 return 이라는 의미있는 단어가 됨 -> 토큰화
- Lexer 를 거치며 이 토큰은 무언가를 반환하라는 명령어구나! 라고 의미를 분석함
- 해당 토큰은 {type: 명령어, value: "return", child: []} 와 같은 식으로 의미가 분석되어 Parser 에게 전달됨

Parser

Parser 는 Lexical Analyze 된 데이터를 구조적으로 나타냅니다.

이 과정에서 데이터가 올바른지 검증하는 역할도 수행하는데, 이를 통틀어 Syntax Analyze 라고 합니다.

만약 실제로 Tokenizer, Lexer, Parser 개념을 이용하여 무언가를 구현해볼 생각이라면, Parser 가 태스크를 수행하는 부분에서 무언가 올바르지 않은 데이터가 발견되었다면 Error 를 던지는 식으로 구현하는게 좋을 것이라고 생각합니다.

Parser 에 의해 도출된 결과는 AST (Abstract Syntax Tree) 형태로 생성됩니다.

AST (Abstract Syntax Tree)

AST 는 이름 그대로 위 과정을 거치며 분석된 구문을 트리의 형태로 나타내는 자료구조입니다.

이는 분석된 소스를 컴퓨터가 이해할 수 있는 구조로 변경시킨 트리라고 생각하시면 됩니다.

AST 는 다음과 같은 구조로 이루어져 있습니다.

예시

간단한 C 코드를 분석해보며 예시를 들어보겠습니다.

예시 1)

예시 1)

// - 입력
printf("Hello World");

// - Tokenizer : 의미있는 단위로 쪼갬 (토큰화)
["printf", "(", "Hello World", ")", ";"]

// - Lexer : 주어진 토큰의 의미 분석
<id, printf>
<punctuation, (>
<literal, "Hello World">
<punctuation, )>
<punctuation, ;>

// - Parser : 분석된 데이터 검증 및 AST 구조화
{
    type: punctuation,
    value: printf,
    child: [
        {
            type: literal,
            value: "Hello World",
            child: []
        }
    ]
}

위의 예시는 정상적으로 구문 분석을 완료했을때를 나타냈습니다.

 

AST 에서는 괄호나 세미콜론과 같은 정보들은 생략하고 소스코드에서 필요한 정보들만 트리형태로 나타낸 것을 확인할 수 있습니다.

 

Abstract 라는 단어가 들어간 이유는 소스코드의 불필요한 정보는 제외하고 핵심 데이터들만을 이용해 트리를 구성하기 때문입니다.

 

예시 2)

예시 1)

// - 입력
printf("Wrong Syntax")

// - Tokenizer : 의미있는 단위로 쪼갬 (토큰화)
["printf", "(", "Wrong Syntax", ")"]

// - Lexer : 주어진 토큰의 의미 분석
<id, printf>
<punctuation, (>
<literal, "Hello World">
<punctuation, )>

// - Parser : 분석된 데이터 검증 및 AST 구조화
Compile Error - missing semicolon

위의 예시에서는 잘못된 코드를 분석하는 과정을 나타내보았습니다.

 

Tokenizer 와 Lexer 는 의미있는 단위로 소스를 분리하고 의미를 분석하는 역할만 할 뿐, 해당 소스가 유효한지 아닌지는 검증하지 않습니다.

 

실제로는 위 과정과 같지는 않겠지만, 이는 Parser 에서 진행되기 때문에 위와 같이 Parser 에서 에러를 던져줄 것이라고 생각했습니다.

 

저희가 겪는 컴파일 에러의 대부분은 위와 같이 Parser 에서 데이터를 AST 로 구조화하지 못했기 때문이라고 생각합니다.

 

마무리 & 참고 링크

Parsing 과정에 대해 공부하기 위해 Tokenizer, Lexer, Parser 와 AST 까지 알아보게 되었는데, 컴파일러 이론 자체를 완벽하게 숙지하고 있지는 않은 터라 틀린 정보가 많을 수도 있음을 양해 부탁드립니다.

 

지적할 점은 언제든 댓글로 남겨주세요! 감사합니다.

 

https://medium.com/teamnexters/koa%ED%8C%80-%EA%B0%9C%EB%B0%9C%EC%9E%90-%EC%A3%BC%EA%B0%84-%EB%AF%B8%EC%85%98-2-938634d86921

koa팀 — 개발자 주간 미션 2

https://gobae.tistory.com/94

[컴파일러] 토크나이저, 렉서, 파서 (Tokenizer, Lexer, Parser)

https://edykim.com/ko/post/the-super-tiny-compiler/

아주 조그마한 컴파일러 만들기

https://chanto11.tistory.com/43

어휘분석, 구문분석, 의미분석