用Python編寫JSON解析器的概述

01-30

0x00 序言

蒟蒻作者對Parser，Tokenizer這些東西並不很了解，或者說了解程度僅足以支撐我寫一個JSON的解析器.....還望各路大佬多多指點，批評。另外這是我第一次在zhihu上寫文章...並不太會用這個編輯器（感覺不太好用...?）所以排版有可能略難堪請各位多多包容（笑

雖然Python已經有自帶的json模塊，但手動實現一個還是能在一定程度上提升對JsonParser的了解....吧。

本文是對整個Parser編寫JSON解析器的簡要概述。

項目地址：JsonParser

由於該項目用於練手+休閑，所以代碼並不賞心悅目。

0x01 解析器架構

效仿大佬們的方法，我們先看一下這個解析器是怎樣工作的：

如圖，首先我們要有原始數據。JSON的原始數據就是一個字元串；然後將字元串傳到Reader中，Reader的功能有：1. 返回當前游標位置的字元;2. 向後移動游標;3. 向前移動游標。這樣做是為了能夠逐個字元讀入原始數據並且通過上下文判斷關鍵詞作用。Tokenizer是將關鍵字身份和關鍵字所對應值存入到一個對象中提供給Parser進行進一步解析。Parser可以通過Tokenizer提供的Tokens判斷語法正確性同時根據tokens的含義將數據存入Python的數據對象中。說起來比較簡單，寫起來難度不大但有一些複雜。這裡直接用Python實現一波了...

0x02 定義JSONArray和JSONObject

這應該是寫這個Parser最容易的一步了。JSONArray是個list，JSONObject是個dict。

對於JSONArray, 我們需要以下這些功能：

1. append()

2. size()

3. __getitem__() #重載list的函數

4. __str__() # 格式化輸出

對於JSONObject:

1. __getitem__(key)

2. __setitem__(key, value)

3. __str__() # 格式化輸出

由於比較Simple，這裡就不粘貼實現了。

0x03 Reader

Reader用於接收一個字元串然後使用一個cursor逐個字元進行讀取。通過nextPos()獲取當前位置字元並將游標向後移動一位：

class Reader(object) :n def __init__(self, data) :n self.data = datan self.cursor = 0n def nextPos(self) :n self.cursor += 1n return self.data[self.cursor-1]n

同時我們需要檢查是否有下一位：

def hasNext(self) :n return self.cursor < len(self.data)n

對於移動到上一位，我們需要作越界判斷：

def prevPos(self) :n self.cursor = max(self.cursor-1, 0)n

至此我們Reader的基礎功能就算完成了。

0x04 Token & Tokenizer

Token用於標註一個詞素的意義以及對應值。例如：[是JSONArray開始(BEGIN_ARRAY)的信號詞，對應值為[。由於JSON中的Token比較少，所以為了方便編寫Parser，我們每一個Token所對應的意義用 $2^k$ 來表示。

Tokenizer是將原始數據轉化為一個Token列表讓，Parser能看懂的數據。

對數據進行Tokenize時，我們需要將字元逐個取出傳入Tokenizer並判斷當前字元是否屬於關鍵字(Signal)，如果是關鍵字，我們對這個字元(或連帶之後的值)一併進行處理。例如，如果當前處理的字元為{，我們就返回一個Token(BEGIN_OBJECT, {)。遇到雙引號時，後面所對應數據為字元串;遇到數字或減號時，後面對應的時數字etc. 這時學習OI時接觸的讀入優化就派上用場啦！事實上，在這個Project中，Tokenizer就是實現各種數據的讀入優化然後將他們的意義和值存入一個列表中....由於代碼較長，具體實現可以看這裡:Tokenizer。當然這裡的Tokenizer並不完美...還需優化（也許有更加優美的實現方法呀）。放一個readInt()佔位好了。

0x05 Parser

整個項目的核心，也是比較難調試的地方...作者的電腦沒有PyCharm只好中間輸出調試+瞪眼法調試了2333。當Parser拿到了她的好朋友Tokenizer辛勤勞動的成果——Tokenlist時，首先她會看一下，我是要解析一個JSONArray呢？還是要解析一個JSONObject呢？於是她就去看了第一個Token，如果這個Token的意義三BEGIN_ARRAY，那麼她就先執行parseArray()，否則去執行parseObject()。在進行解析時，我們首先要規定我們下一個期望出現的Token時什麼。例如，如果當前讀到了BEGIN_ARRAY，那麼下一個Token我們期待是BEGIN_STRING, BEGIN_BOOL, BEGIN_NUM, BEGIN_NULL和END_ARRAY。但如果當前是BEGIN_OBJECT，那麼下一個期待的Token只能是BEGIN_STRING或者END_OBJECT了(JSONObject只能以str作為key)。這時我們規定Token含義為 $2^k$ 的好處就體現出來了。事實上，這樣規定就相當於狀態壓縮：將一個Token的含義定義為在一個整數的二進位下第 $k$ 位為1。這樣，如果我們期望下一次是BEGIN_STRING或者END_OBJECT時，我們期望得到下一個Token的值( $exp$ )和實際接收到的Token的值( $actual$ )進行按位與運算，如果得到的數字不是0，那麼二進位下的 $exp$ 和 $actual$ 有至少一位都是1，這就說明當前Token是我們期望得到的：

# 設定期望Tokennexpected = END_OBJECT | BEGIN_STRINGn# 判定actual是否屬於END_OBJECT或者BEGIN_STRINGnif expected & actual == 0 :n return Falsenreturn Truen

由於STRING在JSONObject中既可以作KEY又可以作VALUE，因此我們需要對其前一個Token進行判斷，如果前一個Token是COLON(冒號)，那麼當前就是VALUE，否則是一個KEY。

另外，中間可能存在遞歸處理，注意一些特殊數據可能會爆棧(滑稽

當然可以用Python方便的tuple來搞啦～反正都可以實現(滑稽

由於Parser實現代碼較長，大家可以去Parser查看代碼。

0x06 後記

寫這個Parser+調試大概花了我一下午吧...第一次寫，不是太清楚。這篇文章也許並不如正在閱讀的您期待的那樣好，只是大概地講述了Json解析的步驟和大致的原理...不過還有代碼可以看嘛233333.......

參考文章

一起寫一個JSON解析器

JAVA自已設計JSON解析器

感謝這兩位作者的文章