什么是生成文法

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

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

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

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

考虑这样的语言:

\[\{a\}\]

我们如何生成它呢?

答案很简单:

\[S\rightarrow a\]

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

  • Terminal
  • Non-Terminal

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

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

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

\[\{\epsilon, ab, aabb, aaabbb, ... \}\]

它可以被以下文法生成:

\[S \rightarrow A\] \[A \rightarrow aAb\] \[A \rightarrow ab\]

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

\[S \rightarrow A\] \[A \rightarrow aAb\] \[aAb \rightarrow aabb\]

生成文法的注意事项

生成文法究竟代表什么

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

生成图

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

1

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

Parse的真正意义

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

四种生成文法

Type 0

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

Type 1 Context-Sensitive Grammar

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

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

\[aBc \rightarrow a\]

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

所以,我们作以下限制:

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

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

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

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

\[A \rightarrow \epsilon\]

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

\[aBc \rightarrow AaC\] \[A \rightarrow \epsilon\] \[C \rightarrow \epsilon\]

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

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

\[A \rightarrow \epsilon\]

而不存在

\[\alpha A \beta \rightarrow \epsilon\]

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

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

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

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

\[{abc, aabbcc, aaabbbccc ...}\]

如何用CSG生成它呢?

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

\[S \rightarrow abc | aSQ\] \[bQc \rightarrow bbcc\] \[cQ \rightarrow Qc\]

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

Type 2 Context Free Grammar

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

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

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

2

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

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

\[bQc \rightarrow bbcc\] \[cQ \rightarrow Qc\]

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

这也就是CFG的限制:

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

uvwxy定理

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

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

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

\[S \rightarrow A\] \[A \rightarrow aAc\] \[A \rightarrow bA\] \[A \rightarrow b\]

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

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

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

uvwxy定理的证明和意义

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

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

\[S \rightarrow A^{0} \tag{0}\] \[A \rightarrow a^{0}A^{1}b^{2} \tag{1}\] \[A \rightarrow a^{0}b^{1} \tag{2}\]

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

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

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

3

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

\[\{1, 0\}, \{0, 0\}\]

第二个a的列表为:

\[\{2, 0\}, \{1, 1\}, \{0, 0\}\]

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

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

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

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

\[C = \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和正则文法。下一篇文章我们将重点讨论正则文法。