본격
= 정규식 해석 엔진 =


저번에 Strong LL grammar 라는 파싱 방법을 사용하여

정규식을 파싱한다고 했습니다.


본래 Strong LL Grammar 는 LL(k) Grammar의 부분집합으로

Context Free Grammar에서 제일 약한 놈이라고 보시면 됩니다..


아 이상한 단어들 너무 많이 나오져?


원래 컴파일러, 혹은 오토마타 수업을 듣게 되면

배우는 순서가

1. Finite Automata (= Regular grammar, Regular Expression)

2. Pushdown Automata (= context free grammar)


인데 웃기게도 

정규식만 대충 살핀 상태에서 

CFG(context free grammar)를 먼저 사용하겠다 이겁니다.


왜냐하면 입력된 정규식은 그냥 문자열 입니다.

이를 원하는 대로 뽑아내고 가공하기 위해서는

최소 SLG( strong ll grammar) 의 힘이 필요하기 때문입니다.

근데 SLG 생각보다 쉽습니다. 걱정하지 마세여



SLG는  \"재귀하향 파싱\" 의 가장 원초적인 형태로서 진짜 간단합니디.

이 SLG의 좋은예로

1. 비야네스트릅스트룹의  \"The C++ Programming Language\" 책에서 계산기 부분

2. 홀럽의 \"실용주의 디자인 패턴\" 에서 미니 데이터베이스 만들때 SQL 처리하는 부분

3. 용책, LL 파싱 부분



우선  CFG 에 익숙해질 필요가 있습니다. 

Expr -> Expr \'+\' Expr

대략 이런 형태입니다.

그냥 단어로 되어 있는 놈

Expr : 논터미널

이라고 합니다.


따옴표로 둘러싸인 놈

\'+\' : 터미널

이라고 합니다.


-> :  프로덕션


프로덕션 좌측을 Head 라고 하고 우측을 Body라고 합니다.


의미가 무엇이냐면  

1. Body 부분이 Head로 대체될 수 있다?

혹은

2. Head 부분이 Body 모양으로 확장된다?

우선 이렇게 간단하게 알아둡시다.



터미널은 파싱을 진행할때 

\'그 순간에 멈추는 놈\' 이라고 보면 됩니다.

실제 들어온 문자열이라고 해야할까요..

논터미널은 파싱을 진행할때

확장 되는 놈 (2번의 의미로 해석하여) 이라고 봅시다.

그리고 SLG 는 재귀 하향 파싱 이라고 했습니다.


그러면 결국 

논터미널 : 프로시져 (함수)

터미널 : 입력되어 쪼개진 토큰 문자열 하나

이 됩니다.


뭔소린가 하실텐데

결국 이겁니다.


예를 들어서

우선 사칙연산을 인식하는 문법을 만들어 보겠습니다.



Expr -> Term Expr_ ;

Expr_ -> \'+\' Term Expr_  | \'-\' Term Expr_ | ;

Term -> Factor Term_ ;

Term_ -> \'*\' Factor Term_ | \'/\' Factor Term_ | ;

Factor -> \'(\' Expr \')\' | \'NUMBER\' ;



\'|\' 문자로 body 가 여러개로 구분되는데 그중 하나를 선택 가능한 겁니다. 

Expr_ 인 경우 body 가 없는 경우도 있죠??



즉 재귀하향파싱의 의미에 의해서

처음 Expr 요놈이

더이상 확장 될 수 없을 때까지

주어진 규칙에 의해서 확장 됩니다.


쫙 트리처럼 펼쳐지겠죠?

아까 논터미널이 함수라고 했는데

그 의미는

Expr -> Term Expr_;

요놈은

void Expr (){
        Term();
        Expr_();
}

이게 되는 겁니다.


Factor -> \'(\' Expr \')\' | \'NUMBER\' ;

요놈은

void Factor(){
        if(strcmp(token, \"(\") == 0){
                matching(\"(\");
                Expr();
                matching(\")\");
        }else
        if(is_number(token)){
                matching(token);
        }else{
                // error
                exit(1);
        }
}

좀 복잡하죠?? UNION에 의해 두개중 택일이 되어야 하니까요

if 문 으로 선택이 되죠

토큰이 \"(\" 도 아니고 숫자도 아니면 문법 상에서 어떻게 진행할 방법이 없습니다.

에러를 뱉어버리고 종료되겠죠 

컴파일러라면? 컴파일 에러죠 ㅋㅋ



Expr_ -> \'+\' Term Expr_  | \'-\' Term Expr_ | ;

요놈은 재밌는 놈입니다.

왜냐하면 body 중에 \'아무것도 없는\' 놈이 있으니까요 (맨뒤에놈)


void Expr_(){

        if(strcmp(token, \"+\")==0){
                matching(\"+\");
                Term();
                Expr_();
        }else
        if(strcmp(token, \"-\")==0){
                matching(\"+\");
                Term();
                Expr_();
        }
}


위와 차이점은  위경우는 두개중 하나가

\'반드시\' 선택이 되어야 하여 

else 문으로 에러이면 강제종료입니다.


지금 같은 경우는 body 에 \'아무것도 없는놈\' (epsilon 이라합니다)

이 있기 때문에 그냥 넘어갑니다.

터미널이 아무것도 매치 안되면 결국은 \'없는 놈\' 이 되지 않겠습니까??



또 재밌는 사실은

Expr_ -> \'+\' Term Expr_  | \'-\' Term Expr_ | ;

요놈은 꼬리 재귀 (tail recursion) 형태입니다.

epsilon 을 제외하고 모든 바디의 뒷부분에 자기자신이 있죠?


tail recursion 은 손쉽게 반복문으로 바꿀수 있습니다.


void Expr_(){
        while(1){
                if(strcmp(token, \"+\")==0){
                        matching(\"+\");
                        Term();
                        continue;
                }else
                if(strcmp(token, \"-\")==0){
                        matching(\"+\");
                        Term();
                        continue;
                }
                break;
        }
}


기가 막히지 않나요?? 저는 처음 이 형태를 봤을때 온몸에 전율이 돋더라고요






지금까지

함수로 옮긴 형태가

재귀하향 파싱 방법이고

SLG 형태였습니다.

이 SLG는 문법을 바로 프로시져의 형태로

구현 가능하다는 점에서

쉽고, 간단하다는 장점이 있습니다.



하지만 몇가지 제약 사항이 있는데요



1.  UNION 에 의해 body 가 여러개로 나누어 질때는 반드시 body 제일 앞에

터미널이 와야 하고, 중복이 되면 안됩니다.

반드시 하나로 선택이 되어야 합니다.

여러개의 body 중 하나를 선택하기 위한 조건이죠


2. tail recursion 의 경우에는 반드시 epsilon 도 같이 있어야 합니다.

재귀 호출에서 탈출조건이 있어야 하는 것처럼요 어떤 터미널에도 매치 안되면

재귀에서 탈출해야죠


3.  1번과 2번에 의해서 tail recursion의 경우는 반드시 body 앞에 터미널이 와야하며

body는 반드시 epsilon 을 포함하여야 합니다.



위 조건을 만족하면서 문법을 작성하기란 굉장히 어려운 일입니다.

특히 계속 반복을 사용해야 하는 상황에서는

반드시 tail recursion을 쓸수 밖에 없는데요

앞대가리에 반드시 터미널이 오게 문법을 작성하는것이 굉장히 고역입니다..


어쨋든 문법을 \"잘\" 작성하게 되면


손쉽게 프로그램으로 옮길 수 있습니다.

그리고 문법이 그대로 코드에 반영된다는 점에서 이해하기 쉽죠






지금까지 SLG에 대해서 알아본 이유는

정규식을 해석하기 위해서죠?


그래서 준비했습니다.

제가 나름 짱구 돌려가면서


프갤 스캐너 제네레이터용

정규식을 인식하는

SLG 문법을 작성해보았습니다.




Regex -> Concat Regex_;

Regex_ -> \'UNION\' Concat Regex_ | ;

Quant -> \'PLUS\' | \'STAR\' | \'QUES\' | ;

Concat -> 
                         \'LP\' Regex \'RP\' Quant Concat_  
                        |\'LB\' Class \'RB\' Quant  Concat_ 
                        |\'ES\' Escape Quant Concat_ 
                        |\'DOT\' Quant Concat_
                        |\'FACTOR_CHARACTERS\' Quant Concat_  ;

Concat_ -> 
                         \'LP\' Regex \'RP\' Quant  Concat_ 
                        |\'LB\' Class \'RB\' Quant Concat_ 
                        |\'ES\' Escape Quant Concat_ 
                        |\'DOT\' Quant Concat_
                        |\'FACTOR_CHARACTERS\' Quant Concat_ 
                        |
                        ;

// character class //

Class -> Not Body;

Not -> \'HAT\' | ;

Body -> \'CLASS_CHAR\' Range Body | ;

Range -> \'HYPEN\' \'CLASS_CHAR\' | ;


// escape //

Escape -> \'SPACE\' | \'TAB\' | \'LINE\'
                | \'ES\'
                | \'PLUS\' | \'STAR\' | \'QUES\'
                | \'LB\' | \'RB\' | \'LP\' | \'RP\'
                | \'UNION\'
                | \'DOT\'
                ;




뭔가 굉장히 복잡하죠?? ㅋ

터미널이 기호로 안되어있고 전부 문자로 되어있는데요

그 이유는 제가 만든 툴에 적용 시키기 위해서 입니다.


Strong
LL grammar
To
Procedure

SL2P 라는 프로그램이 있는데요 , 제 블로그에 소스가 있습니다,

사용하고 싶으시믄 컴파일 해서 쓰면 됩니다.

진짜 단순한 프로그램으로서 단지 노가다를 줄여주는 의미밖엔 없습니다.

처음엔 직접 프로시져(함수) 로 짜보세연


sl2p 는 문법이 잘 작성 되어있다고 가정하고 동작하기 때문에

에러 체킹 안해서요 잘 작성해야 됩니다.


위 문법을 sl2p 프로그램 돌리고

여러 군데를 수정하여 

c언어 소스는 다음과 같습니다.





걍 정규식을 입력하면

accept 되는지 에러 나는지 확인만 해줍니다. 

(이게 진정한 의미의 파싱입니다)




다음에는  위 간단한  정규식 문법을 뜯어보고

왜 이렇게 만들었는가 를 살펴보겠습니다.