概览：文法、语言、以及文法的类型

如何描述一种语言

• 如果语言是有穷的（只含有有穷个句子），可以将句子逐一列出来表示
• 如果语言是无穷的，则找出语言的有穷表示：
  • 生成方式(文法)：语言中的每个句子可以用严格定义的规则来构造
  • 识别方式(自动机)：用一个过程，当输入一串任意语言时，该过程经过有限次计算就会停止，若属于，回答“是”，若不属于，要能停止并回答“不是”。

文法的定义

语言的定义

文法的类型

通过对产生式施加不同的限制，Chomsky(乔姆斯基)将文法分为四种类型：

0型文法（短语结构文法）的能力相当于图灵机。

1型文法（上下文有关文法）：产生式的形式为 α1Aα2→α1βα2 ，即只有A出现在α1和α2的上下文中时，才允许β取代A。其识别系统是线性界限自动机。

2型文法（上下文无关文法CFG）：产生式的形式为A→β，β取代A时与A的上下文无关。其识别系统是不确定的下推自动机。（其产生式左部只有一个非终结符）

3型文法（正规文法RG）：文法G= (VN,VT,P,S),其中P中的产生式的形式为A→αB或者A→α，其中A和B是非终结符号，α属于VT* 。产生的语言是有穷自动机（FA）所接受的集合。

上下文无关文法(2型文法)有足够的能力描述程序设计语言的语法结构，如描述算术表达式或者各种语句。