使用Python语言编写简单的HTML5语法解析器

1     问题

如何编写一个语法解析器(Parser)呢?在C/C++语言领域,我们有lex & yacc(文法解析器和语法解析器的生成器)及其GNU移植版本flex & bison,yacc是根据大牛Knuth的LALR文法设计的,自底向上进行解析;在Java语言领域,我们有ANTLR,这是是一个基于LL(n)文法的解析器生成器(递归下降,向前看n个Token消解冲突)。通过这些工具,我们只要写出要解析语言的文法、语法定义,就可以让它们帮我们生成对应的解析器,这通常称为编译器的前端(后端指的是代码生成和指令优化),此外,还有称为‘解析器组合子’的半自动工具可用于前端语法分析。

抛开这些工具和第三方库,现在的问题是:给你一个HTML5文件,如何仅使用编程语言本身的库,编写一个语法解析器程序呢?

首先,一个语法解析器需要文法扫描器(Lexer)提供Token序列的输入。而文法扫描器的每个Token通常使用正则表达式来定义,对这里的任务,我们可不想自己实现一套正则表达式引擎(重复造轮子),反之,将依赖本身就提供了正则表达式的编程语言来完成Lexer的编写。

那么,哪些编程语言内置正则表达式引擎呢?C没有,C++ 11之前也没有(可以使用Boost),C++ 11有,Java、C#、Python、Ruby、PHP、Perl则都提供了支持。这里我选择Python,原因无它,相比其他脚本语言,我个人更熟悉Python。而编译型语言处理字符串则不如脚本语言灵活。虽然无类型的Python不像C++/C#/Java那样,有一个好的IDE及调试环境,但记住一点:开发原型优先选择灵活的脚本语言,待技术实现可靠性得到验证后,可以再移植到编译型语言以进一步提高性能。这里值得一说的是,上述语言均支持OOP。我想强调的是,好的OO设计风范(主要涉及类层次结构的定义和核心流程的参数传递)对于编写可读性佳、可维护性高的代码无疑是十分重要的。

2     程序设计思路

2.1 简化版HTML5语法定义

首先,给出一段要解析的HTML文件内容如下:

根据上面的简单用例,我们的程序设计目标限定如下:它能够处理文档类型声明(DocType)、元素(Element)、元素属性(Attr)、Html注释(Comment)和普通文本(Text),暂不支持内嵌JavaScript 的<script>元素和内嵌CSS的<style>元素。也暂不考虑Unicode的解析,假设输入文件是纯英文ASCII编码的。

在此约束条件下,首先来定义此简化版的HTML5语法定义:

注意,这里没有写出严格的定义。在编写demo程序的过程中,重要的是保持思路清晰,但不需要把细节问题一步详细到位,只要保证细枝末节的问题可以随时扩展修正即可。

2.2简化版DOM数据结构定义

我曾经做过Java XML/DOM解析,也维护过浏览器内核DOM模块的代码,但对于我们的demo开发而言,没必要写一个完善的DOM类层次结构定义。尽管如此,保持简明扼要还是很重要的。 DOM数据结构的Python代码如下:(Python没有枚举类型,直接使用字符串代替)

这里Node是所有DOM树节点的基类,DocType、Comment、Element、Attr、Text、Document都是Node的子类。

2.3 TDD:main程序入口

前面说到,我们使用的是Python语言,让我们追随直觉,快速写下main程序的启动代码吧:

从上面的代码可以看到,我们需要实现2个类:Lexer和Parser,一个核心方法parse,解析的结果以Document对象返回。

2.4 Lexer设计与实现

编译原理里提到的文法解析通常基于正则文法(有限自动机理论),然而,实际世界中使用的正则表达式引擎则支持更高级的特性,如字符类、命名捕获、分组捕获、后向引用等。我们这里不关心如何实现一个基于正则文法的有限自动机,而只是使用正则表达式引擎实现Lexer。 由于Lexer的输入为字符流,输出为Token序列,那么将此接口命名为nextToken。 首先,它应该带一个模式(pattern)字符串参数,代表我们期望从字符流中扫描的模式,同时,Lexer对象维护一个状态pos,代表当前扫描的起始位置。 其次,我们给nextToken加上额外的2个参数(注意:这里的API设计仅仅从权考虑,在正式的产品开发中,可能需要根据实际的需求做出改动):

  1. skipLeadingWS  代表在扫描调用者提供的下一个模式之前,是否先忽略前导空白字符串
  2. groupExtract      有的时候,扫描模式有匹配之后,我们只想提取其中的部分返回,这里根据正则表达式引擎的一般后向引用定义,0代表整个模式,而1代表第1个左圆括号对应的部分。

OK,Lexer的设计部分大抵差不多了,可以开始写代码了:

2.4.1验证你不了解的API!

请再看一下上面的函数Lexer.nextToken的API设计与实现。这里的核心要点就是用到了Python 正则表达式库的API PatternObject.match方法。 这里的要点是:对于你不了解的API(所谓的不了解,就是以前你没怎么用过),一定要仔细阅读该API的帮助手册,最好是编写简单的单元测试case来验证它是否能够满足你的需求。 事实上,我一开始使用的是PatternObject.search,而不是match方法,但是我发现了问题:

Python帮助手册里对此API行为居然做出了明确规定,但我不明白API这样设计有何合理性——相当地违背直觉嘛。 山穷水尽疑无路,柳暗花明又一村。当感觉有点绝望的时候(实际上也没那么夸张,可以用一个方法绕过这个缺陷并仍然使用search API来完成工作,就是会有性能缺陷),再看看match方法:… 嗯?这不就是我想要的API嘛:

糟糕的是,match API也有一个问题:m.endpos理所当然的应当返回匹配模式在源字符串中的结束位置,但它实际上返回的却是整个源字符串的结束位置(也就是它的长度),还好,这个问题可以用len(m.group(0))巧妙地绕过且不影响性能。 结论:API使用内藏陷阱,请谨慎使用,使用之前先做好单元测试功能验证。

2.5 Parser设计与实现

让我们先写出parse入口函数:

从这个顶层的parse()来看,一个HTML文档由一个开始的DocType节点和一个根<html>元素组成。parse()内部调用了2个方法:_ parseDocType和_ parseElement。注意,后2个函数名前面加了下划线,代表私有函数,不提供外部使用(脚本语言通常没有C++的名字可见性概念,通常使用命名规范来达到同样的目的)。 ParseFinishException的用法请参考2.7节说明。

2.6 验证Lexer.nextToken:实现_parseDocType()

DocType节点的语法声明参考2.1,下面是_parseDocType()的实现:

_parseDocType的代码完美演示了Lexer.nextToken API的用法,其形参ctx代表当前的上下文节点,比如说,解析DocType时,其ctx就是根Document对象。 这里_parseDocType使用的扫描模式可以提取出像“<!DOCTYPE html>”中的“html”。不过,也许这里可以放松条件以匹配HTML4的语法。

2.7 实现_parseComment()时的代码健壮性考虑

前面实现_parseDocType()时只使用了1次nextToken扫描,这里实现_parseComment()将考虑使得代码更健壮一点。怎么讲呢?HTML注释节点以“<!–”开始,以“–>”结束,中间是任意的字符(不包含连续的–>)。

如果我们的扫描模式写成:

p=re.compile(r”<!–(.*)–>”)

则由于正则表达式的默认贪心模式匹配,它将匹配字符串“<!—abc–>123–>”中的“abc–>123”,为此,可改用非贪心模式匹配:

p=re.compile(r”<!–(.*?)–>”)

这样就行了吗?还不行。当html字符串中只有开始的<!–,没有结束的–>时,将视为一直到文档结束都是注释。为实现这个规约,需要补充进行一次扫描:

如果p=re.compile(r”<!–(.*?)–>”)扫描失败,就用p=re.compile(r”<!–(.*?)$“)重新扫描一次。

2.8难点:递归的_parseElement()

元素节点的解析存在许多难点,比如说,需要在这里解析元素属性、需要递归地解析可能的子节点。让我们尝试着写写看吧:

 

这里的容错处理逻辑是:至少当匹配了’<’及有效的tagName后,才认为找到了一个元素节点,这时可以创建一个element对象,但这时我们还不知道接下来的解析是否会成功,所以暂时不addChild到ctx父节点上。

接下来是属性解析:

如果属性解析失败,则_ parseElement也随之失败,否则将element添加到ctx上:

_parseAttrs函数的一个副作用是设置元素是否直接以‘/>’结束,如果是这样,则该元素没有进一步的子节点;否则需要进一步递归处理子节点的解析。

由于子节点的数目定义在语法规则中是*(0个或多个),则我们需要向前看,即查找形如</xxx>这样的结束标签。如果匹配到endTagName,并且等于当前元素的tagName,则递归解析可以结束;

否则的话,需要向上抛出一个定制的异常,请考虑下面的case:

_parseElement在解析img元素时遇到了</div>结束标签,然后这个结束标签与它自己并不匹配,于是,它需要通知上上层的处于解析<div>位置的_parseElement:

注意,抛出FindElementEndTagException异常的是_parseElement,接受此异常的同样是_parseElement,只不过两者处于Call Stack的不同位置而已。

 

由于FindElementEndTagException异常由Call Stack的最底层向上抛出,tagName与endTagName第一个匹配的_parseElement将捕获到它。

此外,_parseElement 递归调用_parseNode的时候,我们要一对变量(pos_before和pos_after)记住Lexer的前后状态,如果Lexer状态没有发生变化(pos_before==pos_after),说明_parseNode失败。

这对应什么情况呢?因为Node对象包含3种:Comment、Element、Text,不匹配其中任意一种的话,_parseNode就会失败,比如说,一个单独的‘<’。

目前demo程序以抛出解析异常的方法结束,至于怎么容错处理(忽略,或仍然当作Text节点处理),留待读者自行考虑。

如此,最难的_parseElement()函数就结束了。

3     测试

HTML解析之后是一个DOM树,其根节点为Document对象,怎么验证解析得对不对呢?

把这个DOM树重新序列化为html字符串,与原始输入进行比较即可。考虑到HTML5的容错处理,序列化后的结果不能保证与源输入结构上一致。

DOM树的序列化代码从略,它其实就是一个针对子节点的递归调用,这里代码从略(完整脚本代码请参考附件)。

OK,现在HTML5语法解析器基本上已经编写完成了。

4     结语

对于递归下降的语法解析器而言,重要的就是要做好“向前看”的工作,自上而下的递归解析相比自底向上的解析,实际性能并没有什么大的损失,但其代码结构的可理解程度就要高不少了。

感谢你的耐心阅读,欢迎来信交流心得体会。

1 1 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部