[컴파일러 이론] 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://edykim.com/ko/post/the-super-tiny-compiler/
https://chanto11.tistory.com/43
'Studies > Computer Science' 카테고리의 다른 글
[운영체제] 캐시 교체 정책 (0) | 2022.08.20 |
---|---|
[운영체제] 캐시 (Cache) (0) | 2022.08.19 |
[Linux] Linux & Unix (0) | 2022.08.18 |
[네트워크] 쿠키와 세션 (0) | 2022.07.13 |
[네트워크] JSON & XML (0) | 2022.07.05 |