关于解析器:自己动手写json解析器0x03抽象语法树

后面两节咱们介绍了分词和分词荡涤，通过荡涤后的 token 列表曾经能够用来生产语法树，本节咱们将实现语法树的生成，语法树的目标就是将数据结构化，什么叫结构化，比方字符串表达式 (1+(2*3)) 要写个程序计算这个后果还是有点难的，因为这个字符串只是一个字符串，咱们须要去解析，那么这个字符串就不是一个结构化的数据，如果给你的是解析后的数据，那么就很好解决，解析后的数据就是结构化的数据，你可能会说那不就是分词吗，其实不是的，也是以下面那个表达式为例，分词都是平铺构造，没有层级关系，但表达式有优先级，嵌套等层级关系，这个就是语法树要做的事。

生成语法树的难点在于，token 数组是平铺构造，但语法树是树形构造，有层级关系，咱们须要将将平铺构造变成树形构造，当 token 数组中蕴含 object 和 array 时语法树就会有新的分支，因而重点就是要解决好 object 和 array，这两个解决形式实质上是统一的，能够简化为找括号问题，什么意思呢，比方一个表达式 (1+(2+(3+4)+5)+6) 如何找到成对的括号，一种简略的办法是如果碰到 ( 就进入递归，直到碰到 ) 退出，这样最初一次递归会先匹配第一个 ) 和咱们想要的后果相符，有点相似栈，后进先出，就以 (1+(2+(3+4)+5)+6) 为例，总共 17 个字符，括号的匹配状况应该是

 0 匹配 16
3 匹配 13
6 匹配 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 匹配 10
3 匹配 13
0 匹配 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 分支

介绍

实现

难点

实现

测试

代码