[컴파일러] 어휘 분석 (Lexical Analysis)

👑 어휘 분석 (Lexical Analysis)

어휘 분석 (Lexical Analysis)는 컴파일러 전반부(Front-end) 과정에서 이루어지며, 소스 코드를

토큰 (token)으로 분리하는 단계이다. 어휘 분석은 어휘 분석기에 의해 실행되는데, scanner 또는

lexer 라고도 불리며, 문법적으로 유효한 최소 단위(토큰)를 인식하는 역할을 한다.

💡 어휘 분석의 과정

어휘분석기는 원시 프로그램을 긴 문자열로 보고 차례대로 문자를 검사하여 토큰으로 변환한다.

예를 들어 int a = 5; 라는 코드가 입력되었다고 가정하면, 다음과 같이 변환된다.

컴파일러는 미리 정의된 토큰 규칙들을 가지고 있다. 이 규칙은 정규 표현식(regular expression)을

통해 설명되며, 각각의 lexeme이 어떤 토큰으로 분류될지를 결정한다.

lexeme이란? : 소스 코드에서 읽어들인 구체적인 문자열을 말한다.

즉, 어휘 분석기는 소스 코드를 lexeme들로 나누고, lexeme을 토큰으로 변환하여 파서에게
전달하는 것이다.

키워드 : if, int, while, for 등
식별자 : [a-zA-Z_][a-zA-Z0-9_]* (문자나 밑줄로 시작하고, 그 뒤에 문자나 숫자가 오는 패턴)
숫자 리터럴 : [0-9]+

위의 규칙들을 가지고, 실제 입력된 문자열들을 검사하여 토큰으로 변환하는 것이다.

위의 int a = 5;라는 코드를 예로 들면 다음과 같이 변환될 수 있다.

• int : 키워드

• a : 식별자

• = : 할당 연산자

• 5 : 정수 리터럴

• ; : 구분자

사람의 경우 문자열을 토큰으로 쉽게 변환할 수 있지만, 컴퓨터에게 토큰을 설명하기란 쉽지 않다.

컴파일러가 긴 소스 코드에서 토큰을 인식하기 위해서는 어떠한 방법이 필요하고, 그 방법 중 하나로

정규표현식이 사용되는 것이다.

💡 정규 표현식 (Regular Expression)

정규 표현식은 특정 패턴을 기반으로 문자열을 매칭하는 강력한 도구로, 컴파일러의 어휘 분석기는

정규 표현식을 사용하여 미리 패턴을 정의하고, 해당 패턴에 맞는 문자열을 찾아 토큰으로 분류한다.

예를 들어, 식별자(identifier)를 정규 표현식을 통해 다음과 같이 정의할 수 있다.
(첫 글자는 알파벳이나 밑줄로 시작하며, 이후에는 알파벳, 숫자 또는 밑줄이 올 수 있다.)

식별자의 정규 표현식: [a-zA-Z_][a-zA-Z0-9_]*

정수 리터럴 정의: [0-9]+

💡 FSA (Finite State Automata)

컴파일러는 각 토큰(식별자, 숫자, 키워드 등)을 정의하기 위해 정규 표현식을 사용한다.

정규 표현식은 패턴이 어떤 형태인지를 설명하지만, 컴퓨터가 이 패턴을 따라 문자열을 실제로

인식하기 위해서는 정규 표현식을 실행 가능한 형태로 변환해야 한다.

따라서, 정규 표현식을 효율적으로 처리하고, 토큰을 빠르고 정확하게 처리하기 위한 방법으로

유한 상태 오토마타(FSA)를 사용한다. FSA는 상태를 유한한 갯수만큼 가지며, 상태 간의 전이를

정의한다. 또한 정규 표현식과 동일한 표현력을 가지기 때문에 정규 표현식으로 정의된 패턴을

정확하게 인식할 수 있다.

정규 표현식은 일반적으로 NFA(Nondeterministic Finite Automata)로 먼저 변환된 후, DFA로

최적화된다. NFA는 다중 경로를 허용하므로 정규 표현식을 좀 더 쉽게 표현할 수 있다. 이후 DFA로

변환하는 과정을 거치게 되는데, DFA(Deterministic Finite Automata)는 특정 상태에서 입력에

대해 오직 하나의 전이 경로만 존재하므로 정규 표현식 패턴을 매우 빠르게 인식할 수 있게 된다.

💡 정리

• 컴파일러의 어휘 분석 단계에서는 소스 코드를 읽어 lexeme을 토큰으로 변환하여 파서(Parser)에
  전달하여 구문 분석 단계에서 사용하게 한다.

• 각 토큰 유형(키워드, 숫자, 식별자 등)을 정규 표현식으로 정의한다.

• 정규 표현식 → NFA → DFA의 순서로 변환한다.

• DFA는 입력 문자열을 문자 단위로 처리하면서 정규 표현식의 패턴을 인식하여 토큰을 추출한다.

👑 문제

1. 다음을 나타내는 정규 표현식을 작성하시오.
⑴ a로 시작하는 식별자
⑵ 2진수 중 4의 배수

• a로 시작하는 식별자

  • a[a-zA-Z0-9]*

• 2진수 중 4의 배수

  • [01]*00

2. 다음 정규 표현식을 인식하는 FSA를 표현하시오.
⑴ $ (ab)^* $
⑵ $ a^+ c $

• $ (ab)^* $

• $ a^+ c $