從"算法"角度回答—輸入URL后頁面呈現(xiàn)發(fā)生了什么？

猿友 2020-09-02 10:31:12 瀏覽數(shù) (2325)

反饋

文章轉(zhuǎn)載自公眾號：前端三元同學(xué)

老生常談的問題，可以另辟蹊徑來回答！本文不講解 URL 輸入后發(fā)生的網(wǎng)絡(luò)部分，只從算法角度講解拿到頁面后的解析部分，主要分為以下幾個步驟:

構(gòu)建 DOM樹
樣式計算
生成布局樹(Layout Tree)

構(gòu)建 DOM 樹

由于瀏覽器無法直接理解 HTML字符串，因此將這一系列的字節(jié)流轉(zhuǎn)換為一種有意義并且方便操作的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)就是DOM樹。DOM樹本質(zhì)上是一個以document為根節(jié)點的多叉樹。

那通過什么樣的方式來進行解析呢？

HTML文法的本質(zhì)

首先，我們應(yīng)該清楚把握一點: HTML 的文法并不是上下文無關(guān)文法。

這里，有必要討論一下什么是上下文無關(guān)文法。

在計算機科學(xué)的編譯原理學(xué)科中，有非常明確的定義:

若一個形式文法G = (N, Σ, P, S) 的產(chǎn)生式規(guī)則都取如下的形式：V-&w，則叫上下文無關(guān)語法。其中 V∈N ，w∈(N∪Σ)* 。

其中把 G = (N, Σ, P, S) 中各個參量的意義解釋一下:

N 是非終結(jié)符(顧名思義，就是說最后一個符號不是它, 下面同理)集合。
Σ 是終結(jié)符集合。
P 是開始符，它必須屬于 N ，也就是非終結(jié)符。
S 就是不同的產(chǎn)生式的集合。如 S -> aSb 等等。

通俗一點講，上下文無關(guān)的文法就是說這個文法中所有產(chǎn)生式的左邊都是一個非終結(jié)符。

看到這里，如果還有一點懵圈，我舉個例子你就明白了。

比如:

A -> B

這個文法中，每個產(chǎn)生式左邊都會有一個非終結(jié)符，這就是上下文無關(guān)的文法。在這種情況下，xBy一定是可以規(guī)約出xAy的。

我們下面看看看一個反例：

aA -> B
Aa -> B

這種情況就是不是上下文無關(guān)的文法，當遇到B的時候，我們不知道到底能不能規(guī)約出A，取決于左邊或者右邊是否有a存在，也就是說和上下文有關(guān)。

關(guān)于它為什么是非上下文無關(guān)文法，首先需要讓大家注意的是，規(guī)范的 HTML 語法，是符合上下文無關(guān)文法的，能夠體現(xiàn)它非上下文無關(guān)的是不標準的語法。在此我僅舉一個反例即可證明。

比如解析器掃描到form標簽的時候，上下文無關(guān)文法的處理方式是直接創(chuàng)建對應(yīng) form 的 DOM 對象，而真實的 HTML5 場景中卻不是這樣，解析器會查看 form 的上下文，如果這個 form 標簽的父標簽也是 form, 那么直接跳過當前的 form 標簽，否則才創(chuàng)建 DOM 對象。

常規(guī)的編程語言都是上下文無關(guān)的，而HTML卻相反，也正是它非上下文無關(guān)的特性，決定了HTML Parser并不能使用常規(guī)編程語言的解析器來完成，需要另辟蹊徑。

解析算法

HTML5 規(guī)范詳細地介紹了解析算法。這個算法分為兩個階段:

標記化。
建樹。

對應(yīng)的兩個過程就是詞法分析和語法分析。

標記化算法

這個算法輸入為 HTML文本，輸出為HTML標記，也成為標記生成器。其中運用有限自動狀態(tài)機來完成。即在當當前狀態(tài)下，接收一個或多個字符，就會更新到下一個狀態(tài)。

<html>
  <body>
    Hello sanyuan
  </body>
</html>

通過一個簡單的例子來演示一下標記化的過程。

遇到<, 狀態(tài)為標記打開。

接收[a-z]的字符，會進入標記名稱狀態(tài)。

這個狀態(tài)一直保持，直到遇到>，表示標記名稱記錄完成，這時候變?yōu)?strong>數(shù)據(jù)狀態(tài)。

接下來遇到body標簽做同樣的處理。

這個時候html和body的標記都記錄好了。

現(xiàn)在來到<body>中的>，進入數(shù)據(jù)狀態(tài)，之后保持這樣狀態(tài)接收后面的字符hello sanyuan。

接著接收 </body> 中的<，回到標記打開, 接收下一個/后，這時候會創(chuàng)建一個end tag的token。

隨后進入標記名稱狀態(tài), 遇到>回到數(shù)據(jù)狀態(tài)。

接著以同樣的樣式處理 </body>。

建樹算法

之前提到過，DOM 樹是一個以document為根節(jié)點的多叉樹。因此解析器首先會創(chuàng)建一個document對象。標記生成器會把每個標記的信息發(fā)送給建樹器。建樹器接收到相應(yīng)的標記時，會創(chuàng)建對應(yīng)的 DOM 對象。創(chuàng)建這個DOM對象后會做兩件事情:

將DOM對象加入 DOM 樹中。
將對應(yīng)標記壓入存放開放(與閉合標簽意思對應(yīng))元素的棧中。

還是拿下面這個例子說:

<html>
  <body>
    Hello sanyuan
  </body>
</html>

首先，狀態(tài)為初始化狀態(tài)。

接收到標記生成器傳來的html標簽，這時候狀態(tài)變?yōu)?strong>before html狀態(tài)。同時創(chuàng)建一個HTMLHtmlElement的 DOM 元素, 將其加到document根對象上，并進行壓棧操作。

接著狀態(tài)自動變?yōu)?strong>before head, 此時從標記生成器那邊傳來body，表示并沒有head, 這時候建樹器會自動創(chuàng)建一個HTMLHeadElement并將其加入到DOM樹中。

現(xiàn)在進入到in head狀態(tài), 然后直接跳到after head。

現(xiàn)在標記生成器傳來了body標記，創(chuàng)建HTMLBodyElement, 插入到DOM樹中，同時壓入開放標記棧。

接著狀態(tài)變?yōu)?strong>in body，然后來接收后面一系列的字符: Hello sanyuan。接收到第一個字符的時候，會創(chuàng)建一個Text節(jié)點并把字符插入其中，然后把Text節(jié)點插入到 DOM 樹中body元素的下面。隨著不斷接收后面的字符，這些字符會附在Text節(jié)點上。

現(xiàn)在，標記生成器傳過來一個body的結(jié)束標記，進入到after body狀態(tài)。

標記生成器最后傳過來一個html的結(jié)束標記, 進入到after after body的狀態(tài)，表示解析過程到此結(jié)束。

容錯機制

講到HTML5規(guī)范，就不得不說它強大的寬容策略, 容錯能力非常強，雖然大家褒貶不一，不過我想作為一名資深的前端工程師，有必要知道HTML Parser在容錯方面做了哪些事情。

接下來是 WebKit 中一些經(jīng)典的容錯示例，發(fā)現(xiàn)有其他的也歡迎來補充。

1.使用</br>而不是<br>

if (t->isCloseTag(brTag) && m_document->inCompatMode()) {
  reportError(MalformedBRError);
  t->beginTag = true;
}

全部換為<br>的形式。

2.表格離散

<table>
  <table>
    <tr><td>inner table</td></tr>
  </table>
  <tr><td>outer table</td></tr>
</table>

WebKit會自動轉(zhuǎn)換為:

<table>
    <tr><td>outer table</td></tr>
</table>
<table>
    <tr><td>inner table</td></tr>
</table>

3.表單元素嵌套

這時候直接忽略里面的form。

樣式計算

關(guān)于CSS樣式，它的來源一般是三種:

link標簽引用
style標簽中的樣式
元素的內(nèi)嵌style屬性

格式化樣式表

首先，瀏覽器是無法直接識別 CSS 樣式文本的，因此渲染引擎接收到 CSS 文本之后第一件事情就是將其轉(zhuǎn)化為一個結(jié)構(gòu)化的對象，即styleSheets。

這個格式化的過程過于復(fù)雜，而且對于不同的瀏覽器會有不同的優(yōu)化策略，這里就不展開了。

在瀏覽器控制臺能夠通過document.styleSheets來查看這個最終的結(jié)構(gòu)。當然，這個結(jié)構(gòu)包含了以上三種CSS來源，為后面的樣式操作提供了基礎(chǔ)。

標準化樣式屬性

有一些 CSS 樣式的數(shù)值并不容易被渲染引擎所理解，因此需要在計算樣式之前將它們標準化，如em->px,red->#ff0000,bold->700等等。

計算每個節(jié)點的具體樣式

樣式已經(jīng)被格式化和標準化,接下來就可以計算每個節(jié)點的具體樣式信息了。

其實計算的方式也并不復(fù)雜，主要就是兩個規(guī)則: 繼承和層疊。

每個子節(jié)點都會默認繼承父節(jié)點的樣式屬性，如果父節(jié)點中沒有找到，就會采用瀏覽器默認樣式，也叫UserAgent樣式。這就是繼承規(guī)則，非常容易理解。

然后是層疊規(guī)則，CSS 最大的特點在于它的層疊性，也就是最終的樣式取決于各個屬性共同作用的效果，甚至有很多詭異的層疊現(xiàn)象，看過《CSS世界》的同學(xué)應(yīng)該對此深有體會，具體的層疊規(guī)則屬于深入 CSS 語言的范疇，這里就不過多介紹了。

不過值得注意的是，在計算完樣式之后，所有的樣式值會被掛在到window.computedStyle當中，也就是可以通過JS來獲取計算后的樣式，非常方便。

生成布局樹

現(xiàn)在已經(jīng)生成了DOM樹和DOM樣式，接下來要做的就是通過瀏覽器的布局系統(tǒng)確定元素的位置，也就是要生成一棵布局樹(Layout Tree)。

布局樹生成的大致工作如下:

遍歷生成的 DOM 樹節(jié)點，并把他們添加到布局樹中。
計算布局樹節(jié)點的坐標位置。

值得注意的是，這棵布局樹值包含可見元素，對于 head標簽和設(shè)置了display: none的元素，將不會被放入其中。

有人說首先會生成Render Tree，也就是渲染樹，其實這還是 16 年之前的事情，現(xiàn)在 Chrome 團隊已經(jīng)做了大量的重構(gòu)，已經(jīng)沒有生成Render Tree的過程了。而布局樹的信息已經(jīng)非常完善，完全擁有Render Tree的功能。

之所以不講布局的細節(jié)，是因為它過于復(fù)雜，一一介紹會顯得文章過于臃腫，不過大部分情況下我們只需要知道它所做的工作是什么即可，如果想深入其中的原理，知道它是如何來做的，我強烈推薦你去讀一讀人人FED團隊的文章從Chrome源碼看瀏覽器如何layout布局。

總結(jié)

梳理一下這一節(jié)的主要脈絡(luò):

總結(jié)

以上就是W3Cschool編程獅關(guān)于從"算法"角度回答—輸入URL后頁面呈現(xiàn)發(fā)生了什么？的相關(guān)介紹了，希望對大家有所幫助。

前端

0 人點贊