第三章文法和语言

1、第第3章章 文法和语言文法和语言3.1 文法的直观概念文法的直观概念文法文法：描述语言的语法结构的形式规则（即语法规则）。：描述语言的语法结构的形式规则（即语法规则）。1）描述单词）描述单词单词的组成规则单词的组成规则 BNF范式、正规式范式、正规式2）描述语句）描述语句语句的组成规则语句的组成规则BNF范式、语法图范式、语法图3.1 文法的直观概念文法的直观概念例如：判断例如：判断“ 我是大学生我是大学生”是否为句子是否为句子文法如下：文法如下：:= := | := 我我 | 你你 | 他他 :=王明王明| 大学生大学生|工人工人|英语英语:= :=是是 |学习学习:= | “我是大学生我是

2、大学生”的推导过程：的推导过程： - - - 我我 - 我我 - 我是我是 我是我是 - 我是大学生我是大学生 依次可以推导出句子依次可以推导出句子“王明是大学生王明是大学生”、“我学习英语我学习英语”等等等等文法作用文法作用（1）定义句子的结构；）定义句子的结构；（2）用适当条数的规则把语言的全部句子描述出来，以有穷集合刻划）用适当条数的规则把语言的全部句子描述出来，以有穷集合刻划无穷集合。无穷集合。3.2 符号和符号串符号和符号串一、基本概念一、基本概念1.字母表字母表符号的符号的非空有穷非空有穷集合集合用符号用符号或或V表示。表示。例如：例如：=a，b，c 和和 V=0，1都是字母表都是

3、字母表相当于语言中的字符集相当于语言中的字符集2.符号符号语言中不可再分的基本单位语言中不可再分的基本单位3.符号串符号串字母表中的符号组成的任何字母表中的符号组成的任何有穷序列有穷序列。说明说明（1）符号的顺序，如）符号的顺序，如ab与与ba不同；不同；（2）符号串长度：符号串内所含符号的个数）符号串长度：符号串内所含符号的个数其中其中 不含任何符号的符号串称为空符号串不含任何符号的符号串称为空符号串，长度，长度| |03.2 符号和符号串符号和符号串4.句子句子字母表上符合某种规则构成的串字母表上符合某种规则构成的串包含单词和语句包含单词和语句5.语言语言 句子的集合句子的集合3.2 符号

4、和符号串符号和符号串二、符号串的计算二、符号串的计算1.符号串的连接符号串的连接设设x和和y是符号串，它们的连接是符号串，它们的连接xy是把是把y的符号写在的符号写在x的符号之后的符号之后得到的符号串。得到的符号串。例如：例如：x=abc，y=def，则，则xy=abcdef2.符号串的方幂符号串的方幂 设设x是符号串，把是符号串，把x自身连接自身连接n次得到的符号串次得到的符号串z，即，即z=xxxx，称为符号串称为符号串x的方幂，记作的方幂，记作z=xn，即把符号串，即把符号串x重复地写重复地写n次。次。例如：例如： x0= ， x1= x ，x2=xx， x3=xxx 设设x=ab 则则

5、x3= ababab 当当n0时，时， xn x xn-1 = xn-1 x3.2 符号和符号串符号和符号串三、符号串集合的运算三、符号串集合的运算 连接（乘积）：连接（乘积）：设符号串集合设符号串集合A、B，则，则 ABxy | x A且且y B 例如：例如：A=a, b，B=c, d，则集合，则集合AB=ac, ad, bc, bd A = A = A； 一般而言，一般而言，AB BA，但，但(AB)C=A(BC)注意：注意：1)串集自身的连接称为串集的方幂串集自身的连接称为串集的方幂2）A0=3）字母表）字母表A的的n次方幂表示字母表次方幂表示字母表A上长度为上长度为n的字符串集的字符串

6、集3.2 符号和符号串符号和符号串四、字母表的闭包和正闭包四、字母表的闭包和正闭包1.字母表字母表的闭包的闭包 * 0 1 2 n 即由即由上所有符号串组成的符号串集（包含空串）上所有符号串组成的符号串集（包含空串）2. 字母表字母表的的正闭包正闭包 + 1 2 n 即由即由上所有符号串组成的符号串集（不包含空串）上所有符号串组成的符号串集（不包含空串） 显然有显然有* 0 + ; + = *= * 对所有对所有 ，有，有 *。3.3 文法和语言的形式定义文法和语言的形式定义规则，也称为产生式或生成式规则，也称为产生式或生成式如一个产生式的形式是如一个产生式的形式是 （或（或:= )，其中，其

7、中 “”读读为为“是是”或或“定义为定义为”；非终结符：非终结符：在规则中用在规则中用括起来括起来非终结符用非终结符用VN表示表示终结符终结符语言中不可再分的字符串语言中不可再分的字符串终结符用终结符用VT表示表示定义定义3.1 文法文法G G是一个四元式组是一个四元式组 G=(VG=(VT T，V VN N，S S，P)P) 其中其中V VT T：终结符集合（非空、有穷）：终结符集合（非空、有穷）V VN N：非终结符集合（非空、有穷），且：非终结符集合（非空、有穷），且V VT T V VN N= =S S：文法的开始符号，：文法的开始符号，S S V VN NP P：产生式集合：产生式集

8、合( (非空、有穷非空、有穷) )，产生式的形式是产生式的形式是 和和 属于属于 ( (V VT T V VN N) )* *开始符开始符S S至少必须在某个产生式的左部出现一次。至少必须在某个产生式的左部出现一次。3.3 文法和语言的形式定义文法和语言的形式定义例：例： 文法文法G =（VN，VT，P，S） VN标识符，字母，数字标识符，字母，数字， VT a, b, c, , x, y, z, 0,1, , 8, 9 P= | | a|b|c|x|y|z 0|1|2|8|9 S = 注意：注意：有时不用将文法有时不用将文法G G的四元组显示的表示出来，而只写产生式的四元组显示的表示出来，而

9、只写产生式 约定：第一个产生式的左部是开始符号约定：第一个产生式的左部是开始符号 可将可将G写成写成GS，S为文法为文法G的开始符号的开始符号下面是一个文法的等价写法下面是一个文法的等价写法1）G=S,A,a,b,P,S其中其中P：S-aAb A-ab A-aAb A- 2） G: S-aAb A-ab A-aAb A- 3）GS: S-aAb A-ab A-aAb A- 4）GS: A-aAb|ab| S-aAb 有关推导的定义有关推导的定义1、直接推导直接推导 若若AA直接推导出直接推导出 ，即，即 A=A=，当且仅当，当且仅当A A是是一个产生式，且一个产生式，且、(V VN NV VT

10、 T) )* * 符号符号 =指推导一步，即推导每前进一步总是引用一条规则指推导一步，即推导每前进一步总是引用一条规则（产生式）（产生式）2、长度为长度为n（n1）的推导）的推导 若存在直接推导序列若存在直接推导序列a0 a1 an，则，则称称a0可推导出可推导出an。 a0 an 表示：从表示：从a0出发经过一步或若干步，可推导出出发经过一步或若干步，可推导出an 。3、长度为长度为n（n0）的推导）的推导 a1 an 表示：从表示：从a1出发经过出发经过0步（步（ a1 an ）或若干步，可推导出）或若干步，可推导出an 。例：例： 文法文法G ： | | a|b|c|x|y|z 0|1|

11、2|8|9 句型、句子、语言例：例：证明终结符号串证明终结符号串( i*i+i )是文法是文法G：E E+E | E*E | (E)| i的一个句子的一个句子证明：证明： E =( E ) =(E+E)=(E*E+E) =(i*E+E) =(i*i+E)=(i*i+i) 是从开始符号是从开始符号E到到( i*i+i )的一个推导。的一个推导。其中其中E、(E)、(E+E)、(E*E+E)、 (i*E+E) 、 (i*i+E) 、 (i*i+i)都是都是这个文法的一个句型这个文法的一个句型*1. 句型句型：设：设GS是一个文法，是一个文法，S是它的开始符号，若是它的开始符号，若S ,则则称称是文

12、法是文法GS的句型。的句型。2.句子句子：仅含终结符的句型是一个句子，即：仅含终结符的句型是一个句子，即S ，VT*, 则则是句子。是句子。3.语言语言：文法：文法G所产生的句所产生的句 子的全体是一个语言，记作子的全体是一个语言，记作L(G) L(G)=|S ,且且VT*语言的例子语言的例子例：文法例：文法G2：A bA | cc，证明，证明cc、bcc、bbcc、 属于属于L(G2)。证明：证明：VT=b, c ， VN=A， S=A A cc， A bA bcc， A bA bbA bbcc cc、bcc、bbcc、是属于是属于L(G2)的的例：文法例：文法GS为为 (1) S0S10S

13、1； (2) S01,GS(2) S01,GS的语言是什么。的语言是什么。解：通过对第一个产生式使用解：通过对第一个产生式使用n-1n-1次，然后使用第二个产生式一次，得次，然后使用第二个产生式一次，得到：到：S 0S1 00S11 0S 0S1 00S11 0n-1n-1S1S1n-1n-1 0 0n n1 1n n因此因此L(G)=0L(G)=0n n1 1n n|n |n 11 文法的文法的等价等价 若若L(G1) = L(G2)，则称文法，则称文法G1和和G2是等价的是等价的例如例如: 文法文法G1=(VN, VT, P, S)， VN =S， VT =0, 1，P由下列产生式组成：由

14、下列产生式组成： (1) S0S10S1； (2) S01(2) S01； 文法文法G2=(VN, VT, P, S)， VN =A, R， VT =0, 1，P由下列产生式组成：由下列产生式组成： (1) A 0R ; (2) A 01; (3) R A13.4 文法的类型文法的类型 乔姆斯基建立的形式语言对计算机科学的发展具有深刻的乔姆斯基建立的形式语言对计算机科学的发展具有深刻的意义。意义。他把文法分成四种类型：他把文法分成四种类型：0型、型、1型、型、2型和型和3型。型。它们的差别在于对产生式施加不同的限制。它们的差别在于对产生式施加不同的限制。0型文法（或称短语文法）l G=( VN

15、, VT, P, S)是是0型文法是指：型文法是指： 若它的每个产生式若它的每个产生式是这样一种结构是这样一种结构: (VNVT)*且至少含有一个非终结符，且至少含有一个非终结符，(VNVT)*。l 0型文法又称为短语文法型文法又称为短语文法 。 0型文法的能力相当于图灵机型文法的能力相当于图灵机（计算机的一种简单的理论模型）。（计算机的一种简单的理论模型）。1型文法（或称上下文有关文法）型文法（或称上下文有关文法） 如果对如果对0型文法分别加以以下的限制，则可得到型文法分别加以以下的限制，则可得到1型文法。型文法。l设设G=( VN, VT, P, S)为一文法，若为一文法，若G的任何产生式

16、的任何产生式 均均满足满足| | (指符号串的长度指符号串的长度)，仅仅，仅仅S 例外。例外。 上下文有关就是对非终结符进行替换时必须考虑上下文上下文有关就是对非终结符进行替换时必须考虑上下文l例如：例如：1型文法型文法G的产生式也可写成的产生式也可写成A ，其中，其中、都在都在(VNVT)*中，且中，且 ，A VN ，则说明了非终结符，则说明了非终结符A必须在必须在、这样一个上下文环境中才可以替换。这样一个上下文环境中才可以替换。 2型文法（或称上下文无关文法）型文法（或称上下文无关文法） 设设G=( VN, VT, P, S)为一文法，若为一文法，若G的任何产生式形似的任何产生式形似 ，其

17、中，其中 VN， (VNVT)* 。例：例：G=(S,A,B,a,b,P,S)，其中，其中P由下列产生式组成由下列产生式组成SaB|bA Aa|aS|bAABb|bS|Abb例：例：G=(VN, VT, P, S)， VN =S， VT =0, 1，P由下列产生式由下列产生式组成：组成： (1) S0S1； (2) S01； 上下文无关文法的说明上下文无关文法的说明 上下文无关，顾名思义就是非终结符的替换可以不必考上下文无关，顾名思义就是非终结符的替换可以不必考虑上下文。虑上下文。 由于这种文法对程序已基本可以描述，因此，上下文无由于这种文法对程序已基本可以描述，因此，上下文无关文法常简称为文

18、法。关文法常简称为文法。3型文法（或称正规文法）型文法（或称正规文法）设设G=( VN, VT, P, S)为一文法，若为一文法，若G的任何产生式的任何产生式A 或或A B ，其中，其中A、B VN ， VT* 。例：文法例：文法G=(S,A,B,0,1,P,S)，其中，其中P由下列产生式组成由下列产生式组成S 0A|1B|0A 0A|1B|0SB 1B|1|0例：设例：设G=(VN, VT, P, S)， VN =S, B, E， VT =a, b, e，P由下列产生式组成：由下列产生式组成： (1) S aSBE ； (2) S aBE ; (3) EB BE ; (4) aB ab ;

19、(5) bB bb ; (6) bE be ; (7) eE ee ;判断以下文法属于哪类文法？判断以下文法属于哪类文法？3.5 上下文无关文法及其语法树上下文无关文法及其语法树一、语法树（推导树）一、语法树（推导树）1.直观定义：用图表示上下文无关文法句型推导的直观方法。直观定义：用图表示上下文无关文法句型推导的直观方法。2. 形式定义形式定义给定文法给定文法G=( VN, VT, P, S)，对于，对于G的任何句型都能构造与之相关联的语法的任何句型都能构造与之相关联的语法树，这棵语法树满足以下树，这棵语法树满足以下4个条件：个条件：（1）根结点由开始符号）根结点由开始符号S所标记；所标记；

20、（2）每个结点都有一个标记，此标记是）每个结点都有一个标记，此标记是V(即即VN VT)的一个符号；的一个符号；（3） 若结点若结点n至少有一个除它自己以外的子孙结点，并且有标记至少有一个除它自己以外的子孙结点，并且有标记A，则，则A在在VN中；中；（4）如果结点）如果结点n的直接子孙，从左到右的次序是结点的直接子孙，从左到右的次序是结点n1,nk，其标记为，其标记为A1,A2,Ak，那么，那么A-A1A2Ak一定是一定是P中的一个产生式。中的一个产生式。 从根结点从根结点S开始推导，当非终结符被它的某个候选式所替换时，这个非开始推导，当非终结符被它的某个候选式所替换时，这个非终结符的相应结点

21、就产生出下一代新结点，候选式中自左向右的每个符号终结符的相应结点就产生出下一代新结点，候选式中自左向右的每个符号对应一个新结点，并用这些符号标记其相应的新结点。每个新结点与其父对应一个新结点，并用这些符号标记其相应的新结点。每个新结点与其父结点间都有一条连线。结点间都有一条连线。在一棵语法树生长过程中的任何时刻，所有那些没有后代的末端结点自在一棵语法树生长过程中的任何时刻，所有那些没有后代的末端结点自左向右排列起来就是一个句型。左向右排列起来就是一个句型。语法树构造的过程语法树构造的过程E(根根)（E）E+ +EE*Eiii层次层次12345例例1 文法文法G= ( E, +, *, i ,

22、(, ), P, E)，其中，其中P为：为： E E+E | E*E | (E) | i对该文法关于对该文法关于(i*i+i)的推导的语法树如下所示：的推导的语法树如下所示：例例2：G=（S，A，a,b,P,S),其中其中P为：为： (1) S aAS (2) A SbA (3) S a (4) A ba 求文法求文法G的句型的句型aabbaa的推导树。的推导树。最左推导最左推导/最右推导最右推导/规范句型规范句型最左推导最左推导是指：任何一步是指：任何一步= 都是对都是对中的最左非终结符进行替换。中的最左非终结符进行替换。同样，可定义同样，可定义最右推导最右推导（又称规范推导）：任何一步（又

23、称规范推导）：任何一步=都是对都是对中的最中的最右非终结符进行替换。右非终结符进行替换。由规范推导所得到的句型称为由规范推导所得到的句型称为规范句型规范句型。注意：从一个句型到另一个句型的推导过程往往是不唯一的。注意：从一个句型到另一个句型的推导过程往往是不唯一的。例如例如 E+E i+i（a）E+E = E+i = i+i 最右推导最右推导（b）E+E = i+E = i+i 最左推导最左推导一个句型是否只对应唯一的一棵语法树？一个句型是否只对应唯一的一棵语法树？例如例如 对于文法对于文法GE： E E+E | E*E | (E) | i，对于句子，对于句子(i*i+i)存存在语法树：在语法

24、树：E(根根)（E）E+ +EE*EiiiE(根根)（E）E*EE+Eiii 定义：定义： 一个文法的某个句子对应两棵不同的语法树，则这个文法是一个文法的某个句子对应两棵不同的语法树，则这个文法是二义的。二义的。或或 一个文法的某个句子有两个不同的最左（右）推导，则这一个文法的某个句子有两个不同的最左（右）推导，则这个文法是二义的。个文法是二义的。二义性二义性 二义性其它问题二义性其它问题 人们已证明，二义性问题是不可判定的，即不存在一个算法，人们已证明，二义性问题是不可判定的，即不存在一个算法，它能在有限步骤内，确切地判断一个文法是否是二义的。它能在有限步骤内，确切地判断一个文法是否是二义的

25、。我们所能做的就是为无二义性寻找一些充分条件我们所能做的就是为无二义性寻找一些充分条件例如对文法例如对文法GE： E E+E | E*E | (E) | i 修改，规定运算符修改，规定运算符“+”与与“*”的优先关系和结合规则，设的优先关系和结合规则，设“*”的优先性高于的优先性高于“+”，且服从，且服从左结合。左结合。G: E T | E+T T F | T*F F (E) | i 3.6 句型的分析句型的分析 句型分析的任务就是按文法的产生式，识别输入的符号是否是句型分析的任务就是按文法的产生式，识别输入的符号是否是该文法的句型。该文法的句型。我们把完成句型分析的程序称为分析程序或识别程序

26、，分析算法我们把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。又称识别算法。分析算法又分为：分析算法又分为：从左到右分析算法；从左到右分析算法；从右到左分析算法；从右到左分析算法；自上而下的分析法自上而下的分析法自下而上的分析法自下而上的分析法3.6.1自上而下的分析法自上而下的分析法 基本思想：从文法的开始符号出发，反复使用各种产生式，寻基本思想：从文法的开始符号出发，反复使用各种产生式，寻找找“匹配匹配”输入符号串的推导。即对任何输入符号串，从文法的开输入符号串的推导。即对任何输入符号串，从文法的开始符号（根结）出发，自上而下地为输入串建立一棵语法树，直到始符号（根结）出

27、发，自上而下地为输入串建立一棵语法树，直到语法树结果正好是输入的符号串为止。语法树结果正好是输入的符号串为止。例如：文法例如：文法GS: S xAy A * | *，识别输入串，识别输入串x*y是否是该是否是该文法的一个句子。文法的一个句子。解：解：SS S S x A y (2) S S S x A y (3) * (1) 缺陷缺陷关键：关键：回溯问题回溯问题；（；（ 其分析过程是一种试探过程）其分析过程是一种试探过程） 回溯问题回溯问题是从各种可能的候选式中任选一个，进行推导后发现是从各种可能的候选式中任选一个，进行推导后发现该候选式是错误的，则退回去重新选择候选式的方式。例如上例中该候选

28、式是错误的，则退回去重新选择候选式的方式。例如上例中的的(3)。S S S x A y (3) 选用第选用第1个候选式个候选式 * 回溯的产生使算法代价极高，效率很低。回溯的产生使算法代价极高，效率很低。 * 3.6.2自下而上的分析法自下而上的分析法 基本思想：从输入串开始，逐步进行基本思想：从输入串开始，逐步进行“归约归约”，直至归约到文，直至归约到文法的开始符号。即从语法树的末端开始，步步向上法的开始符号。即从语法树的末端开始，步步向上“归约归约”，直到，直到根结。根结。 归约：若归约：若V= ，W=， 是文法的产生式，如有是文法的产生式，如有V=W，则，则W直接归约到直接归约到V。例：

29、例： 文法文法GS： (1)S aAcBe (2) A b (3)A Ab (4) B d 识别识别abbcde是否为文法是否为文法S的一个句子。的一个句子。解题思想：扫描解题思想：扫描abbcde，从中找出一个子串，该子串与某一产生式，从中找出一个子串，该子串与某一产生式的右部相匹配。的右部相匹配。解：a b b c d e(1)a b b c d eA A(2)a b b c d eAA(3)a b b c d eAA(4)Ba b b c d eAA(5)BAS例：例： 文法文法GS： (1)S aAcBe (2) A b (3)A Ab (4) B d自下而上分析法存在的问题自下而上分

30、析法存在的问题可归约串的问题可归约串的问题； 该分析的每一步就是从当前串中找一个子串该分析的每一步就是从当前串中找一个子串（称（称“可归约串可归约串”），将它归约到某个非终结符号），将它归约到某个非终结符号 自下而上分析法的关键就是找哪个子串是自下而上分析法的关键就是找哪个子串是“可归约串可归约串”，哪个，哪个不是不是“可归约串可归约串”。例：上例中的例：上例中的(3)a b b c d eA A(3) 用产生式(2)而非(3)，则不能归约到S 因此必须精确定义因此必须精确定义“可归约串可归约串” 3.6.3 句型分析的有关问题句型分析的有关问题在自上而下的分析方法中，存在的缺陷是在自上而下的

31、分析方法中，存在的缺陷是“回溯回溯”，如何确定用，如何确定用哪个右部代替左部？哪个右部代替左部？在自下而上的分析方法中，解决的关键问题是在自下而上的分析方法中，解决的关键问题是“可归约串可归约串”。短语、直接短语、句柄短语、直接短语、句柄1、短语：、短语：令文法令文法G，开始符号为开始符号为S，是是G的句型的句型（即（即S ），如果），如果S A且且A ，则称，则称是句型是句型相对于非终结符相对于非终结符A的短语。的短语。 如果有如果有A=，则称，则称是句型相对于规则是句型相对于规则A 的的直接短语直接短语。3、句柄、句柄 一个句型的最左直接短语称为该句型的句柄。一个句型的最左直接短语称为该句

32、型的句柄。 解题方法解题方法例：文法例：文法GE: E T | E+T T F | T*F F (E) | i 证明证明i+i*i是是G的一个句型，并指出这个句型的所有短语、直接短语、的一个句型，并指出这个句型的所有短语、直接短语、句柄。句柄。证明：证明：E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i接上例接上例语法树：EE+TTT*FFFi3i1i2第第1层层 i1+i2*i3 相对于相对于E第第2层层 i1 相对于相对于E ; i2*i3 相对于相对于T第第3层层 i1 ,i2 相对于相对于T; i3 相对于相对于F第第4层层 i1 ,i2

33、相对于相对于F(F i直接短语直接短语)第第5层层 i+i*i是是G的一个句型，其中的一个句型，其中i1 , i2 , i3, i2*i3 , i1+i2*i3 都是句型都是句型i1+i2*i3 的的短语，且短语，且i1 , i2 , i3 为直接短语，为直接短语， i1为句柄为句柄分析说明分析说明(2)作为作为“短语短语”的两个条件是不可缺少的，仅仅有的两个条件是不可缺少的，仅仅有A ，未必意，未必意味着味着就是句型就是句型的一个短语，因为还需要有的一个短语，因为还需要有S A这个条件。这个条件。例如：上例中有例如：上例中有E i1+i2，但，但i1+i2并不是该句型的一个短语，因为并不是该

34、句型的一个短语，因为不存在从不存在从E（开始符号）到（开始符号）到E* i3的推导。的推导。(1)短语、直接短语、句柄是针对某一句型（短语、直接短语、句柄是针对某一句型（S ）而言的）而言的;3.7 有关文法实用中的一些说明有关文法实用中的一些说明在实际应用中在实际应用中对文法提出一些限制对文法提出一些限制对文法进行扩充对文法进行扩充3.7.1 有关文法实用限制有关文法实用限制 在实用中，主要是在文法中不得含有有害规则和多余规则。在实用中，主要是在文法中不得含有有害规则和多余规则。1、不含有害规则、不含有害规则有害规则是指形如有害规则是指形如PP的产生式，因为这样的产生式除了引起二义的产生式，

35、因为这样的产生式除了引起二义外，没有任何用处。外，没有任何用处。2、不含多余规则、不含多余规则(1)不可到达的不可到达的即文法中的某些非终结符不在任何规则的右部出现，则任何句子推即文法中的某些非终结符不在任何规则的右部出现，则任何句子推导不可能用到它。也就是说导不可能用到它。也就是说 对非终结符对非终结符P，不存在，不存在S P， , ( (VNVT) )* * 3.7.1 有关文法实用限制有关文法实用限制(2) 不可终止的不可终止的即文法中的某些非终结符不能够从它推出终结符串。也就是说即文法中的某些非终结符不能够从它推出终结符串。也就是说 对非终结符对非终结符P，不存在，不存在P t， t VT* * 若文法均满足以上两个条件，则称这个文法为若文法均满足以上两个条件，则称这个文法为简化了的文法简化了的文法。文法文法GS：(1)SBe(2)BCe(3)BAf(4)AAe(5)Ae(6)CCf(7)Df（7）、（）、（6）、（）、（2）多余规则）多余规则3.7.2 上下文无关文法的上下文无关文法的规则规则自学自学例例1： 证明文法证