확장 정규식 parsing 템플릿

간단프로그래밍2010. 10. 4. 01:47

확장 정규식 parsing 템플릿

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define PRINT
#define REGEX_SIZE 128

#ifdef PRINT
	#define P print_level(l)
#endif

char regex[REGEX_SIZE];
char* lookahead;

//
#ifdef PRINT
void print_level(int level){
	int i;
	for(i=0;i<level; i++)
		printf(".  ");
}
#endif

// util func
void regex_syntax_error(){
	puts("regex syntax error");
	exit(1);
}
int match(const char c){
	if(*lookahead!=c)
		regex_syntax_error();
	lookahead++;
}
void init(){
	lookahead = regex;
}

//
// parse rules
//
void Regex(int);   // Regex		->	Concat Regex_
void Regex_(int);  // Regex_	->	'|' Concat Regex_ | epsilon
void Concat(int);  // Concat	->	Term Term_
void Quant(int);   // Quant		->	'+' | '*' | '?' | epsilon
void Term(int);    // Term		->	'(' Regex ')' Quant
				   //			|	'[' Class ']' Quant
				   //			|	'\' Escape Quant
				   //			|	'[^+*?)\]|]' Quant
void Term_(int);   // Term과 똑같으나 반복한다.
void Class(int);   // Class		->	Not Body
void Escape(int);  // Escape	->	'+' | '*' | '?' | '\|' | '(' | ')' | '[' | ']' | '.' | 'd' | 'w' | 't' | 'n'
void Not(int);     // Not		->	'^' | epsilon
void Body(int);	   // Body		-> Char Range
void Char(int);    // Char		-> '-' 문자가 아닌문자 '\' 문자가 왔을때 '[',']','t','n','-' 이스케이프 처리
void Range(int);   // Range		-> '-' Char | epsilon
//

//************************//
//*                      *//
//* parse regex by LL(0) *//
//*                      *//
//************************//

void parse_regex(){
	Regex(0); match(0);
}

void Regex(int l){
#ifdef PRINT
	P;puts("regex");
#endif
	Concat(l+1); Regex_(l);
}
void Regex_(int l){
	while(1){
		if(*lookahead=='|'){
#ifdef PRINT
	P;puts("union '|'");
#endif
			match('|'); Concat(l+1); continue;
		}
		break; // epsilon
	}
}
void Concat(int l){
#ifdef PRINT
	P;puts("concat");
#endif
	Term(l+1); Term_(l+1);
}
void Quant(int l){
	switch(*lookahead){
		case '+': match('+'); break;
		case '*': match('*'); break;
		case '?': match('?'); break;
		default: return;
	}
#ifdef PRINT
	P;puts("quant");
#endif
}
void Term(int l){
#ifdef PRINT
	P;puts("term");
#endif
	switch(*lookahead){
		case '(':
			match('('); Regex(l+1); match(')'); Quant(l+1); break;
		case '[':
			match('['); Class(l+1); match(']'); Quant(l+1); break;
		case '\\':
			match('\\'); Escape(l+1); Quant(l+1); break;
		
		case '+':case '*':case '?': case ')':case '|':
			regex_syntax_error();

default:
			match(*lookahead); Quant(l+1); break;
	}
}
void Term_(int l){
	while(1){
		if(*lookahead==')'||*lookahead=='|'||*lookahead=='\0')
			break;
#ifdef PRINT
	P;puts("term");
#endif	
		if(*lookahead=='+'||*lookahead=='*'||*lookahead=='?'){
			regex_syntax_error();

}else if(*lookahead=='('){
			match('('); Regex(l+1); match(')'); Quant(l+1); continue;
		}else if(*lookahead=='['){
			match('['); Class(l+1); match(']'); Quant(l+1); continue;
		}else if(*lookahead=='\\'){
			match('\\'); Escape(l+1); Quant(l+1);continue;
		}else{
			match(*lookahead); Quant(l+1); continue;
		}
	}
}

////
void Class(int l){
#ifdef PRINT
	P;puts("Class");
#endif	
	Not(l+1); Body(l+1);
}
void Not(int l){
	if(*lookahead=='^'){
#ifdef PRINT
	P;puts("Not");
#endif	
		match('^');
	}
	// or epsilon
}
void Body(int l){
#ifdef PRINT
	P;puts("Body");
#endif	
	while(1){ // not allow '[', ']' in body
		if((*lookahead != '[') && (*lookahead != ']')){
			Char(l+1); Range(l+2); continue;
		}
		break; // or epsilon
	}
}
void Range(int l){
	if(*lookahead=='-'){
#ifdef PRINT
	P;puts("Range");
#endif	
		match('-'); Char(l+1); 
	}
	//or epsilon
}
void Char(int l){
#ifdef PRINT
	P;puts("Char");
#endif	
	switch(*lookahead){
		case '-' : regex_syntax_error();

case '\\': 
			match('\\');
			switch(*lookahead){
				case 't': match('t'); break;// \t
				case 'n': match('n'); break;// \n
				case '[': match('['); break;// escape '['
				case ']': match(']'); break;// escape ']'
				case '-': match('-'); break;// escape '-'
				default:
					regex_syntax_error();
			}
			break;
		default:
			match(*lookahead); // character
	}
}

void Escape(int l){
#ifdef PRINT
	P;puts("Escape");
#endif
	switch(*lookahead){
		case 't': match('t');break; //tab
		case 'n': match('n');break; // new line
		case '(': match('(');break; // (
		case ')': match(')');break; // )
		case '[': match('[');break; // [
		case ']': match(']');break; // ]
		case '*': match('*');break; // *
		case '+': match('+');break; // +
		case '?': match('?');break; // ?
		case '|': match('|');break; // |
		case '.': match('.');break; // all character
		case 'd': match('d');break; // all digit
		case 'w': match('w');break; // all word
		default:
			regex_syntax_error();
	}
}

int main(void)
{
	init();
	strcpy(regex,"\\d+a[^ac-g]*ef+");
	parse_regex();

puts("\naccept");
	return 0;
}

기본 정규식 |,*, concatenation

에 문자 클래스 ex) [a-z]

포함시키고

몇가지 escape 처리까지 포함 하였다.

http://codepad.org/ExTvEtuR

실행결과는

그냥 파싱(LL(0))만 한다.

맞는지 틀리는지만 확인

저작자표시

'간단프로그래밍' 카테고리의 다른 글

3D 렌더러 학교 플젝 소, opengl 점 찍는 함수만 사용 (0)	2011.06.19
opencv SURF 실험 (0)	2011.05.09
확장 정규식 parsing 템플릿 (0)	2010.10.04
floating point (0)	2010.04.12
BIG INT 그리고 팩토리얼 (0)	2010.03.06
strlen, strcpy, strcat, strcmp 구현해보기 (2)	2009.12.04

Posted by 멍충한아싸

Trackback 0 Comment 0

댓글을 달아 주세요

«이전 1 ··· 6 7 8 9 10 11 12 13 14 ··· 16 다음»

일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

성대아싸의 멍충한 프로그래밍