컴파일러 - 어휘분석기 - 정규표현식

어휘분석기 - 정규표현식(regular expression)

1. 개요

정규표현식을 한마디로 말하자면 문자들의 집합(이 집합을 언어라고 한다) 간결한 패턴으로 표현하는 방법이다.

사실 정규표현식이야 개발간에 많이 사용한다.
가령 로그인간 아이디 형태 검증이나, 이메일 형태 검증만 예시를 들어도 바로 알 수 있을 것이다. 우리가 단순히 문자열 매칭에 사용하기도하지만 그외에 1968년부터 컴파일러의 어휘분석에서도 많이 사용되었다.

여기서 말하는 어휘분석이란 원시 소스코드를 토큰으로 분할하는 패턴을 정의하는 것을 말하며 토큰화 된 데이터를 파서로 넘김으로써 해당 토큰들의 조합에 의미 분석을 하게 된다.

2. 쓰이는 방식

1. 각 토큰 종류(키워드, 식별자, 숫자, 문자열 리터럴, 연산자등)에 대해 정규표현식 규칙을 정의한다.
2. 스캐너 생성기에서 정규 표현식 규칙을 받아 NFA-> 부분집합 변환 -> DFA -> 최소화된 DFA를 만든다.
3. 이후 입력을 한번 훑어서 O(n) 시간에 토큰을 분리하는 스캐너 코드를 생성한다.

3. 정규표현식 문법

기본 문법을 요약해서 표로 나타내면 아래와 같다.

요소	기호 / 예시	설명	컴파일러(lex 계열) 팁
리터럴	abc	문자를 그 순서대로 매칭. 공백·특수문자는 이스케이프 필요할 수 있음.	예약어처럼 고정 문자열 매칭에 사용.
대체(또는)	a|b	a 또는 b 중 하나를 매칭. 괄호와 함께 복합 패턴 구성 가능.	우선순위·길이 규칙으로 어떤 대체가 선택될지 영향 받음.
연결 (Concatenation)	ab	a 다음에 b가 오는 순서로 매칭 (암묵적 연결).	암묵적이므로 따로 기호 없음.
반복 / 수량자	a*, a+, a?, a{2,5}	a*: 0회 이상, a+: 1회 이상, a?: 0 또는 1회, {m,n}: m~n회 반복.	렉서에서 기본적으로 greedy(가장 많이) 매칭을 하는 경우가 많음(주의).
문자클래스	[0-9], [A-Za-z_]	괄호 안의 문자 중 하나를 매칭. 범위(-) 사용 가능. [^…]는 부정.	식별자·숫자 등 토큰 정의에 자주 사용.
닻 (Anchor)	^, $	^: 입력(또는 행)의 시작, $: 입력(또는 행)의 끝을 의미.	스캐너에서는 전체 스트림 기준보다 룰과 함께 longest-match 규칙으로 처리되는 경우가 많음.
그룹 및 캡처	( ... )	패턴을 하나의 단위로 묶음. 캡처는 엔진에 따라 지원(백트래킹 엔진에서 그룹 캡처 사용).	컴파일러 렉서는 캡처 대신 매칭 자체가 중요하므로 단순 그룹화(우선순위)로 사용.
이스케이프	\n, \t, \\, \[	특수문자(메타문자)를 문자 그대로 사용하거나 제어문자 표기.	lex 계열에서는 \ 처리가 도구별로 다를 수 있으니 매뉴얼 확인 권장.
역참조 (주의)	\1 등	이전 그룹에서 캡처한 내용을 다시 참조(백참조).	역참조는 정규 언어의 범위를 벗어나므로 전통적 렉서/스캐너에서는 사용하지 않음.
기타 확장	[:digit:] 등 POSIX 클래스, lookaround 등	엔진에 따라 추가 기능(유니코드, 클래스, lookahead 등)이 존재.	컴파일러용 렉서는 표준화된 단순 문법과 상태(모드)를 선호.

※ 숫자, 식별자, 예약어 충돌 방지 기법

lex/flex 계열에서는 입력 스트림에서 가장 긴 매치(최대 일치, max-munch)를 먼저 찾는 방식과 토큰 우선순위(길이 동일 시 규칙 순서 또는 우선순위 테이블) 규칙을 같이 적용하여 충돌을 방지한다.

4. 실제 컴파일러에서 사용하는 예시

%{
/* C 코드 헤더(선언) */
%}

%%
"if"           { return IF; }            /* 예약어 */
[a-zA-Z_][a-zA-Z0-9_]*  { yylval.s = strdup(yytext); return IDENT; }
[0-9]+(\.[0-9]+)?       { yylval.num = atof(yytext); return NUMBER; }
"//".*                  { /* 한 줄 주석 무시 */ }
[ \t\n]+                { /* 공백 무시 */ }
.                       { return yytext[0]; } /* 기타 문자 */
%%

위 예시는 flex 코드로 짠 예시이다. 위 처럼 정규표현식 규칙과 액션을 쌍으로 제작하면 flex가 자동으로 스캐너 코드를 생성한다.

5. 한계

• 스택이 필요한 중첩구조(중첩 괄호 등)을 처리하지 못하므로 파서나 상태 기반 처리를 해주어야한다.
• 복잡한 백트래킹 패턴은 입력 길이에 따라 매우 느려질 수 있다.
• 문자 인코딩의 차이나 유니코드 처리에 따라 읽는 범위를 달리 처리해주어야한다.

추가 업데이트 예정

참고자료

• 컴파일러 : 원리, 기법, 도구 제 2판. ALFRED V. AHO, MONICA S. LAM, RAVI SETHI, JEFFREY D. ULLMAN. 우원희, 신승철, 우균, 하상호 옮김
• 위키백과 - 컴파일러
• Lexical Analysis With Flex, for Flex 2.6.2
• [컴파일러] - 어휘 분석 (Lexical analysis) II