英语原文共 14 页，剩余内容已隐藏，支付完成后下载完整资料
2 文法作为生成工具
2.1 语言是一个无穷集合
就像日常用语一样，在计算机科学中，“文法”是用来“描述”一种“语言”的。然而如果从表面上看是具有误导性的，因为计算机科学家和普通的说话者对这三个术语含义的理解略有不同。为了建立我们的术语并划定话语世界，我们将从最后一个开始研究上面的术语。
2.1.1 语言
对于大部分人来说，语言首先是一种交流方式，几乎无意识地使用语言，当然在激烈的辩论中也是如此。交流是通过空气振动或通过文字符号携带信息来实现。仔细观察，语言信息会分解成句子，这些句子由单词组成，而单词在书写时又由符号序列组成。语言在所有三个构成层面上都可以不同。字母可能略有不同，如英语和爱尔兰语，或者非常不同，如英语和汉语。语言往往差别很大，甚至在人们熟知的语言中，人们将马称为“un cheval”或“ein Pferd”。句子结构的差异经常被低估。即使是紧密相关的荷兰人，也经常有一种近乎莎士比亚式地语句：“lk geloof je niet”，“i believe you not”，而更多相关的语言很容易找到像匈牙利语“Penzem van”，“money-my is”的结构，而英语中则是“I have money”。
计算机科学家对这一切都有非常抽象的看法。是的，一种语言有句子，而这些句子具有结构。不管它们是否传达了某种信息，都不是他所关心的，但是信息可能来自于它们的结构，因此把这些信息称为句子的“意义”是完全正确的。句子由单词组成，被称为token，每个单词都可能带有一些信息，这就是它对整个句子意义的贡献。但是，语言不能再被分解了，这并不使计算机科学家担心。凭借他对可伸缩的解决方案和多层次技术的热爱，他宣称，如果单词最终有了结构，它们就是用不同语言写成的句子，其中字母就是token。
形式语言学的从业者，从此被称为形式语言学家（将他与“正式语言学家”区分开来，后者的详述留给读者想象），再次从抽象的角度来看待这个问题。语言就是句子的集合，每个句子都是符号的序列，没有意义，没有结构，任何一个句子都属于一个语言，或者不属于。符号的唯一属性是它有一个标识，在任何语言中都有一定数量的不同符号，即字母表，而且数量是有限的。为了方便起见，我们将这些符号写为a，b，c，。。。，但是✆，✈，❐，。。。只要有足够的符号就行。单词序列意味着每个句子中的符号都有固定的顺序，我们不应该将它打乱。单词集合意味着这是一个无序的集合，并且去除了重复项。一个集合可以通过花括号括起来，并写入它的对象来写下一组。所对形式语言学家来说，“a, b, ab, ba”是一种语言，并且{a,aa,aaa,aaaa,...}也是，尽管后者有将在后面解决的计数问题。根据计算机科学家在句子/单词和单词/字母之间看到的对应关系，形式语言学家也把一个句子称为单词，并且说“单词ab属于语言{a, b, ab, ba}”。
现在让我们考虑这些紧凑而强大的想法的含义。
对于计算机科学家来说，语言可能是一个无限大的句子集合，每个句子都是具有结构的记号组成。记号以及对应的结构配合来描述句子的语义，这就是句子的意义。结构和语义都是新的，也就是说，在形式模型中不存在，计算机科学家的责任就是提供和操作它们。对于计算机科学家来说，3 4*5是一个“个位数算法”语言的句子（“个位数”以避免有无数个符号），它的结构可以通过插入括号来显示：(3 (4*5))，它的语义是23。
对于语言学家来说，语言是一组可能相互关联的句子。每个句子都是以一种结构化的方式，包含在现实世界中具有意义的单词。结构和单词一起赋予了句子传达的意义。单词拥有结构并由字母组成，这写字母和一些结构配合赋予这个单词意义。强调语义与现实世界的关系，以及句子与单词和单词与字母两个层次的整合是语言学家的领域。“轮子猛烈地旋转”是一个句子，而“圆圈睡红”是没有意义的。
形式语言学家持有他对语言的看法，因为他想要研究语言最基本的属性。计算机科学家坚持他的观点，因为他想要一个清晰的、透彻的、明确的方法来描述计算机中的物体以及计算机间的通信，这是一个与人类不同的通信伙伴。语言学家持有他对语言的看法，因为它给了他一个严格控制的看似混乱但也无限复杂的对象：自然语言。
2.1.2 文法
凡是学过外语的人都知道，语法是用来描述和教授这门语言的规则和例子。良好的语法对常称之为语法或句法的句子/单词级别和称之为形态学的单词/字母级别进行了仔细的区分。语法包含像“pour que is followed by the subjunctive, but parce que is not”。形态学包含的规则类似于“英文名词的复数形式是通过追加-s形成的，除非单词以-s，-sh，-o，-ch或-x结尾，在这种情况下追加-es，或当这个词有一个不规则的复数”。
我们暂时跳过计算机科学家关于语法的观点，并立即转向正式语言学家的观点。他的观点非常抽象，且与外行人的观点类似：语法是任何精确的、有限的、完整的对语言（即句子集合）的描述。这实际上是学院风格的语法，带有模糊性。虽然这个定义具有充分的普遍性，但事实证明它太笼统，因此相对无力。它包括诸如“可能由Chaucer创作的句子集合”的描述。理想地说，这定义了一个集合，但是我们没办法创建这个集合或者测试一个给定的句子是否属于这种语言。这个特殊的例子，“本来可以”并不让形式语言学家担心，但有更加接近他的研究领域的例子。“pi;的十进制展开式中最长连续出现数字7的块”描述了一种语言，其中最多有一个单词（该单词将仅包含数字7），并且它的定义是准确的，即有限且完整的。然而这有一个不好的问题，人们无法找到这个词：假设某人在十亿数字之后找到了一百个由7连续组成的块，那么在这之后还有可能找到一个由更多7组成的块。另一个问题是，人们甚至不知道这个最长的块是否存在。很可能，当pi;的十进制展开位数越来越多，人们可能会发现更长的由7组成的块，由不断增长的间距间隔。pi;的小数展开的理论可能可以回答这样的问题，但是没有这样的理论存在。
由于这些原因，形式语言学家放弃了对语法的静态的、理想的观点，以获得更具建设性的语法观点，即生成语法：生成语法是一种以精确地、固定大小的方法来构造语言中的句子。这意味着，按照既定规则，必须可以无歧义地构建语言中的每个句子（以有限数量的动作）。这并不意味着，给定一个句子，规则告诉我们该如何构造这个特定的句子，它只是可能这样做。规则的形式有多种，其中一些比另一些更方便。
计算机科学家基本持有相同的观点，通常还要求规则可以暗示如何构建一个句子。
2.1.3 无穷集合的问题
上述语言的定义可以产生无限的符号序列，而语法则是产生这些句子的有限方法，这就产生了两个尴尬的问题：
1. 有限的规则如何产生无限的句子？
2. 如果一个句子只是一个序列而没有结构，并且一个句子的含义是从其句子中衍生的，那么我们该如何获知这个句子的意思？
这些问题有很长且很复杂的答案。我们首先关注第一个问题，然后把这本书的主体放在第二个问题上。
2.1.3.1 从有穷描述中产生无穷的集合
事实上，从单个有限描述中获得无限集合没有问题：“所有正整数的集合”是一个非常有限大小的无限大集合描述。然而，这个想法有些令人不安，因此我们将重新修改我们的问题：“是否所有的语言都可以用有限的描述来描述？”，正如上面所说的，答案是否定的，但是证明并非无意义。它是非常有趣并且非常有名，有必要在这里提出一个大纲。
2.1.3.2 描述是可枚举的
证明基于两个观察和一个技巧。第一个观察是可以列出描述并给出一个数字，如下所示。首先是长度为1的所有描述，即只有一个字母长，并按照字母顺序对它们进行排序。这是我们列表的开始。确切地说，根据我们接受的描述，对于第一个描述，可能有0个，或27个（所有字母和空格），或95个（所有可打印ASCII字符）或类似的东西。这与下面的讨论无关。
然后，我们对大小为2的所有描述按字母顺序排列，以给出列表中的第二个块。以此类推长度为3或4，以及更长的单词。这为列表中的每个描述分配了一个位置。例如描述“the set of all positive integers”，它的大小是32，不包括引号。为了找到他们的位置，我们需要计算有多少描述少于32个字符，命名为L。然后我们必须生成关于长度为32的描述，并对其排序，命名为P，并添加L和P。这将给出一个巨大的数字，但它确保描述都在列表的一个明确的位置上。
这里应该指出两点。首先是只按照字母顺序列出所有描述，而不考虑它们的长度，通常不这样做：已经有无限多的以“a”开始的描述，并且没有以较高字母开头的描述可以在列表上得到一个数字。第二个是没有必要这么做。这只是一个思想试验，它让我们在不能进行实地考察时，能够对一个系统的行为进行研究。
此外，列表上还有许多无意义的描述。事实证明，这对论据并不重要。重要的是，所有有意义的描述都在列表中，且上述论点确保了这一点。
2.1.3.3 语言是无限长的位串
我们知道语言中的单词（句子）是由一组有限的符号组成的，这个集合被称为字母表。我们假设字母表中的符号是有序的。然后语言中的单词也可以排序，我们用Sigma;来表示字母表。
最简单的语言是将字母表中的字母组成的所有单词进行结合。对于字母表 Sigma; ={a, b}，我们可以得到语言{ , a, b, aa, ab, ba, bb, aaa, . . . }。我们称这个语言为Sigma;*。这将在后面解释原因，暂时它只是一个名字。
Sigma;*始于“{, a”，语言中的第一个单词是一个空单词，由0个a和0个b组成。并没有理由去掉它，但是如果写下来，它很容易被忽视，所以我们将它写成ε，而不管字母表（字母表中没有该字符）。所以 Sigma;lowast; = { ε, a, b, aa, ab, ba, bb, aaa, . . . }。在一些自然语言中，动词“to be”的现在时形式是空的词，形成了“I student”，意思是“I am a student”。俄语和希伯来语就是这样的例子。
由于字母表Sigma;中符号是有序的，因此我们可以使用于前一节中相同的技术列出语言Sigma;*中的单词：首先排序所有大小为0的单词，然后为所有大小为1的单词排序，等等。这实际上是Sigma;*中已使用的顺序。
语言Sigma;lowast;具有一个有趣的属性，就是所有使用字母表Sigma;的语言都是它的子集。这意味着，给定另一个比Sigma;更小的语言，称为L，我们可以遍历Sigma;lowast;中的单词列表，并将所有在L中出现的单词取出来，这将覆盖L中的所有单词，因为Sigma;lowast;包含Sigma;中的任何可能单词。
假设我们的语言L是“包含b以外的所有单词的集合”。L是集合{a, aa, aab, aba, baa, . . . }。在列表开头加上记号，看起来如下图所示：
ε
✔ a
b
✔ aa
ab
ba
bb
✔ aaa
✔ aab
✔ aba
abb
✔ baa
bab
bba
bbb
✔ aaaa
... ...
根据字母表的顺序，空白和记号列表就足够识别和描述该语言。为了方便起见，我们将空白记为0，将空格记为1，就好像它们是计算机中的位一样，我们可以写出L = 0101000111010001···（Sigma;lowast; = 1111111111111111···）。应该注意的是，这适用于任何语言，像L这样的正式语言，像Java这样的编程语言，或者像英语这样的自然语言。在英语中，位串中的连续的1是非常少的，因为几乎没有任何的任意排序的单词是一个好的英语句子（并且根据我们是在句子/单词或单词/字母水平，几乎没有任何的任意排列的字母序列是一个好的英语单词）。
2.1.3.4 对角化
上一节将无限比特串0101000111010001···添加到描述“包含b字母以外的所有单词的集合”，同样的，我们可以将位串添加到所有描述中。某些描述可能不会产生一种语言，我们可以将任意的无限位串添加到其中。由于所有的描述都可以放在有单独编号的列表中，所以我们可以得到如下：
Description Language
Description #1 000000100···
Description #2 110010001···
Description #3 011011010···
Description #4 110011010···
Description #5 100000011···
Description #6 111011011···
... ...
左边所有的描述，定义了右边所有的语言。我们现在断言存在许多不在上述语言列表中的语言：上述列表并不完整，尽管描述列表是完整的。我们将用康托尔的对角论证法来证明这一点。
考虑语言C=100110...，它具有第n位比特与描述#n的第n位比特不同的属性。C的第一个比特是1，因为描述#1的第1位比特是0。C的第二个比特是0，因为描述#2的第二位比特是1，等等。C是通过沿着西北到东南的对角线，并复制遇到的位的反面来形成的。如图2.2(a)。语言C不可能在
全文共10981字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[13334]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
