[컴파일러 이론] 1. lexical analysis, scanner, regular expression

보통 우리가 코딩을 하면 어셈블리어로 컴파일되어 기계가 알아들을 수 있게 변환된 다음 코드가 실행된다.

 

이 과정에서 분명 사람은 거의 영어에 가까운 언어로 코딩을 하는데, 기계가 이걸 어떻게 알아듣고 어셈블리어로 바꿀지 의문이 들 수 있다.

 

이 변환을 수행해주는 컴파일러의 원리에 대해 알아보자.

 

위 그림을 보면 source code가 assembly code로 변환될 때까지 꽤 많은 과정이 필요함을 볼 수 있다.

 

이번 글에서는 첫 단계인 Lexical Analysis에 대해 조금 살펴보자.

 

---

Scanner

Lexical Analysis를 수행해주는 프로그램(?)의 이름을 Scanner라고도 하는데, 이름처럼 source code를 스캔하는 작업을 하기 때문이다.

사람들의 언어로 예시를 들면 문장을 받아서 한 단어씩 스캔하여 품사, 기능 등에 따라 분류를 해주는 것이다.

프로그램에서는 단어에 해당하는 것이 토큰(token)이다.

사람은 코드를 보면 자연스럽게 구성요소를 나눠서 생각하지만 이런 행동을 하는 기계를 만들려고 해보면 은근히 간단하지 않다는 것을 깨닫게 된다.

 

---

Tokens

위에서 쪼갠 단위들을 token이라고 한다고 했다.

이 토큰의 종류를 자세히 알아보자.

identifiers 는 흔히 얘기하는 변수명과 비슷하다.

keywords는 우리가 변수 이름으로 사용할 수 없는 동작을 처리하는 예약어들이다.

integers, floating-points,strings은 코딩할 때 쓰는 변수 타입과 같다.

symbols는 기호,괄호,연산자 등이다.

 

---

Regular Expression(RE)

토큰의 종류도 알았으니 source code에 있는 문자들을 token으로 분류를 해야한다.

어떤 문자들의 패턴을 어떤 토큰으로 분류할 것인지 규정하기 위해 regular expression(정규표현식)이라는 것을 사용한다.

 

아래는 기본적인 5가지의 RE들에 대한 설명이다.

a	표현 그대로 a라는 문자를 나타낸다
$\varepsilon$	아무것도 없는 string을 나타낸다
R | S	R과 S 중 아무거나 하나를 나타낸다 (R,S는 각각 RE이다)
RS	R이 나오고 S가 이어 나오는 것을 의미한다.
R*	R을 여러번 이어붙인 것이다. (0번도 포함된다)

 

정규 표현식 R에 대해서 아래처럼 사용한다면

L(R)

R에 의해 표현가능한 모든 문자열의 집합을 의미하게 된다.

말은 어렵지만 아래 예시를 보면 쉽다.

 

L(hello | goodbye) = { hello, goodbye }

L(1(0|1)*) = 1로 시작하는 모든 이진수들

 

따라서 원래 우리가 원하던 token들을 아래처럼 RE로 나타낼 수 있게 되었다.

keyword : L(if | else | while | break ...)

integer : L((-|+|$\varepsilon$)(1|2|3|4...|9)(0|1|2|3|4...|9)*)

 

integer부분을 좀 설명하면, 정수는 앞에 +또는 -기호를 붙여서 표현할 수 있고 아무 기호를 붙이지 않을 수도 있다.

또 기호 뒤에 숫자는 적어도 하나 있어야 하고, 그 뒤에 숫자가 얼마나 오는지는 상관없다.

따라서 위 식은 우리가 아는 +2,+987,-678,345 등의 정수를 모두 표현할 수 있다.

 

<추가 RE들>

위의 RE 문법으로만 표현하다보면 불편함이 느껴진다.

그래서 편리하게 사용할 수 있는 문법을 더 만들었다.

 

 

그럼 실수를 나타내는 RE를 작성해보자.

한번에 작성은 어렵기 때문에 단계적으로 만들면 편하다.

먼저 한자리 숫자를 표현하고,

여러자리 숫자를 표현하고,

양의 정수를 표현하고,

정수를 표현하고,

실수를 표현하는 방식으로 만들 수 있었다.

---

Multiple Match

몇몇 예시를 생각하다보면 여러 방식으로 해석될 여지가 있는 코드가 있을 수 있다.

 

elsex=0

이라는 문자열을 봤을 떄,

① if-else문에서 else일 경우 x에 0을 대입하는 것으로 봐야할지

② elsex라는 변수에 0을 대입하는 것으로 봐야할지 가 그 하나의 예시이다.

 

이럴때는 더 길게 RE와 매칭된 해석을 따른다.

1번의 경우는 else를 keyword로 판단했으므로 길이 4의 매칭이고,

2번의 경우는 elsex를 identifier로 판단한 것이므로 길이 5의 매칭이다.

 

따라서 2번의 해석을 따른다.

---

이번 글의 내용은 RE의 문법에 익숙해지기만 한다면 매우 쉬운 내용이었다.

이번 글에서 한 것은 문자열을 어떤 token으로 분류할지 정의한 규칙을 RE를 통해 만든 것이다.

하지만 이걸 안다고 Scanner를 지금 당장 만들 수 있지는 않다.

 

규칙은 있지만 실제 코드가 그 규칙과 맞는지 비교하는 것은 다른 문제이기 때문이다.

 

실제 코드를 input으로 받아서 어떤 규칙에 부합하는지 비교하는 것은 다음 글에서 알아보자.