基本的HTML文本解析器的设计和实现（C/C++源码），图文并茂

海岸的声音

作者：庄晓立 (liigo)   日期：2011-1-19      关键字：HTML，解析器(Parser)，节点(Node)，标签(Tag)原创链接：http://blog.csdn.net/liigo/archive/2011/01/19/6153829.aspx

这是进入2011年以来，本人(liigo)“重复发明轮子”系列博文中的最新一篇。本文主要探讨如何设计和实现一个基本的HTML文本解析器。
众所周知，HTML是结构化文档(Structured Document)，由诸多标签（<p>等）嵌套形成的著名的文档对象模型（DOM, Document Object Model），是显而易见的树形多层次结构。如果带着这种思路看待HTML、编写HTML解析器，无疑将导致问题复杂化。不妨从另一视角俯视HTML文本，视其为一维线状结构：诸多单一节点的顺序排列。仔细审视任何一段HTML文本，以左右尖括号（<和>）为边界，会发现HTML文本被天然地分割为：一个标签（Tag），接一段普通文字，再一个标签，再一段普通文字…… 如下图所示：

标签有两种，开始标签（如<p>）和结束标签（</p>），它们和普通文字一起，顺序排列，共同构成了HTML文本的全部。
为了再次简化编程模型，我(liigo)继续将“开始标签”“结束标签”“普通文字”三者统一抽象归纳为“节点”（HtmlNode），相应的，“节点”有三种类型，要么是开始标签，要么是结束标签，要么是普通文字。现在，HTML在我们眼里更加单纯了，它就是“节点”的线性顺序组合，是一维的“节点”数组。如下图所示：HTML文本 = 节点1 + 节点2 + 节点3 + ……

海岸的声音

在正式编码之前，先确定好“节点”的数据结构。作为“普通文字”节点，需要记录一个文本(text)；作为“标签”节点，需要记录标签名称(tagName)、标签类型(tagType)、所有属性值(props)；另外还要有个类型(type)以便区分该节点是普通文字、开始标签还是结束标签。这其中固然有些冗余信息，比如对标签来说不需要记录文本，对普通文字来说又不需要记录标签名称、属性值等，不过无伤大雅，简洁的编程模型是最大的诱惑。用C/C++语言语法表示如下：

1. 
   
2. view plaincopy to clipboardprint?
   
3. enum HtmlNodeType   
   
4. {   
   
5.     NODE_UNKNOWN = 0,   
   
6.     NODE_START_TAG,   
   
7.     NODE_CLOSE_TAG,   
   
8.     NODE_CONTENT,   
   
9. };   
   
10. enum HtmlTagType   
    
11. {   
    
12.     TAG_UNKNOWN = 0,   
    
13.     TAG_A, TAG_DIV, TAG_FONT, TAG_IMG, TAG_P, TAG_SPAN, TAG_BR, TAG_B, TAG_I, TAG_HR,   
    
14. };   
    
15. struct HtmlNodeProp   
    
16. {   
    
17.     WCHAR* szName;   
    
18.     WCHAR* szValue;   
    
19. };   
    
20. #define MAX_HTML_TAG_LENGTH (15)   
    
21. struct HtmlNode   
    
22. {   
    
23.     HtmlNodeType type;   
    
24.     HtmlTagType  tagType;   
    
25.     WCHAR tagName[MAX_HTML_TAG_LENGTH+1];   
    
26.     WCHAR* text;   
    
27.     int propCount;   
    
28.     HtmlNodeProp* props;   
    
29. };  
    

复制代码

海岸的声音

具体到编写程序代码，要比想象中容易的多。编码的核心要点是，以左右尖括号（<和>）为边界自然分割标签和普通文字。左右尖括号之间的当然是标签节点（开始标签或结束标签），左尖括号(<)之前（直到前一个右尖括号或开头）、右尖括号(>)之后（直到后一个左尖括号或结尾）的显然是普通文字节点。区分开始标签或结束标签的关键点是，看左尖括号(<)后面第一个非空白字符是否为'/'。对于开始标签，在标签名称后面，间隔至少一个空白字符，可能会有形式为“key1=value1 key2=value2 key3”的属性表，关于属性表，后文有专门的函数负责解析。此外有一点要注意，属性值一般有引号括住，引号内出现的左右尖括号应该不被视为边界分隔符。
下面就是负责把HTML文本解析为一个个节点（HtmlNode）的核心代码（不足百行，够精简吧）：

1. view plaincopy to clipboardprint?
   
2. void HtmlParser::ParseHtml(const WCHAR* szHtml)
   
3. {
   
4. m_html = szHtml ? szHtml : L"";
   
5. freeHtmlNodes();
   
6. if(szHtml == NULL || *szHtml == L'\0') return;
   
7. WCHAR* p = (WCHAR*) szHtml;
   
8. WCHAR* s = (WCHAR*) szHtml;
   
9. HtmlNode* pNode = NULL;
   
10. WCHAR c;
    
11. bool bInQuotes = false;
    
12. while( c = *p )
    
13. {
    
14. if(c == L'"')
    
15. {
    
16. bInQuotes = !bInQuotes;
    
17. p++; continue;
    
18. }
    
19. if(bInQuotes)
    
20. {
    
21. p++; continue;
    
22. }
    
23. if(c == L'<')
    
24. {
    
25. if(p > s)
    
26. {
    
27. //Add Text Node
    
28. pNode = NewHtmlNode();
    
29. pNode->type = NODE_CONTENT;
    
30. pNode->text = duplicateStrUtill(s, L'<', true);
    
31. }
    
32. s = p + 1;
    
33. }
    
34. else if(c == L'>')
    
35. {
    
36. if(p > s)
    
37. {
    
38. //Add HtmlTag Node
    
39. pNode = NewHtmlNode();
    
40. while(isspace(*s)) s++;
    
41. pNode->type = (*s != L'/' ? NODE_START_TAG : NODE_CLOSE_TAG);
    
42. if(*s == L'/') s++;
    
43. copyStrUtill(pNode->tagName, MAX_HTML_TAG_LENGTH, s, L'>', true);
    
44. //处理自封闭的结点, 如 <br/>, 删除tagName中可能会有的'/'字符
    
45. //自封闭的结点的type设置为NODE_START_TAG应该可以接受(否则要引入新的NODE_STARTCLOSE_TAG)
    
46. int tagNamelen = wcslen(pNode->tagName);
    
47. if(pNode->tagName[tagNamelen-1] == L'/')
    
48. pNode->tagName[tagNamelen-1] = L'\0';
    
49. //处理结点属性
    
50. for(int i = 0; i < tagNamelen; i++)
    
51. {
    
52. if(pNode->tagName[i] == L' ' //第一个空格后面跟的是属性列表
    
53. || pNode->tagName[i] == L'=') //扩展支持这种格式: <tagName=value>, 等效于<tagName tagName=value>
    
54. {
    
55. WCHAR* props = (pNode->tagName[i] == L' ' ? s + i + 1 : s);
    
56. pNode->text = duplicateStrUtill(props, L'>', true);
    
57. int nodeTextLen = wcslen(pNode->text);
    
58. if(pNode->text[nodeTextLen-1] == L'/') //去掉最后可能会有的'/'字符, 如这种情况: <img src="..." mce_src="..." />
    
59. pNode->text[nodeTextLen-1] = L'\0';
    
60. pNode->tagName[i] = L'\0';
    
61. parseNodeProps(pNode); //parse props
    
62. break;
    
63. }
    
64. }
    
65. pNode->tagType = getHtmlTagTypeFromName(pNode->tagName);
    
66. }
    
67. s = p + 1;
    
68. }
    
69. p++;
    
70. }
    
71. if(p > s)
    
72. {
    
73. //Add Text Node
    
74. pNode = NewHtmlNode();
    
75. pNode->type = NODE_CONTENT;
    
76. pNode->text = duplicateStr(s, -1);
    
77. }
    
78. #ifdef _DEBUG
    
79. dumpHtmlNodes(); //just for test
    
80. #endif
    
81. }
    

复制代码

海岸的声音

下面是负责解析“开始标签”属性表文本（形如“key1=value1 key2=value2 key3”）的代码，parseNodeProps()，核心思路是按空格和等号字符进行分割属性名和属性值，由于想兼容HTML4.01及以前的不标准的属性表写法（如没有=号也没有属性值），颇费周折：

1. 
   
2. view plaincopy to clipboardprint?
   
3. //[virtual]   
   
4. void HtmlParser::parseNodeProps(HtmlNode* pNode)   
   
5. {   
   
6.     if(pNode == NULL || pNode->propCount > 0 || pNode->text == NULL)   
   
7.         return;   
   
8.     WCHAR* p = pNode->text;   
   
9.     WCHAR *ps = NULL;   
   
10.     CMem mem;   
    
11.     bool inQuote1 = false, inQuote2 = false;   
    
12.     WCHAR c;   
    
13.     while(c = *p)   
    
14.     {   
    
15.         if(c == L'"')   
    
16.         {   
    
17.             inQuote1 = !inQuote1;   
    
18.         }   
    
19.         else if(c == L'\'')   
    
20.         {   
    
21.             inQuote2 = !inQuote2;   
    
22.         }   
    
23.         if((!inQuote1 && !inQuote2) && (c == L' ' || c == L'\t' || c == L'='))   
    
24.         {   
    
25.             if(ps)   
    
26.             {   
    
27.                 mem.AddPointer(duplicateStrAndUnquote(ps, p - ps));   
    
28.                 ps = NULL;   
    
29.             }   
    
30.             if(c == L'=')   
    
31.                 mem.AddPointer(NULL);   
    
32.         }   
    
33.         else  
    
34.         {   
    
35.             if(ps == NULL)   
    
36.                 ps = p;   
    
37.         }   
    
38.         p++;   
    
39.     }   
    
40.     if(ps)   
    
41.         mem.AddPointer(duplicateStrAndUnquote(ps, p - ps));   
    
42.     mem.AddPointer(NULL);   
    
43.     mem.AddPointer(NULL);   
    
44.     WCHAR** pp = (WCHAR**) mem.GetPtr();   
    
45.     CMem props;   
    
46.     for(int i = 0, n = mem.GetSize() / sizeof(WCHAR*) - 2; i < n; i++)   
    
47.     {   
    
48.         props.AddPointer(pp[i]); //prop name   
    
49.         if(pp[i+1] == NULL)   
    
50.         {   
    
51.             props.AddPointer(pp[i+2]); //prop value   
    
52.             i += 2;   
    
53.         }   
    
54.         else  
    
55.             props.AddPointer(NULL); //prop vlalue   
    
56.     }   
    
57.     pNode->propCount = props.GetSize() / sizeof(WCHAR*) / 2;   
    
58.     pNode->props = (HtmlNodeProp*) props.Detach();   
    
59. }  
    

复制代码

海岸的声音

根据标签名称取标签类型的getHtmlTagTypeFromName()方法，就非常直白了，查表，逐一识别：

1. 
   
2. view plaincopy to clipboardprint?
   
3. //[virtual]   
   
4. HtmlTagType HtmlParser::getHtmlTagTypeFromName(const WCHAR* szTagName)   
   
5. {   
   
6.     //todo: uses hashmap   
   
7.     struct N2T { const WCHAR* name; HtmlTagType type; };   
   
8.     static N2T n2tTable[] =   
   
9.     {   
   
10.         { L"A", TAG_A },   
    
11.         { L"FONT", TAG_FONT },   
    
12.         { L"IMG", TAG_IMG },   
    
13.         { L"P", TAG_P },   
    
14.         { L"DIV", TAG_DIV },   
    
15.         { L"SPAN", TAG_SPAN },   
    
16.         { L"BR", TAG_BR },   
    
17.         { L"B", TAG_B },   
    
18.         { L"I", TAG_I },   
    
19.         { L"HR", TAG_HR },   
    
20.     };   
    
21.     for(int i = 0, count = sizeof(n2tTable)/sizeof(n2tTable[0]); i < count; i++)   
    
22.     {   
    
23.         N2T* p = &n2tTable[i];   
    
24.         if(wcsicmp(p->name, szTagName) == 0)   
    
25.             return p->type;   
    
26.     }   
    
27.     return TAG_UNKNOWN;   
    
28. }  
    

复制代码

请注意，上文负责解析属性表的parseNodeProps()函数，和负责识别标签名称的getHtmlTagTypeFromName()函数，都是虚函数（virtual method）。我(liigo)这么设计是有深意的，给使用者留下了很大的定制空间，可以自由发挥。例如，通过在子类中覆盖/覆写（override）parseNodeProps()方法，可以采用更好的解析算法，或者干脆不做任何处理以提高HTML解析效率——将来某一时间可以调用基类同名函数专门解析特定标签的属性表；例如，通过在子类中覆盖/覆写（override）getHtmlTagTypeFromName()方法，使用者可以选择识别跟多的标签名称（包括自定义标签），或者识别更少的标签名称，甚至不识别任何标签名称（以便提高解析效率）。以编写网络爬虫程序为实例，它多数情况下通常只需识别<A>标签及其属性就足够了，没必要浪费CPU运算去识别其它标签、解析其他标签属性。
至于HTML文本解析器的用途，我目前想到的有：用于HTML格式检查或规范化，用于重新排版HTML文本，用于编写网络爬虫程序/搜索引擎，用于基于HTML模板的动态网页生成，用于HTML网页渲染前的基础解析，等等。
下面附上完整源码，仅供参考，欢迎指正。
HtmlParser.h：

1. + expand sourceview plaincopy to clipboardprint?
   

复制代码

HtmlParser.cpp：

1. + expand sourceview plaincopy to clipboardprint?
   

复制代码

补记：本文所提供的源代码，目前有未完善之处，如没有考虑到内嵌JavaScrip代码和HTML注释中的特殊字符（特别是尖括号）对解析器的影响，另外还可能有其他疏漏和bug，故代码仅可用于学习参考研究使用。我今后也将继续改进此HTML语法解析器。特此声明。