寫一個 JSON、XML 或 YAML 的 Parser 的思路是什麼？

01-16

本人是做java開發的。依賴java大量現成的包或者框架，工作中甚至都遇不到要解析xml和json的情況。就算有業務需要定義業務相關的xml(比如自己寫一個簡單的flow引擎),也有大量的第三方包可以非常方便的處理xml。
我知道xml, json和yaml的parser實現都是按照他們的規範來的。
最近比較閑，就想自己實現一個yaml的parser。但是看完規範後，完全沒有思路。看過很多版本的源碼，都感覺需要大量的代碼才能實現。自己完全理不出流程。

感覺可能是自己演算法這塊太弱了。
請問有做過類似事情的么？你們怎麼思考這類問題的？這類問題有一個通用的流程么？這類問題就必須寫那麼多代碼才能實現么？

2016/9/15 更新：請移玉步至《從零開始的 JSON 庫教程 - Milo的編程 - 知乎專欄》。

---

最初我的RapidJSON的parser只有幾百行代碼，因為JSON簡單的特點，寫了一個recursive的parser，tokenizer都不用分開寫。

https://code.google.com/p/rapidjson/source/browse/tags/version0.1/include/rapidjson/reader.h

過了幾年，直至上個月，為了避免recursive parser可能遇到stack overflow的可能性，@丁歐南替RapidJSON寫了一個不使用call stack recursion的"iterative parser"。它的狀態機是這樣的：

這裡有一些記述 RapidJSON: Internals。不過現時iterative版本還是慢一點點，所以暫時兩個parser同時並存，可在編譯期選擇。

我想說，其實因本人的本科非計算機專業，沒學過編譯理論。但對於簡單語法的語言，看著EBNF應該可以寫一個parser。

最重要的，是開發大量的unit test，確保執行正確。RapidJSON除了獨立測試parser的各部分（rapidjson/readertest.cpp at master 路 miloyip/rapidjson 路 GitHub），也測試了一些正確和錯誤JSON文件的roundtrip轉換（rapidjson/bin/jsonchecker at master 路 miloyip/rapidjson 路 GitHub）。基本上是Test-Driven Development(TDD)。

貼一篇老文。

怎樣實現一個JSON庫

關於

本文介紹了如何使用實現一個JSON解析器（parser）。

如果你對下面的內容感興趣：

實現基本的詞法分析，語法分析。
解析器的基本原理。

那麼請繼續閱讀。

注意

代碼大量使用了C# 6中的特性。請使用Visual Studio 2015來組織項目代碼。.NET框架版本為4.6。文中代碼均可以在下列網站找到：

國內用戶請使用GitOSC
Github

使用樣例

這個庫可以被這樣使用：

var jsonValue = FadeJson.JsonValue.FromFile("your json file path"); var value = jsonValue["frameworks"]["dotnet"]["dependencies"]["System.Linq"][5].ValueOf();

什麼是Json

JSON(JavaScript Object Notation)是一種輕量級的數據交換格式。一個典型的JSON文件就像這樣：

{ "name" : "XiaoMing", "age" : 12, "isMarried?" : false, "hobby" : [ "playing football for ", 13 , "years" , true ] }

描述JSON的結構

JSON的結構有兩種，一種是由花括弧（{和}）包裹，並用逗號（,）分隔的值鍵對（key-value-pair）列表；另一種是由中括弧（[和]）包裹，並用逗號分隔的值列表。我們將用同一個類JsonValue來表示所有的字面量和這兩種結構，並用C#中的string，int和bool來分別描述上述的三種字面量類型。

用一個枚舉來表示JsonValue內儲存的值的類型：

public enum JsonType { Array, Object, Int32, String, Double, Boolean, Null, Symbol }

對於JsonValue，我們可以很用一個dictionary和一個list來分別表示給出這樣的表示：

public struct JsonValue { private readonly Dictionary& dictionary; private readonly List& list; public JsonType Type { get; set; } public string Value { get; set; }

public JsonValue(JsonType type) { dictionary = null; list = null; Value = string.Empty; switch (type) { case JsonType.Array: list = new List&(); Type = JsonType.Array; break; case JsonType.Object: dictionary = new Dictionary&(); Type = JsonType.Object; break; } Type = type; } }

解析過程

這個JSON解析器由接受一個文本流作為輸入，輸出一個該文本流對應的JsonObject。解析的過程如下（這是最普通、最通用的結構）：

構造一個詞法分析器，把文本流轉換成Token流
構造一個語法分析器，把Token流轉換成JsonValue

當然，我們可以觀察到，一個通常的JSON字面量是不含葉子的。而不含葉子的JsonValue跟一個通常的Token幾乎等同。所以，我們可以在詞法分析的時候，就構建JsonValue，並且在語法分析的時候再構建一棵樹。

優點自然是減少了新對象的生成，使得運行效率大大提高。因為對GC的負擔幾乎減少了一倍。

詞法分析（Tokenization）

詞法分析負責把輸入字元流解析成一個個詞法單元（Token），以便之後的處理。

首先要定義Token。而在上面的討論中，我們發現可以直接使用JsonValue來代替Token結構。

一般的Lexer是一個DFA（有限狀態機，下面有實例幫助你迅速理解DFA）。

我們可以用很多種方法來表示。比如顯式地使用一個表示狀態的變數來表示當前的狀態。

我更喜歡用控制流的變化來表示隱式地表示狀態的變化。

於是我們可以得到這樣的一個NextToken函數，調用一次這個函數，便會返回一個Token。再調用一次，返回下一個Token。於是我們就把字元流變成了Token流。

NextToken() return Token { c = lookahead() if c is whitespace Consume() return NextToken() if c is a char like "{",":","[" Consume() return new Token(c) if c is digit return GetIntToken() if c is """ return GetStringToken() if c is "t" or "f" return GetBoolToken()

return null }

（偽代碼表示，其中lookahead()表示當前字元，但不移動流指針的位置；Consume()也表示當前的字元，但在調用後，會將表示字元流當前位置的指針推進一位）

為了讓大家更好地理解DFA的概念，我用最簡單也最骯髒的GetBoolToken()函數來舉例子。

我們為了解析true的DFA長這個樣子（用於解析false的DFA同理）：

轉化成代碼是這個樣子：

private Token? GetBoolToken() { var c = PeekChar(); if (c == "t") { GetChar(); c = PeekChar(); if (c == "r") { GetChar(); c = PeekChar(); if (c == "u") { GetChar(); c = PeekChar(); if (c == "e") { GetChar(); return new Token("true", TokenType.BoolType); } } } } if (c == "f") { GetChar(); c = PeekChar(); if (c == "a") { GetChar(); c = PeekChar(); if (c == "l") { GetChar(); c = PeekChar(); if (c == "s") { GetChar(); c = PeekChar(); if (c == "e") { GetChar(); return new Token("false", TokenType.BoolType); } } } } } throw new FormatException(); }

當然我們大可不必這麼寫。

我們還可以計算各個token的FIRST集合。然後就可以得到一個醜陋但是快速的Tokenizer。代碼就是這樣：

public JsonValue GetNextToken() { while (true) { var c = cache.Lookahead(); switch (c) { case " ": case " ": case " ": case " ": cache.Next(); continue; case ":": cache.Next(); return JsonValue.Colon; case ",": cache.Next(); return JsonValue.Comma; case "{": cache.Next(); return JsonValue.LeftBrace; case "}": cache.Next(); return JsonValue.RightBrace; case "[": cache.Next(); return JsonValue.LeftBracket; case "]": cache.Next(); return JsonValue.RightBracket; case "t": case "n": case "f": return ParseKeywordToken(); case """: return ParseStringToken(); case "-": return ParseNumberToken(); case "0": case "1": case "2": case "3": case "4": case "5": case "6": case "7": case "8": case "9": return ParseNumberToken(); default: return JsonValue.Null; } } }

解析其他類型的Token時同理。

語法分析（Parsing）

得到了Token流之後，接下來就是進行語法分析。JSON文法是LL(1)文法，且文法無左遞歸，這使得JSON很容易使用遞歸下降來構造解析器。因此，編寫JSON解析器可以作為一個很好的編譯器前端的學習材料。我們可以簡單地使用遞歸下降構建一個LL(1) Parser。比如：

Parse() return JsonValue{ if lookahead is { return ParseJsonObject() else if lookahead is [ return ParseJsonArray() throw exception }

ParseJsonObject() return JsonValue{ Consume("{") Loop for parsing key-value pair Consume("}") }

以此類推，即可得到一個JSON Parser。

就這樣結束了？

寫一個JSON Parser就是這麼簡單。當然，我也重寫了多次才寫成現在放在github上的那樣的代碼。

那所有的Parser都是這樣簡單的嗎？並不是。

文中的parser還沒有提到錯誤恢復，文法也沒有左遞歸。事實上，一個遞歸下降的parser不能處理左遞歸的文法。現實中的Parser要處理很多問題。比如這樣的歧義（List& b&>）。

它雖然重要，但是很基礎。Parsing不是編譯的全部，這只是編譯的開始。

編譯還包括很多階段，詞法分析和語法分析之後還有語義分析，代碼優化，代碼生成等步驟。當然，隨著相關工具和庫的成熟，編寫一個編譯器也沒有想以前那樣難了。

現在我們要寫一個編譯器，可以直接使用Parser Generater。常見的有ANTLR，bison，flex，VBF等。使用這些工具我們可以很快地生成tokenizer和parser。編譯器前端已經相當成熟。而研究尚未有前端成熟的編譯器後端，也有了很多工具可以選擇。比如LLVM，DLR，JVM，CLR等等。造一門語言不再是一種困難的事情。可以看到每年都有很多語言橫空出世。

如果想練習寫parser的技能，可以嘗試寫寫下列語言的parser或者解釋器（難度逐漸增加）：

小學 - JSON - Lisp

中學 - Lua - Pascal - C的子集

大學 - C - Python

地獄 - C++

先佔坑，說說JSON吧，因為自己寫過。

前面的大神們提到了很多編譯原理的東西，比如詞法分析、EBNF乃至AST之類的名詞。然而如果我們僅僅是要解析JSON這種數據結構的話，其實用不著那麼多東西。要知道JSON的流行很大程度上就是因為它是一個輕量級的、簡單易讀的數據結構。說個無關的，要知道我第一次看編譯原理的書，了解上下文無關文法這個概念的時候，很大程度上是靠了腦子裡閃現出來的JSON官網 JSON 里描述的完整的JSON文法。

object = {} | { members }


members = pair

        | pair , members
pair = string : value
array = []

      | [ elements ]
elements = value

         | value , elements
value = string

      | number

      | object

      | array

      | true

      | false

      | null
string = ""

       | " chars "
chars = char

      | char chars
char = any-Unicode-character-except-"-or--or- control-character

     | "

     | \

     | /

     | 

     | f

     | 
     |

     |

     | u four-hex-digits
number = int

       | int frac

       | int exp

       | int frac exp
int = digit

    | digit1-9 digits

    | - digit

    | - digit1-9 digits
frac = . digits
exp = e digits
digits = digit

       | digit digits

e = e | e+ | e- | E | E+ | E-

JSON的優勢除了文法很簡單之外，還有一個很重要的地方是，我們逐個字元地解析JSON，在不考慮錯誤處理的情況下，甚至都不需要前瞻！舉個例子，在JSON解析的一開始，如果發現是字元"n"，可以立馬斷定是null；是"{"，就是對象。這給我們解析器的編寫帶來了很大的方便。

其實不管是JSON、XML還是YAML，其核心都是要描繪一種樹狀類型的結構。原因是生活中的大部分信息都是以這種形式保存的。有樹，就會有結點。而不同的標記語言，這個結點裡包含的東西也就不同。但是這種樹狀的結構是基本相同的。把源字元串轉換成我們定義好的數據結構的過程，也就是所謂的解析。

那麼解析的難點在哪裡呢？如果一個JSON字元串里的內容僅僅是「true」四個字元，一次strcmp即可完成，你還覺得難嗎？是任意數量的空格嗎？貌似也不是。不知道題主初學編程時有沒有寫過那種「統計輸入中空格的數量」的程序。如果有，其實排除空格的原理差不多。

而且請注意，我們寫一個JSON解析器的目的是讓雜亂的字元串變成C/Java/Python...等語言能夠識別的數據結構。我們所做的工作僅僅是「保存」，沒有「解釋」，更不是「編譯」。外加前面說的根本不需要前瞻一個字元的特性，我們編寫JSON Parser其實連詞法分析都不用。在這裡，我們先定義好一個JSON數據結構的結點類型。

struct json_node { enum { NUMBER, STRING, ARRAY, OBJECT, TRUE, FALSE, NUL, UNKNOWN } type; char *name; union { double number; struct json_node *child_head; char *val_str; }; };

定義好了這個結構體，我們的工作其實就已經完成一半了。根據上面完整定義的文法，再來寫解釋基本類型的代碼。

struct json_node * parse_json(void) { struct json_node *res = malloc(sizeof(struct json_node)); char ch = getchar(); switch (ch) { case "t": while (isalpha(ch)) { ch = getchar(); } res-&>type = TRUE; break; /* 對於null和false也一樣 */ case """: res-&>type = STRING; /* 尋找到第一個不是轉義字元的雙引號 " */ break; case "+": case "-": case "1": /* 1-9 */ res-&>type = NUMBER; /* 緩衝區存儲字元直到停止，然後用系統庫函數轉換 */ default: res-&>type = UNKNOWN; break; } return res; }

挺容易明白的。

那麼為什麼JSON解析對於一個之前從未寫過的人來說會感覺很難呢？

因為它是遞歸的。

遞歸很強大，很直觀，很簡潔。但對於不懂遞歸的人來說，遞歸往往會使人手足無措。我解析一個true可以，但是我要是要解析未知層數的括弧包著的內容呢？沒關係，我們解析的函數也遞歸調用就行了。只要系統的輸入流一直在向前走，這沒關係。

解析object和array的過程類似，只不過我們把詞法分析和語法分析弄到了一起，所以跳過空格的過程會比較麻煩：

struct json_node * parse_json(void) { /* 開頭的聲明 */ switch (ch) { /* 數字和字元串等的解析 */ case "{": { char *tmp_name = NULL; struct json_node *tmp_child = NULL; struct json_node *tmp_tail = NULL; res-&>type = OBJECT; res-&>child_head = NULL; while (ch != "}") { /* 跳過空格 */ /* 向後解析字元串 */ tmp_name = parse_string(ch); /* 跳過空格 */ /* 冒號 */ ch = getchar(); current_child = parse_json(); current_child-&>name = tmp_name; /* 跳過空格 */ /* 逗號 */ ch = getchar(); /* 跳過空格 */ if (res-&>child_head == NULL) { res-&>child_head = tmp_tail = tmp_child; } else { tmp_tail-&>next = tmp_child; tmp_tail = tmp_child; } } break; } case "[": { /* * 跟解析對象的過程類似 * 只不過沒有名字 */ } /* 未知情況 */ } return res; }

通常解析器都有這麼幾個步驟：

詞法分析生成token流
語法分析生成抽象語法樹（AST）
針對抽象語法樹進行語義分析，構建你需要的內部數據結構，或生成代碼

其中語法分析可以用解析器生成工具，如yacc，javacc，antlr什麼的，用BNF或類似的形式語言編寫語法規則以及規約後的處理代碼，然後自動生成編譯器代碼。

參考下編譯原理方面的書吧，然後再找開源的實現看看。

我自己就寫了個類似antlr的東西，然後給json和xml寫了文法，C++代碼就這麼出來了，可供參考。

https://gac.codeplex.com/SourceControl/latest#Common/Source/Parsing/Json/ParsingJson_Parser.parser.txt

https://gac.codeplex.com/SourceControl/latest#Common/Source/Parsing/Xml/ParsingXml_Parser.parser.txt

效果良好，我的庫的所有parser都是這麼寫出來的

占坑

上網搜pyparsing有真相

看看lemon，短小精悍

可以這樣,先分析文法.我沒用yacc,就直接裸寫了.

效率不是重點,重點是原理.

標識的是終結符號.詞法分析我不講了,沒什麼意思.就是把輸入變成終結符序列.重點是語法分析.

JSON_Value =&> JSON_Block ----(1) | string ----(2) | umber ----(3) | [JSON_Value(,JSON_Value,....)] ----(4)

JSON_Block =&> { string:JSON_Value (,string:value ,...) }

其實核心的就是這兩條.

分析JSON_Value的類型,可以只讀取第一個終結符.

cond&<1&> 如果是"[" ,進行列表解析,走路線 4 .對其中每個元素進行JSON_Value的遞歸解析(至於消除遞歸,主要思路就是用模擬調用棧的方法.);

cond&<2&> 如果是"{",進行JSON_Block解析.走路線1.

cond&<3&>是string類型或者
umber類型(null和他們類似),可立即推導出結果.

因此,上述文法是LL(1)的.連左遞歸消除和提取公因子都不需要.

這個實現起來應該是很容易的.大概這樣:(類似的東西我寫過很多份了,就不專門寫了.我在這裡給個大概的框架吧.這個編輯器寫東西也挺麻煩的)

class JSON_Value { JSON_Value(Atom_List)//輸入終結符列表.是可變列表.一次操作至少可以彈出一個元素. { syntaxPath=-1; switch Atom_List[0].Type //預讀一個符號,立即決定產生式. { case "[": ....//遞歸調用. case "{" ...//遞歸調用. } Atom_List.pop(); //一次操作,至少彈出一個元素.調用次數保證為O(n). } } class JSON_Block { JSON_Block(Atom_List) { //同上. } }

大概這樣.如果JSON以{ ... }套住,運行時就只要解析下JSON_Block就可以了.如果可能以[ ... ]開頭就再判斷下.不是很複雜.

先仿製一個yacc,再仿製一個flex,之後就批量生成XML JSON的解析了,

這種批量生成代碼的感覺爽快無比2333(我個人就是這樣乾的

用遞歸下降法。

我的文章http://www.jianshu.com/p/2f33e86dde92。目標當然是把字元串轉換成需要的數據結構。推薦閱讀《編程語言設計模式》。我是從這篇文章學會的https://github.com/rspivak/lsbasi(抄來的代碼)。

主要得熟悉各種類型，和遞歸的思想。

我來推薦一篇閱讀，functional的parser。http://fsharpforfunandprofit.com/posts/understanding-parser-combinators/

這三個都是很簡單的 schema，並不需要什麼高深的理論和演算法。

寫個循環，依次讀入一個字元，根據當前狀態（開標籤、key 已知等）決定怎麼處理和該進入什麼狀態。普通水平兩個小時內 json 能搞定，xml 狀態更多些，體力活兒。

其實就是有限狀態機。

1，了解一點關於自動機的知識。

2，寫一個遞歸下降LL的加減乘除四則計算的parser。估計在200-500行之間。

3，寫一個遞歸下降LL的Json parser。長度看處理問題的能力。500-3000行之間。

如果說LALR(1)解析還算比較麻煩的東西，LL(1) 解析有個毛的難度啊？？？

有限狀態機