오토마타 이론과 Parser의 원리 - HTML Parser 만들기 (Java)

이번 포스팅에서는 비교적 간단한 HTML, XML 문서가 어떻게 파싱되는지 알아보겠습니다. 그 전에 XML, HTML이 무엇인지부터 알아야합니다. XML, HTML을 파싱한 결과물인 DOM의 구조에 대해서도 살펴보겠습니다. HTML, CSS, Javascript 코드는 웹 페이지를 구성하는데요, HTML을 파싱하여 생성된 트리 자료구조를 DOM, CSS를 파싱하여 얻은 자료 구조를 CSSOM, JS 코드는 AST라고 합니다. DOM, CSSOM, AST로 웹브라우저에 화면이 렌더링되는 과정을 살펴보면서 컴파일링 이론을 왜 배워야하는지 생각해보겠습니다. 좀 더 나은 이해를 돕기위해 위의 DOM, 그리고 컴파일러 이론의 기반을 이루는 오토마타 이론을 간단히 알아보고, 이를 바탕으로 간단한 HTML Parser를 구현해보겠습니다.

DOM, AST - Syntax Analyzing 단계의 결과물

XML, HTML이란?

Extensible Markup Language는 Markup Language로 공유 가능한 방식으로 데이터를 정의하고 저장하는 언어입니다. Markup Language의 다른 예로는 대표적으로 HTML이 있습니다.

HyperText Markup Language(HTML)은 웹 페이지 표시를 위한 구조적 의미를 나타내기 위한 markup 언어입니다. XML과의 차이점은 HTML은 이미 약속된 태그들만 사용 가능한 반면, XML은 임의로 생성하여 사용할 수 있다는 점입니다. 이를 통해서 정보들을 태그로 마크하여 필요한 내용을 함께 저장할 수 있다는 장점이 있습니다. 정리하면, XML은 텍스트 기반, 간결한 데이터 형 언어이며, 마크업 언어가 아닌 마크업 언어를 정의하기 위한 언어로 자신의 어플리케이션에 적합하게 작성 가능하다는 특징을 가지고 있습니다.

파서는 XML, HTML, JavaScript 코드, 혹은 우리가 작성한 언어에 맞는 코드를 컴파일 전에 트리구조 형태로 만듭니다. XML과 HTML은 DOM이라는 뼈대를 이루는 객체들이 모인 Object Model 트리구조로 생성하고, 웹 브라우저에 렌더링하기위한 JavaScript는 추상 구문 트리(AST)라는 트리 구조로 결과물을 반환합니다. 웹 브라우저에 화면이 렌더링되는 과정은 아래에서 다시 살펴보겠습니다.

DOM이란?

DOM(Document Object Model)은 XML이나 HTML 문서에 접근하기 위한 API로 W3C 표준 권고안입니다. DOM은 문서 내의 모든 요소를 정의하고, 해당 요소에 접근하는 방법까지 정의합니다. DOM 표준은 아래와 같이 3가지로 구분됩니다.

W3C DOM 표준의 3가지 구분

Core DOM : 모든 문서 타입을 위한 DOM 모델
HTML DOM : HTML 문서를 위한 DOM 모델
XML DOM : XML 문서를 위한 DOM 모델

이 포스팅에서 구현해볼 것은 이 중 XML DOM에 대한 Parser입니다.

추상 구문 트리(Abstract Syntax Tree)란?

추상 구문 트리는 프로그래밍 언어로 작성된 소스 코드의 추상 구문 구조의 트리이며, 이 트리의 각 노드는 소스코드에서 발생되는 구조를 나타냅니다. 쉽게 말하면, 우리가 작성한 JavaScript 소스코드를 문법에 맞게 노드들로 쪼개서 만든 트리입니다. 추상(Abstract)라고 하는 이유는 추상적인 형태이기 때문이 아닌, 코드에 필연적으로 포함되는 괄호, 기타 부호와 같은 코딩 구문을 포함하므로 추상이라고 합니다.

JavaScript의 컴파일 과정을 예로들어 설명해보겠습니다. AST는 컴파일러가 필요한 프로그래밍 언어에서 컴파일 단계 중 구문 분석(Syntax Analyzing) 단계의 결과물입니다. 아래와 같은 순서로 컴파일되어 작동하게 됩니다.

JS의 예시) 자바 스크립트 코드 - Abstract Syntax Tree - 인터프리터 - 바이트 코드

브라우저의 렌더링 과정

위의 개념들을 바탕으로 브라우저가 어떻게 렌더링을 수행하는지 알아보겠습니다.

브라우저는 HTML, CSS, JS 등 렌더링에 필요한 리소스를 요청하고 서버로부터 응답을 받습니다.
브라우저 렌더링 엔진은 서버로부터 응답된 HTML과 CSS를 파싱하여 DOM(HTML), CSSOM(CSS)를 생성하고 결합하여 렌더 트리를 생성합니다.
브라우저의 JS 엔진은 서버로부터 응답된 JS 코드를 파싱하여 AST를 생성, 바이트코드로 변환하여 실행합니다.
이 때, DOM API를 통해 DOM, CSSOM을 변경할 수 있습니다. 변경된 DOM, CSSOM은 렌더 트리로 결합됩니다.
렌더 트리를 기반으로 HTML 레이아웃을 계산하고 화면에 페인팅합니다.

즉, 파싱 결과물인 DOM(HTML), CSSOM(CSS), AST(JS)를 결합하여 렌더 트리를 생성하고 렌더 트리를 유기적으로 변경하면서 화면에 페인팅하게 되는 것이죠. 그리고 그러한 트리 구조를 생성하는 과정을 이해하는 것이 파서의 작동 방식을 이해하는 것이 됩니다.

컴파일러 이론(Tokenizer, Lexer, Parser)

위에서는 코드를 읽어서 파스 트리로 만들기까지의 역할을 Parser라고 설명했지만, 파서를 나누면 아래와 같이 Tokenizer, Lexer, Parser로 기능별로 구분할 수 있습니다.

토크나이저 (Tokenizer)

어떤 구문에서 의미있는 요소들을 토큰으로 쪼개는 역할을 합니다. 토큰이란, 어휘 분석의 단위를 의미하는 컴퓨터 용어로 일반적으로 의미있는 단위로 지정됩니다.

<!DOCTYPE html>
<HTML lang="ko">
  <BODY>
    <P>PORO
	  <IMG SRC="porolog.tistory.com"></IMG>
	  <BR/>
	</P>
  </BODY>
</HTML>

<![<, !, DOCTYPE, html, >, <, HTML, lang, =, ko, >, <, BODY, >, <, P, >, PORO, <, IMG, SRC, =, porolog.tistory.com, >, <, /IMG, >, <, BR/, >, <, /P, >, <, /BODY, >, <, /HTML, >]>

간단한 예시를 들어보겠습니다. 위의 HTML을 토크나이저로 구분하는 경우 위와 같이 되겠습니다. 토큰의 구분은 예시용으로만 참고해주세요.

토큰 종류
- identifier : 식별자
- keyword : 예약어
- separator : 글자를 구분하는 문자
- operator : 연산을 위한 심볼
- literal : 숫자, 논리, 문자
- comment : 줄, 블록 주

코드는 참고만 해주세요.

public class Tokenizer {
    private static List<String> tokens = new LinkedList<>();
    private static int cursor;

    public static void run(String str) {

        while (cursor < str.length()) {
            if (cursor == str.length()) {
                break;
            }
            if (addToken(str, "[a-z]|[A-Z]|[_-]|[0-9]|[/($)]")) { //Keywords : alphabet + underbar
                continue;
            }
            if (addStringToken(str)) { //" " 문자열
                continue;
            }
            if (skipToken(str, ' ')) { //공백 skip
                continue;
            }
            if (skipToken(str, '\n')) { //개행 skip
                continue;
            }
            addToken(str); //그 외 identifier(특수 문자)
        }
    }

    public static boolean skipToken(String str, char target) {
        if (str.charAt(cursor) == target) {
            cursor++;
            return true;
        }
        return false;
    }

    public static void addToken(String str) {
        tokens.add(String.valueOf(str.charAt(cursor)));
        cursor++;
    }

    public static boolean addToken(String str, String regex) {
        int offset = 0;
        while (str.substring(cursor + offset, cursor + offset + 1).matches(regex)) {
            offset++;
        }
        if (offset != 0) {
            tokens.add(str.substring(cursor, cursor + offset));
            cursor += offset;
            return true;
        }
        return false;
    }

    public static boolean addStringToken(String str) {
        int offset = 0;
        if (str.charAt(cursor) == '\"') { //따옴표가 나오면
            cursor++;
            while (str.charAt(cursor + offset) != '\"') //따옴표가 나올 때 까지
            {
                offset++;
            }
            tokens.add(str.substring(cursor, cursor + offset));
            cursor += offset + 1;
            return true;
        }
        return false;
    }

    public static List<String> getTokens() {
        return tokens;
    }
}

렉서 (Lexer)

분해된 토큰의 의미를 분석하는 역할, 토크나이저와 렉서의 역할을 합하여 Lexical Analyze라고 합니다. 의미있는 조각을 검출하여 토큰을 생성하는 것으로, 토큰 단위로 생성된 데이터를 parser에게 넘겨줍니다. 예시로는 아래와 같이 만들었는데, 제 경우는 Lexer에서 토큰을 분석해서 element, attributes, child를 구분해주는 역할까지 추가했습니다.

element: 'HTML',
attributes: [
{name : lang, value : "ko"}
]
child : [BODY]

element: 'BODY',
child : [P]

element: 'P',
text : 'PORO' ,
child : [IMG]

element: 'IMG',
attributes: [
{name : SRC, value : "porolog.tistory.com"}
]

element: 'BR'

마찬가지로 참고용 소스코드입니다.

public class Lexer {

    /**
     * tokenSet : tag를 저장하는 stack
     * bracket : bracket을 저장하는 stack
     */
    public static final Stack<Node> tokenSet = new Stack();
    public static final Stack<String> bracket = new Stack();
    public static final List<Node> nodes = new LinkedList<>();

    public static void run(List<String> tokens) {
        Iterator tokenList = tokens.iterator();
        while (tokenList.hasNext()) {
            String token = (String)tokenList.next();

            // 주석 처리
            if (token.equals("!") || token.equals("?")) {
                while (!token.equals(">")) {
                    token = (String)tokenList.next();
                }
                bracket.pop();
                continue;
            }

            /**
             * 여는 괄호 처리 - Bracket Stack에 추가
             */
            if (token.equals("<")) {
                bracket.push("<");
                continue;
            }
            /**
             * 닫는 괄호 처리 - Bracket Stack에서 제거
             * 가장 위의 토큰의 특성을 더 이상 수정할 수 없는 상태로 만든다.
             */
            if (token.equals(">")) {
                if (!bracket.isEmpty() && bracket.peek().equals("<")) {
                    bracket.pop();
                }
                if (!tokenSet.isEmpty())
                    tokenSet.peek().unmodify();
                continue;
            }

            /**
             * 예외 처리 : BR은 바로 노드에 추가(Closing Tag를 생략)
             */
            if (token.equals("BR/")) {
                nodes.add(new Node("BR"));
                continue;
            }

            /**
             * Closing Tag 처리 : token Stack의 최근 값과 일치하면 pop
             */

            if (!tokenSet.isEmpty()) {
                String name = tokenSet.peek().element;
                if (token.substring(1).equals(name)) {
                    tokenSet.pop();
                    continue;
                }
                else if (token.charAt(0) == '/' && !token.substring(1).equals(name)) {
                    throw new IllegalArgumentException("올바르지 않은 형식입니다.");
                }
            }

            /**
             * text element 처리 : Bracket stack이 비어 있는 경우
             * node의 text 요소에 추가
             */

            if (bracket.isEmpty()) {
                tokenSet.peek().text = token;
                continue;
            }

            /**
             * 속성 처리 : bracket stack에 "<"이 있는 경우
             * attribute, value 값을 순차적으로 추가
             */
            if (!bracket.isEmpty() && bracket.peek().equals("<")) {
                if (!tokenSet.isEmpty() && tokenSet.peek().isAttributeEmpty()) {
                    tokenSet.peek().attribute.add(token);
                    token = (String)tokenList.next();
                }
                if (token.equals("=")) {
                    token = (String)tokenList.next();
                }
                if (!tokenSet.isEmpty() && tokenSet.peek().isValueEmpty()) {
                    tokenSet.peek().value.add(token);
                    continue;
                }
            }
            /**
             * 그 외의 항목은 새로운 Keyword로 node에 추가
             */
            Node e = new Node(token);
            if (!tokenSet.isEmpty()) {
                tokenSet.peek().children.add(e); //아직 안닫혀있으면 children에 추가
            }
            tokenSet.push(e);
            nodes.add(e);
        }
    }

파서 (Parser)

파싱(구문 분석)은 프로그래밍 언어의 문법에 맞게 작성된 텍스트 문서를 읽어 들여 실행하기 위해 텍스트 문서의 문자열을 토큰으로 분해(어휘 분석), 의미와 구조를 반영해 트리 구조의 자료구조인 파스 트리를 생성하는 일련의 과정입니다. 데이터를 구조적으로 바꾸는 과정에서 데이터가 올바른지 검증하는 역할도 수행합니다. 일반적으로 파싱이 완료된 후에는 파스 트리를 기반으로 중간 언어인 바이트 코드를 생성하고 실행합니다. 아래 예시에서는 Parser가 다음 역할들을 수행하도록 작성했습니다.

1. DOM 객체를 생성하여 트리 구조로 데이터를 담아줍니다. (DOM 객체는 트리를 탐색하는 메서드들을 지원합니다.)

2. Tag와 괄호가 제대로 여닫혔는지 검사합니다.

{ 
element: 'HTML',
attributes: [
	{
	name : lang, value : "ko"
	}
]
children : [
	{ 
	element: 'BODY',
	children : [
		{ 
		element: 'P',
		text : 'PORO' ,
		children : [
			{ 
			element: 'IMG',
			attributes: [
				{
				name : SRC, value : "porolog.tistory.com"
				}
			]
            element: 'BR'
			]
		}
		]
	}
	]
}