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

컴파일러

[컴파일러] 컴파일러란?

에서 컴파일러는 소스코드를 기계어로 바꿔주는 역할을 한다고 했다.

 

여기서 컴파일러는

구문 분석 -> 최적화 -> 코드 생성 -> 링킹의 과정을 거친다.

 

이 포스팅에서는 구문 분석에 대해 살펴보겠다.

 

컴파일러의 구문 분석 과정

컴파일의 첫 과정인 구문 분석 과정을 살펴보자.

 

컴파일러가 소스 코드 파일을 읽어서 개별 문법 요소 단위로 자른 뒤,
이 문법 요소들을 해석해서 추상 구문 트리(AST)를 작성한다.

 

사실 필자도 쓰면서 무슨 말인지 잘 모르겠으니, 자세한 설명을 해보겠다.

 

우선 결론은, 제목에 써있는 토크나이저 -> 렉서 -> 파서의 과정이 구문 분석 과정이고,

이 과정을 거친 결과로 나오는 녀석이 추상 구문 트리(AST)이다.

 

추상 구문 트리(AST)

Abstract Syntax Tree의 약자로,
프로그래밍 언어로 쓰여진 소스코드의 Abstract Syntatic 구조를 표현하기 위해 사용되는 자료구조이다.

 

쉽게 말하면, 특정 프로그래밍 언어로 작성된 프로그램 소스를
각각 의미별로 분리한 컴퓨터가 이해할 수 있는 구조로 변경시킨 트리.

 

이런 모습을 보인다.

 

A
ㄴB
  ㄴC
  ㄴD
    ㄴE
      ㄴa
      ㄴb
    ㄴF
  ㄴG

조잡하지만 다음 같이 트리 모양의 자료구조이다.

 

 

Tokenizer, Lexer, Parser

토크나이저, 렉서, 파서를 이용한 구문 분석 과정에 대한 간단한 예시이다.

 

Tokenizer

어떤 대상의 의미있는 요소들을 토큰으로 쪼개는 역할

 

여기서 토큰이란, "어휘 분석의 단위" 를 의미하는 컴퓨터 용어이다.
이 단위는 단어나 단어구, 문자열 등 보통 의미있는 단위로 정한다.

 

Lexer

Tokenizer에 의해 쪼갠 토큰의 의미를 분석하는 역할

 

Tokenizer + Lexer의 두가지 역할을 합해 Lexcial analyze라고 한다.

Lexical Analyze는 의미 있는 조각을 검출하여 토큰을 생성하는 것을 말한다.

 

ex)
Tom is Big.

에서 T o m 는 각각 따로 존재하면 의미가 없지만,
Tom 은 사람을 가리킨다. -> Tom이 토큰이 될 수 있다.

이렇게 "토큰" 단위로 키워드, 속성등을 정의하고 그 데이터를 parser에게 넘겨준다.

 

Parser

Lexical analyze되어 tokenize 된 데이터를 가지고, 구조적으로 나타낸다.

 

그리고 데이터를 구조적으로 바꾸는 과정에서, 데이터가 올바른지 검증하는 역할도 수행한다.

이 Parser에 의해 도출된 결과가 AST의 모습을 보인다.

 

 

Tokenizer -> Lexer -> Parser의 간단한 예시

입력값 : [1, [2,[3]], "he is tall"]


토크나이저 결과 

[ "1", "[2,[3]]", "['he', 'is', 'tall']"]

렉서 결과 

[
	{type: 'number', value:"1" },
	{type: 'array', value: "[2, [3]]"},
	{type: 'array', value: "['he', 'is', 'tall']"},
]

파서 결과  

{
	type: 'array',
	child: [
		{type: 'number', value:'1', child:[] },
		{type: 'array', 
			child: [
			{ type: 'number', value: '2', child:[] },
			{ type: 'array', 
				child:[ {type:'number', value:'3', child:[]}
			]
		}]
		},
		{type: 'array', 
			child:[
			{ type: 'string', value: 'he', child:[] },
			{ type: 'string', value: 'is', child:[] },
			{ type: 'string', value: 'tall', child:[] },
			]
		}]
}

다음과 같이 분석해 볼 수 있겠다.

• 토큰을 나눈 기준은 주관적이므로, "이렇게도 할 수 있겠구나." 라고만 참고하길 바란다.
• 실제로 이 토큰은 단어, 단어구, 의미를 갖는 문자열 등 다양한 기준으로 나눌 수 있다.

이와 같이 마지막 파서에 의해 AST가 만들어지면,

컴퓨터가 이해할 수 있는 언어로 바꿀 준비가 끝난 것이다.

 

이제 이 AST를 가지고 Compiler가 다음 최적화 작업을 수행할 수 있다.

 

참고한 사이트

https://ko.wikipedia.org/wiki/컴파일러

https://velog.io/@mu1616/%EC%BB%B4%ED%8C%8C%EC%9D%BC%EB%9F%AC-%EC%9D%B4%EB%A1%A0%EC%97%90%EC%84%9C-%ED%86%A0%ED%81%AC%EB%82%98%EC%9D%B4%EC%A0%80Tokenizer-%EB%A0%89%EC%84%9CLexer-%ED%8C%8C%EC%84%9CParse-%EC%9D%98-%EC%97%AD%ED%95%A0

https://gyujincho.github.io/2018-06-19/AST-for-JS-devlopers