HTML 파싱 알고리즘: 토큰화와 트리 구축

민주니어·2024년 9월 16일

HTML 파싱은 원시 HTML 텍스트를 구조화된 DOM(Document Object Model) 트리로 변환하는 과정이다.
이 과정은 주로 두 가지 주요 단계로 구성된다: 토큰화(Tokenization)와 트리 구축(Tree Construction)

1. 토큰화 (Tokenization)

토큰화는 HTML 소스 코드를 의미 있는 작은 단위(토큰)로 분할하는 과정이다.

토큰의 종류:

시작 태그: <div>
종료 태그: </div>
속성: class="container"
텍스트: 태그 사이의 일반 텍스트
주석: 
DOCTYPE: <!DOCTYPE html>

토큰화 과정:

HTML 문자열을 왼쪽에서 오른쪽으로 순차적으로 읽는다.
현재 상태(예: 태그 내부, 텍스트 내부 등)에 따라 문자를 해석한다.
특정 패턴을 인식하면 토큰을 생성한다.

예시:

HTML:

<p class="container">Hello, world!</p>

토큰화 결과:
1. 시작 태그 토큰: <p>
2. 속성 토큰: class="container"
3. 텍스트 토큰: Hello, world!
4. 종료 태그 토큰: </p>

토큰화 알고리즘 의사 코드:

// 토큰 타입 정의
type TokenType = 'START_TAG' | 'END_TAG' | 'TEXT' | 'ATTRIBUTE';

interface Token {
    type: TokenType;
    value: string;
}

// DOM 노드 클래스
class Node {
    tagName: string;
    children: (Node | string)[];
    attributes: Map<string, string>;

    constructor(tagName: string) {
        this.tagName = tagName;
        this.children = [];
        this.attributes = new Map();
    }
}

// 토큰화 함수
function tokenize(htmlString: string): Token[] {
    const tokens: Token[] = [];
    let currentToken = '';
    let state: 'DATA' | 'TAG_OPEN' | 'TAG_NAME' | 'ATTR_NAME' | 'ATTR_VALUE' = 'DATA';

    for (const char of htmlString) {
        switch (state) {
            case 'DATA':
                if (char === '<') {
                    if (currentToken) {
                        tokens.push({ type: 'TEXT', value: currentToken });
                        currentToken = '';
                    }
                    state = 'TAG_OPEN';
                } else {
                    currentToken += char;
                }
                break;
            case 'TAG_OPEN':
                if (char === '/') {
                    tokens.push({ type: 'END_TAG', value: '' });
                    state = 'TAG_NAME';
                } else if (char.match(/[a-z]/i)) {
                    currentToken = char;
                    state = 'TAG_NAME';
                }
                break;
            case 'TAG_NAME':
                if (char === '>') {
                    tokens.push({ type: 'START_TAG', value: currentToken });
                    currentToken = '';
                    state = 'DATA';
                } else if (char === ' ') {
                    tokens.push({ type: 'START_TAG', value: currentToken });
                    currentToken = '';
                    state = 'ATTR_NAME';
                } else {
                    currentToken += char;
                }
                break;
            case 'ATTR_NAME':
                if (char === '=') {
                    currentToken += char;
                    state = 'ATTR_VALUE';
                } else if (char === '>') {
                    if (currentToken) {
                        tokens.push({ type: 'ATTRIBUTE', value: currentToken });
                    }
                    currentToken = '';
                    state = 'DATA';
                } else {
                    currentToken += char;
                }
                break;
            case 'ATTR_VALUE':
                if (char === '"') {
                    if (currentToken.endsWith('=')) {
                        currentToken += char;
                    } else {
                        tokens.push({ type: 'ATTRIBUTE', value: currentToken + char });
                        currentToken = '';
                        state = 'ATTR_NAME';
                    }
                } else {
                    currentToken += char;
                }
                break;
        }
    }

    if (currentToken) {
        tokens.push({ type: 'TEXT', value: currentToken });
    }

    return tokens;
}

2. 트리 구축 (Tree Construction)

트리 구축은 토큰화 단계에서 생성된 토큰들을 사용하여 DOM 트리를 생성하는 과정이다.

트리 구축 과정:

토큰 스트림을 순차적으로 처리한다.
시작 태그 토큰을 만나면 새로운 노드를 생성하고 현재 노드의 자식으로 추가한다.
텍스트 토큰을 만나면 텍스트 노드를 생성하고 현재 노드의 자식으로 추가한다.
종료 태그 토큰을 만나면 현재 노드를 닫고 부모 노드로 이동한다.
속성 토큰을 만나면 현재 노드에 속성을 추가한다.

예시:

HTML:

<div>
  <p>Hello</p>
  <p>World</p>
</div>

트리 구축 결과:

div
├── p
│   └── "Hello"
└── p
    └── "World"

트리 구축 알고리즘 의사 코드:

// 트리 구축 함수
function buildTree(tokens: Token[]): Node {
    const root = new Node('root');
    let currentNode = root;
    const stack: Node[] = [root];

    for (const token of tokens) {
        switch (token.type) {
            case 'START_TAG':
                const newNode = new Node(token.value);
                currentNode.children.push(newNode);
                stack.push(newNode);
                currentNode = newNode;
                break;
            case 'END_TAG':
                stack.pop();
                currentNode = stack[stack.length - 1];
                break;
            case 'TEXT':
                currentNode.children.push(token.value);
                break;
            case 'ATTRIBUTE':
                const [name, value] = token.value.split('=');
                currentNode.attributes.set(name, value.replace(/"/g, ''));
                break;
        }
    }

    return root;
}

// HTML 파싱 함수
function parseHTML(html: string): Node {
    const tokens = tokenize(html);
    return buildTree(tokens);
}

// 사용 예시
const html = '<div class="container"><p>Hello, <span>world</span>!</p></div>';
const parsedTree = parseHTML(html);
console.log(JSON.stringify(parsedTree, null, 2));