[컴개/CI] Token

토큰을 어떻게 기술할까?

프로그래밍 언어 제작자는 토큰에 대해 하나하나 기술해야 할 필요가 있다.

이때 주로 사용하는 방법이 정규 표현식(regular expression)이다.

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

표현 방식에 대한 설명은 사진으로 대체하겠다.

위는 표현, 아래는 예시이다.

마지막 예시는 2진수 집합? 이라고 쓰여있는데, 해당 표현 방식이 2진수의 모든 집합을 나타낸 것일까?

 

정답은 아니요이다.  왜냐하면, 2진수에는 0을 포함해야 하는데,

해당 예시에서는 무조건 1부터 시작해야 하기 때문이다.

 

또 다른 표현식과 예시를 보자.

위의 표현식에서 표기할 수 있는 기호와 괄호 안에 들어간 지의 여부를 파악해서

헷갈리지 않도록 조심하자.

 

토큰을 어떻게 인식할까?

우리는 언어를 정규표현식을 통해 표현했다. 이를 그래프로 그릴 수 있는데,

그 그래프를 유한상태오토마타(FSA, Finite State Automata)라고 부른다.

 

유한 상태 오토마타란,

상태를 유한한 개수까지 가질 수 있고,

상태 간의 전의를 정의한다.

또한, 시작 상태 1개와 끝 상태 여러 개를 가진다.

유한 상태 오토마타는 어휘분석의 기초가 되는 이론적 기반인데,

왜냐하면 정규표현식과 동일한 표현력을 갖고 있기 때문이다.

이러한 유한 상태 오토마타는 상태 전이도로 나타낼 수 있다.

 

아래는 유한 상태 오토마타의 예시이다.

l = [a-zA-z]이고, d = [0-9]이다.

식별자 인식

 

정수 인식

위 예시에서는 유달리 + 기호에만 따옴표가 달려 있는데,

그 이유는 + 기호가 1번 이상이라는 의미로 해석될 수 있기 때문에

escape 문자인 따옴표를 달아 +라는 문자로 해석될 수 있게 하였다.

또, ε 문자는 람다와 비슷한 의미로 아무것도 없음을 나타낸다.

 

실수 인식

D 상태부터 E 상태까지의 생김새가 정수와 동일하다.

또한, C 상태에서 종료될 수 있다.

 

문자열 인식

단, a는 "와 \ 이외의 문자이다.

c는 escape 문자이지만, 이 경우에서는 어떤 문자도 될 수 있다.

 

토큰 인식을 위한 처리 절차

토큰 인식을 하기 위해 사용자가 정의한 정규 표현식을 FSA로 표현한다.

이후, FSA대로 인식하면 토큰 인식이 가능하다.

아래 예시를 보자.

정규 표현식을 FSA로 변환한 후 코드로 인식하면 사진과 같다.

위 코드는 입력된 문자가 ! 이면 뒤의 문자까지 확인하여

!=인지 !인지를 판단해 준 후, 다음 문자를 다시 문자열에 넣는다.

코드를 자세히 뜯어보길 바란다.

 

DFA(Deterministic finite automata)

DFA는 FSA의 한 종류로, 간결하여 인식기 구현이 쉽다.

각 상태에서 '나가는 edge'가 레이블 문자에 의해 유일하게 결정되는데,

이 말은 각 상태마다 문자 'a'가 붙은 edge는 하나만 나갈 수 있다는 뜻이다.

 

따라서, 토큰 인식은 정규 표현식을 NFA(none-DFA)로 변환하고,

NFA를 다시 DFA로 변환 후 DFA를 따라 인식하면 된다.

아래의 예를 보자.

 

여러 토큰 인식 시 어떻게 결정할까?

만약 입력으로

elsex = 0;

이 들어왔을 때, 해석은 아래의 두 가지로 나뉠 수 있다.

이러한 경우, 어떻게 해석이 되어야 할까?

 

크게 두 가지의 방법을 사용할 수 있다.

1. 긴 token을 우선으로 한다.

2. token별 우선 순위를 메긴다.

보통은 긴 토큰을 우선으로 하는 방법을 사용한다.

 

토큰은 어떻게 컴퓨터에서 표현될까?

전통적으로 토큰은 컴퓨터에서 Lexeme = <토큰 번호, 토큰 값>의 형식으로 표현된다.

이때 토큰 번호는 각 토큰의 효율적 처리를 위한 고유의 내부번호이고,

토큰 값은 토큰이 프로그래머가 사용한 값을 가질 때의 값을 말한다.

 

이전 포스트에서 식별자와 상수는 다른 방법으로 저장해야 한다고 하였는데,

토큰값에 값을 저장하면서 다른 토큰과의 차이점을 보인다.

명칭(식별자)의 토큰값은 자신의 문자열 값이고,

상수의 토큰 값은 그 자신 상수의 값이다.

아래의 사진은 예시이다.