编译原理第讲文法和语法课件.ppt

《编译原理第讲文法和语法课件.ppt》由会员分享，可在线阅读，更多相关《编译原理第讲文法和语法课件.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理课件第讲文法和语法第1页，此课件共63页哦第一节第一节 语语 言言语言语言语言语言:是由句子组成的集合。是由句子组成的集合。是由句子组成的集合。是由句子组成的集合。汉语汉语-所有符合汉语语法的句子的全体所有符合汉语语法的句子的全体英语英语-所有符合英语语法的句子的全体所有符合英语语法的句子的全体程序设计语言程序设计语言-所有该语言的程序的全体所有该语言的程序的全体研究语言研究语言：每个句子构成的规律每个句子构成的规律每个句子的含义每个句子的含义每个句子和使用者的关系每个句子和使用者的关系第2页，此课件共63页哦研究程序设计语言：研究程序设计语言：每个程序构成的规律 每个程序的含义 每个

2、程序和使用者的关系语言研究的三个方面：语言研究的三个方面：语法 Syntax 语义 Semantics 语用 Pragmatics第3页，此课件共63页哦语法语法：表示构成语言句子的各个记号之间的 组合规律组合规律 语义语义：表示按照各种表示方法所表示的各个 记号的特定含义。（各个记号和记号所 表示的对象之间的关系）语用语用：表示在各个记号所出现的行为中，它 们的来源、使用和影响。第4页，此课件共63页哦第二节第二节 文文 法法“我是大学生”是否是该语言的句子？句子句子:=主语谓语主语谓语主语主语:=代词代词|名词名词代词代词:=你你|我我|他他名词名词:=王明王明|大学生大学生|工人工人|英

3、语英语谓语谓语:=动词直接宾语动词直接宾语动词动词:=是是|学习学习直接宾语直接宾语:=代词代词|名词名词以自然语言为例，用 EBNF(扩展的巴科斯范式)描述一种语言：第5页，此课件共63页哦句子句子 主语谓语主语谓语 句子句子:=主语谓语主语谓语主语主语:=代词代词|名词名词代词代词:=你你|我我|他他名词名词:=王明王明|大学生大学生|工人工人|英语英语谓语谓语:=动词直接宾语动词直接宾语动词动词:=是是|学习学习直接宾语直接宾语:=代词代词|名词名词 代词代词谓语谓语 我我谓语谓语 我我动词动词直接宾语直接宾语 我我是是直接宾语直接宾语 我是我是名词名词 我是我是大学生大学生 第6页，此

4、课件共63页哦句子句子:=主语谓语主语谓语主语主语:=代词代词|名词名词代词代词:=你你|我我|他他名词名词:=王明王明|大学生大学生|工人工人|英语英语谓语谓语:=动词直接宾语动词直接宾语动词动词:=是是|学习学习直接宾语直接宾语:=代词代词|名词名词下列是否是句子下列是否是句子?我大学生是我大学生是 他是工程师他是工程师 大学生是王明大学生是王明第7页，此课件共63页哦事实上，使用文法作为工具，不仅为了严格定义句子的结构，也是为了用适当条数的规则把语言的全部句子描述出来。文法文法是以有穷的集合刻画无穷的集合的一个工具。第8页，此课件共63页哦第三节第三节 符号和符号串符号和符号串字母表字母

5、表：元素的：元素的非空有穷非空有穷集合。（符号集）集合。（符号集）符号符号：字母表中的元素。：字母表中的元素。例如：例如：汉语的字母表中汉语的字母表中 包括汉字、数字及标点符号等。包括汉字、数字及标点符号等。PASCAL PASCAL语言的字母表语言的字母表 是由字母、数字、若干专用符号及是由字母、数字、若干专用符号及BEGINBEGIN、IF IF之类的保留字组成。之类的保留字组成。第9页，此课件共63页哦 符号串符号串：由字母表中的符号组成的任何有穷序列 称为该字母表上的符号串。1.空符号串(没有符号的符号串)是上的符号串。2.若x是上的符号串，a是的元素，则xa和ax是上的 符号串。3.

6、y是上的符号串,当且仅当它可以由1和2导出。例如：=a,b,a,b,aa,ab,aabba,都是上的符号串。第10页，此课件共63页哦例：=0,1,0,1,00,01,11,1001110 等都是上的符号串.例：=a,b,c上的符号串有：a,b,c,ab,ba,aaca,acaa 等.注意：注意：1.符号串中的符号排列是有顺序的.2.可以用字母表示符号串，如：x=aaca第11页，此课件共63页哦如果如果 z=xy 是一符号串，那么：vv x x 是是 z 的头的头(前缀前缀)，y y 是是 z 的尾的尾(后缀后缀)；vv 如果如果 x 非空，那么非空，那么 y y 是固有尾；如果是固有尾；如

7、果 y y 非非 空，那么空，那么 x 是固有头。是固有头。例：例：例：例：设设设设 z=abc,z=abc,z=abc,z=abc,那么那么那么那么z z z z 的头是：的头是：的头是：的头是：,a,ab,abc,a,ab,abc（除除 abc abc 外都是固有头）外都是固有头）z z z z 的尾是：的尾是：的尾是：的尾是：,c,bc,abc,c,bc,abc（除除 abc abc 外都是固有尾）外都是固有尾）第12页，此课件共63页哦几种表示法（x，z是符号串，t是符号）：z=x x 是符号串 z 的头z=x x 是符号串 z 的尾z=x x 在符号串z 中某处出现z=t 符号 t

8、是 符号串 z 的第一个符号z=t 符号 t 是 符号串 z 的最后一个符号第13页，此课件共63页哦符号串的运算符号串的运算 符号串的长度符号串的长度：符号串中符号的个数。符号串符号串中符号的个数。符号串s s的的 长度记为长度记为|s|s|。的长度为的长度为0 0。连连 接接：符号串符号串x x、y y的连接的连接,是把是把y y的符号写在的符号写在x x的符的符 号之后得到的符号串号之后得到的符号串xyxy 例：例：x=STx=ST，y=abu y=abu 则则 xy=STabuxy=STabu|x|=2|x|=2，|y|=3|y|=3，|xy|=5|xy|=5 x=x=x x=x=x第

9、14页，此课件共63页哦 方方 幂幂 符号串符号串x x自身连接自身连接n n次得到的符号串次得到的符号串 xxxxxx(nxx(n个个x)x)表表示为示为 x xn n x x0 0=,x=,x1 1=x,x=x,x2 2=xx=xx，x xn n=xx=xx x x x=AB,x=AB,则则 x x0 0=,x=,x1 1=AB,x=AB,x2 2=ABAB,x=ABAB,x3 3=ABABAB=ABABAB 对于对于 n0,xn0,xn n=xx=xxn-1 n-1=x=xn-1n-1x x 第15页，此课件共63页哦符号串集合：符号串集合：若集合若集合A中一切元素都是某字母表中一切元素

10、都是某字母表 上上 的符的符 号串，则称号串，则称A为字母表为字母表 上的符号串集合。上的符号串集合。两个符号串集合两个符号串集合A和和B的乘积：的乘积：定义为定义为 AB =AB =xy|x xy|x xy|x xy|x A A A A 且且且且 y y y y B B B B 例：例：若，若，集合集合A=a,ba,b B=c,dc,d 则则，AB=ac,ad,bc,bdac,ad,bc,bd A=A A=A A=A A=A =A=A=A=A(x=x=x)(x=x=x)闭闭 包：包：使用使用 *表示表示 上的所有有穷长的串（包括上的所有有穷长的串（包括）的的 集合。集合。*称为称为的的闭包。

11、闭包。正闭包：正闭包：从从*中除去中除去得到得到的集合记为的集合记为+。+称为称为的的 正闭包。正闭包。第16页，此课件共63页哦*=0 1 2 n +=1 2 n *=0 +=*=*+=*-例例1 1：设=0,1，则：*=，0，1，00，01，10，11，000，001，010，例例2 2：设=a,b，则 *=，a，b，aa，ab，ba，bb，aaa，aab，+=a，b，aa，ab，ba，bb，aaa，aab，第17页，此课件共63页哦第四节第四节 文法和语言的形式定义文法和语言的形式定义产生式产生式（重写规则、规则或生成式），是形如或=的（，）有序对，其中是某字母表V的正闭包V+中的一个符

12、号串，是V*中的一个符号串。（V+，V*)称为产生式产生式的左部的左部(或规则的左部)。称为产生式的右部产生式的右部(或规则的右部)。第18页，此课件共63页哦一、一、文文 法法 的的 定定 义义文文 法法 G：定义为四元组四元组（VN，VT，P，S），其中VN ：非终结符集VT ：终结符集P ：产生式（规则）集合S ：开始符号（起始符、识别符号）VN、VT 和 P 是非空有穷集。S 至少在一条规则中作为左部出现。VNVT=，SVN，V=VNVT，称为文法G的字母表（字汇表）注：有的参考书用（VT,VN,S,P）表示文法。第19页，此课件共63页哦例3.1 文法G=（VN，VT，P，S）VN

13、=S,VT=0,1 P =S0S1,S01 S为开始符号 或写成：GS：S0S1,S01 第20页，此课件共63页哦例3.2 文法G=（VN，VT，P，S）VN=标识符，字母，数字VT=a，b，c，x，y，z，0，1，9P=，a，z，0，,9 S=第21页，此课件共63页哦习惯上只将产生式写出。并有如下约定：习惯上只将产生式写出。并有如下约定：第一条产生式的左部是开始符号用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成GS，其中S是开始符号第22页，此课件共63页哦例3.3 文法 G=（VN，VT，P，S）VN=S,VT =0,1 P=S0S1,S0

14、1 S为开始符号可写成：GS：S0S1 S01或写成：GS：S0S1 01注：把注：把“0S10S1”和和“0101”称为产生式称为产生式 S0S1 01 S0S1 01 的候选式的候选式第23页，此课件共63页哦二、二、推推 导导 的的 定定 义义直接推导直接推导 “”是文法G的产生式，,V*，若有v,w满足：v=,w=,则说：v（应用规则）直接产生w或说：w是v的直接推导，直接推导，或说：w直接归约直接归约到v，记作 v w例：G：S0S1，S01直接推导：0S1 0011 （v=0S1，w=0011，使用规则S01，=0，=1）S 0S1 （v=S，w=0S1，使用规则S0S1，=，=）

15、0S1 00S11 （v=0S1，w=00S11，使用规则S0S1，=0，=1）第24页，此课件共63页哦例 文法G=（VN，VT，P，S）VN =标识符，字母，数字；VT =a,b,c,x,y,z,0,1,9P=a,z 0,9 S=指出下面直接推导所使用的规则：abc abc5第25页，此课件共63页哦例：例：G G：S0S1 S0S1，S01 S010S1 0S1 00S11 00S11 000S111 000S111 00001111 00001111 即即 0S1 000011110S1 00001111也记作也记作 0S1 000011110S1 00001111 若存在v=w0 w

16、1.wn=w,(n0)，则称v推导推导出（产生）w（推导长度为n），或称w归约归约v.记作 v w。若有 v w，或 v=w，则记为 v w+*+*和和和和注：注：包含包含0 0步推导；而步推导；而 不包含不包含0 0步推导。步推导。*+推推推推 导导导导第26页，此课件共63页哦例 G:abz 019 x x 1即：x1 也可记作：x1+*第27页，此课件共63页哦句型句型设GS是一文法，如果符号串x是从开始符号推导出来的，即S x，则称x是文法GS的句型。句子句子x仅由终结符号组成（即S x，且xVT*），则称x是GS的句子。例：G：S0S1，S01S 0S1 00S11 000S111

17、00001111三、三、文法的句型、句子的定义文法的句型、句子的定义*第28页，此课件共63页哦四、四、语语 言言 的的 定定 义义由文法G生成的语言语言记为L(G)，它是文法G的全部句子的集合:L(G)=x|S x，且x VT*，其中S为文法的开始符号 文法描述的语言是该文法一切句子的集合。文法描述的语言是该文法一切句子的集合。例：G：S0S1，S01S 0S100S11 0n-1S1n-1 0n1n L(G)=0n1n|n1*第29页，此课件共63页哦例3.3 设G=(VN,VT,P,S),VN=S,B,E,VT=a,b,e,P由下列产生式组成：（1）S aSBE （2）S aBE（3）E

18、B BE （4）aB ab（5）bB bb （6）bE be（7）eE eeS an-1S(BE)n-1an(BE)n anBnEn anbnen L(G)=anbnen|n1*第30页，此课件共63页哦五、五、文文 法法 的的 等等 价价若L(G1)=L(G2)，则称文法G1和G2是等价的。如文法G1A：A0R 与G2S：S0S1 等价 A01 S01 RA1注：语言和文法的对应关系是一对多（注：语言和文法的对应关系是一对多（1 1：n n）的关系。的关系。第31页，此课件共63页哦第五节第五节 文文 法法 的的 类类 型型 通过对产生式施加不同的限制，Chomsky将文法分为四种类型（称为

19、Chomsky 文法）第32页，此课件共63页哦一、文一、文 法法 的的 类类 型型0型文法型文法：对任一产生式，都有(VNVT)+，且至少包含一非终结符，(VNVT)*1型文法型文法：对任一产生式，都有|，仅仅 S 除外 2型文法型文法：对任一产生式，都有VN，(VNVT)*3型文法型文法：任一产生式的形式都为 (1)AaB 或 Aa，其中AVN，BVN，aVT*(右线性文法)或 (2)ABa 或 Aa，其中AVN，BVN，aVT*(左线性文法)第33页，此课件共63页哦1 1型文法型文法：对任一产生式，都有|，仅仅 S除外上下文有关文法上下文有关文法：1A212(A在VN中，其他在V*中，

20、)2 2型文法型文法：对任一产生式，都有VN，(VNVT)*上下文无关文法上下文无关文法：A(A在VN中，在V*中，)3 3型文法型文法也叫正规文法第34页，此课件共63页哦例：1型（上下文有关）文法 文法GS：SaSBESaBEEBBEaBabbBbbbEbeeEee第35页，此课件共63页哦例：2型（上下文无关）文法 文法GS：SaB|bAAa|aS|bAABb|bS|aBB 例:3型文法 GS：S0A|1B|0A0A|1B|0SB1B|1|0第36页，此课件共63页哦四种文法之间的关系是将产生式做进一步限四种文法之间的关系是将产生式做进一步限制而定义的，他们之间的逐级制而定义的，他们之间

21、的逐级“包含包含”关系关系2型文法型文法1型文法型文法0型文法型文法3型文法型文法第37页，此课件共63页哦二、二、文文 法法 和和 语语 言言0型文法(PSG)产生的语言称为0型语言型语言1型文法或上下文有关文法（CSG）产生的语言称为1型语言型语言或上下文有关语言上下文有关语言（CSL）2型文法或上下文无关文法（CFG）产生的语言称为2型语言型语言或上下文无关语言上下文无关语言（CF L）3型文法或正则（正规）文法（RG）产生的语言称为3型语言型语言或正则（正规）语言正则（正规）语言（RL）第38页，此课件共63页哦第六节第六节 上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文

22、法有足够的能力描述现今程序设计语言的语法结构算术表达式语句赋值语句条件语句读语句第39页，此课件共63页哦算术表达式上下文无关文法表示：文法 G=(E,+,*,i,(,),P,E）P:E iE E+EE E*EE (E)条件语句上下文无关文法表示 if then|if then else 第40页，此课件共63页哦一、一、上下文无关文法的语法树上下文无关文法的语法树用于描述上下文无关文法的句型推导的直观方法设G=(VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树语法树(推导树)(派生树）：1.每个结点都有一个标记，此标记是V的一个符号2.根的标记是S3.若一结点n

23、至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4.如果结点n有标记A,其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式第41页，此课件共63页哦 例例:GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的语法树（推导树）的语法树（推导树）叶子结点叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结推导树的结果果。也把该推导树称为该句型的语法树语法树。第42页，此课件共63页哦推导过程中施用产生式的推导过程中施用产生式的顺序顺序 例例:

24、GS:SaASASbAASSSaAba S a A S S b A a a b a句型句型aabbaa的语法树（推导树）的语法树（推导树）S aAS aAa aSbAa aSbbaa aabbaaS aAS aSbAS aabAS aabbaS aabbaaS aAS aSbAS aSbAa aabAa aabbaa第43页，此课件共63页哦 最右（最左）推导最右（最左）推导最右（最左）推导最右（最左）推导：在推导的任何一步，其中、是句型，都是对中的最右（左）非终结符进行替换最右推导被称为规范推导规范推导规范推导规范推导。由规范推导所得的句型称为规范句型规范句型规范句型规范句型SaASaAaa

25、SbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa 例例:GS:SaASASbAASSSaAba第44页，此课件共63页哦一棵一棵语语法法树树表示了一个句型的种种可表示了一个句型的种种可能的能的(但未必是所有的但未必是所有的)不同推不同推导过导过程，包程，包括最左括最左(最右最右)推推导导。但是，一个句型是否只但是，一个句型是否只对应对应唯一的一唯一的一棵棵语语法法树树呢呢?一个句型是否只有唯一的一个最左一个句型是否只有唯一的一个最左(最最右右)推推导导呢呢?第45页，此课件共63页哦例：例：GE:GE:E i

26、E iE E+EE E+EE E*EE E*EE (E)E (E)E E E+E E+E E*E i E*E i i i i i E E E*E E*E i E+E i E+E i i i i句型句型 i*i+i 的两个不同的最左推导：的两个不同的最左推导：推导推导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问题：一个句型是否对应唯一的一棵语法树？问题：一个句型是否对应唯一的一棵语法树？第46页，此课件共63页哦二、二、二二 义义 文文 法法 若一个文法存在某个句子对应两棵不同的语法树，则称这个文法文法是二二义

27、义的。或者说，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法文法是二义二义的。文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G，其中G是二义的，但是却有L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。产生某上下文无关语言的每一个文法都是二义的，则称此语言语言是先天二先天二义义的。第47页，此课件共63页哦判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的。但可以为无二义性寻找一组充分条件。二义文法改造为无二义文法GE:E i GE：E T|E+T E E+E T F|T*F E E*E

28、 F （E）|i E (E)规定优先顺序和结合律对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。语句的分析是唯一的。第48页，此课件共63页哦第七节第七节 句句 型型 的的 分分 析析句型分析句型分析句型分析句型分析 就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分分析程序析程序析程序析程序或识别程序识别程序识别程序识别程序。分析算法又称识别算法识别算法识别算法识别算法。从左到右的分析算法从左到右的分析算法从左到右的分析算

29、法从左到右的分析算法，即总是从左到右地识别输入符号串，首先识别符号串中的最左符号，进而依次识别右边的一个符号。第49页，此课件共63页哦分析算法可分为：分析算法可分为：自上而下分析法自上而下分析法（推导）：（推导）：从文法的开始符号出发，反复使用各种从文法的开始符号出发，反复使用各种 产生式，寻找与输入符号匹配的推导。产生式，寻找与输入符号匹配的推导。（从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串）自下而上分析法自下而上分析法（归约）：（归约）：从输入符号串开始，逐步进行归约，直从输入符号串开始，逐步进行归约，直 至归约到文法的开始符号。至归约到文法的

30、开始符号。（从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树）两种方法反映了两种不同的语法树的构造过程两种方法反映了两种不同的语法树的构造过程第50页，此课件共63页哦一、一、自上而下的语法分析自上而下的语法分析例：文法 G：S cAd A ab A a识别输入串 w=cabd 是否为该文法的句子？SSScAdcAd a b推导过程：推导过程：S cAd cabd第51页，此课件共63页哦二、二、自下而上的语法分析自下而上的语法分析例：文法G：S cAd A ab A a识别输入串 w=cabd 是否该文法的句子SAA c a b d c a b d c a b d 归约过程：归约

31、过程：S cAd cabd第52页，此课件共63页哦自上而下的语法分析自上而下的语法分析(1)S cAd (2)A ab (3)A a 识别输入串识别输入串w=cad是否为该文法的是否为该文法的句子句子若S cAd 后选择(2)扩展A，S cAd cabd那将会？w的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配？宣告分析失败（其意味着，识别程序不能为串cad构造语法树，即cad不是句子）-显然是错误的结论。导致失败的原因是在分析中对A的选择不是正确的。S c A d a b 这时应该回朔回朔，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式（3）第5

32、3页，此课件共63页哦自下而上的语法分析自下而上的语法分析(1)S cAd (2)A ab (3)A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子对串cabd的分析中，如果不是选择ab用产生式(2),而是选择a用产生式(3)将a归约到了A，那么在cAbd中无法找到一个可归约串了，最终就达不到归约到S的结果，因而也无从知道cabd是一个句子c a b d c A b d a第54页，此课件共63页哦三、三、句型分析的有关问题句型分析的有关问题1）如何选择使用哪个产生式进行推导？）如何选择使用哪个产生式进行推导？在自上而下的分析方法中，假定要被代换的最左非终结符号是V，且

33、有n条规则：VA1|A2|An，那么如何确定用哪个右部去替代V？2）如何识别可归约的串？如何识别可归约的串？在自下而上的分析方法中，在分析程序工作的每一步，都是从当前串中选择一个子串，将它归约到某个非终结符号，该子串称为“可归约串”第55页，此课件共63页哦四、短语、直接短语、句柄的定义四、短语、直接短语、句柄的定义 文法 GS，是G的一个句型，如果：S A且 A 则称是句型相对于非终结符A的 短语短语短语短语。若有 A 则称是句型相对于规则A的直接直接直接直接短语短语短语短语（或（或简单短语简单短语简单短语简单短语）。一个句型的最左直接短语称为该句型的句柄句柄句柄句柄。*+第56页，此课件共

34、63页哦GEGE：EE+T|T TT*F|F F(E)|iEE+T|T TT*F|F F(E)|i句型：句型：i i1 1*i*i2 2+i+i3 3短语短语：i1,i2,i3,i1*i2,i1*i2+i3 直接短语直接短语：i1,i2,i3 句柄句柄：i1i3i2i1*FTFE+TEFT第57页，此课件共63页哦v 句型、短语和句柄句型、短语和句柄(1)每一句型都有一棵语法树，每个语法树的 叶组成一句型。(2)每棵子树的叶组成短语，每棵直接子树的 叶组成直接短语，最左直接子树的叶组成 句柄。第58页，此课件共63页哦五、有关文法实用中的一些说明五、有关文法实用中的一些说明 有关文法的实用限制

35、有关文法的实用限制 上下文无关文法中的上下文无关文法中的规则规则第59页，此课件共63页哦有关文法的实用限制有关文法的实用限制文法中不得含有有害规则和多余规则有害规则：形如UU的产生式。会引起文法的二义性。多余规则：指文法中任何句子的推导都不会用到的规则。1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达的。2）文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的。第60页，此课件共63页哦对于文法GS，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1）A必须在某句型中出现。2）必须能从A推出终结符号串t来。即 1）文法GS，对某两个符号串和：S A 2）A t,tVT*+第61页，此课件共63页哦化化 简简 文文 法法例：例：GS 1)SBe GS:SBe BAf AAe Ae 7)Df 6)CCf 2)BCe 3)BAf 4)AAe5)Ae第62页，此课件共63页哦具有形式A的规则称为规则规则，其中AVN某些著作和讲义中限制这种规则的出现。因为规则会使有关文法的一些讨论和证明变得复杂两种定义的唯一差别是句子在不在语言中。上下文无关文法中的上下文无关文法中的规则规则第63页，此课件共63页哦