第3章 文法和语言.

Presentation on theme: "第3章 文法和语言."— Presentation transcript:

1 第3章 文法和语言

2 3.1 文法的直观概念 当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。 以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构，比如汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则：

3 BNF范式和语法图 1、巴科斯范式:EBNF <句子>→<主语><谓语> <主语>→<代词>|<名词> <代词>→你|我|他 <名词>→王明|大学生|工人 <谓语>→<动词><宾语> <动词>→是|学习 <宾语>→<代词>|<名词> 带<>的叫非终止符,不带<>的叫终止符。 <逻辑值>→True|False

4 例子： <句子><主语><谓语> <代词><谓语> 我<谓语> 我<动词><直接宾语> 我是<直接宾语> 我是<名词> 我是大学生

5 “我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。其中一种描述元语言称为文法。

6 语言概述 语言是由句子组成的集合，是由一组符号所构成的集合。 汉语--所有符合汉语语法的句子的全体 英语--所有符合英语语法的句子的全体
程序设计语言--所有该语言的程序的全体 每个句子构成的规律 研究语言 每个句子的含义 每个句子和使用者的关系

7 研究程序设计语言 每个程序构成的规律 每个程序的含义 每个程序和使用者的关系 语言研究的三个方面 语法 Syntax 语义 Semantics 语用 Pragmatics

8 语法 -- 表示构成语言句子的各个记号之间的组合规律
语义 -- 表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系） 语用 --表示在各个记号所出现的行为中，它们的来源、使用和影响。

9 每种语言具有两个可识别的特性，即语言的形式和该形式相关联的意义。
语言的实例若在语法上是正确的，其相关联的意义可以从两个观点来看，其一是该句子的创立者所想要表示的意义，另一是接收者所检验到的意义。这两个意义并非总是一样的，前者称为语言的语义，后者是其语用意义。幽默、双关语和谜语就是利用这两方面意义间的差异。

10 如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什麽符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。

11 <1><整数>→<数字>
例子:整数(1)单个数字是整数 (2)整数再接上数字仍是整数 用BNF范式表示: <1><整数>→<数字> <数字>→0|1|2|…|9 <2><整数>→<整数><数字> <整数>→<数字>|<整数><数字> 所以合起来有： <整数>→<数字>|<整数><数字> <数字>→0|1|2|…|9

12 标识符:以字母开头以后由字母和数字组成的符号串。
例子：<标识符>的巴科斯范式 <标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a|b|…|z <数字>→0|1|…|9

13 例子：判定字符串a4y是<标识符>
<标识符><标识符><字母>  <标识符>y  <标识符><数字>y  <标识符>4y  <字母>4y  a4y

14 2、语法图 作用：直观、形象的描述语法规则。 例子：标识符的语法图表示 标识符 字母 数字

15 例子：无符号数的语法图表示 2.45E+12 无符号数 无符号整数 数字 E

16 3.2 符号和符号串 1、字母表:它是非空有穷集。 例如：∑={a,b,c}或∑={1,2,3} 2、符号：字母表中的元素称为符号。 3、符号串：符号的有穷序列，符号串也称为字。用ε来表示空符号串。 例如：a,ab,abc,dsfsd

17 4、长度：符号串的长度是指该串所包含的符号个数。用|x|表示符号串x的长度。
例如：|a|=1，|abn|=3 5、连结：设x和y为符号串，则称xy 为他们的连结。 例如：x=aa,y=bb,则xy=aabb 6、空集：不含任何元素的集合,记为。

18 7、乘积：设A和B是符号串集，则用AB表示A和B的乘积。
A={a,b},B={c,d},则AB={ac,ad,bc,bd} 8、方幂：设A为符号串集，则定义 A0={ε} A1=A An=An-1 A 例如：A={a,b} 则有： A0={ε} A1={a,b} A2={aa,ab,ba,bb}

19 9、正闭包：设A为符号串集，则用A+表示A的正闭包，其具体定义如下：
A+=A1∪A2∪A3∪… 例如：A={a},A+={a,aa,aaa,……} 10、星闭包：设A为一集合，则定义A的星闭包为A* ，其具体定义如下A*=A0∪A+ 例如：A={a},A*={ε,a,aa,aaa,……}

20 3.3 文法与语言的形式定义 一、引言 例子： y:=a+b*x 语法：赋值语句由变量加“:=”加表达式构成。 语义：右边表达式求值与左变量结合赋值。 用途：表达式的值的保存和计算。

21 形式化方法：用一整套带有严格规定的符号体系来描述问题的理论和方法。 表示文法需要一种工具，其中最常用的工具是所谓的巴克斯范式(BNF)。
例子: A={an|n≥1} A={a2n|n≥1} 其BNF表示有： 其BNF表示有： (1) A→a|aA (1) A→aa|aaA (2) A→a|Aa (2) A→aa|Aaa

22 例子： A={abna|n≥1} 其BNF表示有多种如下：
(1) A→aBa B→b|Bb (2) A→aBa B→b|bB (3) A→aB B→ba|bB

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

24 文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造. 下面给出文法的定义
文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造.下面给出文法的定义.进而在文法的定义的基础上,给出推导的概念,句型、句子和语言的定义.

25 定义 文法G定义为四元组(VN，VT，P，S )其中 VN为非终结符号(或语法实体，或变量)集； VT为终结符号集；
P为产生式(也称规则)的集合； VN，VT和P是非空有穷集。 S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。 VN和VT不含公共的元素，即VN ∩ VT = φ 用V表示VN ∪ VT ，称为文法G的字母表或字汇表 规则，也称重写规则、产生式或生成式，是形如α→β或α∷=β的(α，β)有序对，其中α是字母表V的正闭包V+中的一个符号，β是V*中的一个符号。α称为规则的左部，β称作规则的右部。

26 文法的定义 例 文法G=（VN，VT，P，S） VN = { S }, VT ={ 0, 1 } P={ S→0S1, S→01 } S为开始符号

27 例 文法G=（VN，VT，P，S） VN ={标识符，字母，数字} VT ={a,b,c,…x,y,z,0,1,…,9} P={<标识符>→<字母> <标识符>→<标识符><字母> <标识符>→<标识符><数字> <字母>→a,…, <字母>→z <数字>→0,…, <数字>→9 } S=<标识符>

28 文法的写法 1 G：S→aAb A→ab A→aAb A→ε 2 G[S]： A→ab A→aAb A→ε S→aSb 3 G[S]： A→ab |aAb |ε S→aSb

29 二、文法和语言形式定义 1、规则式，产生式 例子： B→b|Bb A→a|A 2、文法G[Z]：规则的非空有穷集合。Z：识别符号，开始符号。V：字母表，符号集合。 例子：G[S]={S→0，S，1} V＝{S，0，1}

30 定义3.1 文法是一个四元组G(VN，VT，P，Z)。

31 例子：自然数G1(VN,VT,P,Z)和标识符G2
(VN,VT,P,I) VN={ N,D } VT={ 0,1,2,9} P={ N→D|ND, D→0|1|2||9 } G1：N→D|ND D→0|1|2||9

32 标识符G2(VN,VT,P,I) VN={ I,D,L } VT={ 0,1,2,9,a,b…z} P={ I→L|IL|ID, L→a|b|…|z D→0|1|2||9 } G2：I→L|IL|ID L→a|b|c||z D→0|1|2||9

33 1、直接推导：设x和y是符号串，若用一次产生式可从x导出y，则称y为x的直接推导，并记为xy。
定义3.2 1、直接推导：设x和y是符号串，若用一次产生式可从x导出y，则称y为x的直接推导，并记为xy。 例子：x=Ab,y=ab,A→a,Abab 2、推导：若用若干次产生式可从x串导出y串，则称y为x的推导，并记为 x y。  +

34 3、星推导:x y(当且仅当x=y或x y)。 例子：ABAB 0步 ABaB 1步 AB ab 2步 即：AB ab
例子：X=AB,A→a,B→b ABaBab 即：AB ab  +  * 3、星推导:x y(当且仅当x=y或x y)。 例子：ABAB 0步 ABaB 1步 AB ab 2步 即：AB ab +

35 4、句型：称x为句型，若有Z x，其中Z是文法的开始符。凡是由初始符推出的任意符号集合叫句型。
例子：Z→AB,A→a,Z aB 5、句子: 称x为句子，若有Z x，且x中不包含非终极符的句型。不包含非终极符的句型叫句子。  *

36 例子：G[S]:S→0S1 S→01 解: S0S1 00S11 000111 所以有: S={01,0011,000111…} L(G)={0n1n|n≥1}

37 6、语言:所有句子的集合称为语言。设是G给定文法，Z是开始符，则语言L(G)可描述如下：
L(G)=｛x|Z x,x∈VT*｝  * 定义3.3 设G1,G2为给定文法，如果L(G1)=L(G2),则称G1和G2等价。

38 例1 已知文法求语言并判断是否等价 G1=(VN,VT,P,A) G2=(VN,VT,P,Z) VN={A} VN={A,B} VT={a,b} VT={a,b} P={A→ab} P={A→Bb,B→a} A1ab L(G1)={ab} A2Bbab L(G2)={ab}  G1与G2是等价的。

39 S - A S - A a b c A 例2: G3[S]: S→A|S-A A→a|b|c G4[S]: S→A|A-S 推导过程如下：

40 S A - A - S a b c A 推导过程如下： SA-S A-A-S A-A-A a-b-c a-b-c和a-b-c
 G3与G4等价，但G3与G4的语义不同。

41 文法的等价 若L（G1）=L（G2），则称文法G1和G2是等价的。 如文法G1[A]：A→0R 与G2[S]：S→0S1 等价 A→ S→01 R→A1

42 3.4 文法的类型 定义3.4 0型文法(短语结构文法): 产生式为：α→β，其中α和β是符号串。 1型文法(上下文有关文法)：
3.4 文法的类型 定义3.4 0型文法(短语结构文法): 产生式为：α→β，其中α和β是符号串。 1型文法(上下文有关文法)： 产生式为：αAβ→αuβ，其中A∈VN，u为非空串。 2型文法(上下文无关文法): A→β，其中A∈VN，β为非空串。

43 3型文法(正则文法): 产生式为：A→a,A→bB,其中A,B∈VN, #a,b∈VT是符号串。 例子: G[Z]:Z→a Z→aA A→b|bB B→b 所以:G[Z]是3型文法

44 文法的类型 例：1型（上下文有关）文法 文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→ε BD→bD D→ε Aa→bD

45 文法的类型 例：2型（上下文无关）文法 文法G[S]： S→AB A→BS|0 B→SA|1

46 3型文法 G[S]： S→0A|1B|0 A→0A|1B|0S B→1B|1|0 G[I]： I → lT I → l T → lT
T → dT T → l T → d

47 文法的类型 四种文法之间的逐级“包含”关系 0型文法 2型文法 1型文法 3型文法

48 文法和语言 0型文法产生的语言称为0型语言 1型文法或上下文有关文法（ CSG ）产生的语言称为1型语言或上下文有关语言（CSL）
2型文法或上下文无关文法（ CFG ）产生的语言称为2型语言或上下文无关语言（ CF L ） 3型文法或正则（正规）文法（ RG ）产生的语言称为3型语言正则（正规）语言（ RL ）

49 文法和语言 四种文法之间的关系 是将产生式做进一步限制而定义的。 语言之间的关系依次：有不是上下文有关语言的0型语言，有不是上下文无关语言的1型语言，有不是正则语言的上下文无关语言。

50 根据形式语言理论,文法和识别系统间有这样的关系
0型文法（短语结构文法）的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的 1型文法（上下文有关文法）：产生式的形式为α1Aα2→α1βα2，即只有A出现在α1和α2的上下文中时，才允许β取代A。其识别系统是线性界限自动机。

51 2型文法（上下文无关文法CFG）：产生式的形式为A→β，β取代A时与A的上下文无关。其识别系统是不确定的下推自动机。
3型文法（正规文法RG）：产生的语言是有穷自动机（FA）所接受的集合

52 3型文法产生的语言是有穷自动机（FA）所接受的集合.
定理 设G=（VN，VT，P，S）是3型文法，则存在一个有穷自 动机 M=(K, ∑ , f, A, Z)，使得L(M)=L(G) 有穷自动机NFA M 这样构造： · ∑= VT · K= VN ∪{N}, N为一个新状态,它不在VN中 · A=S · Z={N} · 对G中的形如 D→tB的产生式,t为终结符或ε,有f(D,t)=B； 对G中形如D→t的产生式， t为终结符或ε,有f(D,t)=N;   对VT中的每一个a ,有f(N,a)=φ

53 G［Ｓ］： S→aA|bB A→bB|aD|a  B→aA|bD|b D→aD|bD|a|b a a A a S b a a b D Z

54 使其右部为空字符串的产生式，称为空产生式。产生式记为A→或A→
例子: G[S]: S→AaB A→AB| B→bB| 所以:G[S]含有空产生式

55 定义3.5 直接左递归：若有产生式 A→A… 直接右递归：若有产生式 A→…A 左递归：若有推导式 A A… 右递归：若有推导式 A …A
 +

56 例子： 直接递归：A→Aa B→aBB 左递归：S→Qc|c Q→Rb|b R→Sa|a QRbSabQcab  QQcab

57 设xUyxuy是一直接推导。如果U是句型xUy中的最右非终极字符，则称该推导为规范直接推导并记为xUy xuy。
3.5 上下无关文法及其语法树 规范推导和句柄 定义3.6 设xUyxuy是一直接推导。如果U是句型xUy中的最右非终极字符，则称该推导为规范直接推导并记为xUy xuy。 如果x y中的每步都是规范直接推导，则称该推导为规范推导并记为 x y。  r +

58 如果每步都是最右非终极字符，则也称该规范推导为最右推导。
例子：G[S]：S→AB A→Aa|bB B→a|Sb SABbBBbaB(最左推导) SABASbAABbAAabAbBab (最右推导) SABASbbBSbbaSb(非左非右)

59 语法树与二义性 定义3.8 设G=(VN,VT,P,S)是给定文法,则称满足下面条件的树为G的一棵语法树。 每个结点都标有G的一个文法符号,且根结点标有初始符S,非叶结点标有非终极符。 如果一个非叶结点A有n个儿子结点(从左到右)B1,B2,…,Bn,则A→B1B2…,Bn一定是G的一个产生式。

60 S A B a c b 例子：Z→AB A→a B→bc 定义3.9 由某一结点及其所属分枝组成的部分树称为原树的一棵子树。
只有单层分枝的子树称为简单子树。

61 假设Z xUy，U u，则称句型xuy中的u为该句型的短语，其中Z为初始符。
3.6 句型的分析 定义3.7 假设Z xUy，U u，则称句型xuy中的u为该句型的短语，其中Z为初始符。 假设有Z xUy，Uu，则称句型xuy中的u为该句型的简单短语。 最左边的简单短语称为句柄。  * +

62 S baB BSb x U U y u 例子：G[S]：S→AB A→Aa A→bB B→a B→Sb
解：SAB bBB baB baSb S baB  * BSb x U U y u  Sb是句型baSb的短语，简单短语

63 解：SAB ASb bBSb baSb
S bBSb  * Ba U u x U y a是句型baSb的短语，且是简单短语。

64 S ASb Aba U u x U y 解：SABASbbBSbbaSb   ba是句型baSb的短语，但不是简单短语。
* Aba ＋ U u x U y  ba是句型baSb的短语，但不是简单短语。 所以：ba, a, Sb 是句型baSb的短语 a, Sb 是句型baSb的简单短语 a 是句型baSb的句柄。

65 定理3.1 1、每个句型都有一棵语法树，每个语法树的叶组成一句型。 2、每棵子树的叶组成短语，每棵简单子树的叶组成简单短语，最左简单子树的叶组成句柄。 3、用语法树可证明每个句子都有一规范推导。

66 构造语法树 E E G[E]： E→E+T|T T→T*F|F F→(E)|a E + T E + T T
EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a

67 EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*a
EE+T E+T*F E+T*a E+F*a E+a*a T+a*a F+a*a a+a*a EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a E E + T T T * F F F a a a 看不出句型中的符号被替代的顺序

68 用于描述上下文无关文法句型推导的直观方法
上下文无关文法的语法树的用处 用于描述上下文无关文法句型推导的直观方法 句型aabbaa的语法树（推导树） S a A S S b A a a b a 例: G[S]: S→aAS A→SbA A→SS S→a A→ba 叶子结点：树中没有子孙的结点。 从左到右读出推导树的叶子标记连接成的文法符号串，为G[S]的句型。也把该推导树称为该句型的语法树。

69 上下文无关文法的语法树 推导过程中施用产生式的顺序 例: G[S]: S→aAS S a A S A→SbA S b A a A→SS
A→ba S a A S S b A a a b a SaASaAaaSbAaaSbbaaaabbaa SaASaSbASaabASaabbaSaabbaa SaASaSbASaSbAaaabAaaabbaa

70 一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢
一棵语法树表示了一个句型的种种可能的(但未必是所有的)不同推导过程，包括最左(最右)推导。但是，一个句型是否只对应唯一的一棵语法树呢?一个句型是否只有唯一的一个最左(最右)推导呢?

71 E E + E E * E i i i E E * E i E + E i i 例：G[E]: E → i E → E+E E → E*E
推导1：E  E+E  E*E+E  i*E+E  i*i+E  i*i+i 推导2：E  E*E  i*E  i*E+E  i*i+E i*i+i

72 S A B b 例子：G[S]：S→AB A→Aa|bB B→a|Sb 字符串：bBABb 短语：bB,AB,ABb 简单短语：bB,AB

73 定义3.10 如果一个文法G存在某个句子,使得它有两棵语法树,则称G为二义性文法。 例子：证明 G:E→E+E|E*E|(E)|i 则G是二义性文法。 因为句子i+i*i具有两棵语法树分别如图所示。

74 E + i *

75 E + i *

76 例子： 证明 G[S]: S→If B Then S S→If B Then S Else S 是二义性文法。If B1 Then If B2 Then S2 Else S3该句子具有二义性(其中S表示语句，Sx无条件语句，Bx表示布尔变量) ，分析情况如下：

77 　If B1 Then If B2 Then S2 Else S3　　
例子：If x>1 then if x>2 then y:=a else y:=b 解释1:If x>1 then if x>2 then y:=a else y:=b 解释2:If x>1 then if x>2 then y:=a else y:=b

78 S If B１ Then S１ If B２ Then S２ Else S３ If B1 Then If B2 Then S2 Else S3
第一种： If B２ Then S２ Else S３

79 If B１ Then S１ Else S３ S If B２ Then S２ If B1 Then If B2 Then S2 Else S3
第二种： If B１ Then S１ Else S３ S If B２ Then S２

80 语义上限制。 怎样排除二义性： 改写文法。 改写文法如下： S→M|U M→If B Then M Else M|S1 U→If B Then S|If B Then M Else U M为匹配语句，U为非匹配语句。

81 得到语法树如下： U If B１ Then S If B２ Then S２ Else M S3

82 文法中不含有不可到达和不可终止的非终结符
3.7 有关文法实用中的一些说明 文法中不含有有害规则和多余规则 有害规则：形如U→U的产生式。会引起文法的二义性 多余规则：指文法中任何句子的推导都不会用到的规则 文法中不含有不可到达和不可终止的非终结符 1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。 2）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。

83 S 1 S 1 S 1 1.文法中不含有A→A的规则 例:S→0S1|01 无二义性,可以改为:
1 S 1 S 1

84 2.文法中不包含多余规则 ①不可到达：所有推导均不会用到此规则 ②不可终止：推导不出终结符号串 例子: 文法G[S]： (1) S→Be (5)A→e (2) B→Ce不可终止 (6)C→Cf不可终止 (3) B→Af (7)D→f不可达 (4) A→Ae

85 对文法G=(VN,VT,S,P),为了保证其任一非终结符A在句子推导中出现,必须满足如下两个条件：
S αAβ,其中α,β属(VT∪VN)*。 2.必须能够从A推出终结符号串t来。即A t,其中t∈VT*。 因此检查文法是否包含多余规则是很有必要的。  * +

86 3.9 文法的等价转变换 定理3.2 对任一文法G1都可以构造文法G2使得L(G1)=L(G2)，并且G2有这样的特点，即文法的初始符不出现于产生式的右部。 例子：G:E→E+E|E*E|(E)|i 可改写为：G:E’→E E→E+E|E*E|(E)|i

87 定理3.3 对任一文法G1都可以构造文法G2使得L(G1)=L(G2) ，并且G2的每个非终极符出现于某句型中。
定理3.4 对任一文法G1均可构造文法G2使得L(G1)=L(G2)，且在G2中没有形如A→B的产生式,其中B∈VN。

88 证明：我们称形如A→B的产生式为特型产生式。G2的构造算法是： 1、对每个A∈VN，求 βA={D|A D,D∈VN}
2、令G1中所有的非特型产生式为G2的产生式。 3、若有D∈βA，且有D→x(非特型)，则令A→x∈G2 4、删除无用的产生式。  *

89 例子：G[A]:A→B|a B→b 求解如下： 保留：A→a B→b 扩充：A→B B→b  A→b G[A]：A→a|b B→b (多余)  G[A]:A→a|b

90 例子：设有如下文法 G1：A→B|dD B→A|C|b C→B|c D→d|Da A→B A→B B→A  A→A A→B B→C  A→C 所以A={A,B,C}

91 则有：A={A,B,C} B={B,A,C} C={C,A,B} D={ } 令G1中的非特型产生式为G2的产生式： G2：A→dD B→b C→c D→d|Da 再扩充产生式： G2：A→b|c B→dD|c C→dD|b

92 所以G2[A]: A→dD B→b C→c D→d|Da A→b|c B→dD|c C→dD|b 其中B和C不出现在任何句型中，因此可以删去相关的产生式。 得出：G2[A]：A→dD|b|c D→d|Da

93 定理3.5 任一文法G1,可构造文法G2,使得L(G2)=L(G1)且G2中没有ε产生式。
1、开始令β={A|A→ε∈G1 } 2、递归扩充β：β=β∪{ D|D→x∈G1,x∈β+} 3、从G1删除所有ε产生式。 4、从G1删去只能导出空串的非终极符。

94 5、设β=β∪{A1,A2,…An}， VN~β={B1,B2,…Bn} 若有产生式A→C1C2…Cn，则Ci有三种可能： Ci∈VT，Ci∈β，Ci∈VN~β。 如果Ci∈β，则因为删去了所有产生式，以此扩充一产生式A→C1C2…Cn。重复这个过程，直至不出现新的产生式为止。

95 例子：设有文法 G:A→aBbD D→BB B→ε|b 解：B→ε DBB ε  ={B,D}

96 则有β={B,D}删去ε产生式得： A→aBbD D→BB B→b 再扩充下面产生式： A→abD A→aBb A→ab D→B

97 A 定理3.6 设有文法G1,则可构造文法G2,使得L(G2)=L(G1),并且G2没有直接左递归的产生式。 A→A|  A→A’
例子：A→Aab|cd  A→cdA’ A’→abA’|   A

98 一般而言： A→A1|A2|...|An|1|2|…|m 则有: A→ 1A’|2A’|…|m A’ A’→1A’|2A’|…|nA’|

99 例子：考虑下面文法 E→E+T|T T→T*E|F F→(E)|i 用上述方法可以改写为： E→TE’ E’→+TE’| T→FT’ T’→*ET’|