WebKit中的html词法解析 -

vvvvbbbb

浏览: 21239 次
性别:
来自: 北京

最近访客更多访客>>

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (15)

社区版块

存档分类

WebKit中的html词法解析

webkit HTML HTML5 数据结构 .net

语言的解析一般分为词法分析（lexical analysis）和语法分析（Syntax analysis）两个阶段，WebKit中的html解析也不例外，本文主要讨论词法分析。

词法分析的任务是对输入字节流进行逐字扫描，根据构词规则识别单词和符号，分词。

在WebKit中，有两个类，同词法分析密切相关，它是HTMLToken和HTMLTokenizer类，可以简单将HTMLToken类理解为标记，HTMLTokenizer类理解为词法解析器。HTML词法解析的任务，就是将输入的字节流解析成一个个的标记（HTMLToken），然后由语法解析器进行下一步的分析。

在XML/HTML的文档解析中，token这个词经常用到，我将其理解为一个有完整语义的单元（也就是分出来的“词”），一个元素通常对应于3个 token，一个是元素的起始标签，一个是元素的结束标签，一个是元素的内容，这点同DOM树是不一样的，在DOM树上，起始标签和结束标签对应于一个元素节点，而元素内容对应另一个节点。

除了起始标签(StartTag)、结束标签(EndTag)和元素内容（Character），HTML标签还有DOCTYPE（文档类型）,Comment（注释），Uninitialized（默认类型）和EndOfFile（文档结束）等类型，参见HTMLToken.h中的 Type枚举。

htmltoken

上图是HTMLToken类的成员变量，从中我们可以看到一个标记的组成：类型，在字节流中的偏移，数据（m_data,不同的类型具有不同的意义），文档类型，是否自封闭(对于开始和结束标签)，属性列表，当前属性。

HTMLTokenizer就是要从字节流解析出一个个这样的结构体来，他的实现是基于状态机来做的，状态机模型在http://www.w3.org/TR/html5/tokenization.html#tokenization中已经明确定义，nextToken方法实现了该状态机。

对有限状态机不熟悉的童子建议先学习下absurd大大的文章系统程序员成长计划-文本处理(一)状态机（http://blog.csdn.net/absurd/archive/2009/06/07/4249569.aspx）。

下面以一个简单的html文档来复盘状态机的几条路线。

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">



<html>

<body>

<a href=”w3c.org”>w3c</a>

</body>

</html>

不考虑类似<html>和<body>之间的回车换行（webkit里面有做特殊处理，也就是所谓的“authoring convenience”，m_skipLeadingNewLineForListing），从前面的描述中，我们可以确认，该文档有9个 HTMLToken，分别是文档类型声明，注释，html的起始标签，body的起始标签，a的起始标签，a的元素内容，a的介绍标签，body的结束标签，html的结束标签。

起始状态为DataState。

1）DOCTYPE

DataState：<!DOCTYPE，碰到’<’，进入TagOpenState

TagOpenState：<!DOCTYPE, 碰到’!’，进入MarkupDeclarationOpenState状态

MarkupDeclarationOpenState：<!DOCTYPE,碰到’D’，匹配DOCTYPE和--字数都不够，保持现状

MarkupDeclarationOpenState：<!DOCTYPE,匹配doctype，进入DOCTYPEState状态(HTMLToken的type为DOCTYPE)

DOCTYPEState: <!DOCTYPE html PUBL，碰到空格，进入BeforeDOCTYPENameState状态

BeforeDOCTYPENameState: <!DOCTYPE html PUBL，碰到’h’，进入DOCTYPENameState

DOCTYPENameState: <!DOCTYPE html PUBL，碰到’t’,保持原状态，提取html作为文档类型

DOCTYPENameState: <!DOCTYPE html PUBL，碰到空格，进入AfterDOCTYPENameState状态。(HTMLToken的m_data为

                                  html)

AfterDOCTYPENameState：<!DOCTYPE html PUBLIC，碰到’P’，还未能匹配Public或者system，保持状态

AfterDOCTYPENameState：<!DOCTYPE html PUBLIC,匹配public，进入AfterDOCTYPEPublicKeywordState

AfterDOCTYPEPublicKeywordState：<!DOCTYPE html PUBLIC "-/，碰到空格，进入BeforeDOCTYPEPublicIdentifierState

BeforeDOCTYPEPublicIdentifierState：<!DOCTYPE html PUBLIC "-/，碰到’”’，进入

                                                                 DOCTYPEPublicIdentifierDoubleQuotedState

DOCTYPEPublicIdentifierDoubleQuotedState：<!DOCTYPE html PUBLIC "-/，碰到’-‘，保持状态，提取m_publicIdentifier

DOCTYPEPublicIdentifierDoubleQuotedState：<!DOCTYPE html PUBLIC "-/…nal//EN">,碰到’”’,进入

                                                             AfterDOCTYPEPublicIdentifierState 状态。（HTMLToken的m_publicIdentifier确定）

AfterDOCTYPEPublicIdentifierState：<!DOCTYPE html PUBLIC "-/…nal//EN"> ，碰到’>’,进入DataState状态，完成文档类型

                                                           的解析

2）COMMENT

DataState：，碰到’<’，进入TagOpenState

TagOpenState：, 碰到’!’，进入MarkupDeclarationOpenState状态

MarkupDeclarationOpenState：,碰到’-’，匹配DOCTYPE和--字数都不够，保持现状

MarkupDeclarationOpenState：,匹配--，进入CommentStartState状态(HTMLToken的type为COMMENT)

CommentStartState: ,碰到’c’，进入CommentState

CommentState：，碰到’-‘，进入CommentEndDashState状态(HTMLToken的m_data为comment)

CommentEndDashState: ,碰到’-‘，进入CommentEndState状态

CommentEndState：,碰到’>‘，进入DataState状态，完成解析。

3）起始标签a

DataState：<a href=”w3c.org”>，碰到’<’,进入TagOpenState状态

TagOpenState：<a href=”w3c.org”>，碰到’a’,进入TagNameState状态（HTMLToken的type为StartTag）

TagNameState：<a href=”w3c.org”>，碰到空格，进入BeforeAttributeNameState状态（HTMLToken的m_data为a）

BeforeAttributeNameState：<a href=”w3c.org”>，碰到‘h’,进入AttributeNameState状态

AttributeNameState：<a href=”w3c.org”>，碰到‘=’，进入BeforeAttributeValueState状态（HTMLToken

                                                      属性列表中加入一个属性，属性名为href)

BeforeAttributeValueState: <a href=”w3c.org”>，碰到‘“’，进入AttributeValueDoubleQuotedState状态

AttributeValueDoubleQuotedState：<a href=”w3c.org”>，碰到‘w’，保持状态，提取属性值

AttributeValueDoubleQuotedState：<a href=”w3c.org”>，碰到‘“’，进入AfterAttributeValueQuotedState

                                                              (HTMLToken当前属性的值为w3c.org).

AfterAttributeValueQuotedState: <a href=”w3c.org”>，碰到‘>’，进入DataState，完成解析。

在完成startTag的解析的时候，会在解析器中存储与之匹配的end标签（m_appropriateEndTagName），等到解析end标签的时候，会同它进行匹配（语法解析的时候）。

html，body起始标签类似a起始标签，但没有属性解析

4)a元素

DataState：w3c</a>，碰到’w’,维持原状态，提取元素内容(HTMLToken的type为character)。

DataState：w3c</a>，碰到’<’,完成解析，不consume ’<’。(HTMLToken的m_data为w3c)。

5）a结束标签

DataState：w3c</a>，碰到’<’,进入TagOpenState。

TagOpenState：w3c</a>，碰到’/’,进入到EndTagOpenState。（HTMLToken的type为endTag）。

EndTagOpenState：w3c</a>，碰到’a’,进入到TagNameState。

TagNameState：w3c</a>，碰到’>’,进入到DataState，完成解析。

通过以上的复盘，一个标记的token过程清晰呈现在眼前，基本上就是实现http://www.w3.org/TR/html5/tokenization.html这一章的一个过程，html的规范是相当宽松的，所以词法解析要考虑到的问题很多，html5 specfication在这方面为实现者做了绝大部分工作。

另外，html的语法解析会影响词法解析，比如语法解析在解析到head里面title的起始标签后，会将htmltokenizer解析器的状态设置为RCDATAState。

分享到：