利用有限状态机构建简易HTML解析器
本文详解如何使用有限状态机（FSM）实现简易HTML解析器。通过定义状态流转规则，将HTML字符串分解为Token流，再利用栈结构将扁平的Token数组转换为嵌套的抽象语法树（AST）。文章包含数学运算与HTML解析的具体代码示例，解析了词法分析与语法分析的核心逻辑，适用于前端编译原理学习与小程序富文本处理场景。
有限状态机（FSM），亦称有限状态自动机，是一种用于研究具有有限内存的计算过程及特定语言类的抽象计算模型。该模型包含有限数量的状态，每个状态可根据输入字符串迁移至零个或多个后续状态，从而驱动计算流程。
有限状态机的应用场景
在代码编译器的工作流程中，需依次经过词法分析、语法分析和语义分析，最终生成AST（抽象语法树）。首先通过词法分析获取Token流，随后进行语法分析以校验文法并生成语法解析树。这一过程通常存在两种实现路径：
- 边进行词法分析边生成AST，例如HTML和CSS的解析过程。
- 先完成所有Token的词法分析，再进行语法分析以生成AST，例如JavaScript的处理方式。
前端开发中广泛使用的babel、typescript、eslint、postcss、prettier、uniapp、htmlparse以及代码编辑器的语法高亮功能，均基于AST实现。为了构建AST，必须首先进行分词，而利用有限状态机是实现高效分词的优选方案。
代码本质上是字符串，分词即是将代码字符串拆解为不可再分的最小单元，称为Token（此处指技术术语，非登录凭证）。执行分词的组件英文名为Tokenizer。无论是英文文章、中文古诗还是数学运算，均可采用相同的分词技术进行元素拆分。
有限状态机的工作机制
为阐明有限状态机的运作原理，首先实现一个简单的减法运算分词器。目标是将字符串“500-250=250”解析为数组形式。定义两种状态：number（数字）和operator（运算符），每个最小Token仅属于其中一种。具体实现代码如下：
// 500-250=250
// [
// { type: 'number', value: '500' },
// { type: 'operator', value: '-' },
// { type: 'number', value: '250' },
// { type: 'operator', value: '=' },
// { type: 'number', value: '250' }
// ]
function mathTokenizer(text) {
// 匹配数字正则
const numberReg = /[0-9]/
// 匹配运算符正则
const operatorReg = /[-=]/
// 存储所有读取到的 token 数组
let tokens = []
// 当前正在读取的 token 信息
let currentToken = {}
// 初始状态
function init(e) {
if (numberReg.test(e)) {
currentToken = { type: 'number', value: e }
return onNumber
} else if (operatorReg.test(e)) {
currentToken = { type: 'operator', value: e }
return onOperator
}
}
// 读取到数字
function onNumber(e) {
if (numberReg.test(e)) {
currentToken.value += e
return onNumber
}
if (operatorReg.test(e)) {
pushToken(currentToken)
currentToken = { type: 'operator', value: e }
return onOperator
}
}
// 读取到运算符
function onOperator(e) {
if (numberReg.test(e)) {
pushToken(currentToken)
currentToken = { type: 'number', value: e }
return onNumber
}
if (operatorReg.test(e)) {
pushToken(currentToken)
currentToken = { type: 'operator', value: e }
return onOperator
}
}
// 每次读取到完整的一个 token 后存入到数组中
function pushToken(token) {
tokens.push(token)
currentToken = {}
}
// 遍历读取数组
function parse(str) {
const len = str.length
let stateMachine = init
for (let i = 0; i < len; i++) {
const char = str[i]
stateMachine = stateMachine(char)
// 最后一个字符匹配完了要自己 pushToken
if (i === len - 1) {
pushToken(currentToken)
}
}
return tokens
}
return parse(text)
}
const arr = mathTokenizer('500-250=250')
console.log(arr)
简易HTML解析器实现
词法分析与Token流生成
利用状态机生成Token流。为便于理解，以下示例暂不考虑标签属性节点、自闭合标签及各类异常情况的处理。
定义五种状态：标签开始、结束标签开始、标签名、标签结束和文本。每次读取字符时，系统将在上述五种状态间切换。若当前读取内容不属于标签开始、结束标签开始、标签名或标签结束这四种状态，则统一按文本处理。
实际存储时仅需保留开始标签、文本和结束标签这三种状态，对应的节点type分别为startTag、text和endTag。若按前述五种状态存储亦无不可，在后续生成AST时忽略不需要的标签开始或结束信息即可。此处选择在分词阶段直接过滤，以简化后续处理。
可将状态机视为一个函数，每遍历一个字符便将其传入函数。函数根据该字符判断下一个状态，并返回对应的状态处理函数，从而实现状态的流转与控制。
function htmlTokenizer(str){
// 标签开始
const tagStartReg = /</
// 结束标签开始
const closeTagReg = ///
// 标签结束
const tagEndReg = />/
// 标签名
const tagNameReg = /[a-zA-Z]/
let tokens = []
let currentToken = {}
// 初始状态
function init(e) {
if (tagStartReg.test(e)) {
currentToken = { type: 'startTag', tagName: '' }
return init
}
if (closeTagReg.test(e)) {
currentToken = { type: 'endTag', tagName: '' }
return onTagName
}
if (tagNameReg.test(e)) {
currentToken.tagName += e
return onTagName
}
// 不是上面3个状态的都当成文本节点处理
currentToken = { type: 'text', text: e }
return onText
}
// 读取到标签名
function onTagName(e) {
if (tagEndReg.test(e)) {
pushToken(currentToken)
return init
} else {
currentToken.tagName = (currentToken.tagName || '') + e
return onTagName
}
}
// 读取到文本
function onText(e) {
if (tagStartReg.test(e)) {
pushToken(currentToken)
currentToken = { type: 'startTag', tagName: '' }
return init
} else {
currentToken.text = (currentToken.text || '') + e
return onText
}
}
// 每次读取到完整的一个 token 后存入到数组中
function pushToken(e) {
tokens.push(e)
currentToken = {}
}
// 遍历读取数组
function parse(chars){
let stateMachine = init
for (const char of chars) {
stateMachine = stateMachine(char)
}
return tokens
}
return parse(str)
}
const tokenList = htmlTokenizer('<div>静夜思<p>锄禾日当午</p>周小黑<p>粒粒皆辛苦</p>公元一七八八年</div>')
console.log(tokenList)
语法分析与AST抽象语法树生成
此步骤的核心在于如何将分词得到的数组转换为树形Tree数据结构。常规开发中，Array转Tree通常依赖父ID等字段进行遍历生成，但此处获取的数组并不包含父ID信息，需探索其他实现方式。
观察数据结构可知，该数组呈现类似中心对称的结构。暂时忽略type为text的文本内容（因其只能作为子节点，不能作为父节点），过滤文本后，数组的第一个元素与最后一个元素互为配对，第二个元素与倒数第二个元素互为配对。实现目标是将内层获取到的标签对不断挂载到前一对标签的children属性上，从而构建Tree结构。
从数组第一项开始遍历，使用一个数组模拟Stack栈来存储每次遍历到的标签信息。栈遵循先进后出原则，类似往桶中放置物品，最上面的物品最先取出。通过限制数组仅使用push和pop操作，即可模拟栈的行为。
当遇到开始标签时，表示新标签出现，将其push入栈；当遇到结束标签时，表示当前标签信息读取完毕，将其从栈中pop出来。此时栈顶元素即为当前弹出标签的父标签，直接将其挂载至父节点的children属性即可。整个过程主要需理解以下两点：
- 利用栈缓存节点：嵌套内部的节点先出栈，根节点最后出栈。
- 利用引用类型对象的特点，持续挂载节点以构建层级关系。
function htmlAst(tokenList) {
let stack = []
for (let i = 0; i < tokenList.length; i++) {
const node = tokenList[i]
// 开始标签：入栈
if (node.type === 'startTag'){
stack.push(node)
}
// 结束标签：出栈
if (node.type === 'endTag') {
const currentNode = stack.pop()
const parent = stack[stack.length - 1]
if (parent) {
if (!parent.children) parent.children = []
parent.children.push(currentNode)
} else {
const root = { type: 'document', children: [currentNode] }
return root
}
}
// 文本：加到父标签的 children 上
if (node.type === 'text') {
const parent = stack[stack.length - 1]
if (!parent.children) parent.children = []
parent.children.push(node)
}
}
}
执行上述逻辑后，即可获得所需的AST语法树，其结构如下所示：
{
"type": "document",
"children": [
{
"type": "startTag",
"tagName": "div",
"children": [
{
"type": "text",
"text": "静夜思"
},
{
"type": "startTag",
"tagName": "p",
"children": [
{
"type": "text",
"text": "锄禾日当午"
}
]
},
{
"type": "text",
"text": "周小黑"
},
{
"type": "startTag",
"tagName": "p",
"children": [
{
"type": "text",
"text": "粒粒皆辛苦"
}
]
},
{
"type": "text",
"text": "公元一七八八年"
}
]
}
]
}
掌握状态机如同获得一双翅膀，无论输入何种字符内容，均可通过状态机拆解为期望的结构。理解上述原理后，再审视Vue中的模板编译机制，便能明白其语法糖的添加方式。此外，在小程序富文本解析场景中，由于特定平台小程序无法直接识别浏览器HTML，需先将HTML通过状态机转换为AST，再依据小程序语法进行特定转换。
本文关于使用有限状态机实现简易HTML解析器的介绍至此结束。如需了解更多有限状态机实现HTML解析器的相关内容，请搜索本站过往文章或继续浏览后续相关文章，感谢大家的支持。
JS怎么实现页面强制刷新
2026-11-05 14:53:38
点击JS链接直接运行不下载？前端实现.js文件强制下载的三种方法
2026-11-05 12:12:23
怎么封装一个通用的JS创建元素辅助函数
2026-11-05 11:41:41
Swiper.js 怎么监听滑动结束并获取当前索引
2026-11-05 10:57:15
HTML、CSS和JS的关系：Web前端三件套怎么协作
2026-11-04 15:41:40