[형식언어] 어휘분석 - 토큰과 정규 표현

토큰 (Token)

 토큰(Token)이란, 문법적으로 의미 있는 최소 단위를 의미한다. 토큰은 대표 번호(Token Number)와 토큰의 수치, 혹은 string의 값(Token Value)을 가진다. 짧은 구문 'if ( a > 10 )'을 예시로 살펴보자. 'if ( a > 10)'은 토큰 if, (, a, >, 10, )으로 구성된 문장이다. 여기서 'if'는 키워드, '('는 구분자, 'a'는 변수 명, '>'는 연산자, '10'은 상수, ')' 역시 '('와 마찬가지로 구분자에 해당한다. 이렇게 분리된 토큰들은 토큰의 대표 번호와 토큰의 값을 가지고, 이 정보들이 Parser에 전달된다. 분리된 토큰들은 Token Type에 맞게 Parser에 토큰의 정보를 전달한다. Token Type이 (토큰 번호, 토큰 값)이라면, 'if ( a > 10 )' 구문은 if - (32, 0), ( - (7, 0), a - (4, 'a'), ...에 해당하는 정보를 Parser로 전달하는 것이다. 

 

 토큰의 구조(Token Structure)는 정규 표현식으로 표현한다. 변수 명에 해당하는 id를 정규 표현식으로 표현하면 id = (letter + _)(letter + digit + -)$^*$이다. 이 정규 표현식을 해석하면, 변수 명은 문자 혹은 _로 시작해야 하며, 변수 명의 첫 글자 뒤에는 문자, 숫자, _가 0개 이상 반복하여 나타날 수 있음을 의미한다.

 

Token Class

 다음으로 토큰의 종류에 대해 알아보자. 토큰은 특수 형태(Special Form), 일반 형태(General Form)로 구분할 수 있다. 특수 형태 토큰에는 지정어(Keyword), 연산자(Operator Symbols), 구분자(Delimiters)가 존재한다. 지정어는 우리가 흔히 보는 if, else, if, int, double, ...에 해당하는 토큰이며, 연산자는 흔히 사용하는 +, -, *,...와 같은 연산자에 해당한다. 마지막으로 구분자는 ;, (, ), [, ],... 등 토큰 구분의 역할을 하는 토큰이라 생각하면 될 것이다.

 

 일반 형태 토큰에는 명칭(identifier), 상수(constant)가 존재한다. 명칭(id)은 다른 형식언어 포스팅에서도 보았듯 변수 명에 해당하며, 상수 역시 우리가 코드에서 흔히 사용하는 그것이다.

 

어휘 분석기

 어휘 분석기(Lexical Analyzer)는 정규 표현식을 이용해 유한 오토마타(Finite Automata)를 이용해 구현한다. 어휘 분석기를 통해 얻어낸 토큰 정보는 Parser로 향하며 Parser에서는 PushDown Automata를 이용해 구문 분석을 실행한다. 이때 어휘 분석기에서 얻어낸 토큰 정보는 앞서 말한 토큰 타입에 정의한 형태로 전달된다.

 

 어휘 분석기(Scanner)와 구문 분석기(Parser)는 분리하는 것이 좋은데, 모듈러한 컴파일러를 구성할 수 있으며 컴파일러의 이식성과 효율성을 향상할 수 있기 때문이다. Parser에는 파싱 테이블(Parsing table)이라는 Parser의 행동을 결정하는 것이 있는데, 가장 처음 토큰에서 설명한 토큰의 번호가 파싱 테이블의 index가 된다. 파싱 테이블을 보고 파서는 Shift, Reduce, Accept, Error 중 하나의 행동을 결정하게 된다.

 

여러 인식기

 토큰은 유한 오토마타(FA)를 이용하여 표현한다고 하였다. 앞에서 언급한 변수 명에 해당하는 id를 인식하는 인식기를 만들어보자. 변수 명은 문자 혹은 _로 시작해야 하며, 변수 명의 첫 글자 뒤에는 문자(letter), 숫자(digit), _가 0개 이상 반복하여 나타날 수 있어야 하며, 이것을 FA로 구성하면 아래와 같다. 

 

변수 명 다음으로 문자열(string)을 인식하여보자. 문자열은 쌍따옴표 안에 문자가 연속하여 존재하는 것이다. 이것을 정규 표현식으로 표현하면 string = "(a + \c)$*$"이다. 이때, c는 문자 character의 집합이며 a는 c에서 쌍따옴표 "와 escape 문자인 \를 제외한 문자의 집합이다. 이것을 FA로는 아래와 같이 표현할 수 있다.

 

 이외에도 정수, 실수, 주석(Comment) 등을 인식하는 인식기 역시 구현할 수 있다. 정수를 8진수, 10진수, 16진수로 구성한다면, 10진수는 0이 아닌 수로 시작하는 수에 해당하며, 8진수는 0으로 시작하는 수, 16진수는 0x 혹은 0X로 시작하는 숫자이니 이것들을 인식하는 FA를 구성하면 정수를 인식할 수 있다.

 

 실수는 고정 소수점 형태와 부동 소수점 형태가 존재하는데, 고정 소수점 형태부터 처리해 보자. 고정 소수점은 가장 먼저 숫자로 시작하며 이후에 숫자가 0회 이상 연속되어 나타난 이후, 소수점이 나타나고 소수점 뒤에는 반드시 하나 이상의 숫자가 등장해야 한다. 이것을 정규 표현식으로 표현하면 d$^+$.d$^+$ 형태가 된다. 부동 소수점은 고정 소수점 뒤에 지수부가 존재하는 것으로 지수부를 처리해주면 된다. 지수부는 문자 e가 1회 나타나고, e의 지수로 +, -, 숫자가 위치할 수 있다. 이것을 정규 표현식으로는 e(ε+ '+' + -)d$^+$로 표현할 수 있다. 마지막으로 고정 소수점과 부동 소수점의 정규 표현식을 합치면 실수를 표현할 수 있고, 실수는 d$^+$.d$^+$+e(ε+ '+' + -)d$^+$의 정규 표현식 형태로 표현된다.

 

 주석은 /* (주석 내용 (ex) ** ... **))  */의 형태인데, *이 주석 내부에서 나타날 수 있으며 escape 문자인 \를 유의하여 FA를 구성하면 될 것이다.