文法和语言

• ε，｛ε｝，Ø三者之间的区别 ：

  ε是一个终结符推导出的结果，表示一个不包含任何字符的序列。

  Ø是不包含任何元素的空集{}，表示不存在匹配文法的句子。

  ｛ε｝是任意一个符号串集合的0次幂，表示一个由空字组成的集合。

• 句子与句型：

  如果符号串x是由起始符号推导出的，则称x是文法G[S]的句型。

  如果x中只包含终结符，则称x是文法G[S]的句子。

  文法描述的语言是该文法一切句子的集合。

• 四种文法：

  0型文法：α→β，其中α至少包含一个非终结符。

  1型文法（上下文有关文法）：α→β，其中|β|≥|α|，S→ε除外。

  2型文法（上下文无关文法）：a→β，其中a是一个非终结符。

  3型文法（规范文法）：A→a或A→aB.

  4种文法是逐渐增加限制的，所以规范文法一定是0型文法、1型文法、2型文法，上下文无关文法也一定是0型文法、1型文法...

• 规范推导：

  最右推导为规范推导，由规范推导推出的句型称为右句型或规范句型。

• 文法的二义性：

  一个句型可能对应多个语法树，一个句型可能对应多个最左/最右推导。

  如果一个文法中的某个句子可以对应两个不同的语法树，则称这个文法是二义的。

  两个不同的文法可能是一样的语言。

  如果一种语言的所有文法都是二义的，则称此语言先天二义。

  判定一个文法是否是二义的是递归不可解的。