Jsoup代码解读之四-parser(上)

作为Java世界最好的HTML 解析库,Jsoup的parser实现非常具有代表性。这部分也是Jsoup最复杂的部分,需要一些数据结构、状态机乃至编译器的知识。好在HTML语法不复杂,解析只是到DOM树为止,所以作为编译器入门倒是挺合适的。这一块不要指望囫囵吞枣,我们还是泡一杯咖啡,细细品味其中的奥妙吧。

基础知识

编译器

将计算机语言转化为另一种计算机语言(通常是更底层的语言,例如机器码、汇编、或者JVM字节码)的过程就叫做编译(compile)。编译器(Compiler)是计算机科学的一个重要领域,已经有很多年历史了,而最近各种通用语言层出不穷,加上跨语言编译的兴起、DSL概念的流行,都让编译器变成了一个很时髦的东西。

编译器领域相关有三本公认的经典书籍,龙书《Compilers: Principles, Techniques, and Tools 》,虎书《Modern Compiler Implementation in X (X表示各种语言)》,鲸书《Advanced Compiler Design and Implementation》。其中龙书是编译理论方面公认的不二之选,而后面两本则对实践更有指导意义。另外@装配脑袋有个很好的编译器入门系列博客:http://www.cnblogs.com/Ninputer/archive/2011/06/07/2074632.html

编译器的基本流程如下:

其中词法分析、语法分析、语义分析这部分又叫编译器的前端(front-end),而此后的中间代码生成直到目标生成、优化等属于编译器的后端(back-end)。编译器的前端技术已经很成熟了,也有yacc这样的工具来自动进行词法、语法分析(Java里也有一个类似的工具ANTLR),而后端技术更加复杂,也是目前编译器研究的重点。

说了这么多,回到咱们的HTML上来。HTML是一种声明式的语言,可以理解它的最终的输出是浏览器里图形化的页面,而并非可执行的目标语言,因此我将这里的Translate改为了Render。

在Jsoup(包括类似的HTML parser)里,只做了Lex(词法分析)、Parse(语法分析)两步,而HTML parse最终产出结果,就是DOM树。至于HTML的语义解析以及渲染,不妨看看携程UED团队的这篇文章:《浏览器是怎样工作的:渲染引擎,HTML解析》。

状态机

Jsoup的词法分析和语法分析都用到了状态机。状态机可以理解为一个特殊的程序模型,例如经常跟我们打交道的正则表达式就是用状态机实现的。

它由状态(state)和转移(transition)两部分构成。根据状态转移的可能性,状态机又分为DFA(确定有限状态机)和NFA(非确定有限状态自动机)。这里拿一个最简单的正则表达式”a[b]*“作为例子,我们先把它映射到一个状态机DFA,大概是这样子:

状态机本身是一个编程模型,这里我们尝试用程序去实现它,那么最直接的方式大概是这样:

这样写简单的状态机倒没有问题,但是复杂情况下就有点难受了。还有一种标准的状态机解法,先建立状态转移表,然后使用这个表建立状态机。这个方法的问题就是,只能做纯状态转移,无法在代码级别操作输入输出。

Jsoup里则使用了状态模式来实现状态机,初次看到时,确实让人眼前一亮。状态模式是设计模式的一种,它将状态和对应的行为绑定在一起。而在状态机的实现过程中,使用它来实现状态转移时的处理再合适不过了。

“a[b]*“的例子的状态模式实现如下,这里采用了与Jsoup相同的方式,用到了枚举来实现状态模式:

PS:我在github上fork了一份Jsoup的代码,把这系列文章提交了上去,并且给一些代码增加了中文注释,有兴趣的可以看看https://github.com/code4craft/jsoup-learning。本文中提到的几种状态机的完整实现在这个仓库的https://github.com/code4craft/jsoup-learning/tree/master/src/main/java/us/codecraft/learning路径下。

原文发布于微信公众号 - java一日一条(mjx_java)

原文发表时间:2016-02-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏hrscy

Unity 脚本入门

在 Unity 中脚本是必不可少的组成部分,因为它将定义游戏的各种行为。Unity 推荐使用的编程语言是 JavaScript,但是 C# 或 Boo 同样也可...

2202
来自专栏极乐技术社区

微信小游戏初体验

前言 上周【跳一跳】小游戏刷遍了朋友圈,也代表了微信小程序拥有了搭载游戏的功能(早该往这方面发展了,这才是应该有的形态嘛)。作为一个前端er,我的大刀早已经饥渴...

1.3K7
来自专栏JAVA高级架构

两年Java程序员面试经

工作两年有余,本人第一份工作是在一家外包公司,第二份工作是在一家做SAAS平台的公司,第一家公司让我入门,进入了软件开发的行业,了解了一些基础的东西;第二家公司...

3432
来自专栏葡萄城控件技术团队

ActiveReports 报表中 RDF 文件解析

AcitveReport 提供两种报表模板,XML(RPX)模板和Code-Based 模板。两者都可以用于设计报表。 但是 RDF 格式文件我们大多不是很了...

2209
来自专栏蓝天

代码规范:换行对齐问题

对一于单行代码过长时,采取换行,这个没有什么可争议的,主要焦点在新的一行从哪开始,通常有两派,一派就是如上述两段代码所示,另一派则采用如下规范:

782
来自专栏Java学习网

书写高质量代码之状态维护

状态之始 我们第一眼接触新事物所触发的思考方式,决定了以后我们看待这样事物的角度,进而影响更深层次的理解和行为。 编程相对于人类历史的进程而言,不过是个六七岁孩...

3655
来自专栏斑斓

我们的技术实践

本文是我在中生代技术群分享的话题《创业一年经历的技术风雨》中的第三部分《研发团队总结的技术实践》。若要阅读第二部分《技术团队的管理》,请移步中生代技术群公众号。...

3305
来自专栏编舟记

Clojure集合管道函数练习

TDD讨论组里的申导最近在B站直播了Martin Fowler的经典文章Refactoring with Loops and Collection Pipeli...

1362
来自专栏take time, save time

python 爬虫 入门 commit by commit -- commit3

代码你可以在https://github.com/rogerzhu/relwarcDJ 上得到,并且带有我完整的commit记录。

1382
来自专栏编程

使用JavaScript开发一个自修改代码

话说在25年前,我刚刚开始从事软件开发。在工作中,我遇到一个叫Dave的朋友,他曾在一家大型保险公司工作过几年,他的工作重点是开发支持一个名为“个人人寿保险”的...

2837

扫码关注云+社区

领取腾讯云代金券