[PL] Lexical Analysis

👑 소스 코드는 어떻게 처리되는가?

프로그래머가 어떠한 프로그래밍 언어로 짠 코드는 그 자체로 컴퓨터가 이해할 수 없다.

즉, 프로그래밍 언어로 된 코드를 컴퓨터가 이해할 수 있도록 하는 과정을 거쳐야만 한다.

이 과정은 다음과 같이 두 가지로 나뉘게 된다.

• 어휘 분석 (Lexical Analysis)

  • 어휘 분석은 문자열을 입력으로 받아 토큰화 (tokenization, lexing)를 수행하는 것이다.
  • 토큰 (token)이란 프로그래밍 언어의 기본 단위라 볼 수 있는데, 변수, 키워드 등이 될 수 있다.
  • int num = 5; 라는 코드가 있을 때, "int", "num", "=", "5", ";"와 같이 토큰화 된다.

• 구문 분석 (Syntax Analysis)

  • 구문 분석은 어휘 분석으로 나뉜 토큰들을 문법적으로 검사하고, 문장의 구조를 확인한다.
  • 프로그래밍 언어의 문법 규칙에 따라 코드가 올바른지 검사하는 것이다.
  • 예를 들어, C언어에서 변수 선언은 자료형 변수명 의 형태이어야 한다.
    만약 int num = 5;에서 =의 코드 왼쪽에 변수명이 위치하지 않는다면 구문 오류가 발생한다.
  • 구문 분석기는 AST (Abstract Syntax Tree)를 생성하고, 컴파일러, 인터프리터가 이를
    사용하여 코드를 실행시킨다.

👑 Lexical Analysis

어휘 분석 단계에서 프로그래밍 언어의 어휘항목은 각 토큰에 대한 regular expression의 모음이다.

regular expression이란 특정한 규칙을 가진 문자열의 집합을 표현하는 형식 언어이다.

Finite automata (유한 오토마타)를 통해 Regular expression을 표현할 수 있다.

R  ⩴
    | Ø    (no string)      : Ø
    | ϵ    (empty string)   : {ϵ}
    | σ    (symbol in ∑)    : {σ}
    | RR   (concatenation)  : ∑∑
    | R|R  (union)          : ∑ ∪ ∑
    | R*   (kleeneclosure)  : ∑*

연산자 우선순위 : kleene closure > 접합 > 합집합

e.g. 휴대폰 번호를 regular expression 으로 나타낸다면
     L = 010 - [0-9][0-9][0-9][0-9] - [0-9][0-9][0-9][0-9]
     010 - 1234 - 5678 ∈ L

그렇다면 다음의 코드에 대해 Lexical Analysis를 한 결과는 어떻게 되는지 알아보도록 하겠다.

OCaml 언어의 어휘항목

KW_LET : let
IDENT : [a-z][0-9a-zA-Z'_]*
OP_EQ : =
DECIMAL : [1-9][0-9]*
KW_IN : in
KW_WILDCARD : _
LPAREN : \(
RPAREN : \)

let xyz = 3 in
let _ = foo xyz in
()

KW_LET (IDENT "xyz") OP_EQ (INT 3) KW_IN
KW_LET KW_WILDCARD (IDENT "foo") (IDENT "xyz) KW_IN
LPAREN RPAREN

어휘 분석기 (Lexer)는 소스 코드를 토큰화하여 구문 분석기 (Parser)에 반환한다.

구문 분석기는 어휘 분석기에게 요청하여 토큰을 하나씩 전달 받고 파싱에 활용한다.

위의 두 과정에서 문자열이 프로그래밍 언어의 어휘항목에 속하지 않는 경우

lexical error 또는 syntax error가 발생한다.