IR 그룹의 하얀 눈길 님께서 작성하신 글입니다.
원문은 여기를 누르시면 볼 수 있습니다.
소스를 vc++6.0로 바꾸려니 꽤나 갑갑하네요..
프로젝트 압축화일은 자료실에 올리겠습니다.
=================================================================================
HTML이란 Hypertext Markup Language의 약자로서 플랫폼에 의존되지 않는 하이퍼텍스트 문서를 생성할 때 사용되는 구조화된 마크업 언어이다.
현재 버젼 4.01까지 나와 있는 상태이며, 4.01에 대한 자세한 내용은 http://www.w3.org/MarkUp/를 참조하기 바란다.
또한 RFC 1866 문서(http://www.rfc-editor.org/rfc/rfc1866.txt)를 보면 HTML에 대한 문법 및 구조를 정확히 파악할 수 있다.
이 강좌에서는 문법에 대해서 논하기 보다 파서를 구현함에 있어서 알아야 할 기본적인 구조에 대해서만 설명하겠다. 프로그램은 c++로 구현하겠다. 참고로 필자는 c++을 c처럼 쓰는 사람이라 c++에 대한 오류나 더 쉬운 방법이 있다면 제안해 주기 바란다.
다음 예를 보자.
<!DOCTYPE html PUBLIC "-//IETF//DTD HTML 2.0//EN">
<title>HTML 테스트</title>
<p>테스트 페이지입니다.<em>*^_^*</em></p>
예1. html 코드 예제
위 예1. 을 파서가 해석한다면 다음과 같은 형태로 인식하게 될 것이다.
1. 시작태그 : title
2. 데이타 문자들 : "HTML 테스트"
3. 종료태그 : title
4. 시작태그 : p
5. 데이타 문자들 : "테스트 페이지입니다."
6. 시작태그 : em
7. 데이타 문자들 : "*^_^*"
8. 종료태그 : em
9. 종료태그 : p
처음 "<!DOCTYPE..." 은 주석이므로 큰 의미가 없다. 단지 사용자 에이전트가 알 수 있도록 HTML의 버젼과 범용적인 정보를 표시한 것이다. 여기서 7의 항목은 HTML을 위해 정의된 SGML 문법에 따라 *가 "*"로 변환 된 것이다.
위 시퀸스들을 파싱하게 되면 다음 구조가 된다.
도표 1을 보면 html 자체를 하나의 트리로 파싱될 수 있음을 알 수 있다.
HTML, HEAD, BODY 태그는 예1에 존재하지 않지만 HTML 문법상 기본적인 구조를 이루는 것이므로 파싱된 결과에 태그는 없다 하더라도 반영된 것을 볼 수 있다. 이런 식으로 HTML 전체 문서를 파싱하여 트리를 만드는 것으로 파싱 프로그램을 구현하도록 하겠다.
HTML의 기본적인 구조가 있다고 하더라도 원문에 없을 경우 뼈대를 생성할 이유는 없다고 본다. html 문서를 만드는 대부분의 사용자들이 이런 뼈대에 별로 민감하지 않다. 없는 경우도 많고 어떤 경우는 HTML 태그 자체도 여러번 나타날 수 있다. 그래서 이 강좌에서 구현할 파서를 위해 도표1 을 좀더 단순화 하겠다.
도표 2.를 보면 예1의 시퀸스와 부합되어 더 쉽게 이해할 수 있을 것이라 본다.
불필요한 뼈대를 모두 제거했다.
그리고 태그들의 정보와 문자들을 단순한 트리에 연결시킨 것이다.
다음 예2는 예1을 좀더 확장한 것이다.
<title>HTML 테스트</title>
<p id=t1 align=right>테스트 페이지입니다.<em>*^_^*</em></p>
예2. 확장된 HTML 코드 예제
예2에서 확장된 것은 p 태그에 대한 것이다.
태그는 속성을 가질 수 있으며 여러개의 속성을 가질 경우 위 예와같이 계속적으로 나열하여 태그를 구성할 수 있다.
이러한 태그의 속성까지 파싱한 것이 다음 도표 3이다.
다음 그림 도표 3을 보자.
우리의 최종 목표는 도표3과 같은 형태로 파싱하기 위한 파서를 만드는 것이다.
도표 3의 트리는 이진트리로서 왼쪽 노드는 다음 태그를 가리키게 되고, 오른쪽 노드는 현재 태그의 속성을 가리키게 된다. 하나의 오른쪽 노드(속성)는 왼쪽 노드를 가질 수 없으며 다음 속성을 가리키기 위해 계속 오른쪽 노드만 추가하게 된다.
알고리즘은 다음과 같다.
1. 원문에서 처리되지 않은 처음 문자를 읽는다. 그렇지 않으면 종료한다.
2. 공백이면 스킵하고 1로 돌아간다.
3. 종료태그이면 스킵하고 1로 돌아간다.
4. 유효한 시작태그이면 트리에 새로운 태그노드를 삽입한다. 그렇지 않으면 6으로 건너뛴다.
5. 태그 속성을 파싱하여 태그노드에 속성을 연결한후 1로 돌아간다.
6. 데이타 문자열에 현재 문자를 추가한 후 1로 돌아간다.
그럼 지금 부터 실제 코드를 보자.
사실 HTML Parser와 관련된 많은 오픈 소스들이 배포되었고 좋은 성능을 내고 있다. 실제 개발 과정에서는 이러한 라이브러리를 찾아 써도 상관 없지만, 기본적인 개념을 알고 있어야 효과적으로 제어하고 활용할 수 있다.
파싱 트리를 표현하기 위한 클라스는 다음과 같다.
class HtmlTag
{
public:
// Member Variables
HtmlTag *nextHtmlTag; // 다음번 HtmlTag를 가리킴
TagVar *firstTagVar; // HtmlTag안의 첫번째 Variale이 저장될 TagVar를 가리킴
TagVar *lastTagVar; // HtmlTag안의 첫번째 Variale이 저장될 TagVar를 가리킴
HtmlTag();
~HtmlTag();
// get Function
TagVar *getTagVar(char *szName) const;
char *getTagName() const;
// set Function
int setTagName(char *name);
// ETC.
int addTagVar(TagVar *tv);
void print() const;
private:
char szTagName[NAME_SIZE]; // Tag Name 저장
};
태그의 속성을 표시하기 위한 클라스는 다음과 같다.
class TagVar
{
public:
// Member Variables
TagVar *nextTagVar;
TagVar();
~TagVar();
// set Function
int setVar(char *var);
int setVal(char *val);
// get Function
char *getVar() const;
char *getVal() const;
private:
char *szVar, *szVal; // 변수이름과 값을 저장
};
HtmlTag 클라스는 한개의 태그에 대한 정의이다. 이 클래스의 내용을 보면 다음 태그를 트리로 연결하기 위해 멤버변수로 HtmlTag 타입의 nextHtmlTag 포인터를 가지고 있다. 이는 도표 3.의 왼쪽 노드가 된다.
태그의 속성을 표시하기 위해 TagVar 클라스 포인터를 멤버 변수로 가지고 있다. firstTagVar 포인터가 바로 그것이며 이 녀석이 태그의 첫번째 속성을 가지게 된다.
TagVar 클래스의 내용을 보면 다음 속성을 가지기 위해 nextTagVar 포인터를 멤버변수로 가지고 있는 것이 보인다. 이것이 도표3에서의 오른쪽 노드가 되는 것이며 실제는 링크드리스트로 구현된다.
다음은 위 두개의 클래스를 묶어서 전체 HtmlParser 클래스로 정의된 클래스이다.
class HtmlParser
{
public:
HtmlTag *firstHtmlTag; // 문서의 첫번째 HtmlTag를 가리킴.
HtmlTag *lastHtmlTag; // 문서의 첫번째 HtmlTag를 가리킴.
HtmlParser();
~HtmlParser();
int exeParser(char *szHtmlTxt);
void print() const;
private:
int addHtmlTag(HtmlTag *ht);
HtmlTag *parseHtmlTag(char **buf);
HtmlTag *parseTextData(char **buf);
HtmlTag *parseComment(char **buf);
int parseVarVal(HtmlTag *ht, char **buf);
};
HtmlParser 클래스는 Htmltag 클래스를 멤버변수로 가진다. 이 멤버는 html의 처음 태그 위치를 나타내게 된다. lastHtmlTag 멤버는 큰 의미는 없다.
실제 파싱을 수행하는 메소드가 exeParser로서 html 문자열을 입력받아 순차적으로 처리하게 된다. 이 메서드가 위에서 설명한 파싱 알고리즘을 처리하는 부분이다.
print 메소드는 결과 검증을 위해 화면에 출력하도록 만든 테스트용이다.
private의 메소드들은 모두 exeParser 메소드에서 필요에 의해 호출하는 함수들로 세부 내용은 피하도록 하겠다.
다음은 exeParser의 내용이다.
int HtmlParser::exeParser(char *szHtmlTxt)
{
HtmlTag *ht;
if(!szHtmlTxt)
return 0;
while(szHtmlTxt)
{
if(*szHtmlTxt == '' *szHtmlTxt == EOF)
break;
ht = NULL;
skipBlank(&szHtmlTxt);
if(!*szHtmlTxt)
break;
if(*szHtmlTxt == CLOSE_TAG)
{
szHtmlTxt++;
skipBlank(&szHtmlTxt);
continue;
}
else if(*szHtmlTxt == OPEN_TAG)
{
szHtmlTxt++;
skipBlank(&szHtmlTxt);
switch(whatIsTag(szHtmlTxt))
{
// COMMENT TAG
case COMMENT_TAG:
ht = this->parseComment(&szHtmlTxt);
break;
// 여기에선 VALID, INVALID 모두 처리한다.
case VALID_TAG:
case INVALID_TAG:
ht = this->parseHtmlTag(&szHtmlTxt);
break;
// ETC.
default:
continue;
}
}
// OPEN_TAG가 아니면 TEXT_DATA로 간주한다.
else
ht = this->parseTextData(&szHtmlTxt);
if(ht)
this.addHtmlTag(ht);
}
return 1;
}
함수에서 인자로 받는 것은 HTML 스트링이다.
while 루프를 보면 처음에 skipBlank 함수가 있다.
이것은 현재 처리중인 문자가 공백인 것을 무시하고 다음 문자로 넘어가는 것이다.
'CLOSE_TAG'는 '>'를 재정의 한 것이다. OPEN_TAG는 '<'를 재정의 한 것이다. 태그를 분석하는 단계를 3가지로 분류하여 두었다. if 구문을 보면 알 수 있듯이, CLOSE_TAG, OPEN_TAGE, 그외의 일반 데이타로 분리하여 조건문으로 처리하였다. 1. 처음 시작하자마자 CLOSE_TAG가 나타난다면 태그로서 의미를 가지지 않는 일반 텍스트와 동일하다고 보고 루프의 처음으로 돌아가게 된다. 2. OPEN_TAG가 나타나게 되면 OPEN_TAG 바로 다음에 공백이 나올경우를 위해 skipBlank를 한번더 해주고 실제 태그를 파싱하게 된다. Comment tag같은 경우 모양이 약간 틀리기 때문에 case 구문으로 구분하여 별도 처리하였다. 유효한 태그인지 아닌지는 parseHtmlTag 함수에서 처리하며 유효할 경우는 생성된 태그 클라스를, 그렇지 않으면 널값을 리턴한다. 3. Open 태그가 아닐경우는 Text 데이타로 간주하고 다음 Open Tag가 나타날 때 까지를 파싱하여 결과를 저장해 둔다.
마지막으로 위 3가지 조건을 처리하였을 때 새로 생성된 태그가 있다면 html 클라스에 새로운 태그를 추가한다. 이 역할을 addHtmlTag 함수가 수행하게 된다.
Html을 파싱하는 전체 골격은 위와 같이 아주 간단하다.
그렇다면 Valid, Invalid, Text 태그를 파싱하는 함수들을 살펴보자.
우선 parseHtmlTag 함수이다.
HtmlTag * HtmlParser::parseHtmlTag(char **buf)
{
HtmlTag *ht;
char name[NAME_SIZE+1], *tmp;
int nIdx=0;
// Tag Name이 나오기 전까지의 공백 문자를 무시한다.
skipBlank(buf);
// Tag Name을 저장한다.
// Tag Name은 공백이 나오거나 CLOSE_TAG '>'가 나오거나
// '' 문자가 나올때까지.... 읽어서 저장한다.
*********************************************************/
while(**buf != ' ' && **buf != ' ' && **buf != CLOSE_TAG &amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;& **buf)
{
// Tag 중간에 새로운 Tag가 시작하면...
if(**buf == OPEN_TAG)
{
tmp = *buf;
(*buf)++;
skipBlank(buf);
if(whatIsTag(*buf) == VALID_TAG)
{
*buf = tmp;
ht = new HtmlTag();
if(!ht)
return NULL;
// 생성된 HtmlTag의 이름을 세팅.
name[nIdx] = '';
ht->setTagName(name);
ht->nextHtmlTag = NULL;
return ht;
}
*buf = tmp;
}
name[nIdx++] = **buf;
(*buf)++;
// 이름이 NAME_SIZE보다 커질경우 예외처리....
// CLOSE_TAG가 나올때까지.. 무시한다!
if(nIdx >= NAME_SIZE)
{
skipUntilCloseTag(buf);
return NULL;
}
}
ht = new HtmlTag();
if(!ht)
return NULL;
// 생성된 HtmlTag의 이름을 세팅.
name[nIdx] = '';
ht->setTagName(name);
this->parseVarVal(ht, buf);
return ht;
}
처음 while 루프에서는 태그의 이름을 잘라내기 위한 부분이다. '<' 다음에 또다시 '<'가 나오는 경우 처리를 위해 한번더 조건문 처리를 해 주었다. while 루프의 조건이 인 경우 ' ' 인 경우 CLOSE_TAG 인경우, NULL인 경우 까지를 잘라낸다. 한 문자씩 잘라내면서 name 배열에 저장하여 두고 만일 태그 명의 길이가 너무 길어지게 되면 태그로 보지 않고 버리게 된다. while 루프가 끝나게 되면 태그명을 제대로 잘라낸 것이다. 이후에 HtmlTag 클라스를 하나 할당 받은후 setTagName 함수로 태그명을 세팅하고 태그의 하위 변수들이 정의되어 있다면 parseVarVal함수를 사용하여 해당하는 변수들을 잘라내고 세팅하게 된다.
다음은 Text 데이타를 파싱하는 함수이다.
HtmlTag * HtmlParser::parseTextData(char **buf)
{
char *begin, *end, *szVal;
HtmlTag *ht;
TagVar *tv;
int nSize;
skipBlank(buf);
if(**buf &&amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp;amp; **buf != OPEN_TAG)
{
begin = *buf;
while((end=getTerm(buf, "<"))) { (*buf)++; skipBlank(buf); if(**buf == '<') continue; if(whatIsTag(*buf) != INVALID_TAG) break; } *buf = end;
if(!begin)
return NULL;
if(!end)
{
szVal = new char [strlen(begin)+1];
if(!szVal)
return NULL;
strcpy(szVal, begin);
}
else
{
nSize = (unsigned int)(end) - (unsigned int)(begin);
if(nSize < 1)
return NULL;
szVal = new char [nSize+1];
if(!szVal)
return NULL;
strncpy(szVal, begin, nSize);
szVal[nSize] = '';
}
// 새로운 태그 추가
ht = new HtmlTag();
if(!ht)
{
if(szVal)
delete szVal;
return NULL;
}
ht->setTagName("TEXT_DATA");
ht->nextHtmlTag = NULL;
// 태그에 텍스트 데이터 연결
tv = new TagVar();
if(!tv)
{
if(szVal)
delete szVal;
if(ht)
delete ht;
return NULL;
}
tv->setVar("TEXT");
tv->setVal(szVal);
tv->nextTagVar = NULL;
ht->addTagVar(tv);
delete szVal;
}
return ht;
}
이 함수의 용도는 텍스트 데이타도 하나의 태그로 인식하도록 하기 위한 함수이다.
그래서 태그명을 'TEXT_DATA'로 붙여주고, 실제 데이타를 TEXT_DATA 태그의 한 변수로서 'TEXT'라는 변수를 부여하고 이 변수의 값에 실제 데이타를 넣게 된다.
이러한 복잡한 과정을 거치지 않고 직접 넣어도 무방하겠지만 전체 html 트리를 순회하는 동안 모든 태그들을 HtmlTag라는 클라스 하나로 제어하기 위해 이런방식으로 통일하였다.
함수 내부에서 특이할 만한 사항은 택스트 태그가 종료되는 시점은 html 문자열의 끝이나 OPEN_TAG가 나타나는 시점이라는 것이다. while 루프 안에서 이러한 위치를 찾은 후
실제 태그를 parseHtmlTag와 같은 방식으로 추가해 주게 된다.
여기까지 파싱 방법이나 소스상에 중요한 부분에 대한 설명을 마치도록 하겠다.
세부 내용은 실제 소스를 자료실에 올려 놓을 예정이니 참고하기 바란다.
필자는 로봇 프로그램을 작성할 때 이 소스를 개선하여 html 파싱을 전담하도록 하였다.
성능은 그리 빠른 편은 아니나 앵커를 추출하거나 기타 부가 정보를 추출할 때 아주 쉽게 구현 할 수 있었다.
무엇보다 기존 모듈이나 소스를 파악해서 내 것으로 소화하는 것보다 내 맘대로 만든 것이라 내맘대로 조작하는데 편해서
html 파싱에 관련한 부분이 필요하면 이 소스를 응용하고 있다.
이 프로그램은 사실 최적화 된 것이 아니며 여러 부분에서 성능 개선의 여지가 있다.
이런 것은 개발자들이 실제 사용하면 해결해 보는 것도 재미있을 것 같다. ^_^
끝.
==============================================================================================
오늘 강좌는 여기서 끝내겠습니다.
이론과 소스를 설명하려니 꽤 양이 많아졌습니다. 첨부터 훓어보니 사실 그리 많은 내용이 아닌듯 하긴 하네요...
물론 버그도 있습니다~ ^_^; 알아서 해결해 보시길..
그럼 좋은 하루 되세요~
문자열에서 각 음절을 하나의 depth(자식노드)로 볼 수 있으며 같은 depth의 음절은 바로 앞의 음절이 같을 경우 형제노드로 볼 수 있다.
문자열에서 각 음절을 하나의 depth(자식노드)로 볼 수 있으며 같은 depth의 음절은 바로 앞의 음절이 같을 경우 형제노드로 볼 수 있다.
