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

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

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

  1. Tom是一个人名,Dick是一个人名,Harry也是一个人名;

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

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

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

虽然这样说对于读者的理解很管作用,但是却有几个错误的地方。条件3尤其会带来麻烦。例如,句子并不是以“,人名”结束,而是以“,Dick”或类似的名字结束,“人名”只是一个符号用以代替真是的名字;这样的符号不能在真是的句子中出现而且在结尾处的必须用条件0中给出的名字替代。同样,条款中的“句子”是一个符号,指代真实的句子。所以这里涉及到两种符号:出现在完备句子中的真实符号,比如“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)开始替换过程

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

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

Fig 2.3

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

1. 引用至The Hobbit, by J.R.R. Tolkien, Allen and Unwin, 1961, p. 311.

results matching ""

    No results matching ""