一个Json解析库的设计和实现

设计思路

当前很多Json库基于状态机思想，所有Json元素均在同一个状态机中，Json文件的内容以逐字符的方式流入状态机中，促使状态流转。在这个大状态机中，每个Json元素设计为子状态机。具体表现为：为每个Json元素分别定义一个解析函数，再为Json文件设计一个入口函数。从这个入口函数出发，调用各Json元素的解析函数，各Json元素的解析函数依据状态流转递归调用其他Json元素的解析函数。

将Json元素全部放到同一个状态机中，好处是直观，细化到每个字符均可找到不同的状态流转。由于Json元素不多，格式简单，状态机的设计不会很复杂。依据划分的子状态机为每个Json元素单独实现解析函数，并允许相互递归调用减少了代码量。

但这种实现对于Json定制存在复杂性，对于某些场景，要求采用定制特殊语法的Json文件（此时的Json文件已经不是严格意义上的Json），例如加入注释、数值运算、引用等。随着定制元素的增多，状态机的设计愈发复杂。由于Json解析类似编译，采用编译的思路可实现从字符串到Json树、Json树到字符串的转换，编译前端和编译后端的架构使得增加定制元素相对直观和容易修改。

下面是采用编译思路设计的Json库流程图。
前端部分：
在这里插入图片描述

后端部分：
在这里插入图片描述

前端部分将字符串转换为Json树型结构，后端部分将Json树型结构转换为字符串。

实现方法

每个子模块分别实现特定的功能，再将结果传入下一个模块内。

1. 预处理（去除注释）

此步骤类似C编译器的预处理器。此步骤去除注释内容（可选将转义字符\n \t \r \u …的字符串表示转换为UTF8编码，删除部分空格等）。去除注释的过程采用状态机实现，依次将每个字符输入状态机，当状态为PCOMMENT、LINE_COMMENT、LEAVE_COMMENT时跳过字符：
在这里插入图片描述

预处理结束后，文件仍为字符串形式，流入词法分析器

2. 词法分析

Json的数据结构不是很复杂，大致如下表所示：

元素名称	形式	说明
字符串	“xxxx”
数字	-0.1E+8
对象	{xxx: xxx}	无序的 ‘名称:值’ 对集合
数组	[xxx, xxx]
布尔	true, false
Null

为了描述方便，下面以Node指代一个“名称:值”对，其中Field指代“名称”，Value指代“值”。从Json格式描述可知，Json文件中的基本词法单元可定义为：（见仁见智）

词法单元	形式	说明
字符串	“xxxx”
数字	-0.1E+8
域Field	xxx:	仅在对象中存在
布尔	true, false
对象入口	{
对象出口	}
数组入口	[
数组出口	]
分隔符	,
Null

为每个词法单元分别实现其判定函数，每个判定函数的输入为json文件字符串，输出为范围[start, end], 以表示该词法单元在整个Json文件中的起始和终止offset。以文件第一个字符json[0]为起始，将json字符串输入到每个词法单元的解析函数中，只有一个解析函数可以成功，返回该词法单元的范围[start, end]，然后跳过该词法单元，以json+end+1为起始将json字符串输入到每个词法单元的解析函数中，重复上述过程，直至json字符串末尾或所有解析函数均失败。如果所有解析函数均失败，则意味着词法错误，停止后续过程。

下面是string的此法单元判定过程：
在这里插入图片描述

数值的判定过程参见Json标准委员会ECMA-404_2nd文档的流程图，其为如下状态流转：
在这里插入图片描述

布尔等词法单元的判定过程此处不再赘述。
词法分析完成后，生成了一个以{type, [start, end]}为单元的数组，每个数组元素均代表一个词法单元，标识出词法类型和在全文中的范围。该数组送入语法分析模块内。

3. 语法分析

词法分析生成的数组为一维形式，仅标识了单词。单词和单词间的合法性和关系由语法分析去判定和构建。本程序拟采用LR分析法，由于Json元素关系相对简单，文法的表示不长：

定义x为对象，N为Node列表，n为Node，0为Null，f为Field，y为Value，s为字符串，z为数组，num为数组，bool为布尔，NY为数组成员列表；
x->{N}
N->N,n
N->n
N->0
n->fy
y->x
y->z
y->s
y->num
y->bool
z->[NY]
NY->NY,y
NY->y
NY->0

该文法需要根据LR分析过程做局部调整避免二义性。将空数组和空对象直接表示为：
x->{}
z->[]
同时删除N->0和NY->0两个文法。

生成文法列表后，依据LR分析过程用栈回溯方式依次匹配各文法，规约生成树型结构。

4. 树型优化

语法分析生成的二叉语法树，存在大量与Json内容无关的节点，这些节点仅用于表示Json元素的关系，并且受限于二叉树结构，存在大量表示层级关系的节点。需要进一步删除冗余节点，将二叉树变为树。树型优化的工作是找到一个对象、数组的所有成员节点（存在Json元素含义的），将这些成员节点直接连入对象、数组下面，删除对象、数组下面表示元素关系、层级关系（不含Json元素含义的）的节点。这种优化过程如下图所示：
在这里插入图片描述

存在Json元素含义的节点种类为：

Node 文法中表示为n
字符串文法中表示为s
数值文法中表示为num
布尔文法中表示为bool
Field 文法中表示为f
对象Object 文法中表示为s
数组Array 文法中表示为z

该优化的具体实现过程如下，采用先序遍历二叉语法树。从根节点开始，依次访问各子节点，如果找到存在Json元素含义的节点，如Node，则停止Node的向下遍历，将Node接入根节点中，再从Node的兄弟节点开始继续向下遍历，重复上述过程。当根节点遍历完成后，根节点下的所有存在Json元素含义的节点均直接连入根节点下面。再从根节点的子节点出发（此时的子节点全部为存在Json元素含义的节点），对于每个对象Object和数组Array类型的节点，将这些节点作为子树的根，重复上述过程，依次完成所有对象Object、数组Array的子节点的连入。重复上述过程直至整个语法树的每个节点全部访问完为止。

5. Json树构建

当树型优化完成后，该树型即为用户所需的Json树型，但这个树中的节点没有保存数值，仅给出了{type,[start,end]} 词法类型和单词范围。一般情况下，语法树树节点的数据类型也不是用户所需的Json对象类型。Json树构建需要完成两个工作：

从语法树节点生成Json对象，即类型转换，此时维持树型不变；
对于每个Json对象，依据{type,[start,end]}将单词字符串解析为数值。

第一条相对简单，仅依据节点的Node、字符串、数值、布尔、Field等类型依次创建Json对象类型，每创建一个Json对象，替换语法树中相应的节点即可。

第二条仍需要借助状态机，将字符串转换为数值。Json中存在的转换有如下情况：

转换	说明
字符串->数值	整型、浮点型、精度
字符串->布尔
字符串->字符串	转义字符处理

这些从字符串到数值的处理过程在ECMA-404_2nd文档中都有详细的状态机模型，参见其实现即可。由于词法分析已经判定了字符串的合法性，此处的解析省略合法性判定，认为其一定是合法的。

Json树构建完成后，从字符串到Json对象的解析过程就全部完成了。该过程仅为Json库的核心部分。实际使用中，用户总不能直接对树进行遍历查找元素吧。需要设计一套用户接口，实现如create、add、iterator、delete、find等接口，在接口内访问Json树并进行边界检查。这些接口此处不再赘述。