介绍
后面两节咱们介绍了分词和分词荡涤，通过荡涤后的token列表曾经能够用来生产语法树，本节咱们将实现语法树的生成，语法树的目标就是将数据结构化，什么叫结构化，比方字符串表达式(1+(2*3))要写个程序计算这个后果还是有点难的，因为这个字符串只是一个字符串，咱们须要去解析，那么这个字符串就不是一个结构化的数据，如果给你的是解析后的数据，那么就很好解决，解析后的数据就是结构化的数据，你可能会说那不就是分词吗，其实不是的，也是以下面那个表达式为例，分词都是平铺构造，没有层级关系，但表达式有优先级，嵌套等层级关系，这个就是语法树要做的事。
实现
难点
生成语法树的难点在于，token数组是平铺构造，但语法树是树形构造，有层级关系，咱们须要将将平铺构造变成树形构造，当token数组中蕴含object和array时语法树就会有新的分支，因而重点就是要解决好object和array，这两个解决形式实质上是统一的，能够简化为找括号问题，什么意思呢，比方一个表达式(1+(2+(3+4)+5)+6)如何找到成对的括号，一种简略的办法是如果碰到(就进入递归，直到碰到)退出，这样最初一次递归会先匹配第一个)和咱们想要的后果相符，有点相似栈，后进先出，就以(1+(2+(3+4)+5)+6)为例，总共17个字符，括号的匹配状况应该是
0匹配163匹配136匹配10代码实现
public static void test(String text) { int begin = 0; int end = 0; while (index < text.length()) { int c = text.charAt(index); if (c == '(') { begin = index; char cc = text.charAt(++index); while (cc != ')') { test(text); cc = text.charAt(index); } end = index; System.out.println(String.format("%d匹配%d", begin, end)); } else if (c == ')') { break; } ++index; } }输入
6匹配103匹配130匹配16因为是最外面括号开始匹配所以先输入6匹配10，后果是合乎预期的，了解了这个就很容易了解语法树的生成过程
实现
首先定义形象语法树数据结构，如下
public class Ast { //节点类型 private String type; //如果是object则是字段列表 //如果是array则是值列表 private List<Ast> items; //字段名（可为空） private String name; //字段值 private Object value; ....}语法树构建步骤如下
- 如果是object和array，那么就依照递归的形式进行遍历
- 如果是key，那么依据value的类型进行解决，如果是object和array，那么依照递归的形式进行遍历，如果是根本类型，间接解决
- 如果是value，间接解决
代码如下：
/** * 生成形象语法树 * * @return */public List<Ast> generateAST() { List<Ast> items = new ArrayList<>(); //currentIndex作为以后读取token的地位 //取出对象则currentIndex须要往前挪动 Token token = jsonTokens.get(currentIndex); if ("object".equals(token.getType()) && "{".equals(token.getValue())) { Ast item = new Ast(); item.setType(token.getType()); //如果json语法错误currentIndex有可能超过范畴，这里先不思考语法错误问题 Token tt = jsonTokens.get(++currentIndex); while (!"object".equals(tt.getType()) || ("object".equals(tt.getType()) && !"}".equals(tt.getValue()))) { item.getItems().addAll(generateAST()); tt = jsonTokens.get(currentIndex); } items.add(item); ++currentIndex; } else if ("array".equals(token.getType()) && "[".equals(token.getValue())) { Ast item = new Ast(); item.setType(token.getType()); Token tt = jsonTokens.get(++currentIndex); while (!"array".equals(tt.getType()) || ("array".equals(tt.getType()) && !"]".equals(tt.getValue()))) { item.getItems().addAll(generateAST()); tt = jsonTokens.get(currentIndex); } items.add(item); ++currentIndex; } else if ("key".equals(token.getType())) { // key和value是成对呈现，如果只有key没有value阐明json语法错误，这里临时不思考语法错误 Token value = jsonTokens.get(++currentIndex); if ("object".equals(value.getType()) || "array".equals(value.getType())) { //对象和数组须要递归获取语法树 List<Ast> tts = generateAST(); //如果是key-value构造必须设置key的名称 tts.get(0).setName((String) token.getValue()); return tts; } else if ("value".equals(value.getType())) { Ast item = new Ast(); item.setValue(value.getValue()); item.setType(value.getType()); item.setName((String) token.getValue()); items.add(item); ++currentIndex; } } else if ("value".equals(token.getType())) { //只有value没有key的状况，比方["1",2,true,null] Ast item = new Ast(); item.setValue(token.getValue()); item.setType(token.getType()); items.add(item); ++currentIndex; } return items;}代码看着挺长，但就是做下面说的三件事，外面的逻辑并不简单
测试
语法树结构不容易打印进去，咱们用fastjson转化为json进行打印
public class Main { public static void main(String[] args) throws Exception { InputStream fin = Main.class.getResourceAsStream("/example.json"); byte[] buf = new byte[fin.available()]; fin.read(buf); fin.close(); String json = new String(buf, "utf-8"); JSONParser parser = new JSONParser(); List<Token> tokens = parser.tokenizer(json); tokens = parser.tokenClean(tokens); List<Ast> astItems = parser.generateAST(); Ast ast = astItems.get(0); System.out.println(String.format("|%-12s|%-12s|%-15s|", "type", "valueType", "value")); System.out.println("-------------------------------------------"); for (Token t : tokens) { System.out.println(String.format("|%-12s|%-12s|%-15s|", t.getType(), t.getValueType(), t.getValue())); } System.out.println("-------------------------------------------"); System.out.println(JSON.toJSONString(ast, true)); }}后果：
{ "items":[ { "name":"name", "type":"value", "value":"asan" }, { "name":"age", "type":"value", "value":32 }, { "name":"married", "type":"value", "value":true }, { "name":"birthday", "type":"value", "value":"1992-02-08" }, { "name":"salary", "type":"value", "value":1234.56 }, { "name":"description", "type":"value", "value":"a \"hudsom\" man" }, { "items":[ { "type":"value", "value":"coder" }, { "type":"value", "value":"mid-age" } ], "name":"tags", "type":"array" }, { "items":[ { "name":"province", "type":"value", "value":"福建省" }, { "name":"city", "type":"value", "value":"泉州市" }, { "name":"area", "type":"value", "value":"晋江市" } ], "name":"location", "type":"object" }, { "items":[ { "items":[ { "name":"relation", "type":"value", "value":"couple" }, { "name":"name", "type":"value", "value":"Helen" } ], "type":"object" }, { "items":[ { "name":"relation", "type":"value", "value":"daughter" }, { "name":"name", "type":"value", "value":"XiaoMan" } ], "type":"object" } ], "name":"family", "type":"array" } ], "type":"object"}这样咱们胜利构建了一棵语法树
代码
残缺代码请参考我的项目https://github.com/wls1036/tiny-json-parser的0x03分支