项目开篇：项目介绍 & 当前开发成果总结

文集地址：从零开始的minecraft - nbt序列化库

项目地址：https://github.com/Cmyna/mnbt（可使用Jitpack配合Gradle/Maven导入项目）

摘要：nbt作为一种数据结构，也是一种序列化的表示方式，所谓序列化，也就意味着我们可以将其当成一种形式语言进行看待，也可以用4种形式文法总结其语法。那么，nbt是属于哪种形式语言？用哪种形式文法可以表示它？

前置知识： 编译原理 / Chomsky 形式语言相关知识，nbt数据结构

看了一眼上次这个系列的更新时间，已经是四个月前的事情了，当时我已经觉得整个项目的整体框架已经成型了，尽管还有些看起来很别扭的地方，但总体上“似乎”是改不了什么东西，或者做什么结构上的优化了。时隔数个月，突然一时兴起想回顾一下整个项目，突然发现整个架构设计有着一个“根本性错误”，随便找个比喻，这个错误就像是拿电脑显卡去煎蛋，显卡很好，是战术级核显卡，煎蛋也不错，至少它能吃，但是拿显卡去煎蛋……

那么在说清楚这个“根本性错误”之前，我得引入另一个重要概念：形式语言。当然可能诸位不了解形式语言是什么，或者哪怕大学里学过编译原理这门课，知道这是个什么东西，也难以联想这能和一个序列化库的“根本性错误”有什么联系。确实，一般来说形式语言似乎是编程语言工程师或者是编译器开发工程师才会了解的东西；Nbt，一个不算多么复杂的数据结构会需要用到这种东西吗？

如果不考虑NBT这个例子的话，形式语言在其他地方有很多应用，只是由于这些使用实在太过广泛，以至于使用者并不需要了解过编译原理就能“开箱即用”。一个典型的例子是正则表达式，它的绝大部分可以被归属于形式语言中的“正则语言”（Regular Language），也就是可以被有限状态自动机识别；另一个例子是json数据结构，没错它是一个数据结构同时也可以算作一个“上下文无关语言”，而如果了解上下文无关语言的话，与之相对的可以识别的机器模型叫做下推自动机（Push Down Automata）。和有限状态自动机最为不同的一点是下推自动机多了一个栈用于存储额外的信息；正因如此，在实际应用中我们可以简单地使用一个栈或者递归的方式去解析类似json这样的文本。大多数json序列化库也正是这样做的，包括java中著名的Jackson，Gson等序列化库。

还有类似1+1=2这种初等数学表达公式，常用的数学公式语法可以被称为“中缀表达式”这种东西，而中缀表达式是典型的上下文无关语言，同样可以通过下推自动机识别

简而言之，几乎所有的计算机数据格式，乃至于除了计算机数据格式以外的以各种规则限定的的文本写法，都可以用形式语言的方式进行分析。每一个形式语言都对应一个可以解析该语言的机器。总体来说，形式语言的文法可以分为0-3型文法（或者也分别称为短语文法、上下文有关文法、上下文无关文法和正则文法），每种文法对应一种类型的自动机。从0型文法（短语文法）到3型文法（正则文法），文法限制逐渐增加，也意味着表达能力越弱；表达能力强的文法对应的自动机可以处理更弱的文法，反之则不行。因此json格式作为一种上下文无关语言，其属于2型文法，那么从0型到2型文法对应的自动机都可以处理json类型的数据格式，而正则文法对应的有限状态自动机则不行。

（想象一个在随便某个编程语言实现的有限状态自动机，也就是说除了一个状态表、状态转换规则和表示当前状态的变量以外不能有其他东西，然后用这种东西解析一个json数据格式，比如像这样的`[[[[[[[[[[]]]]]]]]]]`，没错这是个合法的json格式，我还可以在里面插无限个方括号，但如果真打算用有限状态自动机的模型实现解析的话emmm）

那么对于NBT这个数据结构呢？它自然也可以被归类为使用某种文法组织的形式语言，以及一个对应的自动机。但这和我所说的项目中的“根本性错误”又有什么关系呢？为了说明清楚问题，我还是得先从弄明白NBT到底可以看作一种什么形式语言开始说起。

形式文法定义：

要分析NBT的文法，我们可以先从经典的形式文法定义开始，也就是四元集合（N, , P, S)

N代表一系列非终结符号，表示一种语言的“生成方式”，它里面所有的符号仅表示一个生成过程，不存在于由文法得到的任意字符串中，

表示终结符号集合，属于某一语言的字符串当中的所有字符应在这个集合X中。

S则是一个简单的开始符号集合，所有该形式语言的字符串都可以从这些开始符号生成

P则表示生成规则，大致长成类似A->B的形式，简单来说就是可以看成从一个符号串到另一个符号串的映射，而这两符号串当中的符号可以属于终结符集合或非终结符N、还可以是开始符号S。不同种类文法的主要区别就在于这个生成规则上，限制越强的语言，其生成规则的限制也同样越强。

子语言：

emmm“子语言”这个称呼是我自创的，因为我确实不知道应该如何形容接下来要说的内容，而且就我学过的科班编译原理课程也没有对这种东西起过正式名称，所以就暂时这么称呼了。子语言是为了把一个很复杂的语言抽象、分离、“解耦”成更简单的部分，这样我们就可以专注于某一部分而不用迷失在细节之中。简单来说，子语言就是某个形式语言的一小部分，它可以被单独分离出来，但同时子语言也是一个完整的形式语言，同样拥有四元集合（N, , P, S)，假设我们将父语言叫做L0，子语言叫做L1，二者关系则为：L1L0

另外作为子语言L1相对于L0的补L2，构成了另一个形式语言，二者的关系为

L1L2=L0, 

L1L2=

也就是L1和L2共同构成语言L0，且L1和L2无交集。

除此之外，L2还承担生成子语言L1的职责，也就是说在L2的生成规则P中会生成一些特定的符号s，这些符号在L2中作为终结符，但是在L1中作为起始符号。换句话说，我们把这些符号s当作是对L1语言的“代表”，每当出现这种符号时，我们就将其当作是一段属于L1语言的字符串即可。

NBT的文法分析：

简单Tag类型

有了以上这些，我们便可以开始尝试分析NBT是什么形式文法了，我们可以先从简单的开始，比如一个Int Tag。它由两部分组成，Tag Head 和Tag Value，根据上面我们所叙述的，我们完全可以把这两部分当成两个独立的“子语言”，不妨称之为和，我们再将NBT所代表的形式语言称为，那么我们便可以开始写他们之间的关系了。中生成一个Int Tag的规则如下：

S是的起始符号，和则是两个终结符，且同样是两个子语言和的起始符号

接下来我们可以开始分析用于生成Tag Head的子语言，然后我们就发现了问题：emmmTag Head包含两部分，id和Tag的名字，Tag的名字相对来说是独立的，只是id……他明显和后面的语言相关联，简单来说就是当后面是一个int值时前面的话就得是一个Int Tag的ID，那么语言的生成规则得添加下面一条：

要特别注意在这里，是起始生成符而不是，在语言中只是普通的终结符号而已，也是一个终结符号，表示Int Tag的id值。表示的是一个String类型值的起始生成符（我们不妨将该子语言称为），用于生成Tag Head当中Tag name的部分，但同样的在语言中只被看作普通的终结符号而已。

从这里如果你还很熟悉各种形式文法的话，就能看出变成了一个上下文相关语言。形成了类似于Ab->xxx的形式。但实际上用于生成Tag Head的语言根本不需要用到这么高等级的文法，正则语言完全可以解决这个问题，以下是正则化的写法：

这是的生成规则，在语言看来右边全都是终结符号，只是和又分别作为和的起始生成符。如果把整个语言合成起来，整个语言的生成规则到此就是一个正则化的生成规则——左边单个生成符，右边是终结符右接生成符（在这里我们使用的是更宽泛的正则语言定义，即允许右式多个终结符和多个生成符链接在一起，但必须符合 终结符串-生成符串 这一规则）

然后就是这一子语言了，这里我也懒得赘述了，想象一下在各种编程语言中如何用一个正则表达式表达一个合法的数值，就知道int值的数据格式是一种什么类型的语言了，哪怕在NBT中是以二进制格式存储也没有差别。

其他类似于Byte Tag、Short Tag、Float Tag等简单的Tag类型和Int Tag一样，其生成规则也是相似的，也同样可以通过正则语言进行表示。这里我刚好漏了一个也算“简单类型”的Tag 格式，那就是String Tag，但实际上如果仔细了解其数据结构的话，那么它的格式实际上更接近数组类型的Tag，同样的在Tag Head中声明Tag 名字的部分，使用的是和String Tag的值一样的数据格式。

至于String Tag，以及数组类型Tag格式，这方面涉及到了更加复杂的文法定义，我决定将本篇结束于此，因此只简述其文法特征：String Tag和数组类型的Tag格式、其文法类型直接超过了上下文无关语言，达到了上下文相关语言的范畴。但它又并不是特别复杂的上下文相关语言，某些特殊形式可以相对简单地表述它，具体内容将在下篇文章分析。