WebKit中的html词法解析（dlmu2001）
WebKit中的html词法解析（dlmu2001）
摘要：webkit源代码分析，webcore，html解析，htmlparse，htmltoken,htmltokenizer，dlmu2001,浏览器,chrome
语言的解析一般分为词法分析（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类的成员变量，从中我们可以看到一个标记的组成：类型，在字节流中的偏移，数据（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"> <!--comment --> <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：<!--comment -->，碰到’<’，进入TagOpenState
TagOpenState：<!--comment -->, 碰到’!’，进入MarkupDeclarationOpenState状态
MarkupDeclarationOpenState：<!--comment -->,碰到’-’，匹配DOCTYPE和--字数都不够，保持现状
MarkupDeclarationOpenState：<!--comment -->,匹配--，进入CommentStartState状态(HTMLToken的type为COMMENT)
CommentStartState: <!--comment -->,碰到’c’，进入CommentState
CommentState：<!--comment -->，碰到’-‘，进入CommentEndDashState状态(HTMLToken的m_data为comment)
CommentEndDashState: <!--comment -->,碰到’-‘，进入CommentEndState状态
CommentEndState：<!--comment -->,碰到’>‘，进入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。