手把手教你實現一個 JSON 解析器

1. 背景

JSON(JavaScript Object Notation) 是一種輕量級的數據交換格式。相對於另一種數據交換格式 XML，JSON 有著諸多優點。比如易讀性更好，佔用空間更少等。

在 web 應用開發領域內，得益於 JavaScript 對 JSON 提供的良好支持，JSON 要比 XML 更受開發人員青睞。所以作為開發人員，如果有興趣的話，還是應該深入瞭解一下 JSON 相關的知識。

本著探究 JSON 原理的目的，我將會在這篇文章中詳細向大家介紹一個簡單的JSON解析器的解析流程和實現細節。

由於 JSON 本身比較簡單，解析起來也並不複雜。所以如果大家感興趣的話，在看完本文後，不妨自己動手實現一個 JSON 解析器。

好了，其他的話就不多說了，接下來讓我們移步到重點章節吧。

2. JSON 解析器實現原理

JSON 解析器從本質上來說就是根據 JSON 文法規則創建的狀態機，輸入是一個 JSON 字符串，輸出是一個 JSON 對象。一般來說，解析過程包括詞法分析和語法分析兩個階段。

詞法分析階段的目標是按照構詞規則將 JSON 字符串解析成 Token 流，比如有如下的 JSON 字符串：

<code>{
    "name" : "小明",
    "age": 18
}/<code>

結果詞法分析後，得到一組 Token，如下：

<code>{、 name、 :、 小明、 ,、 age、 :、 18、 }/<code>

詞法分析解析出 Token 序列後，接下來要進行語法分析。語法分析的目的是根據 JSON 文法檢查上面 Token 序列所構成的 JSON 結構是否合法。

比如 JSON 文法要求非空 JSON 對象以鍵值對的形式出現，形如 object = {string : value}。如果傳入了一個格式錯誤的字符串，比如：

<code>{
    "name", "小明"
}/<code>

那麼在語法分析階段，語法分析器分析完 Token name後，認為它是一個符合規則的 Token，並且認為它是一個鍵。請不要在 JDK 7+ 中使用這個 JSON 包了！這篇看下。

接下來，語法分析器讀取下一個 Token，期望這個 Token 是 :。但當它讀取了這個 Token，發現這個 Token 是,，並非其期望的:，於是文法分析器就會報錯誤。

這裡簡單總結一下上面兩個流程，詞法分析是將字符串解析成一組 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。我們可以定義一個枚舉類來表示上面的數據類型，如下：

<code>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;
    }
}/<code>

在解析過程中，僅有 TokenType 類型還不行。我們除了要將某個詞的類型保存起來，還需要保存這個詞的字面量。所以，所以這裡還需要定義一個 Token 類。用於封裝詞類型和字面量，如下：

<code>public class Token {
    private TokenType tokenType;
    private String value;
    // 省略不重要的代碼
}/<code>

定義好了 Token 類，接下來再來定義一個讀取字符串的類。如下：

<code>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;
    }
}/<code>

有了 TokenType、Token 和 CharReader 這三個輔助類，接下來我們就可以實現詞法解析器了。

<code>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() {...} 

}/<code>

上面的代碼是詞法分析器的實現，部分代碼這裡沒有貼出來，後面具體分析的時候再貼。

先來看看詞法分析器的核心方法 start，這個方法代碼量不多，並不複雜。其通過一個死循環不停的讀取字符，然後再根據字符的類型，執行不同的解析邏輯。

上面說過，JSON 的解析過程比較簡單。原因在於，在解析時，只需通過每個詞第一個字符即可判斷出這個詞的 Token Type。比如：

• 第一個字符是{、}、[、]、,、:，直接封裝成相應的 Token 返回即可
• 第一個字符是n，期望這個詞是null，Token 類型是NULL
• 第一個字符是t或f，期望這個詞是true或者false，Token 類型是BOOLEAN
• 第一個字符是"，期望這個詞是字符串，Token 類型為String
• 第一個字符是0~9或-，期望這個詞是數字，類型為NUMBER

正如上面所說，詞法分析器只需要根據每個詞的第一個字符，即可知道接下來它所期望讀取的到的內容是什麼樣的。如果滿足期望了，則返回 Token，否則返回錯誤。

下面就來看看詞法解析器在碰到第一個字符是n和"時的處理過程。先看碰到字符n的處理過程：

<code>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");
}/<code>

上面的代碼很簡單，詞法分析器在讀取字符n後，期望後面的三個字符分別是u,l,l，與 n 組成詞 null。如果滿足期望，則返回類型為 NULL 的 Token，否則報異常。readNull 方法邏輯很簡單，不多說了。

接下來看看 string 類型的數據處理過程：

<code>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                     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'));
}/<code>

string 類型的數據解析起來要稍微複雜一些，主要是需要處理一些特殊類型的字符。JSON 所允許的特殊類型的字符如下：

<code>\"
\\
\\b
\\f
\\n
\\r
\\t
\\\\u four-hex-digits
\\//<code>

最後一種特殊字符\\/代碼中未做處理，其他字符均做了判斷，判斷邏輯在 isEscape 方法中。在傳入 JSON 字符串中，僅允許字符串包含上面所列的轉義字符。如果亂傳轉義字符，解析時會報錯。

對於 STRING 類型的詞，解析過程始於字符"，也終於"。所以在解析的過程中，當再次遇到字符"，readString 方法會認為本次的字符串解析過程結束，並返回相應類型的 Token。

上面說了 null 類型和 string 類型的數據解析過程，過程並不複雜，理解起來應該不難。至於 boolean 和 number 類型的數據解析過程，大家有興趣的話可以自己看源碼，這裡就不在說了。

關注微信公眾號：Java技術棧，在後臺回覆：java，可以獲取我整理的 N 篇最新Java 教程，都是乾貨。

2.2 語法分析

當詞法分析結束後，且分析過程中沒有拋出錯誤，那麼接下來就可以進行語法分析了。語法分析過程以詞法分析階段解析出的 Token 序列作為輸入，輸出 JSON Object 或 JSON Array。

語法分析器的實現的文法如下：

<code>object = {} | { members }
members = pair | pair , members
pair = string : value
array = [] | [ elements ]
elements = value | value , elements
value = string | number | object | array | true | false | null/<code>

語法分析器的實現需要藉助兩個輔助類，也就是語法分析器的輸出類，分別是 JsonObject 和 JsonArray。Java常用的幾個Json庫，性能強勢對比！這篇推薦看下。

代碼如下：

<code>public class JsonObject {

    private Map<string> map = new HashMap<string>();

    public void put(String key, Object value) {
        map.put(key, value);
    }

    public Object get(String key) {
        return map.get(key);
    }

    public List<map.entry>> 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();
    }
}/<map.entry>/<string>/<string>/<code>

語法解析器的核心邏輯封裝在了 parseJsonObject 和 parseJsonArray 兩個方法中，接下來我會詳細分析 parseJsonObject 方法，parseJsonArray 方法大家自己分析吧。

parseJsonObject 方法實現如下：

<code>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.");
    }
}/<code>

parseJsonObject 方法解析流程大致如下：

1. 讀取一個 Token，檢查這個 Token 是否是其所期望的類型
2. 如果是，更新期望的 Token 類型。否則，拋出異常，並退出
3. 重複步驟1和2，直至所有的 Token 都解析完，或出現異常

上面的步驟並不複雜，但有可能不好理解。這裡舉個例子說明一下，有如下的 Token 序列：

<code>{、 id、 :、 1、 }/<code>

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 更為合適，所以解析的過程中也需要注意一下。

3. 測試及效果展示

為了驗證代碼的正確性，這裡對代碼進行了簡單的測試。測試數據來自網易音樂，大約有4.5W個字符。為了避免每次下載數據，因數據發生變化而導致測試不通過的問題。

我將某一次下載的數據保存在了 music.json 文件中，後面每次測試都會從文件中讀取數據。

關於測試部分，這裡就不貼代碼和截圖了。大家有興趣的話，可以自己下載源碼測試玩玩。

測試就不多說了，接下來看看 JSON 美化效果展示。這裡隨便模擬點數據，就模擬王者榮耀裡的狄仁傑英雄信息吧（對，這個英雄我經常用）。如下圖：

關於 JSON 美化的代碼這裡也不講解了，並非重點，只算一個彩蛋吧。

4. 寫作最後

到此，本文差不多要結束了。本文對應的代碼已經放到了 github 上，需要的話，大家可自行下載：https://github.com/code4wt/JSONParser。

這裡需要聲明一下，本文對應的代碼實現了一個比較簡陋的 JSON 解析器，實現的目的是探究 JSON 的解析原理。JSONParser 只算是一個練習性質的項目，代碼實現的並不優美，而且缺乏充足的測試。

同時，限於本人的能力（編譯原理基礎基本可以忽略），我並無法保證本文以及對應的代碼中不出現錯誤。如果大家在閱讀代碼的過程中，發現了一些錯誤，或者寫的不好的地方，可以提出來，我來修改。如果這些錯誤對你造成了困擾，這裡先說一聲很抱歉。

最後，本文及實現主要參考了一起寫一個JSON解析器和如何編寫一個JSON解析器兩篇文章及兩篇文章對應的實現代碼，在這裡向著兩篇博文的作者表示感謝。好了，本文到此結束，祝大家生生活愉快！再見。

閱讀更多 一隻程序哼 的文章

關鍵字: JSON 實現 JavaScript