什么是生成文法

在谈生成文法之前,我们首先要解释一下什么叫做“文法”(grammar)。

语法(英语:Grammar),也称文法,在语言学中指任意自然语言中句子、短语以及词等语法单位的语法结构与语法意义的规律

可见,文法这东西本身的意义是很宽泛的,我们这里研究的是“生成语法”,也就是说,用来产生语言的文法。

这里的“语言”,指的是由所有合法的句子组成的集合。

考虑这样的语言:

{a}\{a\}

我们如何生成它呢?

答案很简单:

SaS\rightarrow a

可以看到,生成文法是类似于$$\lambda$$演算的替换规则。这些替换规则有两种元素:

  • Terminal
  • Non-Terminal

其中Terminal,也就是所谓的“终结符”是不能被继续替换的符号,Non-Termianl是可以被继续替换的符号

用生成文法生成句子,其实就是不断地替换非终结符,直至句子中全部为终结符,就产生了一个句子。

我们再看一个例子:形如$$a{n}b{n}$$的语言,也就是有相同数量的a和b的语言:

{ϵ,ab,aabb,aaabbb,...}\{\epsilon, ab, aabb, aaabbb, ... \}

它可以被以下文法生成:

SAS \rightarrow A

AaAbA \rightarrow aAb

AabA \rightarrow ab

比如我们要生成$$aabb$$,就进行以下替换就可以:

SAS \rightarrow A

AaAbA \rightarrow aAb

aAbaabbaAb \rightarrow aabb

生成文法的注意事项

生成文法究竟代表什么

生成文法代表了一个语言,也就是一个集合,它由所有合法(可被生成语法生成的)的句子组成。

生成图

很容易看出来,生成句子的过程是一个有向图。如果我们把刚才的生成过程画出来的话,会是这样的:

1

实际上,这是一棵树。但,为什么还是用“图”来称呼它呢?下面会讨论这个问题。

Parse的真正意义

Parse的过程,就是由给定的句子还原生成图的过程,比如说,给定了aabb,我们要还原出来上面的图。

四种生成文法

Type 0

这种文法没有任何限制,最为自由,所以也最没用。

Type 1 Context-Sensitive Grammar

我们对Type 0语法加以一些限制,就得到了Type1型语法–上下文有关语法(CSG)。加上什么限制呢?

在Type 0类语法中,有一些规则我们特别不喜欢:

aBcaaBc \rightarrow a

这种规则是反直觉的,因为如果我们输入了$$a$$,会重建出一颗比$$a$$元素更多的生成图,这在一般情况下都是没有道理的。

所以,我们作以下限制:

  • 所有的规则必须满足箭头左侧的符号数小于等于右侧的符号数

这也叫做“单调性”。有了这个性质,我们就保证了生成的过程是符号数不减的,Parse的过程是符号数不增的。

但这也有一个副作用:空规则被禁止了。

所谓的空规则,也即是类似于

AϵA \rightarrow \epsilon

的规则,这明显是不满足“单调性”的,所以它被禁止了。实际上,如果不禁止空规则,单调性的引入是没有意义的:

aBcAaCaBc \rightarrow AaC

AϵA \rightarrow \epsilon

CϵC \rightarrow \epsilon

但我们一般允许语言本身是空的,也即是$$S \rightarrow \epsilon$$

一个比较好的消息是,如果文法中的空规则只有

AϵA \rightarrow \epsilon

而不存在

αAβϵ\alpha A \beta \rightarrow \epsilon

那么这是可以被消除成没有空规则的形式的。只要消除以后仍然是单调的,这文法也应该被视作CSG,因为文法最终定义的是集合

上下文有关语法还有另外一种定义,这里就不介绍了。

我们来看这样的一个例子:

具有连续相同数目abc的字符串,也就是说: $$a{n}b{n}c^{n}$$

abc,aabbcc,aaabbbccc...{abc, aabbcc, aaabbbccc ...}

如何用CSG生成它呢?

这规则是不太好理解和写出的:

SabcaSQS \rightarrow abc | aSQ

bQcbbccbQc \rightarrow bbcc

cQQccQ \rightarrow Qc

这也就是CSG不太好用的地方–人类难以理解这种语法,所以很难构造它。

Type 2 Context Free Grammar

我们喜欢树。树的各种性质都很美妙,对树的操作天生比对图的操作舒服。

那么,可以把Parse图变为Parse树吗?答案是可以。

生成的过程为什么是图?我们看看用上面的语法生成$$aabbcc$$的过程:

2

可以看到,有两个点的入边和出边都有好几条,如果把它变成无向图会产生回路,所以是图而非树。

这两个点的产生是因为语法规则

bQcbbccbQc \rightarrow bbcc

cQQccQ \rightarrow Qc

左边的符号是复数个。只要我们令左边的符号只能有一个,生成图就会变成生成树!

这也就是CFG的限制:

  • 箭头左边有且只有一个非终结符。

uvwxy定理

这个限制对语言的表现力有什么影响吗,或者说,CFG相比于CSG,在表现力上有什么区别吗?请再次回想我们一直强调的一点:文法最终定义的是集合

要看有没有影响,就要比较CSG和CFG所生成的集合的区别。

再来看看$$a{n}b{n}c^{n}$$这个集合,我们可以用以下CFG生成它的超集:

SAS \rightarrow A

AaAcA \rightarrow aAc

AbAA \rightarrow bA

AbA \rightarrow b

这个文法生成的是形如$$a{n}b{m}c{n}$$的句子,这$$a{b}b{n}c{n}$$构成的集合当然是这些句子构成的集合的子集。

但是,我们能不能找到一个文法,其对应的集合是$$a{n}b{n}c^{n}$$所构成的集合呢?

uvwxy定理告诉我们,这是不可能的。

uvwxy定理的证明和意义

故事要从生成树或者Parse树的构造讲起。

我们将每个规则标号,再将每个规则右侧的符号标号,就像下面这样:

SA0(0)S \rightarrow A^{0} \tag{0}

Aa0A1b2(1)A \rightarrow a^{0}A^{1}b^{2} \tag{1}

Aa0b1(2)A \rightarrow a^{0}b^{1} \tag{2}

研究生成树,我们会发现句子中的每个终结符,都存在一条由终结符起,经历一些非终结符至根的路径,而这条路径,可以被一个二元组的列表定义

如何构造该二元组列表呢?我们可以把生成树中除根以外的每个符号都打上标记,标记的内容是$${规则编号,位置编号}$$,这样一来每个非终结符就唯一地对应一个标记,而把标记串联起来,就得到了这个列表。

例如,对$$aabb$$这个句子,我们可以作以下标记:

3

这样一来,最左侧的a,它的列表为:

{1,0},{0,0}\{1, 0\}, \{0, 0\}

第二个a的列表为:

{2,0},{1,1},{0,0}\{2, 0\}, \{1, 1\}, \{0, 0\}

我们立刻可以发现一个问题:

  • 显然地,给定一个合法列表,有且仅有一个终结符与之对应

这个时候我们立刻会思考一个问题:列表中的二元组,其数量显然是有限的。

什么意思呢?就是说,对一个给定的语法来说,不同二元组的数量就是

C=SymbolsruleC = \sum{Symbols_{rule}}

那么,如果这个列表的长度大于$$C$$,这个列表就一定会有两个相同的元素!

如果长度有最大值,那么所有列表组成的集合的大小实际上也有最大值。

又由于一个列表要么是非法的,要么只有一个终结符与之对应,这样的集合所对应的句子,长度也是有限的。

换言之,只要长度超过了这个上限$$n$$,那一个列表中就必然有两个相同的二元组。而如果一个终结符的列表中有两个相同的二元组,那就说明一个问题:有同一个规则被运用了两次

我们用图片展示一下,就是这样:

4

所以,一个足够长的句子必然可以被分解为$$uvwxy$$五个部分,且$$v$$和$$x$$不同时为空。为什么不能同时为空呢?我们可以继续使用反证法,由于列表集是离散的且有上界$$n$$,必然可以找到句子长度的真正上界$$n_{real}$$。假设一个句子的长度超过了$$n_{real}$$,且可以被分解为$$uwy$$。这也就是说必然存在一个单元规则$$A \rightarrow A$$,而单元规则是可以被消除的,即,移除对应的生成树节点,该生成树仍然是合法的。我们移除这个节点以后,就有两种情况:

  • 这个句子还可以用别的方式被分解为$$uvwxy$$
  • 这个句子没有重复的规则。

第二种情况和长度超过$$n_{real}$$矛盾,所以不存在“一个长度超过$$n_{real}$$,可以被分解为$$uwy$$而不能被分解为$$uvwxy$$的句子”。为了下面证明的方便,这里直接规定$$x$$和$$y$$不同时为空。

这个时候,如果把第二个A代换成第一个A会怎么样呢?这个代换显然也是成立的,因为这个上下文无关文法:

5

我们发现,这句子是$$uvvwxxy$$,或者$$uv{2}wx{2}y$$。

也就是说,如果$$uvwxy$$是一个合法的句子,那么,$$uv{2}wx{2}y$$也一定是个合法的句子!

证明$$a{n}b{n}c^{n}$$不能被CFG生成

用这个性质,我们立刻可以证明$$a{n}b{n}c^{n}$$不能被CFG所生成:

考虑一个句子$$a{k}b{k}c^{k}$$:

  • 如果$$v$$或$$x$$中含有$$b$$,那么,$$v$$中就不得含有$$a$$或$$x$$中就不得含有$$c$$,因为这会使得$$v{2}$$或$$x{2}$$中出现$$a…b…a$$或$$b…c…b$$的序列,而这显然不是$$a{n}b{n}c{n}$$型的句子。所以$$u$$只能为$$a{k}$$或$$y$$只能为$$c^{k}$$,而原本$$v, w, x$$中的$$b$$数量之和为$$k$$,$$v^{2}, w, x{2}$$中$$b$$的数量必然大于$$k$$,所以这会使得$$uv{2}wx{2}y$$也不是$$a{n}b{n}c{n}$$型的句子。所以这种情况不成立。
  • 如果$$v$$和$$x$$中均不含$$b$$,那么,$$b{k}$$一定被分解到了$$w$$中。由于$$x$$和$$v$$非空,必然存在一部分$$a$$被分解到$$x$$中,一部分$$b$$被分解到$$y$$中。同上,这会使得$$uv{2}wx^{2}y$$中含有的$$a, b, c$$数不相等。故也不成立。

所以,$$a{n}b{n}c^{n}$$不能被CFG生成。

Python不是CFG

可以证明,一切类似于Python那样的用多层缩进表示块的语法,都不能用CFG生成。

Type 3 Regular Grammar

正则文法,就是“正则表达式”的那个文法,我们在下期讨论。

Type 4

这类型没什么用,不做讨论。

总结

四种语法中,比较有用的是CFG和正则文法。下一篇文章我们将重点讨论正则文法。