2.1.4 通过有限集描述一门语言

一个好的生成一组对象的方法，是先创建一个小对象，然后制定根据现有对象添加新对象的规则来生成一组完整的对象。“有两个偶数，这两个偶数相加得到的数也是偶数”这样就很有效的生成了所有的偶数的集合。 形式主义者会添加一个说明“并且没有别的数是偶数”，不过我们都理解这个。

假设我们想要生成所有人名的枚举的集合，就像“Tom，Dick和Harry”这种，集合里面除了最后两个之外，其他都用逗号分隔开来。我们不接受“Tom，Dick，Harry”或者“Tom和Dick和Harry”这种类型的，但是我们接受重复的，比如“Grubb, Grubb和Burrowes”¹是可以的。虽然在英语中这不是完整句子，可我们依旧要把他们称作“句子”，因为它们是我们的微型语言——人名枚举集——中的句子。这个简单的结构是：

1. Tom是一个人名，Dick是一个人名，Harry也是一个人名；

2. 一个人名就是一个句子；

3. 一个句子后面跟着一个逗号，然后跟着一个人名又是一个句子；

4. 在枚举结束之前，如果句子的结尾是“，人名”，那用“和人名”来替换。

虽然这样说对于读者的理解很管作用，但是却有几个错误的地方。条件3尤其会带来麻烦。例如，句子并不是以“，人名”结束，而是以“，Dick”或类似的名字结束，“人名”只是一个符号用以代替真实的名字；这样的符号不能在真是的句子中出现而且在结尾处的必须用条件1中给出的名字替代。同样，条款中的“句子”是一个符号，指代真实的句子。所以这里涉及到两种符号：出现在完备句子中的真实符号，比如“Tom”，“Dick”，逗号和“和”；还有中间体符号，像“句子”和“人名”这些不能在完备句子中出现的词。第一种对应前文中提到的单词或标记；它们的专业术语是终结符（或简称终结）。这种中间体符号被称为非终结符，一个很平庸的术语。为了区分它们，我们将终结符用小写字母表示，非终结符用大写字母表示。 非终结符被称为（语法的）变量或句法的类，在语言学语境上。

为了强调按照条件生成的字符，我们应该将“X就是Y”替换成“Y应该用X替换”：如果“tom”是人名（Name）的一个实例，那么不管我们在哪儿看到人名（Name）我们就可以将之缩小范围为“tom”。这给了我们：

1. 人名（Name）可能被“tom”取代

人名（Name）可能被“dick”取代

人名（Name）可能被“harry”取代

2. 句子（Sentence）可能被人名（Name）取代

3. 句子（Sentence）可能被句子（Sentence），人名（Name）取代

4. 句子（Sentence）结尾处的“, 人名（Name）”必须被“和人名（Name）”取代，在人名（Name）被任何替代物替代之前

5. 一个句子只有当它不在包含非终结符时才能结束

6. 我们从句子（Sentence）开始替换过程

条件1到4说明替代物，但是5和6不一样。条件5不是特定于此语法的。它基本都是有效的，而且是我们这个游戏（解析）的规则之一。条件6告诉我们从哪里开始生成。它的名称自然而然的被称为起始符，而且它是每个语法都要求有的。

条件4还是看起来不让人放心；其他大多数规则都写着“可能被取代”，而这条写着“必须被取代”，并且它是指“一个句子的结尾”。其他规则通过替换来生效，但是问题仍在，我们如何用替换来检测一个句子（Sentence）的结尾。这个问题可以通过在结尾处添加一个终止符来解决。如果我们对一个非终结符做了终止标记，这个非终结符不能在除了从“，人名（Name）”替换为“和人名（Name）”处之外使用，那我们就自动执行了这个限制——除非替换检测已经发生否则没有句子将会结束。为了简便起见我们写作——>而不是“可能被替代”；由于终结符和非终结符现在是专业术语，所以我们把他们写成打字机的字样。——>之前的部分称为左手边，之后的部分称为右手边。这就成了图Fig 2.3中的样子。

这是这个配方的简单和比较精确的形式，规则也很简洁明了：由起始符开始，持续替换过程直到没有非终结符剩下。