= 스캐너 제네레이터 =
(스캐너 템플릿)
저번에는 정규식 해석 엔진을 완성했죠,
근데 정규식 하나 입력하고 땡이면 좀 효용성이 없겠져?
그래서 스캐너 제네레이터를 만듭니다.
이는 GNU 의 flex 랑 비슷한겁니다. (어도비(Adobe)의 flex아닙니다!!)
이런 류의 프로그램들을 lexer라고 합니다.
요놈의 역할은 정규식을 입력하고 액션코드를 입력하면
해당 정규식에 텍스트가 매치되었을때 액션코드를 실행하는 겁니다.
템플릿은 다음과 같습니다.
-----------------------------------------
사용자 코드
%%
정규식1 액션코드1
정규식2 액션코드2
...
정규식n 액션코드n
%%
사용자 코드
-----------------------------------------
즉 %% 사이 부분을
스캐너 제네레이터가 자동으로 만들어 주는 겁니다.
C언어로 프로그램 짜는데 단어를 인식하는 부분을 일일히 짜기
귀찬으니까요, 스캐너 제네레이터가 대신 짜주는 겁니다.
결과물은? C언어로 씌어진 코드입니다.
프로그램을 생성하는 프로그램입니다....
재밌지 않나요?? ㅋㅋㅋ
(정규식이 여러개 매치 우선순위)
정규식을 여러개를 매치를 시키게 되므로
정규식 간에도 우선순위가 생기게 됩니다
무슨소리냐고요?? 예를 들면 이런겁니다.
%%
int|char|void printf("type");
[a-z]+ printf("identifier");
; printf("end-statement");
\\s // space char, skip
%%
의 스캐너가 만들어졌다고 해봅시다.
이때 들어오는 문자열이
"int aa;" 라고 하면
첫번째 정규식도 "int"까지 매치하고 성공합니다.
두번째 정규식도 "int" 까지 매치하고 성공합니다.
그러면 어떤 정규식에 매치가 된걸까요???
저희가 구현하려고 하는 pglexer는 이런 상황에서
\'먼저 쓴 놈\' 을 선택합니다.
위 상황의 경우 int 매치가 되면 "type" 가 출력되겠군요
그럼 이런 상황은 어떨까요???
문자열이 "int integer;"
인 경우를 봅시다.
처음 나타나는 "int" 는 매치가 잘되서 "type"
가 될 텐데요 그 뒤에가 문제입니다.
"integer;"
첫번째 정규식의 경우
"int" 까지 매치됩니다.
두번째 정규식의 경우
"integer" 까지 매치됩니다.
그러면 어떤 정규식에 매치되었다고 해야 할까요??
저희가 구현하려는 pglexer 는 이 상황에서는
\'길게 매치된 놈\' 을 선택합니다.
즉 pglexer 는 두가지 원칙을 지니고 있습니다.
1. 길게 매치된 놈
2. 먼저 쓴 놈
을 선택합니다.
원칙이라 말했지만 이건 그냥
max값 찾는거나 마찬가지 입니다.
정규식 매치된 길이를 max값이랑 비교를 하는데
max 보다 더 길게 매치될 때가 되서야 max를 업데이트 합니다.
당연히 max값이니까 길게 매치된것을 선택하는 셈이고
순서대로 찾으니까, 길이가 같게 매치될 경우
먼저 쓴놈이 선택이 되는 겁니다.
(스캐너 함수가 강제 반환후 재호출 되는 상황)
스캔하는 함수명은
pglexer에서는 pg_lex() 입니다.
그냥 \'스캔해라\' 하면 pg_lex()를 호출하면
EOF가 나올때까지 쭉 동작합니다.
근데 파서랑 결합되어서
스캐너 함수가 호출되었다가 반환했다가 하는 경우가 분명 생깁니다.
예를 들면
#define DIGIT 1
#define ADD 2
%%
[0-9]+ return DIGIT;
\\+ return ADD;
[^0-9+]+ // skip
%%
액션 코드에 return 문이 필요한 경우가 생깁니다. 이는
파서와 결합되어 스캔 함수가 토큰을 인식하고
특정 심볼로 반환하는 것을 원하는 경우이지요
다시 파서가 재호출을 할수도 있습니다.
이때 스캐너 함수는 종료되었다가
다시 호출되는 셈이므로
기존에 \'어디까지 매치되었었나??\' 를 알고 있어야 합니다.
pglexer 는 이를 전역변수로 해결합니다. 좀 더럽죠
걍 다시 호출하면
이전까지 매치된 부분부터 다시 시작하여 매칭을 실시하죠
( 어떤 정규식에도 매치되지 않는 상황?)
정규식을 여러개 해놨어도
특수문자를 갈기는 바람에 매치되지 않는 상황도 생길수 있죠?
pglexer같은 경우 이 상황에서는
그냥 error 내뱉고 종료하게 합니다.
왜냐하면 이 스캐너 제네레이터는 DFA 기반입니다.
NFA처럼 유연하지 않습니다.
고로 만일 어떤 정규식에도 매치되지 않는 상황이 생기면
모호해집니다.
준비되지 않은 상황이죠,
만일 모든 정규식이 매치 실패하면
한문자를 건너 뛴다고 해봅시다.
그러면 그 문자는 토큰도 아니죠
텍스트를 토큰으로 쪼개는게 이상해지게 됩니다.
이 부분은 만일 필요하다면 다시 고칠수 있겠죠
(정규식에 매치가 되고 액션코드까지 실행되면 점프한다)
DFA의 파워입니다.
매치된 만큼 건너뛰어 버립니다.
이는 비결정적인 NFA엔진의 백트래킹과는
천지차이인 속도를 보여줍니다.
따라서 \'텍스트 중심 엔진\' 입니다.
(프로그램 완성)
스캐너 제네레이터 완성이 되었습니다.
풀 소스와 예제는 다음에 설명하겠스빈다.
댓글 영역
획득법
① NFT 발행
작성한 게시물을 NFT로 발행하면 일주일 동안 사용할 수 있습니다. (최초 1회)
② NFT 구매
다른 이용자의 NFT를 구매하면 한 달 동안 사용할 수 있습니다. (구매 시마다 갱신)
사용법
디시콘에서지갑연결시 바로 사용 가능합니다.