[프로그래밍언어론] 5. Lexical and Syntax Analysis

만약 우리가 컴파일러를 만든다면, 첫번째로 할 일은 문자열 덩어리인 소스코드를 분석해서 렉심을 추출하는 (렉시컬 토큰을 추출) lexical analysis 과정을 먼저 거쳐야 한다.

 

다음으론 추출한 렉시컬 토큰들을 기반으로 문법이 올바른지 검사하는 syntax analysis 를 해야한다.

이때 문법을 표현하는 기법의 하나로 BNF를 사용했다.

 

이를 다시말하면, syntax analysis 를 할 때는 lexical analyzer 를 이용해 렉시컬 토큰을 추출하는 과정을 먼저 거쳐야 한다.

이 과정을 low-level part 라고도 한다.

이 과정을 수행할 땐 정규 표현식을 이용하거나, 제대로 하려면 오토마타 개념을 이용하여 추출해야 한다.

 

다음으론 high-level part 인 syntax analyzer를 이용해 추출한 토큰들이 문법적으로 올바르게 배치되어 있는지 검사한다.

(syntax analyzer 대신 parser 라고도 한다.)

BNF를 기반으로 파서를 만들면 유지보수도 쉽고, 직접적으로 파서를 만들 수도 있다.

 

파서를 만드는 것은 '컴파일러' 과목에서 배울 내용이므로, 프로그래밍언어론에서는 사람이 파싱한다면 어떻게 파싱하는지 직접 해보는 정도만 배운다.

 

---

 

그렇다면 왜 lexical analysis 와 syntax analysis 과정을 분리했을까?

 

1. simplicity

두 과정이 합쳐져 있으면 매우 복잡한데, 이 둘을 분리하면 복잡도가 감소한다. (단순해진다.)

 

2. Efficiency

lexical analyzer 를 parser 의 일부분처럼 만들어서 더 새롭고 좋은 알고리즘이 나오면 효율적으로 갈아끼울 수 있게 만들었다.

 

3. Portability

lexical analyzer 와 parser를 다른 부품처럼 생각해서 조립한 뒤 돌리면 잘 작동한다.

즉, 다른 데서 더 좋은 렉시컬 어널라이저를 파서에 가져다 붙이면 더 잘 쓸수도 있다.

---

Lexical Analysis

렉시컬 어널라이저는 소스코드 (문자열) 에 대한 패턴을 매칭하는 도구이다.

소스코드에 대해 제일 먼저 실행되는 기능이므로, 컴파일 과정의 "프론트 엔드"라고 볼 수도 있다.

렉시컬 어널라이저의 역할은 패턴을 매칭해서 이 단어가 키워드인지, identifier 인지, 숫자인지, 스트링인지 파악한다.

소스코드의 모든 lexeme을 하나하나 파악해서 렉시컬 토큰을 만든 뒤, 파서에게 전달하는 역할을 한다.

 

렉시컬 어널라이저는 보통 함수로서, 파서가 다음 토큰을 필요로 할 때 호출한다.

렉시컬 어널라이저를 만드는 방법은 크게 3가지가 있다.

 

1. 토큰을 수식으로 묘사한 뒤, 이 수식에 맞는 것은 맞는 렉심이라고 판단하는 방법

2. state diagram (상태도) 를 만들어서 지금 들어오는 게 렉시컬 토큰인지 아닌지 판단하는 프로그램 작성

3. 상태도를 만들고, 이를 손으로 직접 작성

 

State Diagram

그렇다면 상태도는 무엇인가?

 

상태도는 2가지로 구성되어 있다.

1. 상태

2. 하나의 상태에서 다른 상태로 옮겨지는 transition (이동)

 

예를 들어 어떤 글자 하나가 있을 때 다음 글자가 어떤 것이 올 수 있는지 상태도를 그려본다고 하자.

하나의 문자에 대해 모든 상태를 나타낸다면, 숫자, 문자 해서 대충 100개의 상태가 가능할 것이다.

이에 대해 3글자로 이루어진 단어는 100만가지 상태가 가능하다.

 

이렇게 하는 건 너무 비효율적이니 다음과 같이 정의하기도 한다.

- 알파벳 a부터 z 까지는 'letter' 라는 클래스 하나에 모두 넣자.

- 대문자는 대문자 클래스, 소문자는 소문자 클래스에 넣자

- 숫자는 숫자 클래스로 넣자

 

또 C언어 같은 언어에서는 특정한 용도로 사용하는 예약된 단어 (키워드) 가 존재한다.

이런 단어는 identifier로 사용할 수 없다.

그런데 렉시컬 어널라이저가 보기엔 둘다 똑같은 단어 집합인데, 키워드인지 아닌지 어떻게 구분할까?

이를 위해 키워드들을 따로 모아서 하나의 테이블에 저장해놓고, 식별자가 왔을 때 이 식별자가 키워드인지 아닌지 확인하는 방식을 취하면 된다.

(모든 키워드에 대해 각각의 상태를 정의할 필요가 없다)

 

지금까지 설명한 내용을 이미지로 도식화하면 아래와 같다.

 

 

먼저 이 그림에서 하나의 원은 state를 의미한다.

위 그림에서는 start, id, int 3개의 state 가 있다.

그리고 모든 화살표는 transition 을 의미한다.

 

초기 상태는 start 상태이다.

이 상태에서 만약 Letter 로 분류한 문자가 들어오면 상태가 id로 바뀐다.

id 상태에서는 다시 Letter 가 들어올 수도, Digit 이 들어올 수도 있다.

 

이 과정이 반복되다가 스페이스바같이 위에 해당하지 않는 문자셋이 오면 return lookup(lexeme) 함수가 호출된다.

지금까지 만든 문자를 lexeme으로 보고 이 렉심이 키워드인지 아닌지 확인하는 것이다.

 

반면 처음에 숫자로 분류한 데이터가 오면 int 상태로 바뀐 뒤, 숫자를 받는 동안 반복해서 int 상태로 유지한다.

만약 숫자 이외의 데이터가 오면 Int_Lit (정수 리터럴) 로 렉심을 반환한다.

 

---

Example - C언어에 대한 Lexical Analysis

다음은 C언어에 대한 lex 코드이다.

 

 

먼저 다음 정규표현식에 대해 위와 같이 정의한다.

[0-9] 는 숫자이므로 D 라고 정의한다.

이후 패턴매칭시 D를 대신 사용할 수 있다.

 

또 a~z, A~Z, _ 까지 모두 합쳐서 Letter 로 인식하기 위해 L 이라고 정의하였다.

 

H 는 16진수를 구성할 때 사용하는 숫자와 문자 집합

E 는 e-10 같은 과학적 숫자 표현식을 의미한다.

FS 는 실수에 대해 숫자 뒤에 붙는 기호

LS 는 정수에 대해 숫자 뒤에 붙는 기호를 의미한다.

 

 

이 구문은 lex 에서 전처리에 사용하는 구문이다.

 

 

그리고 이 구문부터 패턴 매칭이 시작된다.

/* 가 들어오면 주석을 처리하는 함수를 실행시키라는 의미이다.

 

 

이외에도 각종 c언어 키워드들에 대해 이렇게 count 해서 개수를 센 뒤에 각 키워드를 대문자로 바꾼 lexical token 을 반환한다. (반환하는 대상은 당연히 파서다. 파서가 이 lexical analyzer를 호출했을 것이기 때문이다.)

 

 

이 패턴매칭은 레터 하나 뒤에, 레터 또는 숫자가 0개 이상 반복된다는 의미

즉, 변수명(식별자)을 의미한다.

따라서 check_type() 이라는 함수를 호출해서 변수의 타입을 체크한다.

 

 

이 패턴 매칭들은 16진수, 8진수, 10진수, 소수와 같은 상수 값들을 판단한다.

 

 

문자열 리터럴은 이렇게 " " 큰따옴표 사이에 ( " ) 를 제외한 아무 문자 ( . ) 가 있는지로 판단한다.

 

 

이 패턴매칭은 각종 연산자에 대한 패턴 매칭이다.

 

이런 기호는 기호 그 자체를 토큰으로 반환한다.

 

 

마지막으로 공백문자는 무시하도록 처리하고,

지금까지 패턴매칭에 걸리지 않은 문자가 있다면 이에 해당하는 모든 문자 ( . ) 는 신택스 에러의 대상으로 처리하도록 한다.

 

지금까지 C언어의 Lexical Analyzer 실제 코드 일부를 보았다.

다음 글에서는 C 언어의 BNF를 보고 파싱트리를 그리는 과정을 직접 따라가 볼 것이다.