从零开始实现一个简易json解析器

吁寂 · 2026-2-11 21:20:12

从零开始实现一个简易json解析器

1. MySimpleJsonParser 介绍与整体设计

最近在学习编译原理相关的知识。为了加深对词法分析、语法分析阶段中诸如有限自动机、自顶向下语法分析、AST 等概念的理解，我选择实现一个json解析器作为练手机会。

相比直接实现一门完整的编程语言，将json解析作为练手对象有几个明显优势：

几乎零额外学习成本：json作为一种轻量级的数据交换格式是日常开发中使用最频繁的数据格式之一。
文法足够简单：对于编译原理入门者来说，若选择的语言太复杂，很容易在词法/语法规则上被劝退；而json的词法和语法比较规整，语法分析时通常只需根据下一个token即可决定AST的构造方向。
无需运行时：json不是编程语言，其完全不需要后端的运行时。只要能把json文本转换成正确的AST就已经算完成任务，在此基础上实现一个基于AST的Pretty JSON输出，就能产生一定的成就感。

在本篇博客中，我们将基于java语言，不依赖任何第三方库，从零开始实现一个简单的json解析器：MySimpleJsonParser。其包括以下几个主要模块：

StaticJsonLexer：一次性解析出全部token的静态json词法分析器
StreamJsonLexer：按需惰性解析token的流式json词法分析器
RecursiveJsonParser：基于递归的json语法解析器
StackBaseJsonParser：基于显式堆栈的json语法解析器（非递归）
AST结构：JsonElement及其子类，并基于AST生成Pretty JSON字符串的工具方法

2. 从文法到词法分析器：手写 json lexer

词法分析阶段的任务是：将原始的字符流，按照json的词法规则，转换为token流。之后的语法分析会在token流的基础上按文法规则构建AST。
2.1 json文法与基本结构

根据json官方文档，json中主要包含以下几类结构：

string：由双引号包住的Unicode字符串，可包含转义字符。一个字符（character）也可以是一个单独的字符串（character string）。
number：以0或-开头，可以是整数、小数、、负数或者是包含一个E/e符号的指数。
object：以“{” 开头，以“}”结尾。
array：以“[” 开头，以“]”结尾。
value：可以是string、number、true(关键字)、false(关键字)、null(关键字)、object或者array。
whitespace：由任意个space空格、linefeed换行符、carriage return回车符以及tab制表符组成，本身无意义，仅起到分割的作用。

仔细分析后，发现string结构、number结构和whitespace结构以及{、}、[、] 这类符号都是基本结构，是自身无法再嵌套其它结构的基本单元，因此其都是最终AST中的叶子节点，而object、array和value都是可以互相嵌套的复合结构，其都是AST中的非叶子节点。
对于这些可嵌套的非AST叶子节点，必须在语法分析中才能完成解析；而string结构、number结构、false、true、null关键字以及“{”、“]”等特殊符号，则适合在词法分析中完成解析。
因为json语法中，无论原始的json字符串中一个number字面量有多复杂(比如-2.03214e+6605218)，在语法分析中都只需要当做一个完整的number类型的token来处理即可。
词法分析专注于局部，将原始的字符流按照词法规则正确的转换为token流；而语法分析则专注于将token流按照语法规则转换为正确的AST树结构。
通过将整个分析流程，有机的分解为词法分析和语法分析等等不同步骤，每个步骤都依赖于前一个步骤的产出的分层设计，能够很好的控制解析器整体的复杂度，方便调试的同时性能上也有很大的提升。
因此，除了少数非常简单的语言外，几乎所有的编译器都会采用分层的架构来实现整体的功能。

2.2 token类型定义

从文法角度，json中允许的token类型大致可分为三类：

特殊符号：诸如“{”、“}”、“[”、“]”、“,”,“:”,“"”等独立的字符是json中的特殊符号
关键字：完整且独立的true、false、null被视为关键字
字面量：number、string这两种复杂字符流字面量

因此我们可以先定义出json的token类型枚举。其中EOF类型是额外的，用于在完成整个字符流的词法分析后，追加到token流的最后，标志着token流的结束。

public enum JsonTokenTypeEnum { LEFT_BRACE("{"), RIGHT_BRACE("}"), LEFT_BRACKET("["), RIGHT_BRACKET("]"), COMMA(","), COLON(":"), TRUE("true"), FALSE("false"), NULL("null"), STRING("string"), NUMBER("number"), EOF("EOF"), ; private final String key; JsonTokenTypeEnum(String key) { this.key = key; } public String getKey() { return key; }}

复制代码

2.3 词法分析器整体框架与特殊字符的词法分析

现在我们已经知道诸如“{”、“]”等独立字符是json中的特殊符号，但是当我们在字符流中遇到了一个“{”字符时，并不能无脑的将其作为一个LEFT_BRACE类型的token来处理。因为如果其是被双引号包裹的，作为string类型token内容的一部分，那么就并不能将其直接当做独立的token来对待。
所以，词法分析中一般使用有限状态自动机来解决此类“同一字符在不同上下文含义不同”的问题，在判断如何处理字符流时并不仅仅取决于下一个字符是什么，而还要结合当前自动机的状态来决定行为。
以上述对“{”字符的处理为例，如果是在初始化状态下(已经完成了一个完整token的解析,准备开始解析下一个新token)，碰到“{”字符时可以确定的将其转化为LEFT_BRACE类型的token，但是当自动机处于string类型token的解析状态时，则需要将其作为string类型token内容的一部分。
json词法分析自动机总览图

基于官方文档中的json文法规则，我们可以设计出一个如下图所示的json有限状态自动机来实现我们的词法分析。

在json解析一开始，自动机位于状态0，随后便会基于字符流的下一个字符的类型进行状态转换，在读取到诸如“{”、“[”、“,”等独立符号时，便会直接接收该字符，推进字符流，同时生成对应类型的token。
在完整的解析出一个完整token后，自动机便会重新回到状态0，准备尝试解析下一个新的token。状态0只能合法的接收有限种类的字符，对于不符合json文法的字符将认为当前字符流不是合法的json字符串而直接报错，退出解析。
对于更复杂的string类型、number类型token的解析，我们放在后面的小节再展开，总览图中暂时省略。

静态的词法分析器实现

public class StaticJsonLexer extends AbstractJsonLexer{ public StaticJsonLexer(String jsonString) { super(jsonString); } /** * 一次完整的扫描，非流式的处理 * */ public List doLex(){ char[] chars = super.jsonStringArray; // 相当于是状态0 while(doLexContext.currentIndex < chars.length){ char ch = chars[doLexContext.currentIndex]; switch(ch){ case '{': doLexContext.tokenCollector.add(new JsonToken(JsonTokenTypeEnum.LEFT_BRACE)); doLexContext.currentIndex++; break; case '}': doLexContext.tokenCollector.add(new JsonToken(JsonTokenTypeEnum.RIGHT_BRACE)); doLexContext.currentIndex++; break; case '[': doLexContext.tokenCollector.add(new JsonToken(JsonTokenTypeEnum.LEFT_BRACKET)); doLexContext.currentIndex++; break; case ']': doLexContext.tokenCollector.add(new JsonToken(JsonTokenTypeEnum.RIGHT_BRACKET)); doLexContext.currentIndex++; break; case ',': doLexContext.tokenCollector.add(new JsonToken(JsonTokenTypeEnum.COMMA)); doLexContext.currentIndex++; break; case ':': doLexContext.tokenCollector.add(new JsonToken(JsonTokenTypeEnum.COLON)); doLexContext.currentIndex++; break; case '"': doLexContext.tokenCollector.add(parseString(chars, doLexContext)); break; case 't': // 尝试解析true关键字 doLexContext.tokenCollector.add(parseTrueKeyword(chars, doLexContext)); break; case 'f': // 尝试解析false关键字 doLexContext.tokenCollector.add(parseFalseKeyword(chars, doLexContext)); break; case 'n': // 尝试解析null关键字 doLexContext.tokenCollector.add(parseNullKeyword(chars, doLexContext)); break; default: // 其它case if(ch == '-' || CommonStringUtil.is0_9(ch)){ // number解析 JsonToken numberToken = parseNumber(chars, doLexContext); doLexContext.tokenCollector.add(numberToken); break; }else if(CommonStringUtil.isWhitespace(ch)){ // whiteSpace 直接跳过 doLexContext.currentIndex++; break; }else{ throw new MuJsonParserException("unexpected character: " + ch + " at index " + doLexContext.currentIndex); } } } // 最后加上EOF doLexContext.tokenCollector.add(new JsonToken(JsonTokenTypeEnum.EOF)); return doLexContext.tokenCollector; }}

复制代码

抽象父类AbstractJsonLexer封装了string/number/keyword等具体类型的公共解析逻辑：

public abstract class AbstractJsonLexer { protected final char[] jsonStringArray; protected final DoLexContext doLexContext; public AbstractJsonLexer(String jsonString) { this.jsonStringArray = jsonString.toCharArray(); this.doLexContext = new DoLexContext(); } protected JsonToken parseNumber(char[] chars, DoLexContext doLexContext){ // number类型的内容 String numberStr = new NumberLexStatemachine().tryParse(chars,doLexContext); return new JsonToken(JsonTokenTypeEnum.NUMBER, numberStr); } protected JsonToken parseString(char[] chars, DoLexContext doLexContext){ // string类型的内容 String stringStr = new StringLexStatemachine().tryParse(chars,doLexContext); return new JsonToken(JsonTokenTypeEnum.STRING, stringStr); } protected JsonToken parseTrueKeyword(char[] chars, DoLexContext doLexContext){ // true关键字 String stringStr = new KeywordTrueLexStatementMachine().tryParse(chars,doLexContext); return new JsonToken(JsonTokenTypeEnum.TRUE, stringStr); } protected JsonToken parseFalseKeyword(char[] chars, DoLexContext doLexContext){ // false关键字 String stringStr = new KeywordFalseLexStatementMachine().tryParse(chars,doLexContext); return new JsonToken(JsonTokenTypeEnum.FALSE, stringStr); } protected JsonToken parseNullKeyword(char[] chars, DoLexContext doLexContext){ // null关键字 String stringStr = new KeywordNullLexStatementMachine().tryParse(chars,doLexContext); return new JsonToken(JsonTokenTypeEnum.NULL, stringStr); }}

复制代码

为了支持后续流式的词法分析器，静态的词法分析器StaticJsonLexer继承自AbstractJsonLexer类，构造方法中接收一个字符串，并通过方法doLex进行解析，返回一次性完整解析字符串后的token列表。
doLex方法中是一个while循环，每一次循环开始都相当于是自动机位于状态0，在解析时会通过自增currentIndex不断地推进字符流，成功解析出完整的token后便会将新的token保存到上下文中的tokenCollector中。只有在解析报错或者成功完成了整个字符串的解析后才会退出循环。
在正常退出while循环后，doLex方法返回前token集合的尾部会追加一个特殊的EOF类型的token，用于告知下一阶段的parser已经解析到了token流的末尾，该结束解析了。

2.4 number类型的词法分析

number的词法规则相对复杂，因为number类型作为json中表示数字的组件，其可以是整数，也可以是小数、负数，同时还可以是带符号e/E的指数形式。
json number类型token的词法规则

number integer fraction exponentinteger digit onenine digits '-' digit '-' onenine digitsdigits digit digit digitsdigit '0' onenineonenine '1' . '9'fraction "" '.' digitsexponent "" 'E' sign digits 'e' sign digitssign "" '+' '-'

复制代码

基于上述词法规则，我们可以构造出如下图所示的用于解析number类型token的状态自动机。
number类型解析的状态自动机示意图

设计好上述的状态自动机后，就可以按照图中的状态转移关系手写一个简单的状态机来解析number类型的token了。
number类型解析状态机实现源码

public class NumberLexStatemachine extends LexStatementMachine{ private static final Map staticFinalStateMap; private static final LexStateHandler[] lexStateHandlers; static{ staticFinalStateMap = new HashMap(); staticFinalStateMap.put(-1,true); staticFinalStateMap.put(1,true); staticFinalStateMap.put(2,false); staticFinalStateMap.put(3,true); staticFinalStateMap.put(4,true); staticFinalStateMap.put(5,false); staticFinalStateMap.put(6,true); staticFinalStateMap.put(7,false); staticFinalStateMap.put(8,false); staticFinalStateMap.put(9,true); lexStateHandlers = new LexStateHandler[]{ new State0Handler(), new State1Handler(), new State2Handler(), new State3Handler(), new State4Handler(), new State5Handler(),new State6Handler(),new State7Handler(),new State8Handler(),new State9Handler() }; } public NumberLexStatemachine() { this.stateHandlers = lexStateHandlers; this.isFinalStateMap = staticFinalStateMap; } private static abstract class NumberLexStateHandler implements LexStateHandler { @Override public int processInState(char[] chars, DoLexContext doLexContext, LexStatementMachine lexStatementMachine, StringBuilder oneTokenAcceptResult) { char currentChar = chars[doLexContext.currentIndex]; // whitespace符号以及number后合法的终结符 if(CommonStringUtil.isWhitespace(currentChar) || currentChar == ']' || currentChar == '}' || currentChar == ',' || currentChar == ':'){ if(lexStatementMachine.currentStateIsFinal()){ // 结束number的解析 return -1; }else{ // 遇到了分隔符，但是当前number解析的状态不是终态，无法转换为一个合法的number类型的token，抛异常 throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } } return doProcessInState(currentChar,doLexContext, oneTokenAcceptResult); } abstract int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult); } private static class State0Handler extends NumberLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { if(currentChar == '0'){ // accept accept(currentChar,doLexContext,oneTokenAcceptResult); // 进入状态1 return 1; } if(currentChar == '-'){ // accept accept(currentChar,doLexContext,oneTokenAcceptResult); // 进入状态2 return 2; } if(CommonStringUtil.is1_9(currentChar)){ // accept accept(currentChar,doLexContext,oneTokenAcceptResult); // 进入状态3 return 3; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } } private static class State1Handler extends NumberLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { if(currentChar == '.'){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 5; } if(currentChar == 'e' || currentChar == 'E'){ accept(currentChar,doLexContext, oneTokenAcceptResult); return 7; } throw new MuJsonParserException("unexpected char '" + currentChar + "', index=" + doLexContext.currentIndex); } } private static class State2Handler extends NumberLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { if(currentChar == '0'){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 1; } if(CommonStringUtil.is1_9(currentChar)){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 3; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } } private static class State3Handler extends NumberLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { if(currentChar == '.'){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 5; } if(currentChar == 'e' || currentChar == 'E'){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 7; } if(CommonStringUtil.is0_9(currentChar)){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 4; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } } private static class State4Handler extends NumberLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext,StringBuilder oneTokenAcceptResult) { if(currentChar == '.'){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 5; } if(currentChar == 'e' || currentChar == 'E'){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 7; } if(CommonStringUtil.is0_9(currentChar)){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 4; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } } private static class State5Handler extends NumberLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { if(CommonStringUtil.is0_9(currentChar)){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 6; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } } private static class State6Handler extends NumberLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext,StringBuilder oneTokenAcceptResult) { if(CommonStringUtil.is0_9(currentChar)){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 6; } if(currentChar == 'e' || currentChar == 'E'){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 7; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } } private static class State7Handler extends NumberLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext,StringBuilder oneTokenAcceptResult) { if(CommonStringUtil.is0_9(currentChar)){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 9; } if(currentChar == '-' || currentChar == '+'){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 8; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } } private static class State8Handler extends NumberLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { if(CommonStringUtil.is0_9(currentChar)){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 9; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } } private static class State9Handler extends NumberLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { if(CommonStringUtil.is0_9(currentChar)){ accept(currentChar,doLexContext,oneTokenAcceptResult); return 9; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } }}

复制代码

public abstract class LexStatementMachine { protected int currentState = 0; protected StringBuilder oneTokenAcceptResult = new StringBuilder(); protected LexStateHandler[] stateHandlers; protected Map isFinalStateMap; public String tryParse(char[] chars, DoLexContext doLexContext){ doParse(chars,doLexContext); boolean isFinalState = isFinalStateMap.get(currentState); if(isFinalState){ return oneTokenAcceptResult.toString(); }else{ throw new MuJsonParserException(String.format("currentState is not finalState! acceptResult=%s, acceptResult=%s",currentState, oneTokenAcceptResult)); } } public boolean currentStateIsFinal(){ return isFinalStateMap.get(currentState); } protected static void accept(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult){ oneTokenAcceptResult.append(currentChar); doLexContext.currentIndex++; } private void doParse(char[] chars, DoLexContext doLexContext){ // 一进来是状态0 while(doLexContext.currentIndex < chars.length){ if(currentState == -1){ // 遇到了合法的分隔符号，退出token解析 return; } if(currentState >= stateHandlers.length){ // 有bug throw new MuJsonParserException(String.format("unknown state! currentState=%s",currentState)); } LexStateHandler targetStateHandler = stateHandlers[currentState]; currentState = targetStateHandler.processInState(chars,doLexContext,this,oneTokenAcceptResult); } }}

复制代码

NumberLexStatemachine继承自父类LexStatementMachine。在LexStatementMachine中与doLex方法类似，也是一个while循环来反复的处理每一次的状态跳转。
子类NumberLexStatemachine定义了一系列的LexStateHandler状态处理器，每一个状态处理器都对应状态机示意图中的一个状态。
每一个LexStateHandler中的功能都比较类似，即决定在当前状态下自己能够接收的字符类型，以及控制在合法接收字符流当前字符后应该跳转的下一个状态是什么。
在合法接收字符时，会修改上下文中的当前字符指针以推进字符流，同时将接受到的当前合法字符追加到oneTokenAcceptResult中。
如果遇到了合法的结束分隔符，比如whitespace或者“}”、“]”之类的字符，且当前状态是属于number解析的终态，则NumberLexStateHandler会返回-1，终止当前token的解析。(比如{"number":-123.0}结束时的状态是6，6是终态，所以其是合法的json串)
如果状态处理器中遇到当前状态下不合法的字符，或者在退出解析时当前状态不属于number解析的终态，说明当前字符串不是合法的json串，则会直接抛出异常，退出词法解析。(比如{"number":-123.}结束时的状态是5,5不是终态，所以其是不合法的json串)
NumberLexStatemachine状态机正常退出当前number类型token后，返回收集到的所有字符oneTokenAcceptResult，作为number类型的字面量返回。

2.5 string类型的词法分析

string类型的词法规则相比之下比较简单，要求以双引号开头，并以双引号结尾即可，但需要额外处理转义字符相关的逻辑。
json string类型token的词法规则

string '"' characters '"'characters "" character characterscharacter '0020' . '10FFFF' - '"' - '\' '\' escapeescape '"' '\' '/' 'b' 'f' 'n' 'r' 't' 'u' hex hex hex hexhex digit 'A' . 'F' 'a' . 'f'

复制代码

基于上述词法规则，我们构造出如下图所示的用于解析string类型token的状态自动机。
string类型解析的状态自动机示意图

string类型解析状态机实现源码

public class StringLexStatemachine extends LexStatementMachine{ private static final Map staticFinalStateMap; private static final LexStateHandler[] lexStateHandlers; static{ staticFinalStateMap = new HashMap(); staticFinalStateMap.put(-1,true); staticFinalStateMap.put(1,false); staticFinalStateMap.put(2,true); staticFinalStateMap.put(3,false); staticFinalStateMap.put(4,false); staticFinalStateMap.put(5,false); staticFinalStateMap.put(6,false); staticFinalStateMap.put(7,false); lexStateHandlers = new LexStateHandler[]{ new State0Handler(),new State1Handler(),new State2Handler(),new State3Handler(),new State4Handler(), new State5Handler(),new State6Handler(),new State7Handler()}; } public StringLexStatemachine() { this.stateHandlers = lexStateHandlers; this.isFinalStateMap = staticFinalStateMap; } private static abstract class StringLexStateHandler implements LexStateHandler { @Override public int processInState(char[] chars, DoLexContext doLexContext, LexStatementMachine lexStatementMachine, StringBuilder oneTokenAcceptResult) { char currentChar = chars[doLexContext.currentIndex]; return doProcessInState(currentChar,doLexContext,oneTokenAcceptResult); } abstract int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult); } private static class State0Handler extends StringLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { if(currentChar == '"'){ // accept accept(currentChar,doLexContext,oneTokenAcceptResult); // 进入状态1 return 1; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } } private static class State1Handler extends StringLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { if(currentChar == '"'){ // accept accept(currentChar,doLexContext,oneTokenAcceptResult); // 进入状态2 return 2; } if(currentChar == '\\'){ // accept accept(currentChar,doLexContext,oneTokenAcceptResult); // 进入状态3 return 3; } // 控制字符是不合法的，不能出现在string中 if (currentChar < 0x20) { throw new MuJsonParserException("unexpected control char " + currentChar + " in string, " + doLexContext.currentIndex); } // 除了["]和[\]两个字符，别的都当做字符串的一部分接收 // accept accept(currentChar,doLexContext,oneTokenAcceptResult); return 1; } } private static class State2Handler extends StringLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { // 终态，完成一个string的解析，直接退出 return -1; } } private static class State3Handler extends StringLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { // 合法的转义字符 if(currentChar == '"' || currentChar == '\\' || currentChar == '/' || currentChar == 'b' || currentChar == 'f' || currentChar == 'n' || currentChar == 'r' || currentChar == 't'){ // 接收，回到状态1 accept(currentChar,doLexContext,oneTokenAcceptResult); return 1; } if(currentChar == 'u'){ // 特殊case 要求后面连续4个hex字符 '\\u hex hex hex hex' accept(currentChar,doLexContext,oneTokenAcceptResult); return 4; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } } private static class State4Handler extends StringLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { if(CommonStringUtil.isHex(currentChar)){ // 接收，进入状态5 accept(currentChar,doLexContext,oneTokenAcceptResult); return 5; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } } private static class State5Handler extends StringLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { if(CommonStringUtil.isHex(currentChar)){ // 接收，进入状态6 accept(currentChar,doLexContext,oneTokenAcceptResult); return 6; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } } private static class State6Handler extends StringLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { if(CommonStringUtil.isHex(currentChar)){ // 接收，进入状态7 accept(currentChar,doLexContext,oneTokenAcceptResult); return 7; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } } private static class State7Handler extends StringLexStateHandler { @Override int doProcessInState(char currentChar, DoLexContext doLexContext, StringBuilder oneTokenAcceptResult) { if(CommonStringUtil.isHex(currentChar)){ // 连续接收了4个hex字符，回到状态1 accept(currentChar,doLexContext,oneTokenAcceptResult); return 1; } throw new MuJsonParserException("unexpected char " + currentChar + " " + doLexContext.currentIndex); } }}

复制代码

string类型token解析的状态机与number类型的工作模式类似，同样继承自LexStatementMachine，并且定义了一系列的对应状态机示意图中各个状态的LexStateHandler。

2.6 关键字的词法分析

最后，json的词法分析中还有关键字类型的token解析需要实现。所幸json的文法非常简单，只有true、false和null三个关键字，且这三个关键字的f(1)都不相同，也与其它类型的token的f(1)不相同。
因此，在词法解析时，我们可以很简单的根据第一个字符来决定要解析的关键字类型，在状态0时，如果碰到字符t就尝试解析true类型的token；碰到字符f就尝试解析false类型的token；碰到字符n就尝试解析null类型的token。
因此我们可以很简单的得到如下图所示的三个关键字的状态自动机。
关键字类型解析的状态自动机示意图

keyword类型解析状态机实现源码

public abstract class KeywordLexStatementMachine extends LexStatementMachine{ protected final String keyword; public KeywordLexStatementMachine(String keyword) { this.keyword = keyword; } protected static Map buildIsFinalStateMap(String keyword){ Map isFinalStateMap = new HashMap(keyword.length() + 1); isFinalStateMap.put(-1,true); for(int i=0; i= jsonStringArray.length){ return new JsonToken(JsonTokenTypeEnum.EOF); } while(true) { char ch = jsonStringArray[doLexContext.currentIndex]; // 每一次尝试解析一个完整的token前，都是状态0 switch (ch) { case '{': doLexContext.currentIndex++; return new JsonToken(JsonTokenTypeEnum.LEFT_BRACE); case '}': doLexContext.currentIndex++; return new JsonToken(JsonTokenTypeEnum.RIGHT_BRACE); case '[': doLexContext.currentIndex++; return new JsonToken(JsonTokenTypeEnum.LEFT_BRACKET); case ']': doLexContext.currentIndex++; return new JsonToken(JsonTokenTypeEnum.RIGHT_BRACKET); case ',': doLexContext.currentIndex++; return new JsonToken(JsonTokenTypeEnum.COMMA); case ':': doLexContext.currentIndex++; return new JsonToken(JsonTokenTypeEnum.COLON); case '"': return parseString(jsonStringArray, doLexContext); case 't': // 尝试解析true关键字 return parseTrueKeyword(jsonStringArray, doLexContext); case 'f': // 尝试解析false关键字 return parseFalseKeyword(jsonStringArray, doLexContext); case 'n': // 尝试解析null关键字 return parseNullKeyword(jsonStringArray, doLexContext); default: // 走其它case break; } // 其它case if (CommonStringUtil.is0_9(ch) || ch == '-') { // number解析 return parseNumber(jsonStringArray, doLexContext); } else if (CommonStringUtil.isWhitespace(ch)) { // whiteSpace 直接跳过 doLexContext.currentIndex++; } else{ throw new MuJsonParserException("unexpected character: " + ch + ",charIndex=" + doLexContext.currentIndex); } } }}

复制代码

public class StreamJsonTokenReader implements JsonTokenReader { private int currentIndex; private final StreamJsonLexer streamJsonLexer; private JsonToken peekToken; private boolean hasNextToken; public StreamJsonTokenReader(String jsonString) { this.currentIndex = 0; this.hasNextToken = true; this.streamJsonLexer = new StreamJsonLexer(jsonString); } @Override public boolean hasNextToken() { return hasNextToken; } @Override public JsonToken nextToken() { JsonToken nextToken = getNextToken(); if(nextToken.getType() == JsonTokenTypeEnum.EOF){ hasNextToken = false; } currentIndex++; return nextToken; } private JsonToken getNextToken() { if(peekToken != null){ JsonToken nextToken = peekToken; this.peekToken = null; return nextToken; } return streamJsonLexer.doLex(); } @Override public JsonToken peek() { if(peekToken == null) { peekToken = streamJsonLexer.doLex(); } return peekToken; } @Override public int currentIndex() { return currentIndex; }}

复制代码

流式的词法解析器StreamJsonLexer的核心工作原理与之前已经实现的静态的StaticJsonLexer别无二致，其底层依赖的代码都是相同的。
最大的区别在于解析出一个完整的token后，在维护当前字符流下标的同时提前终止了后续的词法分析。在StreamJsonTokenReader调用nextToken时，才会按需的惰性解析新的token并返回。
流式的词法解析毫无疑问是性能更好的，主流的json解析器也都是流式的解析。但静态的词法解析更容易理解，也更容易调试，所以在一开始介绍词法分析原理时，我们先实现了静态的词法分析，将其作为基础，略微的改造后便实现了流式的词法解析。

6. 基于堆栈实现的json语法解析

第二个性能问题则是基于递归实现的json语法解析器受限于较小的线程栈空间，无法处理嵌套层级非常深的json串。

我们知道，一个普通的java进程通常都含有大量的线程，因此给每个线程分配的线程栈通常都比较小，比如1m。而递归实现的语法解析器，在每深入一个层次的json子树时便会向栈上压入一些局部变量，当极端情况下要解析的json串层次过深时，则会出现StackOverflowError，导致解析失败。
而内存的堆通常都是以GB为单位的，因此如果把递归中隐式压栈的解析逻辑转换为等价的显式基于内存堆的压栈，则可以很好的解决线程栈过小无法处理大深度json串的问题了。

基于堆栈的语法解析状态自动机示意图

为了尽可能的将状态转移与递归实现的逻辑保持一致，堆栈的状态自动机依然冗余了两个状态(obj-0和arr-0)。
可以看到，基于堆栈的状态自动机会在array与object的解析状态中互相转移，相当于将之前递归实现的各个状态自动机的子状态图合并为了一个大而全的状态自动机。
同时，由于还涉及了手动模拟的入栈与出栈处理(obj-2，obj-4，arr-1，arr-2)，因此整体的复杂度比起递归实现要高出一个量级。

json根节点解析状态自动机实现源码

/** * 基于堆栈的，非递归的json语法解析器 * */public class StackBaseJsonParser extends JsonParser { private final JsonParseStack parseStack = new JsonParseStack(); private StackBaseJsonParserStatusEnum currentStatus; public StackBaseJsonParser(JsonTokenReader tokenReader) { super(tokenReader); this.currentStatus = StackBaseJsonParserStatusEnum.START_PARSE; } private void accept(){ jsonTokenReader.nextToken(); } @Override public JsonElement doParse() { while(jsonTokenReader.hasNextToken()){ JsonToken token = jsonTokenReader.peek(); if(currentStatus == StackBaseJsonParserStatusEnum.END_PARSE){ break; } switch (currentStatus){ case START_PARSE: processInStartParse(token); break; case PARSE_OBJECT_0: processInParseObject0(token); break; case PARSE_OBJECT_1: processInParseObject1(token); break; case PARSE_OBJECT_2: processInParseObject2(token); break; case PARSE_OBJECT_3: processInParseObject3(token); break; case PARSE_OBJECT_4: processInParseObject4(token); break; case PARSE_OBJECT_5: processInParseObject5(token); break; case PARSE_OBJECT_6: processInParseObject6(token); break; case PARSE_ARR_0: processInParseArr0(token); break; case PARSE_ARR_1: processInParseArr1(token); break; case PARSE_ARR_2: processInParseArr2(token); break; case PARSE_ARR_3: processInParseArr3(token); break; default: throw new MuJsonParserException("Unexpected currentStatus: " + currentStatus); } } // 如果json字符串是合法的，那么最后栈顶必然是有且唯一的一个JsonElement类型的对象 if(this.parseStack.size() != 1){ throw new MuJsonParserException("after parse，stack element size > 1! stack=" + this.parseStack); } JsonParseStackValue object = this.parseStack.pop(); return (JsonElement) object.getValue(); } private void processInStartParse(JsonToken token){ if (token.getType() == JsonTokenTypeEnum.LEFT_BRACE) { this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_0; this.parseStack.push(new JsonParseStackValue(JsonParseStackValueTypeEnum.JSON_OBJECT,new JsonObject())); return; } if (token.getType() == JsonTokenTypeEnum.LEFT_BRACKET) { this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_ARR_0; this.parseStack.push(new JsonParseStackValue(JsonParseStackValueTypeEnum.JSON_ARRAY,new JsonArray())); return; } if (token.getType().isPrimitiveValue()) { accept(); this.currentStatus = StackBaseJsonParserStatusEnum.END_PARSE; this.parseStack.push(new JsonParseStackValue(JsonParseStackValueTypeEnum.JSON_PRIMITIVE,new JsonPrimitiveStr(token.getContent()))); return; } // 第一个token，不属于json规则的f(1)集合 throw new MuJsonParserException("unexpected start json token! token=" + jsonTokenReader.currentIndex()); } private void processInParseObject0(JsonToken token){ if(token.getType() != JsonTokenTypeEnum.LEFT_BRACE){ throw new MuJsonParserException("unexpected token! index=" + jsonTokenReader.currentIndex()); } accept(); this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_1; } private void processInParseObject1(JsonToken token){ if(token.getType() == JsonTokenTypeEnum.RIGHT_BRACE){ this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_2; return; } if(token.getType() == JsonTokenTypeEnum.STRING){ // 把key先压入栈中，然后等构造kv对时弹出 this.parseStack.push(new JsonParseStackValue(JsonParseStackValueTypeEnum.JSON_KEY,token)); accept(); this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_3; return; } throw new MuJsonParserException("unexpected token! index=" + jsonTokenReader.currentIndex()); } private void processInParseObject2(JsonToken token){ // 遇到'}'才会进来 if(token.getType() != JsonTokenTypeEnum.RIGHT_BRACE){ throw new MuJsonParserException("unexpected token! index=" + jsonTokenReader.currentIndex()); }else{ accept(); } // 当前栈顶必定是JsonObject，先将其弹出，然后看栈顶的元素类型判断 JsonParseStackValue currentJsonObjectStackValue = this.parseStack.popAndCheck(JsonParseStackValueTypeEnum.JSON_OBJECT); if(this.parseStack.isEmpty()){ // 说明是root的JsonObject解析完了，再推回去直接返回 this.parseStack.push(currentJsonObjectStackValue); this.currentStatus = StackBaseJsonParserStatusEnum.END_PARSE; return; } JsonObject currentJsonObject = (JsonObject) currentJsonObjectStackValue.getValue(); JsonParseStackValueTypeEnum topObjType = this.parseStack.peekTopType(); if(topObjType == JsonParseStackValueTypeEnum.JSON_KEY){ // 如果是json_key，说明是当前jsonObject是父object的一个k/v项中的value。 JsonParseStackValue keyStackValue = this.parseStack.popAndCheck(JsonParseStackValueTypeEnum.JSON_KEY); JsonToken keyJsonToken = (JsonToken) keyStackValue.getValue(); JsonParseStackValue parentObject = this.parseStack.peekAndCheck(JsonParseStackValueTypeEnum.JSON_OBJECT); // 将当前k/v项附加在父object上 ((JsonObject)parentObject.getValue()).putKV(keyJsonToken.getContent(), currentJsonObject); // 基于下一个token判断状态跳转 JsonToken nextJsonToken = this.jsonTokenReader.peek(); if(nextJsonToken.getType() == JsonTokenTypeEnum.COMMA){ this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_5; return; }else if (nextJsonToken.getType() == JsonTokenTypeEnum.RIGHT_BRACE){ this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_2; return; }else{ throw new MuJsonParserException("unexpected token! index=" + (jsonTokenReader.currentIndex()+1)); } }else if(topObjType == JsonParseStackValueTypeEnum.JSON_ARRAY){ // 说明当前jsonObject是jsonArray的一个元素 JsonParseStackValue parentArr = this.parseStack.peekAndCheck(JsonParseStackValueTypeEnum.JSON_ARRAY); ((JsonArray)parentArr.getValue()).addElement(currentJsonObject); // 基于下一个token判断状态跳转 JsonToken nextJsonToken = this.jsonTokenReader.peek(); if(nextJsonToken.getType() == JsonTokenTypeEnum.COMMA){ this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_ARR_3; return; }else if (nextJsonToken.getType() == JsonTokenTypeEnum.RIGHT_BRACKET){ this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_ARR_2; return; }else{ throw new MuJsonParserException("unexpected token! index=" + (jsonTokenReader.currentIndex()+1)); } }else{ // 别的情况都说明有问题，不是合法的json throw new MuJsonParserException("unexpected token! index=" + jsonTokenReader.currentIndex()); } } private void processInParseObject3(JsonToken token){ if(token.getType() == JsonTokenTypeEnum.COLON){ accept(); this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_4; return; } throw new MuJsonParserException("unexpected token! index=" + jsonTokenReader.currentIndex()); } private void processInParseObject4(JsonToken token){ // 嵌套的jsonObject结构 if(token.getType() == JsonTokenTypeEnum.LEFT_BRACE){ // 发现'{'，栈上推进一个JsonObject this.parseStack.push(new JsonParseStackValue(JsonParseStackValueTypeEnum.JSON_OBJECT, new JsonObject())); accept(); this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_1; return; } // 嵌套的jsonArray结构 if(token.getType() == JsonTokenTypeEnum.LEFT_BRACKET){ // 发现'['，栈上推进一个JsonArr this.parseStack.push(new JsonParseStackValue(JsonParseStackValueTypeEnum.JSON_ARRAY, new JsonArray())); accept(); this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_ARR_1; return; } // 基础类型的value if(token.getType().isPrimitiveValue()){ JsonParseStackValue jsonKeyToken = this.parseStack.popAndCheck(JsonParseStackValueTypeEnum.JSON_KEY); JsonToken keyToken = (JsonToken) jsonKeyToken.getValue(); Assert.assertTrue(keyToken.getType() == JsonTokenTypeEnum.STRING,"parse object keyToken not match!"); // 获取栈顶的jsonObject对象，设置k/v JsonParseStackValue topJsonObject = this.parseStack.peekAndCheck(JsonParseStackValueTypeEnum.JSON_OBJECT); ((JsonObject) topJsonObject.getValue()).putKV(keyToken.getContent(), new JsonPrimitiveStr(token.getContent())); accept(); // 基于下一个token判断状态跳转 JsonToken nextJsonToken = this.jsonTokenReader.peek(); if(nextJsonToken.getType() == JsonTokenTypeEnum.COMMA){ this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_5; return; }else if (nextJsonToken.getType() == JsonTokenTypeEnum.RIGHT_BRACE){ this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_2; return; }else{ throw new MuJsonParserException("unexpected token! index=" + (jsonTokenReader.currentIndex()+1)); } } throw new MuJsonParserException("unexpected token! index=" + jsonTokenReader.currentIndex()); } private void processInParseObject5(JsonToken token){ if(token.getType() == JsonTokenTypeEnum.COMMA){ accept(); this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_6; return; } throw new MuJsonParserException("unexpected token! index=" + jsonTokenReader.currentIndex()); } private void processInParseObject6(JsonToken token){ if(token.getType() == JsonTokenTypeEnum.STRING){ // 把key先压入栈中，然后等构造kv对时弹出 this.parseStack.push(new JsonParseStackValue(JsonParseStackValueTypeEnum.JSON_KEY,token)); accept(); this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_3; return; } throw new MuJsonParserException("unexpected token! index=" + jsonTokenReader.currentIndex()); } private void processInParseArr0(JsonToken token){ if(token.getType() == JsonTokenTypeEnum.LEFT_BRACKET){ accept(); this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_ARR_1; return; } throw new MuJsonParserException("unexpected token! index=" + jsonTokenReader.currentIndex()); } private void processInParseArr1(JsonToken token){ if(token.getType() == JsonTokenTypeEnum.RIGHT_BRACKET){ this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_ARR_2; return; } // 嵌套的jsonObject结构 if(token.getType() == JsonTokenTypeEnum.LEFT_BRACE){ // 发现'{'，栈上推进一个JsonObject this.parseStack.push(new JsonParseStackValue(JsonParseStackValueTypeEnum.JSON_OBJECT, new JsonObject())); accept(); this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_1; return; } // 嵌套的jsonArray结构 if(token.getType() == JsonTokenTypeEnum.LEFT_BRACKET){ // 发现'['，栈上推进一个JsonArr this.parseStack.push(new JsonParseStackValue(JsonParseStackValueTypeEnum.JSON_ARRAY, new JsonArray())); accept(); this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_ARR_1; return; } // 基础类型的value if(token.getType().isPrimitiveValue()){ // 获取栈顶的jsonArr对象，添加一个元素 JsonParseStackValue topJsonArr = this.parseStack.peekAndCheck(JsonParseStackValueTypeEnum.JSON_ARRAY); ((JsonArray) topJsonArr.getValue()).addElement(new JsonPrimitiveStr(token.getContent())); accept(); // 基于下一个token判断状态跳转 JsonToken nextJsonToken = this.jsonTokenReader.peek(); if(nextJsonToken.getType() == JsonTokenTypeEnum.COMMA){ this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_ARR_3; return; }else if (nextJsonToken.getType() == JsonTokenTypeEnum.RIGHT_BRACKET){ this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_ARR_2; return; }else{ throw new MuJsonParserException("unexpected token! index=" + (jsonTokenReader.currentIndex()+1)); } } throw new MuJsonParserException("unexpected token! index=" + jsonTokenReader.currentIndex()); } private void processInParseArr2(JsonToken token){ // 遇到']'才会进来 if(token.getType() != JsonTokenTypeEnum.RIGHT_BRACKET){ throw new MuJsonParserException("unexpected token! index=" + jsonTokenReader.currentIndex()); }else{ accept(); } // 当前栈顶必定是JsonArray，先将其弹出，然后看栈顶的元素类型判断 JsonParseStackValue currentJsonObjectStackValue = this.parseStack.popAndCheck(JsonParseStackValueTypeEnum.JSON_ARRAY); if(this.parseStack.isEmpty()){ // 说明是root的JsonArr解析完了，再推回去直接返回 this.parseStack.push(currentJsonObjectStackValue); this.currentStatus = StackBaseJsonParserStatusEnum.END_PARSE; return; } JsonArray jsonArray = (JsonArray) currentJsonObjectStackValue.getValue(); JsonParseStackValueTypeEnum topObjType = this.parseStack.peekTopType(); if(topObjType == JsonParseStackValueTypeEnum.JSON_KEY){ // 如果是json_key，说明是当前jsonArray是父object的一个k/v项中的value。 JsonParseStackValue keyStackValue = this.parseStack.popAndCheck(JsonParseStackValueTypeEnum.JSON_KEY); JsonToken keyJsonToken = (JsonToken) keyStackValue.getValue(); JsonParseStackValue parentObject = this.parseStack.peekAndCheck(JsonParseStackValueTypeEnum.JSON_OBJECT); // 将当前k/v项附加在父object上 ((JsonObject)parentObject.getValue()).putKV(keyJsonToken.getContent(), jsonArray); // 基于下一个token判断状态跳转 JsonToken nextJsonToken = this.jsonTokenReader.peek(); if(nextJsonToken.getType() == JsonTokenTypeEnum.COMMA){ this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_5; return; }else if (nextJsonToken.getType() == JsonTokenTypeEnum.RIGHT_BRACE){ this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_OBJECT_2; return; }else{ throw new MuJsonParserException("unexpected token! index=" + (jsonTokenReader.currentIndex()+1)); } }else if(topObjType == JsonParseStackValueTypeEnum.JSON_ARRAY){ // 说明当前jsonObject是jsonArray的一个元素 JsonParseStackValue parentArr = this.parseStack.peekAndCheck(JsonParseStackValueTypeEnum.JSON_ARRAY); ((JsonArray)parentArr.getValue()).addElement(jsonArray); // 基于下一个token判断状态跳转 JsonToken nextJsonToken = this.jsonTokenReader.peek(); if(nextJsonToken.getType() == JsonTokenTypeEnum.COMMA){ this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_ARR_3; return; }else if (nextJsonToken.getType() == JsonTokenTypeEnum.RIGHT_BRACKET){ this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_ARR_2; return; }else{ throw new MuJsonParserException("unexpected token! index=" + (jsonTokenReader.currentIndex()+1)); } }else{ // 别的情况都说明有问题，不是合法的json throw new MuJsonParserException("unexpected token! index=" + jsonTokenReader.currentIndex()); } } private void processInParseArr3(JsonToken token){ if(token.getType() == JsonTokenTypeEnum.COMMA){ accept(); this.currentStatus = StackBaseJsonParserStatusEnum.PARSE_ARR_1; return; } throw new MuJsonParserException("unexpected token! index=" + jsonTokenReader.currentIndex()); }}

复制代码

比较堆栈与递归实现性能差异的demo

我们可以很简单的构造出一个非常深嵌套层次的json串，即由连续N个“[”和连续N个“]”构成的json字符串。即根节点为数组，同时每个数组中都有且仅有一个子元素，子元素的类型依然是数组，依次类推。

public class TestHugeLevelJsonParse { @Test public void testHugeLevelJsonParse() { int level = 3500; String hugeLevelJson = TestUtil.buildHugeLevelJson(level); // 3500层的深度，会StackOverflowError栈溢出 Error recursiveJsonParseEx = null; try{ RecursiveJsonParser recursiveJsonParser = new RecursiveJsonParser(new StreamJsonTokenReader(hugeLevelJson)); JsonElement obj = recursiveJsonParser.doParse(); }catch (Error e){ recursiveJsonParseEx = e; } Assert.assertTrue(recursiveJsonParseEx instanceof StackOverflowError); System.out.println("level = " + level + " recursiveJsonParseEx has StackOverflowError!"); // jackson默认json深度为1000，超过了会报错 { try { Object obj = JackSonUtil.string2Obj(hugeLevelJson, Object.class); }catch (Exception e){ // 会报错 System.out.println("jackson parse hugeLevelJson error! " + e.getCause().getMessage()); } } // 基于堆栈的能正确的解析出来，不会StackOverflowError栈溢出 { StackBaseJsonParser stackBaseJsonParser = new StackBaseJsonParser(new StreamJsonTokenReader(hugeLevelJson)); JsonElement obj = stackBaseJsonParser.doParse(); int arrayLevel = TestUtil.getSpecialJsonArrayLevel(obj); Assert.assertEquals(arrayLevel, level - 1); System.out.println("stackBaseJsonParser parse，arrayLevel=" + arrayLevel); } }}

复制代码

递归 vs 堆栈解析的取舍

基于递归的json语法解析器实现简单，思路更直观，但受限于线程栈大小，在极深层级下会出现StackOverflow。
基于堆栈的json语法解析器状态机更庞大，实现起来更复杂，但将调用栈搬到堆上之后，能处理极深层级的json（只要堆内存足够）。
Jackson等成熟的三方库即使同样基于堆栈实现，通常也会设置一个合理的深度上限，避免恶意或异常的json导致系统资源耗尽。

总结

到这里，我们已经如开头所说的那般，一步一步的从零开始实现了一个简单的json解析器。
虽然网络上已经有着大量关于json解析器实现原理的博客，甚至利用ai都能帮你实现的大差不差。但是纸上得来终觉浅，绝知此事要躬行，想要更好的学习编译原理，去理解乃至实现更复杂的编译器、解释器，通过自己动手去体会那些晦涩抽象的原理也许是一种效率较低但长远看受益无穷的学习方式。

博客中展示的完整代码在我的github上：https://github.com/1399852153/MySimpleJsonParser (main分支)。
希望能够帮助到对json解析或是编译原理感兴趣的读者，内容如有错误，还请多多指教。

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

账号		自动登录	找回密码
密码			立即注册

从零开始实现一个简易json解析器

相关帖子

签约作者

从零开始实现一个简易json解析器

相关帖子

相关推荐

签约作者