[컴파일러] Tokenizer, Lexer, Parser에 대해 알아보자

Tokenizer, Lexer, Parser

컴파일러 실행 순서

------ 전단부 ------

1. 어휘 분석(Lexical Analysis)

2. 구문 분석(Synatax Analysis)

3. 중간 코드 생성(Intermediate Code Generation)

------ 후단부 ------

4. 코드 최적화(Code Optimization)

5. 목적 코드 생성(Target Code Generation )

 

어휘 분석 / 구문 분석 단계 과정에서

소스 코드 > (Tokenizer) > 토큰 > (Lexer) > 노드 > (Parser) > AST 과정을 거친다.

 

Tokenizer / Lexer / Parser란?

Tokenizer와 Lexer는 함께 어휘 분석(Lexical Analysis)을 수행하는 역할을 한다.

 

`Tokenizer` : 어떤 대상의 의미 있는 요소들을 토큰을 분리하는 역할을 한다.

(토큰 : 프로그래밍 언어에서 문법적으로 의미를 갖는 최소한의 단위를 의미한다.)

공백, 숫자, 문자열, 연산자 등을 기준으로 토큰화한다.

(예를 들어, `let a = 10;`은 `let`, `a`, `=`, `10`, `;` 토큰으로 나뉜다.)

 

`Lexer` : 이러한 토큰에 구문적 의미를 부여하고 분류하는 역할을 한다.

(예를 들어, `let a = 10;`은 `let`이라는 키워드, `a`라는 식별자, `10`이라는 숫자 리터럴을 각각 토큰으로 분류한다.)

 

`Parser` : 어휘 분석 단계에서 생성된 토큰을 받아들여, 구문 분석(Syntax Analysis)을 수행하며,  AST(추상 구문 트리)를 생성하는 역할을 한다.

(AST : 파싱 트리에서 불필요한 구문적 요소를 제거한 형태로,

컴파일러가 최적화를 수행하거나 기계어로 변환하기 위한 기반 구조로 사용된다.)

 

Tokenizer / Lexer / Parser 예시

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

`1`, `[2, [3]]`, `he is tall` 3개의 원소를 갖는 배열을 입력했다고 하자.

 

1. Tokenizer

`[`, `1`, `,`, `[`, `2`, `,`, `[`, `3`, `]`, `]`, `,`, `"he is tall"`, `]`로 토큰화가 된다.

Tokenizer 결과
['[', '1', ',', '[', '2', ',', '[', '3', ']', ']', ',', '"he is tall"', ']']

 

2. Lexer

유형은 `number`, `string`, `array start`, `array end`로 나뉜다.

Lexer 결과
[
  { type: 'array_start', value: '[' },
  { type: 'number', value: '1' },
  { type: 'comma', value: ',' },
  { type: 'array_start', value: '[' },
  { type: 'number', value: '2' },
  { type: 'comma', value: ',' },
  { type: 'array_start', value: '[' },
  { type: 'number', value: '3' },
  { type: 'array_end', value: ']' },
  { type: 'array_end', value: ']' },
  { type: 'comma', value: ',' },
  { type: 'string', value: '"he is tall"' },
  { type: 'array_end', value: ']' }
]

 

3. Parser

Parser 결과
root (type: array)
├── number (value: '1')
├── array
│   ├── number (value: '2')
│   └── array
│       └── number (value: '3')
└── string (value: "he is tall")

토큰화된 데이터를 AST 트리로 나타내면 이렇게 된다.

 

다음 AST 구조를 JSON 형식으로 변환하면 다음과 같다.

{
  "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": "string",
      "value": "he is tall",
      "child": []
    }
  ]
}

각 노드가 `type`, `value`, `child` 배열을 가지고 있다.

 

 

각 파서에 맞는 출력물을 확인할 수 있다.

https://astexplorer.net/