브라우저 동작 원리(쉽게 알아보기) - 정규 표현식/BNF/파서의 종류/HTML 파싱(6)

이 글은 이스라엘 개발자 탈리 가르시엘(Tali Garsiel)이 html5rocks.com에 게시한

"How Browsers Work: Behind the scenes of modern web browsers"를 인용하고 있습니다.

아무것도 모르는 초보자의 시선에서

하나하나 모르는 용어는 용어대로 찾아가면서

정리해보는 글입니다.

 

저와같이 아무것도 모르는 초보자를 기준으로 글을 작성했습니다.

 

부디 이 글에 마지막에는

글을 쓰고 있는 저도, 독자도 어렴풋이라도

브라우저가 어떻게 동작하는지 이해할 수 있었으면 좋겠습니다. 🙏

 

이 글은 브라우저 동작 원리 6편입니다.

다른 편은 아래 링크나 블로그에서 참조해주세요!

• 브라우저 동작 원리 1편
• 브라우저 동작 원리 2편
• 브라우저 동작 원리 3편
• 브라우저 동작 원리 4편
• 브라우저 동작 원리 5편

 

Formal definitions for vocabulary and syntax
(어휘와 구문에 대한 공식적인 정의)

---

전문

Formal definitions for vocabulary and syntax

Vocabulary is usually expressed by regular expressions.

For example our language will be defined as:

As you see, integers are defined by a regular expression.

Syntax is usually defined in a format called BNF. Our language will be defined as:

We said that a language can be parsed by regular parsers if its grammar is a context free grammar. An intuitive definition of a context free grammar is a grammar that can be entirely expressed in BNF. For a formal definition see Wikipedia's article on Context-free grammar

어휘는 일반적으로 정규식으로 표현됩니다.

예를 들어 우리의 언어는 다음과 같이 정의됩니다.

위와 같이, 정수는 정규 표현식으로 정의됩니다.

 

구문은 BNF라 불리는 형식으로 보통 정의됩니다.

언어는 다음과 같이 정의됩니다.

만약 문법이 문맥 자유 문법이라면, 언어는 정규 파서로 파싱 할 수 있습니다.

문맥 자유 문법에 대한 정의는 BNF로 완전히 표현가능 한 문법을 말합니다.

 

저는 다음 내용을 읽으면서도 하나도 이해하지 못했습니다.. 😭😭

이해하기 위해서 정규 표현식이 무엇인지, BNF, 문맥 자유 문법이 무엇인지 알아보겠습니다.

 

 

정규식/정규 표현식(Regular Expression)

---

저 같은 초보자가 자주 애용하는 사이트인 '생활코딩'에서는

정규식을 다음과 같이 설명하고 있습니다.

 

정규식은 정규 표현식이라고도 부르며,
정규표현식(Regular Expression)은 문자열을 처리하는 방법 중의 하나로 특정한 조건의 문자를 '검색'하거나 '치환'하는 과정을 매우 간편하게 처리할 수 있도록 하는 수단이다.

 

예를 들어, '2021년 10월 05일'이라고 문장을 입력했을 때,

입력한 문장에서 숫자만을 검색하여

해당 년, 월, 일을 다른 숫자로 치환하는 과정을

쉽게 할 수 있도록 하는 수단을 말합니다.

 

 

 

BNF(배커스-나우르 표기법)

---

BNF는 '문맥 자유 문법'을 나타내기 위해 만들어진 표기법입니다.

 

문맥 자유 문법을 자세하기 다루기에는

너무나 어렵고 방대한 내용이기 때문에

쉽게 정리하자면,

 

문맥 자유 문법이란

말 그대로 문맥으로부터 자유로운 문법을 말합니다.

 

이는 의미를 따지지 않고도 형태만으로 문법을 파악할 수 있다는 것을 의미합니다.

 

이러한 문맥 자유 문법을 나타내기 위해 만들어진 표기법이 바로 BNF입니다.

 

BNF는 단말 표현, 비 단말 표현, 메타 표현 등으로 나뉩니다.

단말 표현은 더 이상 유도할 수 없는 표현으로 수식에서 1, 2, …, +, -, *, / 등이 있습니다.

비단말 표현이란 유도가 가능한 표현으로 <digit>처럼 < >를 이용하여 표현합니다.

유도 과정에서 := 는 정의를 의미하며 <digit>:=0|1|2|3|4|5|6|7|8|9처럼 표현합니다.

메타 표현은 |와 같은 기호로, |는 '또는'을 의미합니다.

 

위의 구문 분석 예시 사진을 다시 보겠습니다.

위 사진에서 유도 과정에서 ':='로 정의되는 것을 볼 수 있고,

'|'와 같은 메타 표현도 사용되는 것을 확인할 수 있습니다.

 

 

 

Types of parsers(파서의 타입들)

---

전문

There are two types of parsers: top down parsers and bottom up parsers. An intuitive explanation is that top down parsers examine the high level structure of the syntax and try to find a rule match. Bottom up parsers start with the input and gradually transform it into the syntax rules, starting from the low level rules until high level rules are met.

Let's see how the two types of parsers will parse our example.

The top down parser will start from the higher level rule: it will identify 2 + 3 as an expression. It will then identify 2 + 3 - 1 as an expression (the process of identifying the expression evolves, matching the other rules, but the start point is the highest level rule).

The bottom up parser will scan the input until a rule is matched. It will then replace the matching input with the rule. This will go on until the end of the input. The partly matched expression is placed on the parser's stack.

                                                                                         

Stack	Input
	2 + 3 - 1
term	+ 3 - 1
term operation	3 - 1
expression	- 1
expression operation	1
expression	-

This type of bottom up parser is called a shift-reduce parser, because the input is shifted to the right (imagine a pointer pointing first at the input start and moving to the right) and is gradually reduced to syntax rules.

 

파서에는 'Top down(하향식)' 방식과 'Bottom up(상향식)'방식이 존재합니다.

하향식 방식의 파서는 구문의 상위 구조부터 규칙이 일치하는지 찾기 시작하고

상향식 방식의 파서는 입력부터 시작해

점진적으로 상위 구조까지 일치하는 규칙을 찾기 시작합니다.

 

두 가지 타입의 파서가 어떻게 동작하는지 예시를 보겠습니다.

하향식 파서는 상위 수준 규칙에서 시작합니다.

하향식 파서는 '2+3'을 인식합니다.

그다음 '2+3-1'을 인식합니다.

(표현식을 식별하는 프로세스가 진화하여

다른 규칙과 매칭 되어도, 시작점은 가장 높은 수준의 규칙입니다.)

 

상향식 파서는 입력부터 규칙이 일치할 때까지 스캔합니다.

이후 맞는 입력값은 규칙으로 바꿉니다.

이러한 과정은 입력이 끝날 때까지 계속하여 진행됩니다.

부분적으로 일치하는 표현식은 파서 스택에 쌓입니다.

                                                                        

Stack	Input
	2 + 3 - 1
term	+ 3 - 1
term operation	3 - 1
expression	- 1
expression operation	1
expression	-

 

이러한 유형의 상향식 파서는 'Shift-Reduce' 파서라고 부릅니다.

입력 값의 오른쪽으로 이동하면서,

(포인터가 입력 값의 처음을 가리킨 후 오른쪽으로 이동하는 것을 상상해보세요)

구문 규칙으로 점차 감소하기 때문입니다.

 

 

 

Generating parsers automatically(파서 자동 생성)

---

전문

There are tools that can generate a parser. You feed them the grammar of your language–its vocabulary and syntax rules–and they generate a working parser. Creating a parser requires a deep understanding of parsing and it's not easy to create an optimized parser by hand, so parser generators can be very useful.

WebKit uses two well known parser generators: Flex for creating a lexer and Bison for creating a parser (you might run into them with the names Lex and Yacc). Flex input is a file containing regular expression definitions of the tokens. Bison's input is the language syntax rules in BNF format.

파서를 생성시킬 수 있는 툴이 존재합니다.

만약 어휘와 구문 규칙을 가진 언어를 제공하면

이 툴은 동작하는 파서를 만들어 줍니다.

 

파서를 만드는 것은 파싱에 대한 깊은 이해가 필요하고

수동으로 파서를 최적화하여 만드는 것은 어렵습니다.

때문에 파서 생성기는 매우 유용합니다.

 

Webkit은 두 가지 유명한 파서 생성기(Flex, Bison)를 사용합니다.

'Flex'는 렉서를 생성하는 데 사용하고,

'Bison'은 파서를 생성하는데 사용한다.

(Lex 및 Yacc라는 이름으로 실행될 수도 있습니다.)

 

Flex의 입력은 토큰으로 정의된 정규식을 포함하는 파일입니다.

Bison의 입력은 BNF 형식의 언어 구문 규칙입니다.

 

 

 

Not a context free grammar(문맥 자유 문법이 아닌 것)

---

전문

As we have seen in the parsing introduction, grammar syntax can be defined formally using formats like BNF.

Unfortunately all the conventional parser topics do not apply to HTML (I didn't bring them up just for fun–they will be used in parsing CSS and JavaScript). HTML cannot easily be defined by a context free grammar that parsers need.

There is a formal format for defining HTML–DTD (Document Type Definition)–but it is not a context free grammar.

This appears strange at first sight; HTML is rather close to XML. There are lots of available XML parsers. There is an XML variation of HTML–XHTML–so what's the big difference?

The difference is that the HTML approach is more "forgiving": it lets you omit certain tags (which are then added implicitly), or sometimes omit start or end tags, and so on. On the whole it's a "soft" syntax, as opposed to XML's stiff and demanding syntax.

This seemingly small detail makes a world of a difference. On one hand this is the main reason why HTML is so popular: it forgives your mistakes and makes life easy for the web author. On the other hand, it makes it difficult to write a formal grammar. So to summarize, HTML cannot be parsed easily by conventional parsers, since its grammar is not context free. HTML cannot be parsed by XML parsers.

앞서 설명드렸듯, 문법 구문은 BNF와 같은 형식을 사용하여 공식적으로 정의할 수 있습니다.

Webkit은 Flex와 Bison과 같은 파서 생성기를 이용해 파싱을 할 수 있다고 말씀드렸는데,

여기서 파싱이 가능한 문서는 CSS와 JavaScript입니다.

HTML은 이러한 파서 생성기로 파싱이 불가능합니다.

HTML은 파서가 필요로 하는 문맥 자유 문법으로 쉽게 정의할 수 없습니다.
HTML 정의를 위한 공식적인 형식으로 DTD(문서 형식 정의)가 있지만

이것은 문맥 자유 문법이 아닙니다.

HTML은 XML에 가깝고,

사용 가능한 XML 파서가 많이 있습니다.

XML 변형의 HTML-XHTML도 있습니다.

 

하지만 차이점이 존재합니다.

차이점은 HTML 접근 방식이 더 "관용"된다는 것입니다.

HTML 접근 방식을 사용하면 특정 태그(암묵적으로 추가됨)를 생략하거나

때로는 시작 또는 종료 태그 등을 생략할 수 있습니다.

전체적으로 뻣뻣하고 까다로운 XML 구문과 달리

HTML은 "부드러운" 구문입니다.

이 작은 차이가 큰 차이를 만듭니다.

HTML은 개발자들의 작은 실수를 용인하여 웹 작성자의 편의를 확대하지만

이러한 특성 때문에 HTML은 공식적인 문법으로 작성하기 어렵습니다.

 

쉽게 말해, HTML은 어느 정도의 실수를 용인하는

부드러운 구문으로 문맥 자유 문법이 아닙니다.

때문에 전통적인 파서로 파싱을 하기 어렵습니다.

 

HTML은 XML 파서로도 파싱 될 수 없습니다.

 

 

 

HTML DTD

---

전문

HTML definition is in a DTD format. This format is used to define languages of the SGML family. The format contains definitions for all allowed elements, their attributes and hierarchy. As we saw earlier, the HTML DTD doesn't form a context free grammar.

There are a few variations of the DTD. The strict mode conforms solely to the specifications but other modes contain support for markup used by browsers in the past. The purpose is backwards compatibility with older content. The current strict DTD is here: www.w3.org/TR/html4/strict.dtd

HTML 정의는 DTD 형식을 따릅니다. 이 형식은 SGML 계열의 언어를 정의하는 데 사용합니다.

 

SGML이란 태그 등을 이용해 문서를 작성하는'마크업 언어'의 한 종류로

 

마크업 언어에는 SGML을 포함하여 XML, HTML 등이 있습니다.

 

XML은 SGML에서 파생되어 나온 언어이고,

HTML은 본래 별도로 설계되었으나 나중에 SGML을 기반으로 하여 재정의 되었습니다.

 

이 형식은 허용되는 모든 요소와 그들의 속성

그리고 계층 구조에 대한 정의를 포함합니다.

 

앞서 말 한대로 HTML DTD는 문맥 자유 문법이 아닙니다.

 

DTD에는 몇 가지 변형이 있습니다.

'엄격 모드(The strict mode)'는 명세만을 따르지만,

다른 모드는 과거의 브라우저에서 사용한 마크업을 지원합니다.

 

과거의 브라우저에서 사용한 마크업을 지원하는 이유는

'오래된 콘텐츠에 대한 하위 호환성' 때문입니다.

 

 

 

DOM

---

전문

The output tree (the "parse tree") is a tree of DOM element and attribute nodes. DOM is short for Document Object Model. It is the object presentation of the HTML document and the interface of HTML elements to the outside world like JavaScript.
The root of the tree is the "Document" object.

The DOM has an almost one-to-one relation to the markup. For example:

This markup would be translated to the following DOM tree:

Figure : DOM tree of the example markup

Like HTML, DOM is specified by the W3C organization. See www.w3.org/DOM/DOMTR. It is a generic specification for manipulating documents. A specific module describes HTML specific elements. The HTML definitions can be found here: www.w3.org/TR/2003/REC-DOM-Level-2-HTML-20030109/idl-definitions.html.

When I say the tree contains DOM nodes, I mean the tree is constructed of elements that implement one of the DOM interfaces. Browsers use concrete implementations that have other attributes used by the browser internally.

파싱 트리는 DOM 요소와 속성 노드의 트리입니다.

DOM은 Document Object Model로

DOM에 대한 설명은 지난 글을 참조하시면 좋을 것 같습니다.

 

트리의 최상위 계층은 '문서'입니다.

DOM은 마크업과 거의 1 대 1 관계를 맺습니다.

 

예를 들어,

 

이러한 마크업은 다음과 같은 DOM 트리로 변환할 수 있습니다.

 

 

HTML처럼 DOM은 W3C에 의해 명세되어 있습니다.

 

트리가 DOM 노드를 포함한다는 말은,

트리가 DOM 인터페이스 중 하나를 실행하는

요소로 구성되어 있다는 것을 의미합니다.

 

브라우저는 내부적으로 사용하는 다른 속성들을 가지는

인터페이스나 클래스와 같은 'Concreate implementation'을 사용합니다.

 

 

 

The parsing algorithm(파싱 알고리즘)

---

전문

As we saw in the previous sections, HTML cannot be parsed using the regular top down or bottom up parsers.

The reasons are:

1. The forgiving nature of the language.
2. The fact that browsers have traditional error tolerance to support well known cases of invalid HTML.
3. The parsing process is reentrant. For other languages, the source doesn't change during parsing, but in HTML, dynamic code (such as script elements containing document.write() calls) can add extra tokens, so the parsing process actually modifies the input.

Unable to use the regular parsing techniques, browsers create custom parsers for parsing HTML.

The parsing algorithm is described in detail by the HTML5 specification. The algorithm consists of two stages: tokenization and tree construction.

Tokenization is the lexical analysis, parsing the input into tokens. Among HTML tokens are start tags, end tags, attribute names and attribute values.

The tokenizer recognizes the token, gives it to the tree constructor, and consumes the next character for recognizing the next token, and so on until the end of the input.

Figure  : HTML parsing flow (taken from HTML5 spec)

위에서 언급했듯이,

HTML은 일반적인 상향식 혹은 하향식 파서로 파싱이 불가능합니다.

 

이유를 정리하면 다음과 같습니다.

1. HTML 작성자의 실수를 용인해줍니다.
2. 잘 알려져 있는 HTML 오류에 대해서 브라우저에서 용인해줍니다.
3. HTML은 동적 코드로 입력 과정에서 파싱이 수정될 수 있습니다.

따라서 HTML을 파싱 할 때는 별도의 파서를 정의해야 합니다.

 

파싱 알고리즘은 다음 사이트에 잘 정리되어 있습니다.

참조 : HTML 5 Specification

 

HTML 파싱 알고리즘은 두 단계로 나눌 수 있습니다. 단계는 다음과 같습니다.

1. 토큰화
2. 트리 생성

이 두 단계에 대한 이해는 앞선 글에서 확인하실 수 있습니다!

브라우저 동작 원리 5탄 참조하기

 

HTML 파싱에 대한 과정을 그림으로 나타내면 다음과 같습니다.

토큰화 과정은 입력이 끝날 때까지 계속해서 일어납니다.

 

쉽게 말해, 토큰을 인지하여 트리 생성자에게 보내고,

다음 토큰을 인지하여 다시 트리 생성자에게 보내는

과정이 입력의 시작과 끝까지 일어나는 것입니다.

 

 

 

The tokenization algorithm(토큰화 알고리즘)

---

전문

The algorithm's output is an HTML token. The algorithm is expressed as a state machine. Each state consumes one or more characters of the input stream and updates the next state according to those characters. The decision is influenced by the current tokenization state and by the tree construction state. This means the same consumed character will yield different results for the correct next state, depending on the current state. The algorithm is too complex to describe fully, so let's see a simple example that will help us understand the principle.

Basic example–tokenizing the following HTML:

The initial state is the "Data state". When the < character is encountered, the state is changed to "Tag open state". Consuming an a-z character causes creation of a "Start tag token", the state is changed to "Tag name state". We stay in this state until the > character is consumed. Each character is appended to the new token name. In our case the created token is an html token.

When the > tag is reached, the current token is emitted and the state changes back to the "Data state". The <body> tag will be treated by the same steps. So far the html and body tags were emitted. We are now back at the "Data state". Consuming the H character of Hello world will cause creation and emitting of a character token, this goes on until the < of </body> is reached. We will emit a character token for each character of Hello world.

We are now back at the "Tag open state". Consuming the next input / will cause creation of an end tag token and a move to the "Tag name state". Again we stay in this state until we reach >.Then the new tag token will be emitted and we go back to the "Data state". The </html> input will be treated like the previous case.

Figure  : Tokenizing the example input

알고리즘의 결과물은 토큰입니다.

알고리즘은 'State machine'이라고 볼 수 있습니다.

 

각 State, 즉 상태는 하나 이상의 문자를 입력받아

그 문자에 따라 다음 상태를 업데이트합니다.

 

하지만 이런 State는 현재 토큰화 상태와 트리 생성의 영향을 받습니다.

 

즉, 같은 문자열이 입력되어도

현재 상태에 따라 다른 결과를 낳을 수 있다는 것입니다.

 

HTML에 대한 쉬운 예를 보겠습니다.

최초의 상태는 'Data State'입니다.

이후 '<'가 입력되면 'Tag open State'가 됩니다.

 

'a-z'같은 문자를 입력하면, 'Start tag token'이 생성되고

상태는 'Tag name State'가 됩니다.

이 상태는 '>'가 입력될 때까지 유지됩니다.

 

각 문자에는 새로운 토큰 이름이 붙습니다.

이 경우 토큰은 HTML 토큰입니다.

 

'>'가 입력된다면, 현재 토큰이 발행되고

상태는 다시 'Data State' 상태가 됩니다.

 

동일한 방식으로 <html>, <body>까지 입력하고 나면

'Hello world'라는 문자를 입력하게 되고,

이에 따른 문자 토큰이 생성되고 발행되게 됩니다.

 

'/' 문자는 종료 태그를 생성합니다.

따라서 Hello world라는 문자열을 입력하고

'</body>'를 입력하기 위해

'<'를 입력하면 'Tag open State'가 되고,

'/'가 입력되어 종료 태그가 생성됩니다.

이후 문자열 입력을 통해 'Tag name State'로 전환되고,

'>'가 입력될 때까지 지속됩니다.

 

이후 새로운 태그 토큰이 발행되고

상태는 다시 'Data State'로 전환됩니다.

 

아래 그림은 위의 그림을 정리한 그림입니다.

 

위의 그림을 보면서 내용을 다시 한번 정리하겠습니다.

'Data State' 상태에서 출발합니다.

시작은 '<' 태그이기 때문에 'Tag open' 상태로 진입합니다.

이후 닫는 태그인지, 새로 시작하는 태그인지에 따라

종료 태그가 생성되는 상태로 진입하거나

Tag name을 입력하는 상태로 진입합니다.

 

이후 경우에 따라 문자 토큰을 발행하고

비슷한 방식으로 글의 끝까지 토큰을 발행합니다.

 

---

이번 글에서는

정규 표현식과 BNF에 대해 간단히 알아보았고,

파서의 종류, 그리고 일반적인 파서가 왜 HTML에 적용되지 않는지,

또 적용되지 않는 HTML에는 어떻게 파서가 적용되는지 알아보았습니다.

 

다음 글에서는 CSS를 파싱 하는 방법부터 설명하도록 하겠습니다.

 

읽어주셔서 감사합니다.

글 내용에서 오류를 발견하시면 댓글이나 메일 부탁드리겠습니다!🙇‍♂️🙇‍♂️