Better

都知道浏览器和服务端是通过 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：domtree