JSON 解析器原理

输入 JSON 字符串，对象或数组相互嵌套着，如：
{
“firstName”: “John”,
“lastName”: “Smith”,
“age”: 25,
“address”: {
“streetAddress”: “21 2nd Street”,
“city”: “New York”,
“state”: “NY”,
“postalCode”: 10021
},
“phoneNumbers”: [
{
“type”: “home”,
“number”: “212 555-1234”
},
{
“type”: “fax”,
“number”: “646 555-4567”
}
]
}

如果只考虑 JSON 简单情况（此种情况固然是不能放在生产环境的）是可以的，而且代码行数少，正好适合我们初学理解。下面是该函数的完整代码。

/**

• @param jsonstring


• 
  

  @return
  */
  @SuppressWarnings(“unchecked”)
  public static Object json2Map(String jsonstring) {
  char[] cs = jsonstring.toCharArray();
  Stack<Map> maps = new Stack<>(); //用来表示多层的json对象
  Stack lists = new Stack<>(); //用来表示多层的list对象
  Stack islist = new Stack<>();//判断是不是list
  Stack keys = new Stack<>(); //用来表示多层的key

  
  
  

  String keytmp = null;
  Object valuetmp = null;
  StringBuilder builder = new StringBuilder();

  
  
  

  for (int i = 0; i < cs.length; i++) {

  
  
  

   switch (cs[i]) {
  
       case '{': //如果是{map进栈
  
           maps.push(new HashMap());
  
           islist.push(false);
  
           break;
  
       case ':'://如果是：表示这是一个属性建，key进栈
  
           keys.push(builder.toString());
  
           builder = new StringBuilder();
  
           break;
  
       case '[':
  
           lists.push(new ArrayList());
  
           islist.push(true);
  
           break;
  
       case ',':
  
           if (builder.length() > 0)
  
               valuetmp = builder.toString();
  
           builder = new StringBuilder();
  
  
  
           boolean listis = islist.peek();
  
           if (!listis) {
  
               keytmp = keys.pop();
  
               maps.peek().put(keytmp, valuetmp);
  
           } else
  
               lists.peek().add(valuetmp);
  
  
  
           break;
  
       case ']':
  
           islist.pop();
  
  
  
           if (builder.length() > 0)
  
               valuetmp = builder.toString();
  
           lists.peek().add(valuetmp);
  
           valuetmp = lists.pop();
  
           builder = new StringBuilder();
  
           break;
  
       case '}':
  
           islist.pop();
  
           //这里做的和，做的差不多，只是需要把valuetmp=maps.pop();把map弹出栈
  
           keytmp = keys.pop();
  
  
  
           if (builder.length() > 0)
  
               valuetmp = builder.toString();
  
  
  
           builder = new StringBuilder();
  
           maps.peek().put(keytmp, valuetmp);
  
           valuetmp = maps.pop();
  
           break;
  
       default:
  
           builder.append(cs[i]);
  
           break;
  
   }
  
  

  
  
  

  }
  return valuetmp;
  }
  该函数输入一个 String 类型的参数，返回一个 Object 类型结果。Object 类型只有两种真实类型，要么是 Map，要么是 List，分别对应最外层的 JSON 类型。

  
  

怎么理解这个函数呢？首先方法输入的是字符串，我们把字符串“打散”，也就是 char[] cs=jsonstring.toCharArray(); 这句把字符串转换为字符数组。变成数组的目的是要遍历也就是把数组中的每一个字符都读出来。读了一个字符，并进行解析。解析完毕了，我们叫“消耗”。把这个字符消耗了，接着就读取下一个字符重复上述过程。如此 JSON 里面每一个字符都会被读取、解析、消耗。

将字符串变为字符数组，实际上很多 JSON 解析库都会那么做，是为第一步之工序。得到 char[] 然后遍历它，其中的遍历过程就是具体的一个解析 JSON 的过程。

至于遍历 for 里面具体怎么个解析法？此固然是要重点探讨的话题。

解析过程
栈结构的运用
函数中一口气声明了 4个 Stack：

Stack<Map<String, Object» maps = new Stack<>(); // 用来保存所有父级对象
Stack<List

同理，遇到数组的方式也可以这样去理解，保存在 lists 变量中。

当然，必须先有父级节点，才会有子节点，否则子节点就没有容身的“场所”。故而第一个欲消耗的字符永远要么是 {，永远要么是 [，才会 new 第一个 map 对象或者 list 对象。第一个 { 或 [ 可以称为“根节点”或“顶级节点”。

回到函数中，分别是如下进行字符的消耗的：
switch (cs[i]) {
case ‘{‘: // 如果是 { map 进栈
maps.push(new HashMap<String, Object>());
isList.push(false);
continue;
……
……
case ‘[’:
isList.push(true);
lists.push(new ArrayList

光有进栈不够，应该还有“退栈”的那么一个操作。不过这里权且埋下伏笔，回过头来我们再看退栈。
结对匹配
上述过程就是匹配 JSON 字符串中的两种括号：尖括号和方括号，如 [ { }, [ ], [ ] ] 或 { [ ], [ ] } 等为正确格式，[ { ] } 或 { [ } } 为不合法格式。我们把 JSON 字符串抽象成这个格式去理解，有助于我们理解怎么匹配成对出现的结构。

例如考虑下面的括号序列。

[ { [ ] [ ] } ]
1 2 3 4 5 6 7 8
1
2
当消耗了第 1 个括号 [ 之后，期待与它匹配的第 8 个括号 ] 出现，然而等来的却是第 2 括号 {，此时第 1 个括号只能靠边站，不过没关系，因为我们消耗过程中已经把它保存起来，进行过“入栈”了；好，接着第 2 个括号要匹配的是 }，但是很遗憾，第 3 个括号并不是期待的 }，而是 [。不过同样没关系，因为第 2 个括号已经保存起来，先记着；现在轮到第 3 个括号，就要看看第 4 个括号怎么样？第 4 个括号正好是 ]，完成匹配！期待得到了满足！但是不要忘记刚才第 3 个括号已经入过栈，所以现在满足之后，当前就不是原来的位置——需要执行什么操作？就是要“退栈”的操作。

执行完退栈之后，当前位置是第 5 个括号，而当前所期待的括号理应是第 2 个括号的期待，这个期待最为迫切。不过很遗憾，第 2 个括号还必须“忍一忍”，因为第 5 个括号是 [，说明又有新的期待进来，迫切性更高，第 2 个括号必须“让位于”第 5 个括号。——这里我们假设是故意弄错，第 6 个括号进入的是一个右尖括号 }，明显这样不能构成结对，是非法字符，于是应中止遍历，立刻报错。回到正确的例子上，我们看到第 6 个括号是合法的括号，完成匹配，接下来期待第 2 个括号的匹配，或者是 [ or { 新开一级的匹配——这都是可以、合法的。

由此可见，这过程与栈的结构相吻合。“一进一退”是必须完成的结对，否则是不合法的过程。
https://blog.csdn.net/zhangxin09/article/details/77132093

用 JSON 表现树的结构兼谈队列、堆栈
K/V 与 Array
接触 JSON 的人都知道，JSON 可通过 K/V（Key/Value） 结构很直观地表现一棵树，因为 V 可以“包含”另外一个 K/V 从而不断嵌套下去形成“树状”的结构。但 V 不一定必须为另外一个 K/V，而是可以为 Array 数组。数组中由可以“包含”更多的 K/V 或者又是数组类型——也是可以的。如此反复下去，可以形成层数很深的一棵树。例如

{
aa : {
cc ：[
“dd”,
{
ee: true, ff: “hihi”
}
]
},
bb: [ ]
}

这里说的树是指无序树，甚至根节点也没有，不过没关系，在最外一层加上便是。

比较微妙的是 JSON 允许了数组和 K/V 相互嵌套。下级子节点应该用 K/V 来装，还是用 Array 来装呢？又怎么理解数组和 K/V 的关系呢？个人理解，数组本质上也可以归纳其为 K/V。我们一般讨论数组时候还会接触到数组的索引，例如 arr[0] = a, arr[1] = b，索引便是 key 的一种，只不过我们通常 JSON 里面的 key 为字符串，实际上为 int 类型也是允许的。相较而言，数组结构比 K/V 的简单，是 K/V 的一种简化。当然我这种只是“大而化之”的理解，——实际上它们差别很多，好比它们的数据结就显著不同：数组仅仅是一个线性表；K/V 会复杂的多，一般要经过多步 hash 的运算。

再看看上面的 JSON 例子，看起来这个 JSON 想要表达很多东西，最外层是个 K/V，里面的 aa 是下一层的 K/V，但 bb 却是数组，——似乎结构有点混乱。如果用来表现一个树，显然也是一颗“混乱的树”。如果实际开发遇到这样结构的设计，那肯定有问题的，需要好好简化的。不过，无论怎么简化，一旦引入树的概念后，好像还是会有矛盾的地方，例如 K/V 和 Array 两者都可以延伸一下级节点，它们之间有什么不同呢？什么时候该用 K/V 呢？什么时候又该使用 Array 呢？这并无标准答案，JSON 自身并不会说明清楚或者强制要求。再例如 cc 这个数组，第一个元素是字符串，第二个元素是 K/V。因为我们知道，JSON 包含的元素可允许是不同类型的，即混合多种类型的值为一个数组——那样本身是没问题的。但结合树的概念的话问题就来了，是否 K/V 就必须是引出下级树节点吗？——我大可以理解为 JSON 的一个值，她是 K/V 类型，那也是合法的啊，同理数组也不一定引出下级的节点，当前只是表现同类对象的集合，——那也是完全合法的。所以怎么定义这是个树节点，还是说一个 JSON 值？二义性的问题由此产生了。

为解决这个二义性的问题，我们可以对 JSON 作适当的约定，以便更清晰地和准确地反映一棵树。首先节点用 K/V 表示；Children 是下级节点的数组，是容器。它不能是其他的类型如 map 的类型，只能是 Array。只有 最外一层 和 父容器名为 children 的数组，里面的 K/V 才是树节点。一个节点可以有零个或一个 children 的 K/V，且 V 必然是数组。

如下便是一个我们约束定义的树：
[ {
    ’name’ : “关于我们”,
    ’id’ : ‘about’,
    ’children’ : [
        {
            name : “公司历程”,
            id : ‘history’
        },
        {
            name : “企业文化”,
            id : ‘cluture’
        }
    ]
}, {
    ’name’ : “美食天地”,
    ’id’ : ‘product’,
    ’children’ : [
        {
            name : “最新美食”,
            id : ‘new’,
            ’children’ : [
                {
                    ’id’ : ‘yuecai’,
                    ’name’ : ‘粤菜’
                },
                {
                    ’id’ : ‘yuecai’,
                    ’name’ : ‘湘菜’
                }
            ]
        },
        {
            name : “热门菜谱”,
            id : ‘hot’
        }
    ]
},
{
    ’name’ : “最新资讯”,
    ’id’ : ‘news’
},
{
    ’name’ : “招聘信息”,
    ’id’ : ‘hr’
}, {
    ’name’ : “联系我们”,
    ’id’ : ‘contact’
}]
值得注意的是该结构最外一层为 Array 而不是 K/V。

遍历 JSON
JSON 本身乃 JavaScript 的产物，虽然也有序列化和反序列化的过程，但使用起来还是比较自然、“原生原味”的。

这里重点说说 Java 世界处理 JSON 的话题。当 JSON 字符串经过解析器反序列化之后，可得到 Java 识别的类型。如果引入三方包，就有其自定义的类型（如 JSONArray、JSONObject）。但是我们这里不使用三方包的类型来说明问题（虽然可能都是“同理”得出一致的结论），——因为那又牵涉到该使用哪个三方包的问题（选择困难症患者-_-）。

于 Java 而言与 JSON 对应的结构一般自然的选择是 Map/List 组合——本文就拿 Map/List 就好了。这里用泛型可以加强说明所包含元素的类型是什么，使之更加直观和清晰，即 Map，其中，String 是 key 的类型，我们知道 JSON 的key 类型就是字符串类型；Object 便是 Value 的类型，可以是合法的 JSON 值（字符串、数字、null），或者是另外一个 Map 或 List。至于 List 的泛型便是嵌套的 List<Map>。于是，我们可以写一个方法（或者第三方包），JSON 字符串被解析之后，得到 Map/List 结构的 Java 类型，变成 Java 可以理解的“树”。应该怎么遍历的这棵树呢？最简单的方法，莫过于递归这个 Map/List。

好比现在输入这段 JSON，这是网站的配置文件：

{
“site” : {
“titlePrefix” : “大华•川式料理”,
“keywords” : “大华•川式料理”,
“description” : “大华•川式料理饮食有限公司于2015年成立，本公司目标致力打造中国新派川菜系列。炜爵爷川菜料理系列的精髓在于清、鲜、醇、浓、香、烫、酥、嫩，擅用麻辣。在服务出品环节上，团队以ISO9000为蓝本建立标准化餐饮体系，务求以崭新的姿态面向社会各界人仕，提供更优质的服务以及出品。炜爵爷宗旨：麻辣鲜香椒，美味有诀窍，靓油用一次，精品煮御赐。 “,
“footCopyright”:”dsds”
},
“dfd”:{
“dfd”:’fdsf’,
“id”: 888,
“dfdff”:{
“dd”:’fd’
}
},
“clientFullName”:”大华•川式料理”,
“clientShortName”:”大华”,
“isDebug”: true,
“data” : {
“newsCatalog_Id” : 6,
“jobCatalog_Id” :7
}
}
送入 JSON 解析器得到 Map：

这里暂忽略 JSON 解析器的原理。先接着看看遍历 JSON 的过程。假设我们要把所有 key 列出来

@SuppressWarnings(“unchecked”)
public void travel(Map<String, Object> map) {
    for (String key : map.keySet()) {
        Object obj = map.get(key);
        System.out.println(“The key is:” + key);

        if (obj != null && obj instanceof Map) {
            Map<String, Object> _map = (Map<String, Object>) obj;
            travel(_map);     
        }
    }
}
打印结果如下

前面说到，我们讨论的是树结构，已经有这样的约定：如果遇到 Key 为 children 且 value 为数组元素的话，那就下级节点，数组里的都是子节点 K/V。否则就是普通的一个 JSON 数组。

@SuppressWarnings(“unchecked”)
public void travel(Map<String, Object> map) {
for (String key : map.keySet()) {
Object obj = map.get(key);
System.out.println(“The key is:” + key);

	if (obj != null && obj instanceof Map) {

		Map<String, Object> _map = (Map<String, Object>) obj;

		if (_map.get(children) != null && _map.get(children) instanceof List) {

			List<Map<String, Object>> list = (List<Map<String, Object>>) _map.get(children);

 

			for (Map<String, Object> __map : list)

				travel(__map);

		}

	}

} } 与前面的函数相比只是增加了 children 的判断，然后遍历 children 里面各项的 map。——一切都非常简单是吧？可以说毫无惊艳之处。不过读者可试着改造一下，把当前支持 Map<String, Object> map 类型的参数改为List<Map<String, Object>> list 的，看看遍历过程有什么不同。

分析树
现在不妨把需求的难度提高那么一丢丢：希望可以完整记下节点的完整的“路径”和层级。文章到这里写得太长太冗长了，笔者还是赶紧给出代码，赶紧收尾。

输入 JSON 数组：

[ {
‘name’ : “关于我们”,
‘id’ : ‘about’,
‘children’ : [
{
name : “公司历程”,
id : ‘history’
},
{
name : “企业文化”,
id : ‘cluture’
}
]
}, {
‘name’ : “美食天地”,
‘id’ : ‘product’,
‘children’ : [
{
name : “最新美食”,
id : ‘new’,
‘children’ : [
{
‘id’ : ‘yuecai’,
‘name’ : ‘粤菜’
},
{
‘id’ : ‘yuecai’,
‘name’ : ‘湘菜’
}
]
},
{
name : “热门菜谱”,
id : ‘hot’
}
]
},
{
‘name’ : “最新资讯”,
‘id’ : ‘news’
},
{
‘name’ : “招聘信息”,
‘id’ : ‘hr’
}, {
‘name’ : “联系我们”,
‘id’ : ‘contact’
}]
这里给出前一小节的答案，就是遍历 List 的，并增加了功能。

/**
     * 分析这棵树，为每个节点增加 fullPath 和 level 属性，分别表示完整的路径和层数
     *
     * @param list
     *            输入的树，必须为 List
     * @param superNode
     *            父级节点
     * @param level
     *            层数
     */
@SuppressWarnings(“unchecked”)
public void travelList(List<Map<String, Object» list, Map<String, Object> superNode, int level) {
for (Map<String, Object> map : list) {
if (map != null) {
String currerntPath = (superNode != null ? superNode.get(“fullPath”).toString() : “”) + “/” + map.get(id).toString();
map.put(“fullPath”, currerntPath);
map.put(“level”, level);

		// 记录父级信息

		List<String> supers = new ArrayList<>();

		map.put("supers", supers);

 

		if (superNode != null) {

			supers.addAll((List<String>) superNode.get("supers"));

			supers.add(superNode.get("fullPath") + ":" + superNode.get("name")); // 仅记录 id 和 name

		}

 

		if (map.get(children) != null && map.get(children) instanceof List)

			travelList((List<Map<String, Object>>) map.get(children), map, level + 1);

	}

} } https://blog.csdn.net/zhangxin09/article/details/76566021

在JSON中，分为6种对象：

数字（整数或浮点数）
字符串（在双引号中）
逻辑值（true 或 false）
数组（JsonArray）
对象（JsonObject）
null

JSON字符串的解析
以这个字符串为例：

{“success”:true,”id”:-10.5,”employees”:[{“firstName”:”Bill”,”lastName”:”Gates”},{“firstName”:”George”,”lastName”:”Bush”},{“firstName”:”Thomas”,”lastName”:”Carter”}]}

我们保证在只扫描一次整个的情况下，就将json结构解析成功。

传统的解析策略通常是通过词法分析，将json分为一个个的token，而这些token有着自己的类型和值；再通过语法分析构建一棵抽象语法树，进一步处理。比如”“是一种，true/false又是一种。

其实根本不需要这么复杂。依我看来，json的token只有五种：true/false/null（归为一种，因为它们是固定值）、number、string、object、array。也不用特别在意start和end的Token区分，比如 { 符号和 } 符号。从一个 { 符号开始，到下一个它对应的 } 符号都是属于同一个json object的。这里的 { 与 } 、[ 与 ] 符号都是一一对应的。
我设计了一个nextObject()方法，它可以解析出json字符串中的下一个对象，然后在适当的时候装配即可。

nextObject方法的实现
提取字符
public static boolean isSpace(char c){
return c == ‘ ‘ || c == ‘\r’ || c == ‘\n’;
}

//方法得到当前字符，忽略空格、换行符

private char getChar(){

    char c = json.charAt(pos);

    while(isSpace(c)){

        pos++;

        c = getCurrentChar();

    }

    return c;

}

上面方法是消耗掉所有空白字符，直到读取到一个非空白字符，isSpace方法用于判断一个字符是否属于空白字符，pos表示当前指针指向的那个字符。也就是说，DFA从起始状态开始，若读到一个空字符，会在起始状态不断循环，直到遇到非空字符，状态转移情况如下：

解析

根据提取到的字符，转入不同的解析方法中，

例如字符是t，说明值可能是true，只需检查后面三个字符，如果是r、u、e，则可以直接返回true。

字符是f，说明值可能是false，只需检查后面四个字符，如果是a、l、s、e，则可以直接返回false。

碰到 \”，说明是字符串，在下一个\”出现之前，把扫描出来的字符都当成字符串中的字符，放到一个StringBuilder中去。

碰到 [ 符号，说明是数组了，就需要new一个JsonArray，在下一个 ] 符号出现之前，调用nextObject方法，把解析到的对象都放到这个JsonArray里面去。

碰到 { 符号，说明是JsonObject，就new一个JsonObject，这里每次需要连续调用两次nextObject，第一次结果作为key，第二次结果作为value。放到JsonObject中去。

解析boolean、null值
这类值的字符串只有固定的三种true、false、null，是最好解析的。在扫描到第一个字符为t、f、n时，只需检测后续字符是否符合固定值就可以了。checkChars方法实现了这个功能，chars是固定的序列，如果检测通过则返回true，否则返回false。

复制代码
private boolean checkChars(char …chars){
for(char ch : chars){
char c = getCurrentCharNext(); //得到当前字符，包括空格、换行符。将指针指向下一个字符
if(Character.toLowerCase(ch) != Character.toLowerCase(c)){
return false;
}
}
return true;
}
复制代码

如果是true,就是checkChars('t','r','u','e')

解析数字
解析数字的实现是parseNumber方法，我们先new一个StringBuilder，向后扫描只要碰到0-9或者+-小数点，就添加到这个StringBuilder当中去，否则就StringBuilder.toString，将这个字符串转换成数字。

如果包含小数点，就用double，否则就用integer。

解析字符串
在json中字符串都是以双引号”开头，再以双引号”结尾的。当扫描到双引号”时，new一个StringBuilder，然后在下一个双引号”出现之前的每一个字符都需要添加到这个StringBuilder中去。需要注意的一点，字符串中是可能出现转义字符的。因此在扫描到一个字符为斜杠\时，需要取出下一个字符进行特殊处理。

解析JsonObject
连续调用两次nextObject，第一次结果作为key，第二次结果作为value。放到JsonObject中去。
注意逗号和冒号的处理。

JsonArray的解析
在下一个 ] 符号出现之前，递归调用nextObject方法，把解析到的对象都放到这个JsonArray里面去。

返回
由于nextObject只返回一个对象，我们用nextObject方法处理整个json字符串。那么nextObject方法就会得到你需要的JsonObject。

超大json对象的解析
在大数据量的json场景下，不必将整个json字符串全部解析成json object后再处理，而是通过迭代器模式我们可以在解析字符串的同时使用对象。这样可以大大的提高程序的执行效率。

扩展ObjectParser类，使其成为一个迭代器，
public class ObjectParser implements Iterator

public Object next(){

    return nextObject();

}



public boolean hasNext(){

    return pos < json.length();

}



@Override

public void remove() {



}

}

这样就可以边解析边使用对象了。

ObjectParser parser = new ObjectParser (“json”);
while(parser.hasNext()){
Object object = parser.next();
}

超大的json串，通常是以流的方式提供，我们不必要一次性将流字节全部读入内存，而是可以逐字符的解析。每次读取若干个字符，解析成对象；实现方式是使用BuffererReader，修改getChar等方法，每次读字符时从BuffererReader中读取。配合上面的迭代器模式，可考虑将一个BuffererReader封装成Iterator

https://www.cnblogs.com/xcr1234/p/7860069.html

https://blog.csdn.net/dxiaolai/article/details/76359332

https://blog.csdn.net/dxiaolai/article/details/76359332

JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式。相对于另一种数据交换格式 XML，JSON 有着诸多优点。比如易读性更好，占用空间更少等。在 web 应用开发领域内，得益于 JavaScript 对 JSON 提供的良好支持，JSON 要比 XML 更受开发人员青睐。所以作为开发人员，如果有兴趣的话，还是应该深入了解一下 JSON 相关的知识。本着探究 JSON 原理的目的，我将会在这篇文章中详细向大家介绍一个简单的JSON解析器的解析流程和实现细节。由于 JSON 本身比较简单，解析起来也并不复杂。所以如果大家感兴趣的话，在看完本文后，不妨自己动手实现一个 JSON 解析器。好了，其他的话就不多说了，接下来让我们移步到重点章节吧。

1. JSON 解析器实现原理
   JSON 解析器从本质上来说就是根据 JSON 文法规则创建的状态机，输入是一个 JSON 字符串，输出是一个 JSON 对象。一般来说，解析过程包括词法分析和语法分析两个阶段。词法分析阶段的目标是按照构词规则将 JSON 字符串解析成 Token 流，比如有如下的 JSON 字符串：

{
“name” : “小明”,
“age”: 18
}
结果词法分析后，得到一组 Token，如下：
{、 name、 :、 小明、 ,、 age、 :、 18、 }

图1 词法分析器输入输出

词法分析解析出 Token 序列后，接下来要进行语法分析。语法分析的目的是根据 JSON 文法检查上面 Token 序列所构成的 JSON 结构是否合法。比如 JSON 文法要求非空 JSON 对象以键值对的形式出现，形如 object = {string : value}。如果传入了一个格式错误的字符串，比如

{
“name”, “小明”
}
那么在语法分析阶段，语法分析器分析完 Token name后，认为它是一个符合规则的 Token，并且认为它是一个键。接下来，语法分析器读取下一个 Token，期望这个 Token 是 :。但当它读取了这个 Token，发现这个 Token 是 ,，并非其期望的:，于是文法分析器就会报错误。

图2 语法分析器输入输出

这里简单总结一下上面两个流程，词法分析是将字符串解析成一组 Token 序列，而语法分析则是检查输入的 Token 序列所构成的 JSON 格式是否合法。这里大家对 JSON 的解析流程有个印象就好，接下来我会详细分析每个流程。

2.1 词法分析
在本章开始，我说了词法解析的目的，即按照“构词规则”将 JSON 字符串解析成 Token 流。请注意双引号引起来词–构词规则，所谓构词规则是指词法分析模块在将字符串解析成 Token 时所参考的规则。在 JSON 中，构词规则对应于几种数据类型，当词法解析器读入某个词，且这个词类型符合 JSON 所规定的数据类型时，词法分析器认为这个词符合构词规则，就会生成相应的 Token。这里我们可以参考http://www.json.org/对 JSON 的定义，罗列一下 JSON 所规定的数据类型：

BEGIN_OBJECT（{）
END_OBJECT（}）
BEGIN_ARRAY（[）
END_ARRAY（]）
NULL（null）
NUMBER（数字）
STRING（字符串）
BOOLEAN（true/false）
SEP_COLON（:）
SEP_COMMA（,）
当词法分析器读取的词是上面类型中的一种时，即可将其解析成一个 Token。我们可以定义一个枚举类来表示上面的数据类型，如下：

public enum TokenType {
BEGIN_OBJECT(1),
END_OBJECT(2),
BEGIN_ARRAY(4),
END_ARRAY(8),
NULL(16),
NUMBER(32),
STRING(64),
BOOLEAN(128),
SEP_COLON(256),
SEP_COMMA(512),
END_DOCUMENT(1024);

TokenType(int code) {

    this.code = code;

}



private int code;



public int getTokenCode() {

    return code;

} } 在解析过程中，仅有 TokenType 类型还不行。我们除了要将某个词的类型保存起来，还需要保存这个词的字面量。所以，所以这里还需要定义一个 Token 类。用于封装词类型和字面量，如下：

public class Token {
private TokenType tokenType;
private String value;
// 省略不重要的代码
}
定义好了 Token 类，接下来再来定义一个读取字符串的类。如下：

public CharReader(Reader reader) {
this.reader = reader;
buffer = new char[BUFFER_SIZE];
}

/**

 * 返回 pos 下标处的字符，并返回

 * @return 

 * @throws IOException

 */

public char peek() throws IOException {

    if (pos - 1 >= size) {

        return (char) -1;

    }



    return buffer[Math.max(0, pos - 1)];

}



/**

 * 返回 pos 下标处的字符，并将 pos + 1，最后返回字符

 * @return 

 * @throws IOException

 */

public char next() throws IOException {

    if (!hasMore()) {

        return (char) -1;

    }



    return buffer[pos++];

}



public void back() {

    pos = Math.max(0, --pos);

}



public boolean hasMore() throws IOException {

    if (pos < size) {

        return true;

    }



    fillBuffer();

    return pos < size;

}



void fillBuffer() throws IOException {

    int n = reader.read(buffer);

    if (n == -1) {

        return;

    }



    pos = 0;

    size = n;

} } 有了 TokenType、Token 和 CharReader 这三个辅助类，接下来我们就可以实现词法解析器了。

public class Tokenizer {
private CharReader charReader;
private TokenList tokens;

public TokenList tokenize(CharReader charReader) throws IOException {

    this.charReader = charReader;

    tokens = new TokenList();

    tokenize();



    return tokens;

}



private void tokenize() throws IOException {

    // 使用do-while处理空文件

    Token token;

    do {

        token = start();

        tokens.add(token);

    } while (token.getTokenType() != TokenType.END_DOCUMENT);

}



private Token start() throws IOException {

    char ch;

    for(;;) {

        if (!charReader.hasMore()) {

            return new Token(TokenType.END_DOCUMENT, null);

        }



        ch = charReader.next();

        if (!isWhiteSpace(ch)) {

            break;

        }

    }



    switch (ch) {

        case '{':

            return new Token(TokenType.BEGIN_OBJECT, String.valueOf(ch));

        case '}':

            return new Token(TokenType.END_OBJECT, String.valueOf(ch));

        case '[':

            return new Token(TokenType.BEGIN_ARRAY, String.valueOf(ch));

        case ']':

            return new Token(TokenType.END_ARRAY, String.valueOf(ch));

        case ',':

            return new Token(TokenType.SEP_COMMA, String.valueOf(ch));

        case ':':

            return new Token(TokenType.SEP_COLON, String.valueOf(ch));

        case 'n':

            return readNull();

        case 't':

        case 'f':

            return readBoolean();

        case '"':

            return readString();

        case '-':

            return readNumber();

    }



    if (isDigit(ch)) {

        return readNumber();

    }



    throw new JsonParseException("Illegal character");

}



private Token readNull() {...}

private Token readBoolean() {...}

private Token readString() {...}

private Token readNumber() {...} } 上面的代码是词法分析器的实现，部分代码这里没有贴出来，后面具体分析的时候再贴。先来看看词法分析器的核心方法 start，这个方法代码量不多，并不复杂。其通过一个死循环不停的读取字符，然后再根据字符的类型，执行不同的解析逻辑。上面说过，JSON 的解析过程比较简单。原因在于，在解析时，只需通过每个词第一个字符即可判断出这个词的 Token Type。比如：

第一个字符是{、}、[、]、,、:，直接封装成相应的 Token 返回即可
第一个字符是n，期望这个词是null，Token 类型是NULL
第一个字符是t或f，期望这个词是true或者false，Token 类型是 BOOLEAN
第一个字符是”，期望这个词是字符串，Token 类型为String
第一个字符是0~9或-，期望这个词是数字，类型为NUMBER
正如上面所说，词法分析器只需要根据每个词的第一个字符，即可知道接下来它所期望读取的到的内容是什么样的。如果满足期望了，则返回 Token，否则返回错误。下面就来看看词法解析器在碰到第一个字符是n和”时的处理过程。先看碰到字符n的处理过程：

private Token readNull() throws IOException {
if (!(charReader.next() == ‘u’ && charReader.next() == ‘l’ && charReader.next() == ‘l’)) {
throw new JsonParseException(“Invalid json string”);
}

return new Token(TokenType.NULL, "null"); } 上面的代码很简单，词法分析器在读取字符n后，期望后面的三个字符分别是u,l,l，与 n 组成词 null。如果满足期望，则返回类型为 NULL 的 Token，否则报异常。readNull 方法逻辑很简单，不多说了。接下来看看 string 类型的数据处理过程：

private Token readString() throws IOException {
StringBuilder sb = new StringBuilder();
for (;;) {
char ch = charReader.next();
// 处理转义字符
if (ch == ‘\’) {
if (!isEscape()) {
throw new JsonParseException(“Invalid escape character”);
}
sb.append(‘\’);
ch = charReader.peek();
sb.append(ch);
// 处理 Unicode 编码，形如 \u4e2d。且只支持 \u0000 ~ \uFFFF 范围内的编码
if (ch == ‘u’) {
for (int i = 0; i < 4; i++) {
ch = charReader.next();
if (isHex(ch)) {
sb.append(ch);
} else {
throw new JsonParseException(“Invalid character”);
}
}
}
} else if (ch == ‘”’) { // 碰到另一个双引号，则认为字符串解析结束，返回 Token
return new Token(TokenType.STRING, sb.toString());
} else if (ch == ‘\r’ || ch == ‘\n’) { // 传入的 JSON 字符串不允许换行
throw new JsonParseException(“Invalid character”);
} else {
sb.append(ch);
}
}
}

private boolean isEscape() throws IOException {
char ch = charReader.next();
return (ch == ‘”’ || ch == ‘\’ || ch == ‘u’ || ch == ‘r’
|| ch == ‘n’ || ch == ‘b’ || ch == ‘t’ || ch == ‘f’);
}

private boolean isHex(char ch) {
return ((ch >= ‘0’ && ch <= ‘9’) || (‘a’ <= ch && ch <= ‘f’)
|| (‘A’ <= ch && ch <= ‘F’));
}
string 类型的数据解析起来要稍微复杂一些，主要是需要处理一些特殊类型的字符。JSON 所允许的特殊类型的字符如下：

"


\b
\f
\n
\r
\t
\u four-hex-digits
\/

最后一种特殊字符\/代码中未做处理，其他字符均做了判断，判断逻辑在 isEscape 方法中。在传入 JSON 字符串中，仅允许字符串包含上面所列的转义字符。如果乱传转义字符，解析时会报错。对于 STRING 类型的词，解析过程始于字符”，也终于”。所以在解析的过程中，当再次遇到字符”，readString 方法会认为本次的字符串解析过程结束，并返回相应类型的 Token。

上面说了 null 类型和 string 类型的数据解析过程，过程并不复杂，理解起来应该不难。至于 boolean 和 number 类型的数据解析过程，大家有兴趣的话可以自己看源码，这里就不在说了。

2.2 语法分析
当词法分析结束后，且分析过程中没有抛出错误，那么接下来就可以进行语法分析了。语法分析过程以词法分析阶段解析出的 Token 序列作为输入，输出 JSON Object 或 JSON Array。语法分析器的实现的文法如下：

object = {} | { members }
members = pair | pair , members
pair = string : value
array = [] | [ elements ]
elements = value | value , elements
value = string | number | object | array | true | false | null
语法分析器的实现需要借助两个辅助类，也就是语法分析器的输出类，分别是 JsonObject 和 JsonArray。代码如下：

public class JsonObject {

private Map<String, Object> map = new HashMap<String, Object>();



public void put(String key, Object value) {

    map.put(key, value);

}



public Object get(String key) {

    return map.get(key);

}



public List<Map.Entry<String, Object>> getAllKeyValue() {

    return new ArrayList<>(map.entrySet());

}



public JsonObject getJsonObject(String key) {

    if (!map.containsKey(key)) {

        throw new IllegalArgumentException("Invalid key");

    }



    Object obj = map.get(key);

    if (!(obj instanceof JsonObject)) {

        throw new JsonTypeException("Type of value is not JsonObject");

    }



    return (JsonObject) obj;

}



public JsonArray getJsonArray(String key) {

    if (!map.containsKey(key)) {

        throw new IllegalArgumentException("Invalid key");

    }



    Object obj = map.get(key);

    if (!(obj instanceof JsonArray)) {

        throw new JsonTypeException("Type of value is not JsonArray");

    }



    return (JsonArray) obj;

}



@Override

public String toString() {

    return BeautifyJsonUtils.beautify(this);

} }

public class JsonArray implements Iterable {

private List list = new ArrayList();



public void add(Object obj) {

    list.add(obj);

}



public Object get(int index) {

    return list.get(index);

}



public int size() {

    return list.size();

}



public JsonObject getJsonObject(int index) {

    Object obj = list.get(index);

    if (!(obj instanceof JsonObject)) {

        throw new JsonTypeException("Type of value is not JsonObject");

    }



    return (JsonObject) obj;

}



public JsonArray getJsonArray(int index) {

    Object obj = list.get(index);

    if (!(obj instanceof JsonArray)) {

        throw new JsonTypeException("Type of value is not JsonArray");

    }



    return (JsonArray) obj;

}



@Override

public String toString() {

    return BeautifyJsonUtils.beautify(this);

}



public Iterator iterator() {

    return list.iterator();

} } 语法解析器的核心逻辑封装在了 parseJsonObject 和 parseJsonArray 两个方法中，接下来我会详细分析 parseJsonObject 方法，parseJsonArray 方法大家自己分析吧。parseJsonObject 方法实现如下：

private JsonObject parseJsonObject() {
JsonObject jsonObject = new JsonObject();
int expectToken = STRING_TOKEN | END_OBJECT_TOKEN;
String key = null;
Object value = null;
while (tokens.hasMore()) {
Token token = tokens.next();
TokenType tokenType = token.getTokenType();
String tokenValue = token.getValue();
switch (tokenType) {
case BEGIN_OBJECT:
checkExpectToken(tokenType, expectToken);
jsonObject.put(key, parseJsonObject()); // 递归解析 json object
expectToken = SEP_COMMA_TOKEN | END_OBJECT_TOKEN;
break;
case END_OBJECT:
checkExpectToken(tokenType, expectToken);
return jsonObject;
case BEGIN_ARRAY: // 解析 json array
checkExpectToken(tokenType, expectToken);
jsonObject.put(key, parseJsonArray());
expectToken = SEP_COMMA_TOKEN | END_OBJECT_TOKEN;
break;
case NULL:
checkExpectToken(tokenType, expectToken);
jsonObject.put(key, null);
expectToken = SEP_COMMA_TOKEN | END_OBJECT_TOKEN;
break;
case NUMBER:
checkExpectToken(tokenType, expectToken);
if (tokenValue.contains(“.”) || tokenValue.contains(“e”) || tokenValue.contains(“E”)) {
jsonObject.put(key, Double.valueOf(tokenValue));
} else {
Long num = Long.valueOf(tokenValue);
if (num > Integer.MAX_VALUE || num < Integer.MIN_VALUE) {
jsonObject.put(key, num);
} else {
jsonObject.put(key, num.intValue());
}
}
expectToken = SEP_COMMA_TOKEN | END_OBJECT_TOKEN;
break;
case BOOLEAN:
checkExpectToken(tokenType, expectToken);
jsonObject.put(key, Boolean.valueOf(token.getValue()));
expectToken = SEP_COMMA_TOKEN | END_OBJECT_TOKEN;
break;
case STRING:
checkExpectToken(tokenType, expectToken);
Token preToken = tokens.peekPrevious();
/*
* 在 JSON 中，字符串既可以作为键，也可作为值。
* 作为键时，只期待下一个 Token 类型为 SEP_COLON。
* 作为值时，期待下一个 Token 类型为 SEP_COMMA 或 END_OBJECT
*/
if (preToken.getTokenType() == TokenType.SEP_COLON) {
value = token.getValue();
jsonObject.put(key, value);
expectToken = SEP_COMMA_TOKEN | END_OBJECT_TOKEN;
} else {
key = token.getValue();
expectToken = SEP_COLON_TOKEN;
}
break;
case SEP_COLON:
checkExpectToken(tokenType, expectToken);
expectToken = NULL_TOKEN | NUMBER_TOKEN | BOOLEAN_TOKEN | STRING_TOKEN
| BEGIN_OBJECT_TOKEN | BEGIN_ARRAY_TOKEN;
break;
case SEP_COMMA:
checkExpectToken(tokenType, expectToken);
expectToken = STRING_TOKEN;
break;
case END_DOCUMENT:
checkExpectToken(tokenType, expectToken);
return jsonObject;
default:
throw new JsonParseException(“Unexpected Token.”);
}
}

throw new JsonParseException("Parse error, invalid Token."); }

private void checkExpectToken(TokenType tokenType, int expectToken) {
if ((tokenType.getTokenCode() & expectToken) == 0) {
throw new JsonParseException(“Parse error, invalid Token.”);
}
}
parseJsonObject 方法解析流程大致如下：

读取一个 Token，检查这个 Token 是否是其所期望的类型
如果是，更新期望的 Token 类型。否则，抛出异常，并退出
重复步骤1和2，直至所有的 Token 都解析完，或出现异常
上面的步骤并不复杂，但有可能不好理解。这里举个例子说明一下，有如下的 Token 序列：

{、 id、 :、 1、 }

parseJsonObject 解析完 { Token 后，接下来它将期待 STRING 类型的 Token 或者 END_OBJECT 类型的 Token 出现。于是 parseJsonObject 读取了一个新的 Token，发现这个 Token 的类型是 STRING 类型，满足期望。于是 parseJsonObject 更新期望Token 类型为 SEL_COLON，即:。如此循环下去，直至 Token 序列解析结束或者抛出异常退出。

上面的解析流程虽然不是很复杂，但在具体实现的过程中，还是需要注意一些细节问题。比如：

在 JSON 中，字符串既可以作为键，也可以作为值。作为键时，语法分析器期待下一个 Token 类型为 SEP_COLON。而作为值时，则期待下一个 Token 类型为 SEP_COMMA 或 END_OBJECT。所以这里要判断该字符串是作为键还是作为值，判断方法也比较简单，即判断上一个 Token 的类型即可。如果上一个 Token 是 SEP_COLON，即:，那么此处的字符串只能作为值了。否则，则只能做为键。
对于整数类型的 Token 进行解析时，简单点处理，可以直接将该整数解析成 Long 类型。但考虑到空间占用问题，对于 [Integer.MIN_VALUE, Integer.MAX_VALUE] 范围内的整数来说，解析成 Integer 更为合适，所以解析的过程中也需要注意一下。

https://segmentfault.com/a/1190000010998941

https://github.com/code4wt/JSONParser

https://www.cnblogs.com/absfree/p/5502705.html
https://www.liaoxuefeng.com/article/994977272296736
https://www.zhihu.com/question/24640264/answer/80500016

http://json.org/json-zh.html
http://golang.org/pkg/encoding/json/

https://www.jianshu.com/p/4e206ee7dca0
https://github.com/square/moshi

Json解析器
https://blog.csdn.net/u013243347/article/details/81138443

https://tuanz1.github.io/post/nfa-dfa/

https://www.zhihu.com/question/53105355
https://www.cnblogs.com/absfree/p/5502705.html

https://blog.csdn.net/lixiaoxiong55/article/details/88777582
https://blog.csdn.net/itmrchen/article/details/90618468

golang 的一些json库对比分析
https://github.com/bitly/go-simplejson
在golang标准库的基础上做了一层包装
解析流程是：
1，将字符串解析成interface｛｝
2,通过类型推断获取对应的值
应用场景：
输入json不标准，导致部分字段解析失败，此包可以保证部分成功

https://github.com/mailru/easyjson
和官方包实现不同地方在于：
官方包Unmarshal函数输入是interface｛｝
因此需要通过反射获取对应feild ，设置值，效率比较低

easyjson的思路是提前通过代码生成器，生成定制化的解析函数
省去了反射环节，代码更高效，比如：
type person struct｛
Name string json :"name"
｝

官方包需要reflect方式获取name，然后去解析流里匹配
easyjson 在解析流里遇到了 name 直接给Name字段赋值

https://github.com/json-iterator/go
https://github.com/buger/jsonparser

Jsoniter 有三个不同的 api 用于不同的场合：
iterator-api：用于处理超大的输入
bind-api：日常最经常使用的对象绑定
any-api：lazy 解析大对象，具有 PHP Array 一般的使用体验

不同于其他json包的优化点
单次扫描
所有解析都是在字节数组流中直接在一次传递中完成的。单程有两个含义：

在大规模：迭代器api只是前进，你从当前点获得你需要的。没有回头路。
在微观尺度上：readInt或readString一次完成。例如，解析整数不是通过剪切字符串输出，然后解析字符串。相反，我们使用字节流直接计算int值。甚至readFloat或readDouble都以这种方式实现，但有例外。
最小化分配
在所有必要的手段上避免复制。例如，解析器有一个内部字节数组缓冲区，用于保存最近的字节。解析对象的字段名称时，我们不会分配新字节来保存字段名称。相反，如果可能，缓冲区将重用为切片。
Iterator实例本身保留了它使用的各种缓冲区的副本，并且可以通过使用新输入重置迭代器而不是创建全新迭代器来重用它们。

从stream中拉出来
输入可以是InputStream或io.Reader，我们不会将所有字节读入大数组。相反，解析是以块的形式完成的。当我们需要更多时，我们从流中拉出来。

认真对待string
如果处理不当，字符串解析就是性能杀手。我从jsonparser和dsljson学到的技巧是为没有转义字符的字符串采取快速路径。

对于golang，字符串是utf-8字节。构造字符串的最快方法是从[]byte直接转换为字符串，如果可以确保[]byte不会消失或被修改。

对于java，字符串是基于utf-16 char的。将utf8字节流解析为utf16字符串数组由解析器直接完成，而不是使用UTF8字符集。构造字符串的成本，简单地说是一个char数组副本。

基于Schema
与tokenizer api相比，Iterator api是活动的而不是被动的。它不解析令牌，然后分支。相反，在给定模式的情况下，我们确切地知道我们前面有什么，所以我们只是将它们解析为我们认为它应该是什么。如果输入不一致，那么我们会引发正确的错误。

跳过不同的路径
跳过一个object或array采取不同的路径是从jsonparser学到的。当我们跳过整个对象时，我们不关心嵌套字段名称。

表查找
一些计算，例如char’5’的int值可以提前完成。

其他
绑定到对象不使用反射api。而是取出原始指针interface{}，然后转换为正确的指针类型以设置值。例如：

((int)(ptr)) = iter.ReadInt()
另一个优化是我们知道有多少字段在解析结构，所以我们可以用不同的方式编写字段调度。对于没有领域，我们只是跳过。对于一个字段，if / else就足够了。2~4个字段切换案例。5个或更多字段，我们callback使用基于map的字段调度。

Golang版本没有使用，go generate因为我觉得它对新开发者不友好。我可能会添加go generate一个选项并对后续的版本进行优化。它可以更快。由于能够访问原始指针，golang数据绑定性能已经足够好了。正如我们从基准测试中看到的那样，手动绑定代码只是快一点。这种情况可能会改变，如果golang决定关闭它的内存布局以进行直接操作，或者如果我们可以摆脱虚拟方法引入的指针追逐，JIT可以优化更多。

后续
adapter：相当于json序列化和反序列化的工具类 直接使用即可通过一行代码完成相关的操作
iter: 迭代器的定义 用于json内容的解析
stream: 通过流的方式操作json
config: 按需定义了一些默认的操作配置类 默认已提供多个config，自己也可以通过jsoniter.Config{CaseSensitive: true}.Froze()定制需要的json API实例
pool:缓存池 按需缓存不同的实例对象 减少内存的分配以及资源的占用提高性能
reflect:反射工具类 针对标准库中的reflect包的反射相关接口进行优化 增强其原有的性能
any：惰性json实现保持[]byte并延迟解析，把 json 解析为 Any 对象，然后就可以直接使用了。使用体验和 PHP 的 json_decode 差不多。