都知道浏览器和服务端是通过 http 协议进行数据传输的，而 http 协议又是纯文本协议，那么浏览器在得到服务端传输过来的 html 字符串，是如何解析成真实的 dom 元素的呢，也就是我们常说的生成 dom tree，最近了解到状态机这样一个概念，于是就萌生一个想法，实现一个 innerhtml 功能的函数，也算是小小的实践一下。
函数原型
我们实现一个如下的函数，参数是 dom 元素和 html 字符串，将 html 字符串转换成真实的 dom 元素且 append 在参数一传入的 dom 元素中。
function html(element, htmlstring) {
// 1. 词法分析
// 2. 语法分析
// 3. 解释执行
}
在上面的注释我已经注明，这个步骤我们分成三个部分，分别是词法分析、语法分析和解释执行。
词法分析
词法分析是特别重要且核心的一部分，具体任务就是：把字符流变成 token 流。
词法分析通常有两种方案，一种是状态机，一种是正则表达式，它们是等效的，选择你喜欢的就好。我们这里选择状态机。
首先我们需要确定 token 种类，我们这里不考虑太复杂的情况，因为我们只对原理进行学习，不可能像浏览器那样有强大的容错能力。除了不考虑容错之外，对于自闭合节点、注释、cdata 节点暂时均不做考虑。
接下来步入主题，假设我们有如下节点信息，我们会分出哪些 token 来呢。
<p class="a" data="js">测试元素</p>
对于上述节点信息，我们可以拆分出如下 token
- 开始标签：<p
- 属性标签：class="a"
- 文本节点：测试元素
- 结束标签：</p>
状态机的原理，将整个 html 字符串进行遍历，每次读取一个字符，都要进行一次决策（下一个字符处于哪个状态），而且这个决策是和当前状态有关的，这样一来，读取的过程就会得到一个又一个完整的 token，记录到我们最终需要的 tokens 中。
万事开头难，我们首先要确定起初可能处于哪种状态，也就是确定一个 start 函数，在这之前，对词法分析类进行简单的封装，具体如下
function htmllexicalparser(htmlstring, tokenhandler) {
this.token = [];
this.tokens = [];
this.htmlstring = htmlstring
this.tokenhandler = tokenhandler
}
简单解释下上面的每个属性
- token：token 的每个字符
- tokens：存储一个个已经得到的 token
- htmlstring：待处理字符串
- tokenhandler：token 处理函数，我们每得到一个 token 时，就已经可以进行流式解析
我们可以很容易的知道，字符串要么以普通文本开头，要么以 < 开头，因此 start 代码如下
htmllexicalparser.prototype.start = function(c) {
if(c === '<') {
this.token.push(c)
return this.tagstate
} else {
return this.textstate(c)
}
}
start 处理的比较简单，如果是 < 字符，表示开始标签或结束标签，因此我们需要下一个字符信息才能确定到底是哪一类 token，所以返回 tagstate 函数去进行再判断，否则我们就认为是文本节点，返回文本状态函数。
接下来分别展开 tagstate 和 textstate 函数。 tagstate 根据下一个字符，判断进入开始标签状态还是结束标签状态，如果是 / 表示是结束标签，否则是开始标签， textstate 用来处理每一个文本节点字符，遇到 < 表示得到一个完整的文本节点 token，代码如下
htmllexicalparser.prototype.tagstate = function(c) {
this.token.push(c)
if(c === '/') {
return this.endtagstate
} else {
return this.starttagstate
}
}
htmllexicalparser.prototype.textstate = function(c) {
if(c === '<') {
this.emittoken('text', this.token.join(''))
this.token = []
return this.start(c)
} else {
this.token.push(c)
return this.textstate
}
}
这里初次见面的函数是 emittoken 、 starttagstate 和 endtagstate 。
emittoken 用来将产生的完整 token 存储在 tokens 中，参数是 token 类型和值。
starttagstate 用来处理开始标签，这里有三种情形
- 如果接下来的字符是字母，则认定依旧处于开始标签态
- 遇到空格，则认定开始标签态结束，接下来是处理属性了
- 遇到>，同样认定为开始标签态结束，但接下来是处理新的节点信息
- endtagstate用来处理结束标签，结束标签不存在属性，因此只有两种情形
- 如果接下来的字符是字母，则认定依旧处于结束标签态
- 遇到>，同样认定为结束标签态结束，但接下来是处理新的节点信息
逻辑上面说的比较清楚了，代码也比较简单，看看就好啦
htmllexicalparser.prototype.emittoken = function(type, value) {
var res = {
type,
value
}
this.tokens.push(res)
// 流式处理
this.tokenhandler && this.tokenhandler(res)
}
htmllexicalparser.prototype.starttagstate = function(c) {
if(c.match(/[a-za-z]/)) {
this.token.push(c.tolowercase())
return this.starttagstate
}
if(c === ' ') {
this.emittoken('starttag', this.token.join(''))
this.token = []
return this.attrstate
}
if(c === '>') {
this.emittoken('starttag', this.token.join(''))
this.token = []
return this.start
}
}
htmllexicalparser.prototype.endtagstate = function(c) {
if(c.match(/[a-za-z]/)) {
this.token.push(c.tolowercase())
return this.endtagstate
}
if(c === '>') {
this.token.push(c)
this.emittoken('endtag', this.token.join(''))
this.token = []
return this.start
}
}
最后只有属性标签需要处理了，也就是上面看到的 attrstate 函数，也处理三种情形
- 如果是字母、单引号、双引号、等号，则认定为依旧处于属性标签态
- 如果遇到空格，则表示属性标签态结束，接下来进入新的属性标签态
- 如果遇到>，则认定为属性标签态结束，接下来开始新的节点信息
代码如下
htmllexicalparser.prototype.attrstate = function(c) {
if(c.match(/[a-za-z'"=]/)) {
this.token.push(c)
return this.attrstate
}
if(c === ' ') {
this.emittoken('attr', this.token.join(''))
this.token = []
return this.attrstate
}
if(c === '>') {
this.emittoken('attr', this.token.join(''))
this.token = []
return this.start
}
}
最后我们提供一个 parse 解析函数，和可能用到的 getoutput 函数来获取结果即可，就不啰嗦了，上代码
htmllexicalparser.prototype.parse = function() {
var state = this.start;
for(var c of this.htmlstring.split('')) {
state = state.bind(this)(c)
}
}
htmllexicalparser.prototype.getoutput = function() {
return this.tokens
}
接下来简单测试一下，对于 <p class="a" data="js">测试并列元素的</p><p class="a" data="js">测试并列元素的</p> html 字符串，输出结果为
看上去结果很 nice，接下来进入语法分析步骤
语法分析
首先们需要考虑到的情况有两种，一种是有多个根元素的，一种是只有一个根元素的。
我们的节点有两种类型，文本节点和正常节点，因此声明两个数据结构。
function element(tagname) {
this.tagname = tagname
this.attr = {}
this.childnodes = []
}
function text(value) {
this.value = value || ''
}
目标：将元素建立起父子关系，因为真实的 dom 结构就是父子关系，这里我一开始实践的时候，将 childnodes 属性的处理放在了 starttag token 中，还给 element 增加了 isend 属性，实属愚蠢，不但复杂化了，而且还很难实现。
仔细思考 dom 结构，token 也是有顺序的，合理利用栈数据结构，这个问题就变的简单了，将 childnodes 处理放在 endtag 中处理。具体逻辑如下
- 如果是 starttag token，直接 push 一个新 element
- 如果是 endtag token，则表示当前节点处理完成，此时出栈一个节点，同时将该节点归入栈顶元素节点的 childnodes 属性，这里需要做个判断，如果出栈之后栈空了，表示整个节点处理完成，考虑到可能有平行元素，将元素 push 到 stacks。
- 如果是 attr token，直接写入栈顶元素的 attr 属性
- 如果是 text token，由于文本节点的特殊性，不存在有子节点、属性等，就认定为处理完成。这里需要做个判断，因为文本节点可能是根级别的，判断是否存在栈顶元素，如果存在直接压入栈顶元素的 childnodes 属性，不存在 push 到 stacks。
代码如下
function htmlsyntacticalparser() {
this.stack = []
this.stacks = []
}
htmlsyntacticalparser.prototype.getoutput = function() {
return this.stacks
}
// 一开始搞复杂了，合理利用基本数据结构真是一件很酷炫的事
htmlsyntacticalparser.prototype.receiveinput = function(token) {
var stack = this.stack
if(token.type === 'starttag') {
stack.push(new element(token.value.substring(1)))
} else if(token.type === 'attr') {
var t = token.value.split('='), key = t[0], value = t[1].replace(/'|"/g, '')
stack[stack.length - 1].attr[key] = value
} else if(token.type === 'text') {
if(stack.length) {
stack[stack.length - 1].childnodes.push(new text(token.value))
} else {
this.stacks.push(new text(token.value))
}
} else if(token.type === 'endtag') {
var parsedtag = stack.pop()
if(stack.length) {
stack[stack.length - 1].childnodes.push(parsedtag)
} else {
this.stacks.push(parsedtag)
}
}
}
简单测试如下：
没啥大问题哈
解释执行
对于上述语法分析的结果，可以理解成 vdom 结构了，接下来就是映射成真实的 dom，这里其实比较简单，用下递归即可，直接上代码吧
function vdomtodom(array) {
var res = []
for(let item of array) {
res.push(handledom(item))
}
return res
}
function handledom(item) {
if(item instanceof element) {
var element = document.createelement(item.tagname)
for(let key in item.attr) {
element.setattribute(key, item.attr[key])
}
if(item.childnodes.length) {
for(let i = 0; i < item.childnodes.length; i++) {
element.appendchild(handledom(item.childnodes[i]))
}
}
return element
} else if(item instanceof text) {
return document.createtextnode(item.value)
}
}
实现函数
上面三步骤完成后，来到了最后一步，实现最开始提出的函数
function html(element, htmlstring) {
// parsehtml
var syntacticalparser = new htmlsyntacticalparser()
var lexicalparser = new htmllexicalparser(htmlstring, syntacticalparser.receiveinput.bind(syntacticalparser))
lexicalparser.parse()
var dom = vdomtodom(syntacticalparser.getoutput())
var fragment = document.createdocumentfragment()
dom.foreach(item => {
fragment.appendchild(item)
})
element.appendchild(fragment)
}
三个不同情况的测试用例简单测试下
html(document.getelementbyid('app'), '<p class="a" data="js">测试并列元素的</p><p class="a" data="js">测试并列元素的</p>')
html(document.getelementbyid('app'), '测试<div>你好呀，我测试一下没有深层元素的</div>')
html(document.getelementbyid('app'), '<div class="div"><p class="p">测试一下嵌套很深的<span class="span">p的子元素</span></p><span>p同级别</span></div>')
声明：简单测试下都没啥问题，本次实践的目的是对 dom 这一块通过词法分析和语法分析生成 dom tree 有一个基本的认识，所以细节问题肯定还是存在很多的。
总结
其实在了解了原理之后，这一块代码写下来，并没有太大的难度，但却让我很兴奋，有两个成果吧
- 了解并初步实践了一下状态机
- 数据结构的魅力
代码已经基本都列出来了，想跑一下的童鞋也可以 clone 这个 repo：
总结
