前言
虚拟语法树(Abstract Syntax Tree, AST)是解释器/编译器进行语法分析的基础, 也是众多前端编译工具的基础工具, 比如webpack, postcss, less等. 对于ECMAScript, 由于前端*众多, 人力过于充足, 早已经被人们玩腻了. 光是语法分析器就有uglify, acorn, bablyon, typescript, esprima等等若干种. 并且也有了AST的社区标准: ESTree.
这篇文章主要介绍如何去写一个AST解析器, 但是并不是通过分析JavaScript, 而是通过分析html5的语法树来介绍, 使用html5的原因有两点: 一个是其语法简单, 归纳起来只有两种: Text和Tag, 其次是因为JavaScript的语法分析器已经有太多太多, 再造一个*毫无意义, 而对于html5, 虽然也有不少的AST分析器, 比如htmlparser2, parser5等等, 但是没有像ESTree那么标准, 同时, 这些分析器都有一个问题: 那就是定义的语法树中无法对标签属性进行操作. 所以为了解决这个问题, 才写了一个html的语法分析器, 同时定义了一个完善的AST结构, 然后再有的这篇文章.
AST定义
为了跟踪每个节点的位置属性, 首先定义一个基础节点, 所有的结点都继承于此结点:
export interface IBaseNode {
start: number; // 节点起始位置
end: number; // 节点结束位置
}如前所述, html5的语法类型最终可以归结为两种: 一种是Text, 另一种是Tag, 这里用一个枚举类型来标志它们.
export enum SyntaxKind {
Text = 'Text', // 文本类型
Tag = 'Tag', // 标签类型
}对于文本, 其属性只有一个原始的字符串value, 因此结构如下:
export interface IText extends IBaseNode {
type: SyntaxKind.Text; // 类型
value: string; // 原始字符串
}而对于Tag, 则应该包括标签开始部分open, 属性列表attributes, 标签名称name, 子标签/文本body, 以及标签闭合部分close:
export interface ITag extends IBaseNode {
type: SyntaxKind.Tag; // 类型
open: IText; // 标签开始部分, 比如 <div id="1">
name: string; // 标签名称, 全部转换为小写
attributes: IAttribute[]; // 属性列表
body: Array<ITag | IText> // 子节点列表, 如果是一个非自闭合的标签, 并且起始标签已结束, 则为一个数组
| void // 如果是一个自闭合的标签, 则为void 0
| null; // 如果起始标签未结束, 则为null
close: IText // 关闭标签部分, 存在则为一个文本节点
| void // 自闭合的标签没有关闭部分
| null; // 非自闭合标签, 但是没有关闭标签部分
}标签的属性是一个键值对, 包含名称name及值value部分, 定义结构如下:
export interface IAttribute extends IBaseNode {
name: IText; // 名称
value: IAttributeValue | void; // 值
}其中名称是普通的文本节点, 但是值比较特殊, 表现在其可能被单/双引号包起来, 而引号是无意义的, 因此定义一个标签值结构:
export interface IAttributeValue extends IBaseNode {
value: string; // 值, 不包含引号部分
quote: '\'' | '"' | void; // 引号类型, 可能是', ", 或者没有
}Token解析
AST解析首先需要解析原始文本得到符号列表, 然后再通过上下文语境分析得到最终的语法树.
相对于JSON, html虽然看起来简单, 但是上下文是必需的, 所以虽然JSON可以直接通过token分析得到最终的结果, 但是html却不能, token分析是第一步, 这是必需的. (JSON解析可以参考我的另一篇文章: 徒手写一个JSON解析器(Golang)).
token解析时, 需要根据当前的状态来分析token的含义, 然后得出一个token列表.
首先定义token的结构:
export interface IToken {
start: number; // 起始位置
end: number; // 结束位置
value: string; // token
type: TokenKind; // 类型
}Token类型一共有以下几种:
export enum TokenKind {
Literal = 'Literal', // 文本
OpenTag = 'OpenTag', // 标签名称
OpenTagEnd = 'OpenTagEnd', // 开始标签结束符, 可能是 '/', 或者 '', '--'
CloseTag = 'CloseTag', // 关闭标签
Whitespace = 'Whitespace', // 开始标签类属性值之间的空白
AttrValueEq = 'AttrValueEq', // 属性中的=
AttrValueNq = 'AttrValueNq', // 属性中没有引号的值
AttrValueSq = 'AttrValueSq', // 被单引号包起来的属性值
AttrValueDq = 'AttrValueDq', // 被双引号包起来的属性值
}Token分析时并没有考虑属性的键/值关系, 均统一视为属性中的一个片段, 同时, 视=为一个
特殊的独立段片段, 然后交给上层的parser去分析键值关系. 这么做的原因是为了在token分析
时避免上下文处理, 并简化状态机状态表. 状态列表如下:
enum State {
Literal = 'Literal',
BeforeOpenTag = 'BeforeOpenTag',
OpeningTag = 'OpeningTag',
AfterOpenTag = 'AfterOpenTag',
InValueNq = 'InValueNq',
InValueSq = 'InValueSq',
InValueDq = 'InValueDq',
ClosingOpenTag = 'ClosingOpenTag',
OpeningSpecial = 'OpeningSpecial',
OpeningDoctype = 'OpeningDoctype',
OpeningNormalComment = 'OpeningNormalComment',
InNormalComment = 'InNormalComment',
InShortComment = 'InShortComment',
ClosingNormalComment = 'ClosingNormalComment',
ClosingTag = 'ClosingTag',
}整个解析采用函数式编程, 没有使用OO, 为了简化在函数间传递状态参数, 由于是一个同步操作,
这里利用了JavaScript的事件模型, 采用全局变量来保存状态. Token分析时所需要的全局变量列表如下:
let state: State // 当前的状态
let buffer: string // 输入的字符串
let bufSize: number // 输入字符串长度
let sectionStart: number // 正在解析的Token的起始位置
let index: number // 当前解析的字符的位置
let tokens: IToken[] // 已解析的token列表
let char: number // 当前解析的位置的字符的UnicodePoint在开始解析前, 需要初始化全局变量:
function init(input: string) {
state = State.Literal
buffer = input
bufSize = input.length
sectionStart = 0
index = 0
tokens = []
}然后开始解析, 解析时需要遍历输入字符串中的所有字符, 并根据当前状态进行相应的处理
(改变状态, 输出token等), 解析完成后, 清空全局变量, 返回结束.
export function tokenize(input: string): IToken[] {
init(input)
while (index < bufSize) {
char = buffer.charCodeAt(index)
switch (state) {
// ...根据不同的状态进行相应的处理
// 文章忽略了对各个状态的处理, 详细了解可以查看源代码
}
index++
}
const _nodes = nodes
// 清空状态
init('')
return _nodes
}语法树解析
在获取到token列表之后, 需要根据上下文解析得到最终的节点树, 方式与tokenize相似,
均采用全局变量保存传递状态, 遍历所有的token, 不同之处在于这里没有一个全局的状态机.
因为状态完全可以通过正在解析的节点的类型来判断.
export function parse(input: string): INode[] {
init(input)
while (index < count) {
token = tokens[index]
switch (token.type) {
case TokenKind.Literal:
if (!node) {
node = createLiteral()
pushNode(node)
} else {
appendLiteral(node)
}
break
case TokenKind.OpenTag:
node = void 0
parseOpenTag()
break
case TokenKind.CloseTag:
node = void 0
parseCloseTag()
break
default:
unexpected()
break
}
index++
}
const _nodes = nodes
init()
return _nodes
}不太多解释, 可以到GitHub查看源代码.
结语
项目已开源, 名称是html5parser, 可以通过npm/yarn安装:
npm install html5parser -S
# OR
yarn add html5parser 或者到GitHub查看源代码: acrazing/html5parser.
目前对正常的HTML解析已完全通过测试, 已知的BUG包括对注释的解析, 以及未正常结束的
输入的解析处理(均在语法分析层面, token分析已通过测试).