javascript
自己动手实现一个简单的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 字符串:
| 1 2 3 4 | {"name" : "小明","age": 18 } |
結果詞法分析后,得到一組 Token,如下:
{、?name、?:、?小明、?,、?age、?:、?18、?}
圖1 詞法分析器輸入輸出
詞法分析解析出 Token 序列后,接下來要進行語法分析。語法分析的目的是根據 JSON 文法檢查上面 Token 序列所構成的 JSON 結構是否合法。比如 JSON 文法要求非空 JSON 對象以鍵值對的形式出現,形如?object = {string : value}。如果傳入了一個格式錯誤的字符串,比如
| 1 2 3 | {"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。我們可以定義一個枚舉類來表示上面的數據類型,如下:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | 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 類。用于封裝詞類型和字面量,如下:
| 1 2 3 4 5 | public class Token {private TokenType tokenType;private String value;// 省略不重要的代碼 } |
定義好了 Token 類,接下來再來定義一個讀取字符串的類。如下:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | 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 這三個輔助類,接下來我們就可以實現詞法解析器了。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | 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,Token 類型是?BOOLEAN
- 第一個字符是",期望這個詞是字符串,Token 類型為String
- 第一個字符是0~9或-,期望這個詞是數字,類型為NUMBER
正如上面所說,詞法分析器只需要根據每個詞的第一個字符,即可知道接下來它所期望讀取的到的內容是什么樣的。如果滿足期望了,則返回 Token,否則返回錯誤。下面就來看看詞法解析器在碰到第一個字符是n和"時的處理過程。先看碰到字符n的處理過程:
| 1 2 3 4 5 6 7 | 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"); } |
上面的代碼很簡單,詞法分析器在讀取字符n后,期望后面的三個字符分別是u,l,l,與?n?組成詞 null。如果滿足期望,則返回類型為 NULL 的 Token,否則報異常。readNull 方法邏輯很簡單,不多說了。接下來看看 string 類型的數據處理過程:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | 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 == '"') { // 碰到另一個雙引號,則認為字符串解析結束,返回 Tokenreturn 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。語法分析器的實現的文法如下:
| 1 2 3 4 5 6 | 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。代碼如下:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 | 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;}@Overridepublic 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;}@Overridepublic String toString() {return BeautifyJsonUtils.beautify(this);}public Iterator iterator() {return list.iterator();} } |
語法解析器的核心邏輯封裝在了 parseJsonObject 和 parseJsonArray 兩個方法中,接下來我會詳細分析 parseJsonObject 方法,parseJsonArray 方法大家自己分析吧。parseJsonObject 方法實現如下:
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 | 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 objectexpectToken = SEP_COMMA_TOKEN | END_OBJECT_TOKEN;break;case END_OBJECT:checkExpectToken(tokenType, expectToken);return jsonObject;case BEGIN_ARRAY: // 解析 json arraycheckExpectToken(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 序列:
{、?id、?:、?1、?}
parseJsonObject 解析完?{?Token 后,接下來它將期待 STRING 類型的 Token 或者 END_OBJECT 類型的 Token 出現。于是 parseJsonObject 讀取了一個新的 Token,發現這個 Token 的類型是 STRING 類型,滿足期望。于是 parseJsonObject 更新期望Token 類型為 SEL_COLON,即:。如此循環下去,直至 Token 序列解析結束或者拋出異常退出。
上面的解析流程雖然不是很復雜,但在具體實現的過程中,還是需要注意一些細節問題。比如:
?3. 測試及效果展示
為了驗證代碼的正確性,這里對代碼進行了簡單的測試。測試數據來自網易音樂,大約有4.5W個字符。為了避免每次下載數據,因數據發生變化而導致測試不通過的問題。我將某一次下載的數據保存在了 music.json 文件中,后面每次測試都會從文件中讀取數據。關于測試部分,這里就不貼代碼和截圖了。大家有興趣的話,可以自己下載源碼測試玩玩。
測試就不多說了,接下來看看 JSON 美化效果展示。這里隨便模擬點數據,就模擬王者榮耀里的狄仁杰英雄信息吧(對,這個英雄我經常用)。如下圖:
圖3 JSON 美化結果
關于 JSON 美化的代碼這里也不講解了,并非重點,只算一個彩蛋吧。
?4. 寫作最后
到此,本文差不多要結束了。本文對應的代碼已經放到了 github 上,需要的話,大家可自行下載。傳送門 ->?JSONParser。這里需要聲明一下,本文對應的代碼實現了一個比較簡陋的 JSON 解析器,實現的目的是探究 JSON 的解析原理。JSONParser 只算是一個練習性質的項目,代碼實現的并不優美,而且缺乏充足的測試。同時,限于本人的能力(編譯原理基礎基本可以忽略),我并無法保證本文以及對應的代碼中不出現錯誤。如果大家在閱讀代碼的過程中,發現了一些錯誤,或者寫的不好的地方,可以提出來,我來修改。如果這些錯誤對你造成了困擾,這里先說一聲很抱歉。最后,本文及實現主要參考了一起寫一個JSON解析器和如何編寫一個JSON解析器兩篇文章及兩篇文章對應的實現代碼,在這里向著兩篇博文的作者表示感謝。好了,本文到此結束,祝大家生生活愉快!再見。
?參考
- 本文鏈接:?https://www.tianxiaobo.com/2018/01/18/自己動手實現一個簡單的JSON解析器/
from:http://www.tianxiaobo.com/2018/01/18/%E8%87%AA%E5%B7%B1%E5%8A%A8%E6%89%8B%E5%AE%9E%E7%8E%B0%E4%B8%80%E4%B8%AA%E7%AE%80%E5%8D%95%E7%9A%84JSON%E8%A7%A3%E6%9E%90%E5%99%A8/?
總結
以上是生活随笔為你收集整理的自己动手实现一个简单的JSON解析器的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 爬虫技术经历
- 下一篇: 自己动手实现的 Spring IOC 和