第三章
解析
在渲染引擎中解析是一个很精密的过程,接下来我们从更深的角度来解释。让我们从简短介绍解析开始。
解析一个文档意味着将它翻译成被理解、可使用有意义的结构。解析的结果是使用节点树展示文档的结构,被称之为词法树或者语法树。
例子:解析2+3-1的表达式生成树的过程
图:数学表达式的树节点
语法
解析是基于语法规则,文档遵循一些被定义下来的语言和格式。所解析的格式必须是有明确包括词汇和语法规则的语法,称之为“上下文空闲语法context free grammar”。人类语言并如此,因此不能使用传统的解析技术来进行解析。
解析-词法分析结合(lexer combination)
解析可以被分成两个子处理过程-词法分析和语法分析
词法分析是将输入信息切成小令牌(token)的过程。小令牌是语言词汇,即有效建筑模块的集合。相对于人类语言,它包括各种出现字典中的单词。
语法分析是语法规则的应用。
解析一般是在两个部分中切分工作。一个是词法分析(有时候称之为令牌化)负责将输入的信息切分成有效的令牌,另一个是解释,负责通过语言语法规则分析文档结构来构造解析树。这个词法分析知道如何剥夺不相干的字符,如空格和换行符。
图:源代码解析树
解析是一个递归过程。解析通常对于一个新令牌要求词法分析并且尝试用其中一个语法规则去匹配。如果某一个规则被匹配,该令牌与节点保持一致添加到解析树中,然后解析将使用另一个令牌。
如果规则没有被匹配,解析内部存储该令牌,然后不断使用令牌,直到一个匹配能匹配所有内部储存的令牌规则被找到。如果该规则没有被找到,解析将会抛出异常。这就意味着文档不是有效的,是有语法错误的。
翻译
很多时候解析树并不是最终产品,解析经常被用作翻译-将输入的文档转变成另一种格式。编译就是一个例子。编译是将源代码编译成机器码。这一过程首先是将源代码解析成解析树然后将解析树翻译成机器码文档。
解析例子
在图5中,我们从一个数学表达式中创建了一个解析树。让我们在试着定义了一个简单的数学语言然后在了解这一解析过程。
词汇:我们语言包括整数、加号和减号。
语法:
<ol>
第一个字串匹配的规则是2,通过规则5我们知道是一个术语。第二个字串匹配的是2+3,匹配的是第三个规则-即一个术语跟随一个操作符跟随另一个术语。接 下来匹配仅仅击中了最后的输入。2+3-1是一个表达式,因为我们已经知道2+3是一个术语,所以我们有一个术语跟随一个操作符跟随另一个术语。2++将 不会匹配任何规则,因此是一个无效的输入。正式定义的词汇和语法词汇通常使用正则表达式表达.
例如:我们的语言定义如下:
整数:0|[1-9][0-9]*
加号:+
减号:-
正如你看到的,整数使用正则表达式定义
语法通常用BNF格式定义。我们的语言定义如下:
表达式 := 术语 操作符 术语
操作符 := 加号|减号
术语:= 整数|正则表达式
我们说如果语言的语法是一个上下文空间语法(context frees grammar),那么该语言会被一般解析规则(regular parsers)所解析。上下文空间语法的直觉定义(intuitive definition)是一个完全用BNF表达的语法。
解析类型
有两种基本的解析类型-自上向下解析和自下向上解析。一个直觉的解析是自上向下看作是语法的高级别结构然后去匹配其中的每一个规则。自底向上解析从输入信息开始然后渐渐的将输入的信息翻译进语法规则中,从低级规则开始直到被高级规则匹配。
让我们看下这两种类型解析范例:
自顶向下解析从高级别规则开始-识别出2+3并作为一个表达式,然后在识别出2+3-1也作为一个表达式(识别表达式的过程进行匹配其他规则,但是开始点是最高级别规则)
自底向上解析扫描输入的信息直到被某一条规则匹配,然后用该规则取代匹配到的信息,在此继续直到匹配到最后的数据。解析棧会取代部分的匹配表达式。
自底向上的解析类型又被称之为”a shift-reduce”解析,因为输入被转向正确(想象一个指针指向第一个输入开始位置,并且移到右边去)并且渐渐减少语法规则。
一般自动化解析
有一些工具可以为你产生解析,称之为解析产生。反馈你所定义语言语法-包括词汇和语法规则-他们产生工作解析(working parser).创建这个解析需要对解析有一个深层次的理解,手动创建一个优化解析也并非易事,所以解析产生是非常有用的。Bison的输入信息是用 BNF格式的语言语法规则。
Webkit使用了著名的解析产生,flex用于产生词法分析器和bison用于创建解析器(你也可以使用lex和yacc)。Flex输入信息是一个文件包括定义了各种令牌的正则表达式。Bison的输入信息是用BNF格式的语言语法规则。
Html解析
Html解析的工作是将html标记解析成一棵解析树。
Html语法定义
Html 的词汇和语法是有w3c组织起草的说明书中定义的。当前版本是html4和正在进行中的html5.
并非是一个上下文空闲语法
正如我们在解析介绍中的那样,语法可以使用BNF 类似的正式格式去定义。
不幸的是,并不是所有常规的解析主题(the conventional parser topics)都能应用到html。Html不能被很容易的通过解析所需要的上下文空闲语法所定义。
有一种正是的格式用于定义html.-DTD(文档类型定义)-而并非是上下文空闲语法。
第一次不自在的出现(appears strange at first sight).html是非常接近于xml。存在很多可用的xml解析器。也有一个html的xml变化版本-xhtml,那么他们有什么差别呢?
不同在于html技术更加“宽恕”(forgiving)。他默许你含蓄的忽略(omit)本应该添加的适当标签,有时候忽略开始或者结尾的标签等等。总而言之,html是一个温柔的语法,相对于xml的严谨(stiff)和命令式的语法。
表面上这看起来小小的不同却让世界发生了不同。一方面这也是html如此流行的主要原因-html 宽恕你的错误和让web开发者的生活变得简单。另一方面,编写正式的语法变得困难起来。总结来说,html不能被很容易的解析,自从语法不是上下文空闲语 法就不能通过传统解析,,也不能通过xml解析。
Html文档类型定义
Html 定义是用文档类型定义格式。这种格式被用作定义SGML家族语言。这种格式包括定义所有容许的元素,他们的属性和层级。但是我很早就知道, html文档类型并不是来自于上下文空闲语法。
文档类型定义有很多变种。严厉模式(strict mode)完全遵循说明书但是其他模式包括曾经浏览器所使用支持的标记。目的就是要向后兼容(backwards compatibility)老的内容。
DOM
输出树-解析树是一棵dom元素和属性节点树。Dom是文档对象模型的简称。是html文档和html元素面向外部世界的接口(如javascript)的对象展示。
树的根节点是文档对象。
Dom与标记几乎有着一对一的关联,例如,这个标记
1 2 3 4 5 6 7 |
<span style="color: #0000ff;"><code> <html> <body> Hello world </body> </html> </code></span> |
像html、dom都是由w3c组织定义的,请查看 www.w3.org/dom/domtr.
对于操作文档来说只是一般说明书。一个指定的模块描述html指定元素。Html定义可以在 www.w3.org/tr/2003/rec-dom-level-2-html-20030109/idl-definitions.html找到。
当我说树中包括dom节点,我的意思是树是由dom接口实现的元素所构成的。浏览器使用具体实现,而有些其他属性是通过浏览器内部使用。
————————————-更新线——————————————————-
解析算法
正如上一章所说,html不能使用一般的自顶向下或者自下向上解析。
理由是:
<ol>
在解析的过程中源码通常是不能改变的,但是在html中,脚本标签包含document.write可以额外添加令牌,所以实际上解析的过程是可以修改输入信息。</ol>不能使用传统的解析技术,浏览器在解析html会创建自定义解析。
解析的算法在html5说明书中有详细的介绍。算法包括两个策略。分词和树结构。
分词是词法分析,将输入的信息解析成令牌。在html中令牌是开始标签、结束标签、属性名字和属性值。
分词器识别令牌,并将令牌交给树结构,耗尽下一个字符是为了识别下一个令牌,直到信息的结束。
分词算法
算法的输出是html令牌。算法用状态机表示。每一种状态消耗一个或多个输入符,通过这些字符将更新下一种状态。当前的分词状态和树结构状态都影响 决定。这意味着消耗相同的字符将放弃对于正确的下一个状态的不同结果。根据当前的状态,算法变得太复杂而不能描述全部。所以让我们来看一个简单的例子将帮 助我们理解这个原则。
基础例子-分词下面的 html
1 2 3 4 5 6 7 |
<span style="color: #0000ff;"><code> <html> <body> Hello world </body> </html> </code></span> |
初始化状态是”数据状态”。当遇到”<”,状态将改编成“打开状态”。消耗一个a-z字符引起”开始标签令牌”的创建,状态改变成“标签名字 状态”,我们将一直保持这个状态直到遇到”>”字符。每一个字符都被添加一个新的令牌名字。在我们的例子中,html令牌使我们创建的令牌。
当到达”>”标签时,当前的令牌被发散(emitted),状态并回到“数据状态”。<body>标签被相同的步骤看待。目前来 说,html和body标签都是被发散的。我们现在返回到“数据状态”消耗”hello world”中的h字符将引发 创造和一个字符的发散,反复这个过程直到遇到</body>标签中的<字符。我们会为hello world中的每一个字符发散一个字符令牌。
我们在回到“开放状态”。消耗下一个输入/将引发一个结束令牌的创建并且移向“标签名字状态”.我们将再一次保持这个状态直到遇到>标签。然后新的标签令牌将被发散出,之后我们回到“数据状态”</html>输入被看作是前一个场景。
图:令牌化处理
树构造算法
当解析被创建的时候,文档对象也会被创建。在树构造策略中,dom树会伴随文档根元素修改,元素将添加到dom树中。每个节点会通过分词而发散,通 过树构造而被处理。对于每一个令牌跟dom元素有着关联的说明定义,并被每一个令牌所创建。除了添加到dom树中的元素以外,也被添加到公开元素的堆中。 这个堆中用于收集嵌套错误和未必合的标签。这个算法也被描述成状态机。这个状态也称之外“插入模式”.
让我们看一下树构造的处理过程
1 2 3 4 5 6 7 |
<span style="color: #0000ff;"><code> <html> <body> Hello world </body> </html> </code></span> |
输入到树构造策略是一个从分词策略中的一组顺序令牌。第一个模式是“初始化模式”接收到html 令牌将引起向”before html”移动模式,并且在那种模式下会再次处理这个令牌。这会引起HTMLHtmlElement元素的创建和被添加到根文档对象中。
策略将被改变为”before head”。我们接收到”body”令牌。HTMLHeadElement将被含蓄的创建,尽管我们并没有head令牌,然后会被添加到树中。
我们现在移到”in head”模式,然后到 “after head”。Body令牌被再一次处理。 HTMLBodyElement被创建、插入然后模式被转移到”in body”。
“hello world”字符令牌现在被接受。第一个将引起创建然后一个“文本”字节被插入。其他的字节将添加到那个字节中。
Body结束令牌被收到之后,将引起转移到”after body”模式。现在我们收到移动到”after afterbody”模式的html结束标签。收到文件令牌的结束,解析也就结束。
图:树结构例子
解析完成后的行为
在这个策略,浏览器将标记文档为内部行为。开始解析被”延迟”模式的脚本-当文档解析之后,这些被延迟的脚本才会被执行。文档状态被设置为”完毕”和”加载”事情会被触发。
你可以在html5说明书中看到分词和树构造的完整算法。
浏览器的错误容忍
你不会在页面中看到无效语法错误。浏览器会帮你修复任何无效内容并继续执行。
下面代码为例:
1 2 3 4 5 6 7 8 9 10 11 |
<span style="color: #0000ff;"><code> <html> <mytag> </mytag> <div> <p> </div> Really lousy HTML </p> </html> </code></span> |
我已经违反了百万规则(“mytag”不是一个标准标签,p和div元素的错误嵌套)但是浏览器还是会正确的显示,并且不会抱怨。所以大量的解析代码用来修复页面开发者的错误。
错误处理与浏览器保持一致。但是吃惊的是它并不是当前html 说明书中的一部分。像书签和前进/后退按钮,这些已经在很多年前就已经被开发了。在很多网站都会报告一些很出名的无效html结构,浏览器厂商与其他厂商达成一致规则去试图修复他们。
Html5说明书并没有定义这些需求。Webkit在html类的开始的注释中总结这些。
解析器解析令牌到文档中,创建文档树。如果文档是格式良好,解析将会变得很快。
不幸的是,我们不得不去处理很多格式不好的文档,所以解析器不得不去容忍这些错误。
我们不得不关系最近如下错误条件:
<ol>
1 |
<span style="color: #0000ff;"><code></br>instead of <br></code></span> |
一些站点使用
替代
.为了兼容ie和firefox浏览器。Webkit这样处理如
1 2 3 4 5 |
<span style="color: #0000ff;"><code>代码: if (t->isCloseTag(brTag) && m_document->inCompatMode()) { reportError(MalformedBRError); t->beginTag = true; } |
记住:错误处理是在内部进行的,他不会展示给用户。
一个偏离的(stray)表格
一个偏离的表格是一个表格中内嵌另一个表格并不是内嵌一个表格单元(cell)
例如:
1 2 3 4 5 6 7 8 |
<span style="color: #0000ff;"><code> <table> <table> <tr><td>inner table</td></tr> </table> <tr><td>outer table</td></tr> </table> </code></span> |
webkit将改变这两个兄弟节点表格的层级
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
<span style="color: #0000ff;"><code> <table> <tr><td>outer table</td></tr> </table> <table> <tr><td>inner table</td></tr> </table> if (m_inStrayTableContent && localName == tableTag) popBlock(tableTag); <span style="color: #0000ff;">webkit为当前元素内容使用一个堆-将弹出外部表格堆中的内部表格。这些表格现在就是兄弟节点。</span> <span style="color: #0000ff;">嵌套表格元素</span> <span style="color: #0000ff;">这种场景,用户将一个内部表格放到另一个表格,第二个表格会被忽略。</span> <pre><span style="color: #0000ff;"><code>代码: if (!m_currentFormElement) { m_currentFormElement = new HTMLFormElement(formTag, m_document); }</code></span> |
一个深标签层级
注释:
www.liceo.edu.mx是一个有着1500标签的嵌套行为。我们只允许嵌套相同类型的标签,其余都会被忽略。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
<span style="color: #0000ff;"> bool HTMLParser::allowNestedRedundantTag(const AtomicString& tagName) { unsigned i = 0; for (HTMLStackElem* curr = m_blockStack; i < cMaxRedundantTagDepth && curr && curr->tagName == tagName; curr = curr->next, i++) { } return i != cMaxRedundantTagDepth; } if (t->tagName == htmlTag || t->tagName == bodyTag ) return; </code></span> |
错位的(misplace)的html或者body结束标签。
再注释
支持真正意思上的片段html。我们从不关闭body标签,在文档实际关闭之前,然而一些愚蠢的网页将会关闭它。我们依赖调用end方法来关闭。
1 2 |
<span style="color: #0000ff;"><code>if (t->tagName == htmlTag || t->tagName == bodyTag ) return;</code></span> |
所以网页设计师要小心(beware),如果你不想在 webkit错误容忍代码片段作为例子出现,写结构良好的html.
暂无评论