項(xiàng)目開篇：項(xiàng)目介紹 & 當(dāng)前開發(fā)成果總結(jié)

文集地址：從零開始的minecraft - nbt序列化庫

項(xiàng)目地址：https://github.com/Cmyna/mnbt（可使用Jitpack配合Gradle/Maven導(dǎo)入項(xiàng)目）

摘要：nbt作為一種數(shù)據(jù)結(jié)構(gòu)，也是一種序列化的表示方式，所謂序列化，也就意味著我們可以將其當(dāng)成一種形式語言進(jìn)行看待，也可以用4種形式文法總結(jié)其語法。那么，nbt是屬于哪種形式語言？用哪種形式文法可以表示它？

前置知識： 編譯原理 / Chomsky 形式語言相關(guān)知識，nbt數(shù)據(jù)結(jié)構(gòu)

看了一眼上次這個系列的更新時間，已經(jīng)是四個月前的事情了，當(dāng)時我已經(jīng)覺得整個項(xiàng)目的整體框架已經(jīng)成型了，盡管還有些看起來很別扭的地方，但總體上“似乎”是改不了什么東西，或者做什么結(jié)構(gòu)上的優(yōu)化了。時隔數(shù)個月，突然一時興起想回顧一下整個項(xiàng)目，突然發(fā)現(xiàn)整個架構(gòu)設(shè)計(jì)有著一個“根本性錯誤”，隨便找個比喻，這個錯誤就像是拿電腦顯卡去煎蛋，顯卡很好，是戰(zhàn)術(shù)級核顯卡，煎蛋也不錯，至少它能吃，但是拿顯卡去煎蛋……

那么在說清楚這個“根本性錯誤”之前，我得引入另一個重要概念：形式語言。當(dāng)然可能諸位不了解形式語言是什么，或者哪怕大學(xué)里學(xué)過編譯原理這門課，知道這是個什么東西，也難以聯(lián)想這能和一個序列化庫的“根本性錯誤”有什么聯(lián)系。確實(shí)，一般來說形式語言似乎是編程語言工程師或者是編譯器開發(fā)工程師才會了解的東西；Nbt，一個不算多么復(fù)雜的數(shù)據(jù)結(jié)構(gòu)會需要用到這種東西嗎？

如果不考慮NBT這個例子的話，形式語言在其他地方有很多應(yīng)用，只是由于這些使用實(shí)在太過廣泛，以至于使用者并不需要了解過編譯原理就能“開箱即用”。一個典型的例子是正則表達(dá)式，它的絕大部分可以被歸屬于形式語言中的“正則語言”（Regular Language），也就是可以被有限狀態(tài)自動機(jī)識別；另一個例子是json數(shù)據(jù)結(jié)構(gòu)，沒錯它是一個數(shù)據(jù)結(jié)構(gòu)同時也可以算作一個“上下文無關(guān)語言”，而如果了解上下文無關(guān)語言的話，與之相對的可以識別的機(jī)器模型叫做下推自動機(jī)（Push Down Automata）。和有限狀態(tài)自動機(jī)最為不同的一點(diǎn)是下推自動機(jī)多了一個棧用于存儲額外的信息；正因如此，在實(shí)際應(yīng)用中我們可以簡單地使用一個棧或者遞歸的方式去解析類似json這樣的文本。大多數(shù)json序列化庫也正是這樣做的，包括java中著名的Jackson，Gson等序列化庫。

還有類似1+1=2這種初等數(shù)學(xué)表達(dá)公式，常用的數(shù)學(xué)公式語法可以被稱為“中綴表達(dá)式”這種東西，而中綴表達(dá)式是典型的上下文無關(guān)語言，同樣可以通過下推自動機(jī)識別

簡而言之，幾乎所有的計(jì)算機(jī)數(shù)據(jù)格式，乃至于除了計(jì)算機(jī)數(shù)據(jù)格式以外的以各種規(guī)則限定的的文本寫法，都可以用形式語言的方式進(jìn)行分析。每一個形式語言都對應(yīng)一個可以解析該語言的機(jī)器。總體來說，形式語言的文法可以分為0-3型文法（或者也分別稱為短語文法、上下文有關(guān)文法、上下文無關(guān)文法和正則文法），每種文法對應(yīng)一種類型的自動機(jī)。從0型文法（短語文法）到3型文法（正則文法），文法限制逐漸增加，也意味著表達(dá)能力越弱；表達(dá)能力強(qiáng)的文法對應(yīng)的自動機(jī)可以處理更弱的文法，反之則不行。因此json格式作為一種上下文無關(guān)語言，其屬于2型文法，那么從0型到2型文法對應(yīng)的自動機(jī)都可以處理json類型的數(shù)據(jù)格式，而正則文法對應(yīng)的有限狀態(tài)自動機(jī)則不行。

（想象一個在隨便某個編程語言實(shí)現(xiàn)的有限狀態(tài)自動機(jī)，也就是說除了一個狀態(tài)表、狀態(tài)轉(zhuǎn)換規(guī)則和表示當(dāng)前狀態(tài)的變量以外不能有其他東西，然后用這種東西解析一個json數(shù)據(jù)格式，比如像這樣的`[[[[[[[[[[]]]]]]]]]]`，沒錯這是個合法的json格式，我還可以在里面插無限個方括號，但如果真打算用有限狀態(tài)自動機(jī)的模型實(shí)現(xiàn)解析的話emmm）

那么對于NBT這個數(shù)據(jù)結(jié)構(gòu)呢？它自然也可以被歸類為使用某種文法組織的形式語言，以及一個對應(yīng)的自動機(jī)。但這和我所說的項(xiàng)目中的“根本性錯誤”又有什么關(guān)系呢？為了說明清楚問題，我還是得先從弄明白NBT到底可以看作一種什么形式語言開始說起。

形式文法定義：

要分析NBT的文法，我們可以先從經(jīng)典的形式文法定義開始，也就是四元集合（N, , P, S)

N代表一系列非終結(jié)符號，表示一種語言的“生成方式”，它里面所有的符號僅表示一個生成過程，不存在于由文法得到的任意字符串中，

表示終結(jié)符號集合，屬于某一語言的字符串當(dāng)中的所有字符應(yīng)在這個集合X中。

S則是一個簡單的開始符號集合，所有該形式語言的字符串都可以從這些開始符號生成

P則表示生成規(guī)則，大致長成類似A->B的形式，簡單來說就是可以看成從一個符號串到另一個符號串的映射，而這兩符號串當(dāng)中的符號可以屬于終結(jié)符集合或非終結(jié)符N、還可以是開始符號S。不同種類文法的主要區(qū)別就在于這個生成規(guī)則上，限制越強(qiáng)的語言，其生成規(guī)則的限制也同樣越強(qiáng)。

子語言：

emmm“子語言”這個稱呼是我自創(chuàng)的，因?yàn)槲掖_實(shí)不知道應(yīng)該如何形容接下來要說的內(nèi)容，而且就我學(xué)過的科班編譯原理課程也沒有對這種東西起過正式名稱，所以就暫時這么稱呼了。子語言是為了把一個很復(fù)雜的語言抽象、分離、“解耦”成更簡單的部分，這樣我們就可以專注于某一部分而不用迷失在細(xì)節(jié)之中。簡單來說，子語言就是某個形式語言的一小部分，它可以被單獨(dú)分離出來，但同時子語言也是一個完整的形式語言，同樣擁有四元集合（N,?,?P, S)，假設(shè)我們將父語言叫做L0，子語言叫做L1，二者關(guān)系則為：L1L0

另外作為子語言L1相對于L0的補(bǔ)L2，構(gòu)成了另一個形式語言，二者的關(guān)系為

L1L2=L0,?

L1L2=

也就是L1和L2共同構(gòu)成語言L0，且L1和L2無交集。

除此之外，L2還承擔(dān)生成子語言L1的職責(zé)，也就是說在L2的生成規(guī)則P中會生成一些特定的符號s，這些符號在L2中作為終結(jié)符，但是在L1中作為起始符號。換句話說，我們把這些符號s當(dāng)作是對L1語言的“代表”，每當(dāng)出現(xiàn)這種符號時，我們就將其當(dāng)作是一段屬于L1語言的字符串即可。

NBT的文法分析：

簡單Tag類型

有了以上這些，我們便可以開始嘗試分析NBT是什么形式文法了，我們可以先從簡單的開始，比如一個Int Tag。它由兩部分組成，Tag Head 和Tag Value，根據(jù)上面我們所敘述的，我們完全可以把這兩部分當(dāng)成兩個獨(dú)立的“子語言”，不妨稱之為和，我們再將NBT所代表的形式語言稱為，那么我們便可以開始寫他們之間的關(guān)系了。中生成一個Int Tag的規(guī)則如下：

S是的起始符號，和則是兩個終結(jié)符，且同樣是兩個子語言和的起始符號

接下來我們可以開始分析用于生成Tag Head的子語言，然后我們就發(fā)現(xiàn)了問題：emmmTag Head包含兩部分，id和Tag的名字，Tag的名字相對來說是獨(dú)立的，只是id……他明顯和后面的語言相關(guān)聯(lián)，簡單來說就是當(dāng)后面是一個int值時前面的話就得是一個Int Tag的ID，那么語言的生成規(guī)則得添加下面一條：

要特別注意在這里，是起始生成符而不是，在語言中只是普通的終結(jié)符號而已，也是一個終結(jié)符號，表示Int Tag的id值。表示的是一個String類型值的起始生成符（我們不妨將該子語言稱為），用于生成Tag Head當(dāng)中Tag name的部分，但同樣的在語言中只被看作普通的終結(jié)符號而已。

從這里如果你還很熟悉各種形式文法的話，就能看出變成了一個上下文相關(guān)語言。形成了類似于Ab->xxx的形式。但實(shí)際上用于生成Tag Head的語言根本不需要用到這么高等級的文法，正則語言完全可以解決這個問題，以下是正則化的寫法：

這是的生成規(guī)則，在語言看來右邊全都是終結(jié)符號，只是和又分別作為和的起始生成符。如果把整個語言合成起來，整個語言的生成規(guī)則到此就是一個正則化的生成規(guī)則——左邊單個生成符，右邊是終結(jié)符右接生成符（在這里我們使用的是更寬泛的正則語言定義，即允許右式多個終結(jié)符和多個生成符鏈接在一起，但必須符合 終結(jié)符串-生成符串 這一規(guī)則）

然后就是這一子語言了，這里我也懶得贅述了，想象一下在各種編程語言中如何用一個正則表達(dá)式表達(dá)一個合法的數(shù)值，就知道int值的數(shù)據(jù)格式是一種什么類型的語言了，哪怕在NBT中是以二進(jìn)制格式存儲也沒有差別。

其他類似于Byte Tag、Short Tag、Float Tag等簡單的Tag類型和Int Tag一樣，其生成規(guī)則也是相似的，也同樣可以通過正則語言進(jìn)行表示。這里我剛好漏了一個也算“簡單類型”的Tag 格式，那就是String Tag，但實(shí)際上如果仔細(xì)了解其數(shù)據(jù)結(jié)構(gòu)的話，那么它的格式實(shí)際上更接近數(shù)組類型的Tag，同樣的在Tag Head中聲明Tag 名字的部分，使用的是和String Tag的值一樣的數(shù)據(jù)格式。

至于String Tag，以及數(shù)組類型Tag格式，這方面涉及到了更加復(fù)雜的文法定義，我決定將本篇結(jié)束于此，因此只簡述其文法特征：String Tag和數(shù)組類型的Tag格式、其文法類型直接超過了上下文無關(guān)語言，達(dá)到了上下文相關(guān)語言的范疇。但它又并不是特別復(fù)雜的上下文相關(guān)語言，某些特殊形式可以相對簡單地表述它，具體內(nèi)容將在下篇文章分析。