Written by imsoo
on 

Let's Build a Browser Engine!
제2 장: HTML

이 글은 Matt Brubeck의 Let’s Build a Browser Engine!을 번역한 글입니다.

알림 : 부족한 실력 탓에 잘못된 번역, 부자연스러운 문장이 있을 수 있습니다. 해당 문제에 대한 의견을 댓글이나 GitHub 저장소 Pull Request를 통해 제안해 주시면 감사한 마음으로 적극 반영하도록 하겠습니다. 감사합니다.

Let’s Build a Browser Engine!

제2 장: HTML

이 글은 토이 브라우저 렌더링 엔진 구축 시리즈의 두 번째 장입니다.

이 글은 DOM 노드 트리를 생성하기 위해 HTML 소스 코드를 파싱 하는 것을 다룹니다. 파싱은 매우 흥미로운 주제지만 이 주제를 소개하기엔 시간과 필자의 역량이 부족합니다. 독자는 좋은 컴파일러 강의 혹은 서적 을 통해서 세부적인 소개를 얻을 수 있습니다. 또는 독자가 선택한 프로그래밍 언어로 작동하는 파서 생성기 의 문서를 통해 시작해 볼 수도 있을 것 입니다.

HTML은 자신만의 독특한 파싱 알고리즘 을 갖습니다. 대부분의 프로그래밍 언어와 파일 형식에 대한 파서들과 달리 HTML 파싱 알고리즘은 잘못된 입력을 거부하지 않습니다. 대신에 명확한 에러 처리 방식을 포함하고 있습니다. 이를 통해 웹 브라우저가 구문 규칙에 어긋난 페이지조차도 표현할 수 있도록 합니다. 웹 초기부터 규칙을 따르지 않는 HTML이 지원되어 왔고 잘못된 규칙을 따르는 웹 페이지들이 현재 웹페이지들의 대다수를 차지하고 있기 때문에 웹 브라우저는 반드시 이와 같이 해야 합니다.

간략한 HTML 언어

필자는 표준 HTML 파싱 알고리즘을 구현하지 않았습니다. 대신에 HTML 구문의 작은 부분집합에 대한 기본적인 파서를 작성했습니다. 필자의 파서는 다음과 같은 간단한 페이지를 처리할 수 있습니다.

<html>
    <body>
        <h1>Title</h1>
        <div id="main" class="test">
            <p>Hello <em>world</em>!</p>
        </div>
    </body>
</html>

다음과 같은 구문은 허용됩니다.

다음을 포함한 다른 모든 구문은 허용되지 않습니다.

이 프로젝트의 각 단계에서 필자는 추후 단계를 지원하기 위한 필요 코드들을 최소한으로 작성하고 있습니다. 하지만 독자가 파싱 이론과 도구에 대해 더 배우길 원한다면 독자 스스로 프로젝트를 더 원대하게 만들 수 있을 것입니다.

예제 코드

다음으로, 이것이 단지 하나의 방법 일뿐임을 명심하면서 필자의 토이 파서를 살펴봅시다. (아마 최선의 방법도 아닐 것입니다.) 파서의 구조는 대략적으로 Servo cssparser 라이브러리의 토크나이저 모듈을 기반으로 합니다. 파서는 대부분의 경우 실제적인 에러 처리가 없으며, 예상치 못한 구문을 직면했을 땐 그냥 중단합니다. 코드는 Rust 로 되어있지만, Java, C++ 혹은 C#과 같이 유사한 형태의 언어를 사용하는 독자들이 쉽게 읽을 수 있도록 하였습니다. 파서는 1장 에서 만든 DOM 데이터 구조를 사용합니다.

파서는 입력 문자열과 문자열 내 현재 위치를 갖습니다. 위치는 우리가 아직 처리하지 않은 다음 문자의 인덱스 값입니다.

struct Parser {
    pos: usize, // "usize" 는 unsigned integer를 의미하며 C의 "size_t"와 같습니다."
    input: String,
}

이 구조체를 사용해서 입력의 다음 문자를 탐색하는 몇 가지 간단한 메소드들을 구현할 수 있습니다.

impl Parser {
    // 현재 문자를 소모하지 않고 읽어옵니다.
    fn next_char(&self) -> char {
        self.input[self.pos..].chars().next().unwrap()
    }

    // 다음 문자가 주어진 문자열로 시작하는지 확인합니다.
    fn starts_with(&self, s: &str) -> bool {
        self.input[self.pos ..].starts_with(s)
    }

    // 모든 입력이 소모된 경우 true를 반환합니다.
    fn eof(&self) -> bool {
        self.pos >= self.input.len()
    }

    // ...
}

Rust의 문자열은 UTF-8 바이트 배열로 저장됩니다. 따라서 단지 한 바이트를 더하는 것으로 다음 문자로 이동할 순 없습니다. 그래서 멀티 바이트 문자들을 정확하게 처리해 주는 char_indices 를 사용합니다. (문자열이 고정 폭 문자를 사용하는 경우 pos 를 단지 1만큼 증가시킬 수 있을 것입니다.)

// 현재 문자를 반환하고 self.pos를 다음 문자로 이동시킵니다.
fn consume_char(&mut self) -> char {
    let mut iter = self.input[self.pos..].char_indices();
    let (_, cur_char) = iter.next().unwrap();
    let (next_pos, _) = iter.next().unwrap_or((1, ' '));
    self.pos += next_pos;
    return cur_char;
}

우리는 종종 문자열의 연속된 문자들을 소비시켜야 합니다. consume_while 메소드는 주어진 조건을 만족하는 문자를 소비하고, 그것들을 문자열로 반환합니다. 이 메소드의 아규먼트는 char 를 입력받아 bool 을 반환하는 함수입니다.

// `test` 가 false를 반환할 때까지 문자를 소비합니다.
fn consume_while<F>(&mut self, test: F) -> String
        where F: Fn(char) -> bool {
    let mut result = String::new();
    while !self.eof() && test(self.next_char()) {
        result.push(self.consume_char());
    }
    return result;
}

이 메소드를 사용하면 일련의 공백 문자를 무시하거나 문자열의 알파벳과 숫자 문자들을 소비할 수 있습니다.

// 0개 이상의 공백 문자들을 소비하여 버립니다.
fn consume_whitespace(&mut self) {
    self.consume_while(CharExt::is_whitespace);
}

// 태그나 속성의 이름을 파싱 합니다.
fn parse_tag_name(&mut self) -> String {
    self.consume_while(|c| match c {
        'a'...'z' | 'A'...'Z' | '0'...'9' => true,
        _ => false
    })
}

이제 HTML을 파싱 하기 위한 준비가 되었습니다. 하나의 노드를 파싱 하기 위해선 첫 문자를 검사하여 요소 인지 텍스트 노드인지 확인해야 합니다. 우리의 단순화한 버전의 HTML에서 텍스트 노드는 <를 제외한 어떤 문자도 포함할 수 있습니다.

// 하나의 노드를 파싱 합니다.
fn parse_node(&mut self) -> dom::Node {
    match self.next_char() {
        '<' => self.parse_element(),
        _   => self.parse_text()
    }
}

// 텍스트 노드를 파싱 합니다.
fn parse_text(&mut self) -> dom::Node {
    dom::text(self.consume_while(|c| c != '<'))
}

요소 노드는 좀 더 복잡합니다. 요소 노드는 열리고 닫히는 태그들을 포함합니다. 그리고 사이에 임의의 자식 노드들을 갖습니다.

// 열리는 태그, 콘텐츠, 닫히는 태그를 포함한 하나의 요소 노드를 파싱 합니다.
fn parse_element(&mut self) -> dom::Node {
    // 열리는 태그
    assert!(self.consume_char() == '<');
    let tag_name = self.parse_tag_name();
    let attrs = self.parse_attributes();
    assert!(self.consume_char() == '>');

    // 콘텐츠
    let children = self.parse_nodes();

    // 닫히는 태그
    assert!(self.consume_char() == '<');
    assert!(self.consume_char() == '/');
    assert!(self.parse_tag_name() == tag_name);
    assert!(self.consume_char() == '>');

    return dom::elem(tag_name, attrs, children);
}

우리의 단순 문법에서 속성(Attribute)을 파싱 하는 것은 매우 쉽습니다. 열리는 태그의 끝(>)에 도달할 때까지 속성 이름을 찾고 뒤이어 = 과 따옴표로 둘러싸인 문자열을 찾습니다.

// 하나의 이름="값" 쌍을 파싱 합니다.
fn parse_attr(&mut self) -> (String, String) {
    let name = self.parse_tag_name();
    assert!(self.consume_char() == '=');
    let value = self.parse_attr_value();
    return (name, value);
}

// 따옴표로 둘러싸인 값을 파싱 합니다.
fn parse_attr_value(&mut self) -> String {
    let open_quote = self.consume_char();
    assert!(open_quote == '"' || open_quote == '\'');
    let value = self.consume_while(|c| c != open_quote);
    assert!(self.consume_char() == open_quote);
    return value;
}

// 공백문자로 구분된 이름="값" 쌍들의 리스트를 파싱 합니다.
fn parse_attributes(&mut self) -> dom::AttrMap {
    let mut attributes = HashMap::new();
    loop {
        self.consume_whitespace();
        if self.next_char() == '>' {
            break;
        }
        let (name, value) = self.parse_attr();
        attributes.insert(name, value);
    }
    return attributes;
}

자식 노드들을 파싱 하기 위해 닫히는 태그에 도달할 때까지 parse_node 를 재귀적으로 호출합니다. 이 함수는 Rust의 동적 배열(growable array)인 Vec 을 반환합니다.

// 연속된 형제 노드들을 파싱 합니다.
fn parse_nodes(&mut self) -> Vec<dom::Node> {
    let mut nodes = Vec::new();
    loop {
        self.consume_whitespace();
        if self.eof() || self.starts_with("</") {
            break;
        }
        nodes.push(self.parse_node());
    }
    return nodes;
}

마지막으로, 전체 HTML 문서를 파싱 한 모든 결과들을 종합해서 DOM 트리에 집어넣습니다. 이 함수는 명시되어 있지 않더라도 문서(document)에 해당하는 루트 노드를 하나 생성합니다. 이것은 실제 HTML 파서가 수행하는 것과 같습니다.

이 부분은 원문과 비교해서 보시길 바랍니다.

Finally, we can put this all together to parse an entire HTML document into a DOM tree. This function will create a root node for the document if it doesn’t include one explicitly; this is similar to what a real HTML parser does.

// HTML 문서를 파싱 하여 루트 요소를 반환합니다.
// Parse an HTML document and return the root element.
pub fn parse(source: String) -> dom::Node {
    let mut nodes = Parser { pos: 0, input: source }.parse_nodes();

    // 문서가 루트 노드 하나만을 갖는 경우, 단순 반환합니다. 그렇지 않다면 하나 생성합니다.
    // If the document contains a root element, just return it. Otherwise, create one.
    if nodes.len() == 1 {
        nodes.swap_remove(0)
    } else {
        dom::elem("html".to_string(), HashMap::new(), nodes)
    }
}

끝났습니다! Robinson HTML 파서 의 전체 코드입니다. 모든 것이 단지 100줄 정도의 코드뿐입니다. (공백과 주석은 제외했습니다.) 독자가 훌륭한 라이브러리나 파서 생성기를 사용한다면, 아마 더 적은 규모로 유사한 토이 파서를 만들 수 있을 것입니다.

연습

아래 사항들은 직접 실습해볼 몇 가지 사항들입니다. 이전과 마찬가지로 한 개 이상 선택하여 수행해보거나 무시하고 넘어갈 수 있습니다.

  1. HTML의 부분집합을 입력받아 DOM 노드 트리를 생성하는 파서를 만들어보세요. (“직접” 또는 라이브러리나 파서 생성기를 사용)

  2. Robinson의 HTML 파서를 수정하여 주석처럼 빠진 기능들을 추가해 보세요. 또는 라이브러리 혹은 생성기로 만들어진 더 나은 파서로 바꿔보세요.

  3. 독자의 파서(또는 필자의 것)를 실패하게 만드는 잘못된 HTML 파일을 생성해보세요. 그 후 에러로부터 회복하여 테스트 파일의 DOM 트리를 생성하도록 파서를 수정해보세요.

지름길

파싱 과정을 완전히 생략하고자 하는 경우 프로그램을 통해 DOM 트리를 생성하는 대신 아래와 같은 몇 줄의 코드를 추가하여 생성할 수 있습니다. (의사 코드로써 1장에서 작성한 독자의 DOM 코드에 맞추길 바랍니다.)

// <html><body>Hello, world!</body></html>
let root = element("html");
let body = element("body");
root.children.push(body);
body.children.push(text("Hello, world!"));

또는 기존에 존재하던 HTML 파서를 찾아 독자의 프로그램에 포함시킬 수도 있습니다.

다음 장에선 CSS 데이터 구조와 파싱을 다루겠습니다.

Discussion and feedback