2.2.1 正式语法的形式主义

由于正式语言是数学的一个分支,所以这一领域的工作是在一个特殊符号下完成的。若要展示一些他的韵味,我们就应该正式定义一下语法,然后解释一下为什么这样就描述了一种语法,就像图 Fig 2.3中的那个一样。形式主义的使用是必不可少的,为了证明的准确性等,但是不是为了理解其基本原理;在这展示只是为了给读者一个印象,或者说跨过沟壑的一个桥梁。

定义2.1: 一个生成语法是一个4元组 ,像这样:

(1) 是符号的有限集,

(2) ,

(3) 是一个有序数对 ,像这样

(3a)

(3b) ,

(4)

一个4元组只是一个包含了4个可辨识部分的对象;这4个部分按照顺序是非终结符、终结符、规则和起始符。上述定义没有说明这点所以这需要老师来解释。非终结符集用 来表示,终结符集用 来表示。对我们的语法来说,我们就有

(注意,终止符的那个集合)

(2)的交集必须是空集,用空集合符号 表示。所以非终结符集和终结符集不可能有公共元素,这是可以理解的。

R是所有规则(3)的集合,PQ分别是放左侧和放右侧的内容。每一个P必须包含一个或多个非终结符和终结符的序列,每一个Q必须包含零个或多个非终结符和终结符的序列。对我们的语法来说,我们就有:

再次注意,两个不同的逗号。

起始符必须是里面的元素,也就是说必须是非终结符:

我们的领域在这里就结束了,后面是语言学的领域。简言之,数学上的正式语言就是一门语言,一门必学的语言;它让表达“是什么”和“怎么做”变得非常简单,但是关于“为什么”却给了很少的说明。把这本书当作一个翻译和一个注释。