24短语、直接短语和句柄

24短语、直接短语和句柄内容摘要：

ck | i=j 或 j=k 且 i, j, k≥1} 便是这种语言。 文法和语言的分类 著名的语言学家 乔姆斯基 (Chomsky) 将文法和语言分为四大类，即 0型、 1型、 2型、 3型。 划分的依据是对文法中的规则施加不同的限制。 文法和语言的分类 0型文法（无限制文法） 若文法 G=(VN,VT, P, S)中的每条规则 αβ 是这样一种结构： 而且 α中至少含一个非终结符 , 则称 G 是 0型文法。 α(VN∪ VT)+ , β(VN∪ VT)* 0型文法描述的语言是0型语言。 0型文法没有加任何限制条件，又称为 无限制性文法，相应的语言称为 无限制 性语言。 0型语言由图灵机识别。 文法和语言的分类 例如，有 0型文法 G=(VN,VT, P, S) 其中： VN={A,B,S} , VT={0,1} 其描述的 0 型语言为 L0(G[S])={ } P: S  0AB 1B  0 B  SA | 01 A1  SB1 A0  S0B STOP 文法和语言的分类 1型文法（上下文有关文法） 1型文法也称为上下文有关文法， 相应 的语言又称为 上下文有关语言。 若文法 G=(VN,VT, P, S)中的每一条规则的 形式为 αAβ αμβ , 其中： α, β(VN∪ VT)* , AVN , 则称 G是 1型文法。 1型文法描述的语言是 1型语言。 1型语言由线性界限自动机识别。 μ(VN∪ VT)+ 文法和语言的分类 例如，有 1型文法 G=(VN,VT, P, S) 其中： VN={S,A,B} , VT={a,b,c} P: S aSAB | abB BA  BA39。 BA39。  AA39。 AA39。  AB bA  bb bB  bc cB  cc 其描述的 1型语言为 L1(G[S])={anbn | n≥1} 文法和语言的分类 2型文法（上下文无关文法） 2型文法又称上下文无关文法，其产生的 语言又称为 上下文无关的语言。 若文法 G=(VN,VT, P, S)中的每一条规则的 形式为 A β , 其中： AVN , β(VN∪ VT)* 则称 G是 2型文法。 2型文法描述的语言是 2型语言。 2型语言由下推自动机识别。 例如前面描述算术表达式的文法 G[E]: EE+E | E*E | (E) | i 文法和语言的分类 其描述的语言为 L2(G[S])={x | x  {a, b}+ 且 x中 a和 b的个数相同 } 例如，有 2型文法 G=(VN,VT, P, S) 其中： VN={S, A, B} , VT={a, b} P={ S aB | bA A a | aS | bAA B b | bS | aBB } 文法和语言的分类 文法和语言的分类 3型文法（正规文法） 右线性文法和左线性文法都称为 3型文法。 若文法 G=(VN,VT, P, S)中的每一条规则的形式 为 A aB 或 A a , 其中： A , BVN, a VT*, 则称 G是 右线性文法。 若文法 G=(VN,VT, P, S)中的每一条规则的形式 为 A Ba 或 A a , 其中： A , BVN , a VT*, 则称 G是 左线性文法。 3型文法描述的语言是 3型语言。 3型语言由有穷自动机识别。 3型文法也称 正规文法。 正规文法产生的语言 称为 正规语言。 例如，用左线性正规文法和右线性正规文法定义标识符 文法和语言的分类 用 I代表标识符。 l代表任意一个字母。 d代表任意一个数字。 则定义标识符的文法为： 左线性文法 : P: I→ l | Il | Id 右线性文法 : P: I→ l | lT T→l | d | lT| dT 例如，用左线性正规文法和右线性正规文法定义无符号整数 文法和语言的分类 用 N代表无符号整数。 d代表任意一个数字；则定义的无符号整数文法为： 左线性文法 : P: N→ Nd | d 右线性文法 : P: N→ dN | d 文法和语言的分类 由上述四类文法的定义可知 , 从 0型文法到 3型文法 , 是逐渐增加对规则的限制条件而得到的，因此 每一种正规文法都是上下文无关的文法， 每一种上下文无关的文法都是上下文有关的文法，而每一种上下文有关的文法都是 0型文法 , 而由它们所定义的语言类是依次缩小的， 有 L0  L1  L2  L3。 有关文法的实用限制和变换 文法是用来描述程序设计语言的，在 实际应用中需要对文法加一些限制条件。 1. 文法中不能含有形如 A →A 的规则。 这种规则我们称之为 有害规则。 对文法的实用限制有以下两点： 有关文法的实用限制和变换 2. 文法中不能有 多余规则。 所谓多余规则是指文法中出现以下两种规则： (1) 某条规则 A α 的左部符号 A不在所属文法的任何其他。