自己動手實作一個簡單的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 字元串：

{
    "name" : "小明",
    "age": 18
}

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

、

name

小明

age

圖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 BOOLEAN
" ，期望這個詞是字元串，Token 類型為 String
0~9 - ，期望這個詞是數字，類型為 NUMBER

正如上面所說，詞法分析器隻需要根據每個詞的第一個字元，即可知道接下來它所期望讀取的到的内容是什麼樣的。如果滿足期望了，則傳回 Token，否則傳回錯誤。下面就來看看詞法解析器在碰到第一個字元是

和

時的處理過程。先看碰到字元

的處理過程：

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

上面的代碼很簡單，詞法分析器在讀取字元

後，期望後面的三個字元分别是

，與

組成詞 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

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 美化效果展示。這裡随便模拟點資料，就模拟王者榮耀裡的狄仁傑英雄資訊吧（對，這個英雄我經常用）。如下圖：

圖3 JSON 美化結果

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

4. 寫作最後

到此，本文差不多要結束了。本文對應的代碼已經放到了 github 上，需要的話，大家可自行下載下傳。傳送門 ->

JSONParser

。這裡需要聲明一下，本文對應的代碼實作了一個比較簡陋的 JSON 解析器，實作的目的是探究 JSON 的解析原理。JSONParser 隻算是一個練習性質的項目，代碼實作的并不優美，而且缺乏充足的測試。同時，限于本人的能力（編譯原理基礎基本可以忽略），我并無法保證本文以及對應的代碼中不出現錯誤。如果大家在閱讀代碼的過程中，發現了一些錯誤，或者寫的不好的地方，可以提出來，我來修改。如果這些錯誤對你造成了困擾，這裡先說一聲很抱歉。最後，本文及實作主要參考了

一起寫一個JSON解析器如何編寫一個JSON解析器

兩篇文章及兩篇文章對應的實作代碼，在這裡向着兩篇博文的作者表示感謝。好了，本文到此結束，祝大家生生活愉快！再見。

參考

本文在知識共享許可協定 4.0 下釋出，轉載需在明顯位置處注明出處

作者：coolblog

本文同步釋出在我的個人部落格：
http://www.coolblog.xyz

本作品采用

知識共享署名-非商業性使用-禁止演繹 4.0 國際許可協定

進行許可。

自己動手實作一個簡單的JSON解析器

1. 背景

2. JSON 解析器實作原理

2.1 詞法分析

2.2 文法分析

3. 測試及效果展示

4. 寫作最後

參考

繼續閱讀

debian9更新4.9.0核心到4.19.2核心過程

Javascript建構Bingo卡片遊戲

JavaScript的那些坑之事件代理事件代理事件階段

javascript的for (var i in data)慎用javascript中的for (var i in data)謹慎用

tab滑鼠經過菜單切換

vue （vue2.0）使用總結(從大體結構總結)

vue搭建過程及出現問題

/\B(?=(?:\d{3})+$)/g 一條令人費解的正規表達式

适用于JavaScript的ECMAScript 2020規範向前發展

【python】【資料處理】畫多元資料分布圖

JS生成uuid的四種方法

vue-cli簡介（中文翻譯）

Ajax發送和擷取json資料到Spring mvc 1.spring mvc後端2.web前段

layui多任務上傳添加進度條

JSONObject包導入異常 java.lang.NoClassDefFoundErrorweb項目的導入包的問題