2.1 将一门语言看作一个无限大的集合

language是sentences的集合，sentence是tokens组成的序列。

sentences的语义由sentences的结构和token决定。

语法：

静态的规则可能描述不了某些语言，故将其作为语法可能会无能为力。

一系列确定的有限的description也不能完备描述所有语言。

证明：（对角线证明）

可以有序地枚举所有description（无穷多）。可以有序地枚举由一个字母表产生的所有word（无穷多），令该枚举列表为EnumList。则任何语言，其所用的所有word都在EnumList里面。对于某个在EnumList中的word，一个language可以有，也可以没有。因此在不考虑语言的structure，仅考虑language所用的word，对于所有语言，都可以用一个无穷长的二进制向量表示，该向量的某一位的值表示，对于该位对应EnumList中的单词，该语言是否包含。

构造这样的表，它仅有两列，第一列是所有的description，第二列是每个description对应的language（有些description对应多个language，这样，仅仅选择一个language作为其对应项）。列表形如下：

Description           Language

Description #1      000000100· · ·

Description #2      110010001· · ·

Description #3      011011010· · ·

Description #4       110011010· · ·

Description #5       100000011· · ·

Description #6        111011011· · ·

. . .                               . . .

构造这样的language，它具有这样的特性：该language对应二进制向量的第n位的值与第n个description对应的language的二进制向量的第n位的值相反。这样，该language的二进制值就是language列组成的表中的对角线值再对每位取反。

这样的话该language必不在language列组成的表中，因为它不可能是第一行，因为它第一位跟第一行不一样，更一般地，它不可能是第i行，因为它第i位与第i行不一样。所以它不可能存在于这个表中任何一行。因此，这个language不可能有与之对应的description（这个description由有限由有限条规则组成）。

这里有个问题，为什么所构造的那个language用到的描述“该language对应二进制向量的第n位的值与第n个description对应的language的二进制向量的第n位的值相反”不在Description列里面！！

我没有深究，似乎是由悖论引起的，豆瓣上的评论有提到，另外可以看看罗素悖论。

2.2 形式语法

若如下看待语言：由object组成。先有基本的object，然后有一套规则来在基本的object上构造新的object。

则语言有一个四元组组成：（非终止object集合，终止object集合，规则，开始object）

非终止object集合 和 终止object集合 都是有限的symbol集合，且两集合无交集。

规则是形如 X -> Y 的转换规则，X和Y都必须是一串symbol，X不可为空串，Y可以（书中集合右上角星号是克莱尼星号）

开始object必须是一个非终止object。

利用上述方法生成一个sentence的过程可以用一个无环有向图表示。

第十六页的：Amazingly, we have succeeded in implementing the notion “must replace” in a system that only uses “may replace”; looking more closely, we see that we have split “must replace” into “may replace” and “must not be a non-terminal”

还没找到比phrase structure grammar更sufficient的语法描述方法。

2.3 The Chomsky Hierarchy of Grammars and Languages

type 0 grammar 是无任何限制的phrase structure grammars

type 1 grammar（上下文有关文法）：两种定义

（1）不存在这样的规则，左边的symbol数量比右边的symbol数量多

（2）所有的规则都是上下文有关，规则上下文有关就是sentence中只有一个非终结词经过规则变换后得到替代，且替代结果至少有一个symbol。

它的某个sentence的生成图是有向无环图

type 2 grammar（上下文无关文法）：规则左边只有一个symbol。

它的某个sentence的生成图是树。

二型文法中，某个symbol可以独立作为一门language，因为其它symbol对它的映射结果不影响。

type 3 grammar：左线性，右线性

type 4 grammar：规则右边只能是终止的symbol

2.4 使用上述grammar生成sentences的算法

一个广度优先搜索算法

该算法可以用来证明某个grammar可以生成至少一个sentence，但不能证明不能。

并阐述了一个检查2型文法是否生成至少一个sentence的算法

2.5 只有0型文法会生成空串

如果一个文法能生成空串，那么parsing会变得复杂

2.9 去除文法中无用的规则

type 2 grammar相较于0型和1型，容易找出文法中无用的规则。

type 2 grammar无用的规则包括如下问题：

（1）包含未定义的非终结符号 undefined non-terminals

（2）从开始symbol，不可能产生符合规则左边的符号序列 unreachable non-terminals

（3）不能产生任何东西（无限递归）non-productive

一个闭包算法首先清除non-productive 和 undefined non-terminals的规则

另一个闭包算法清除unreachable non-terminals的规则

第二个闭包算法在清规则的时候不会让一个non-terminal（设为N）编程undefined，因为N是reachable的，因此它的所有定义（左边是N的规则）都不会在这个闭包算法中被清掉。同样的道理，第二个闭包算法也不会让N编程non-productive

如果两个闭包算法倒过来用，很可能会在第二次的时候生成unreachable non-terminals

2.11 语义与文法

某个sentence的语义与这个sentence的生成结构图（production tree）有关。

(1)attribute grammar（将语义作为attribute绑定到symbol上）

(2)transduction grammar（语义是sentence作为input string得到的output string的语义）

(3)Augmented Transition Networks（将actions绑定到生成结构图的结点上，语义就是遍历结点时触发的action）

2.12 各级文法的比较

More powerful grammars can define more complicated boundaries between correct and incorrect sentences. Some boundaries are so fine that they cannot be described by any grammar (that is, by any generative process).