前后文无关文法和语言 .ppt

《前后文无关文法和语言 .ppt》由会员分享，可在线阅读，更多相关《前后文无关文法和语言 .ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、前后文无关文法和语言 现在学习的是第1页，共67页重点：重点：本章中涉及的概念和术语的理解本章中涉及的概念和术语的理解文法和语言的形式定义文法和语言的形式定义难点：难点：短语和句柄的识别短语和句柄的识别二义性文法的判定二义性文法的判定现在学习的是第2页，共67页规定一种语言首先要规定它各种构造成分的形式，词规定一种语言首先要规定它各种构造成分的形式，词汇、句子等的构造规则及表示法。汇、句子等的构造规则及表示法。编译原理则应建立有关语言的数学化（形式化）编译原理则应建立有关语言的数学化（形式化）模型，以便对程序语言进行研究。模型，以便对程序语言进行研究。现在学习的是第3页，共67页定义定义1：相

2、当大的地区内公众所懂得并使用的相当大的地区内公众所懂得并使用的“话话”，以及组成这，以及组成这些些“话话”的方法的统一体。的方法的统一体。 缺点：不够形式化和精确化缺点：不够形式化和精确化定义定义2：某一个字母表上的符号串的（句子）的集合。某一个字母表上的符号串的（句子）的集合。 缺点：缺乏语言句子的结构性组成描述，缺点：缺乏语言句子的结构性组成描述， 缺乏判断任一符缺乏判断任一符号串是否为合法句子判断机制。号串是否为合法句子判断机制。因此，如果能刻画一个语言句子，就定义了该语言。因此，如果能刻画一个语言句子，就定义了该语言。现在学习的是第4页，共67页1956年，年，chomsky建立建立文

3、法文法的数学模型，对形式的数学模型，对形式化语言和自动机理论的研究取得较大的成果。化语言和自动机理论的研究取得较大的成果。1960年。年。P.Nuaur和和J.Boukas首先用首先用BNF成功对成功对ALGOL语言的文法进行了描述，虽然对语义形式化语言的文法进行了描述，虽然对语义形式化描述不理想，但在程序设计语言的语法描述上有足够描述不理想，但在程序设计语言的语法描述上有足够的能力。的能力。 至此，程序语言就有了形式化表述。至此，程序语言就有了形式化表述。现在学习的是第5页，共67页枚举枚举（句子有限）（句子有限）例：例：L=We are learning computer science,

4、it is interesting数学表示数学表示(句子无限句子无限)例例:1,1/2,1/3,1/n1/n|nN 制定有限条规则，用来产生所需描述语言中的句子全部，这些规制定有限条规则，用来产生所需描述语言中的句子全部，这些规则即则即文法。文法。建立一种算法能对于任给的符号串，判别是否为给定语言的合法句子建立一种算法能对于任给的符号串，判别是否为给定语言的合法句子。现在学习的是第6页，共67页现在学习的是第7页，共67页 “我是大学生” 是汉语的一个句子。句子句子 =主语谓语主语谓语主语主语 =代词名词代词名词代词代词 =我我你你他他名词名词 =王明王明大学生大学生工人工人英语英语谓语谓语

5、=动词直接宾语动词直接宾语动词动词 =是是学习学习直接宾语直接宾语 =代词名词代词名词 返回现在学习的是第8页，共67页 =左端的规则由左端的规则由 =右端的符号串代替：右端的符号串代替：句子句子 主语主语谓语谓语 代词代词谓语谓语 我我谓语谓语 我我动词动词直接宾语直接宾语 我是我是直接宾语直接宾语 我是我是名词名词 我是大学生我是大学生 按照如下方式用它们导出句子：现在学习的是第9页，共67页大学生句子主语 谓语代词动词直接宾语名词我是“我大学生是”是否为?现在学习的是第10页，共67页sentence subject This | Computers | Iverb-phrase | a

6、dverb neververb is | run | am | tellobject the | a | noun university | world | cheese | liesThis is a university.Computers run the world.I am the cheese.I never tell lies.英语句子英语句子现在学习的是第11页，共67页表示一个语法单位；表示一个语法单位； =（ ）表示）表示“定义为定义为”； | 表示为表示为“或或” 。描述语言的形式结构的规则。描述语言的形式结构的规则。 产生式，产生式， 产生式左部，产生式左部， 产生式右部

7、产生式右部现在学习的是第12页，共67页仅出现在产生式右部的符号仅出现在产生式右部的符号 VT；至少在产生式左部出现过一次的符号至少在产生式左部出现过一次的符号VN；特殊的非终结符，表示了定义语言中最特殊的非终结符，表示了定义语言中最感兴趣的语法范畴。感兴趣的语法范畴。 S；P G=VT，VN，S，P 例如例如 现在学习的是第13页，共67页q VN，VT和P是 非空有穷集；q VN和VT不含公共的元素，即VN VT = ；q 用V表示VNVT，称文法G的字母表或字汇表；q 产生式是形如或 =的（ ，）有序对，其中是字母表V的一个非空符号串(V+)，是V中的一个符号串，可为空串(V*)。 称为

8、产生式左部， 称作产生式右部。 现在学习的是第14页，共67页句子句子 主语主语谓语谓语 代词代词谓语谓语 我我谓语谓语 现在学习的是第15页，共67页l 文法的作用就是用有限条规则产生无限多句子。l 某一文法产生的全部句子所组成的集合 该文法产生的语言。现在学习的是第16页，共67页1、符号：符号：可以相互区别的记号（元素）。可以相互区别的记号（元素）。2、字母表字母表 ：符号（元素）的非空有穷集合。符号（元素）的非空有穷集合。3、符号串：符号串：由字母表由字母表 中的符号组成的任何有穷序列。中的符号组成的任何有穷序列。(没有符号的符号串没有符号的符号串)是是 上的符号串。上的符号串。n若若

9、x是是 上的符号串，上的符号串，a是是 的元素，则的元素，则xa是是 上的符号串。上的符号串。n y是是 上的符号串，当且仅当它可以由上的符号串，当且仅当它可以由1和和2导出。导出。 例如：例如： =a,b ，a，b，aa，ab，aabba都是都是 上的符号串上的符号串现在学习的是第17页，共67页4、符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串。 如： b是符号串banana的一个前缀. banana是 banana前缀。 5、符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串。 如: nana是符号串banana的一个后缀. banana是 b

10、anana后缀。 现在学习的是第18页，共67页6、符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。 如:ana是符号串banana的一个子串。7、符号串s的真前缀，真后缀，真子串：任何非空符号串 x，是s的前缀，后缀或子串，并且 s x。8、符号串的长度：符号串中符号的个数。符号串s的长度记为|s|。 的长度为0。 对于每个符号串s，s和两者都是符号串s的前缀，后缀和子串。现在学习的是第19页，共67页1、连接：连接：符号串符号串x、y的连接，是把的连接，是把y的符号写在的符号写在x的符号之后得的符号之后得到的符号串到的符号串xy。 如：如： x=ba,y=ck 则则 xy=bac

11、k 有有a = a 2、方幂：方幂：符号串自身连接符号串自身连接n次得到的符号串。次得到的符号串。 an 定义为定义为 aaaa n个个a a1=a, a2=aa a0=现在学习的是第20页，共67页 若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。 1、符号串集合乘积：两个符号串集合A和B的乘积定义为 AB =xy|xA且yB 例如：若 集合A=ab，cde B = 0，1 则 AB =ab1，ab0，cde0，cde12、的闭包：上的一切符号串（包括）组成的集合。记为.2*现在学习的是第21页，共67页.32*3、的正闭包：上的除外的所有符号串组成的集合。记为例：=

12、a,b ，求*和。*=,a,b,aa,ab,ba,bb,aaa,aab,+=a,b,aa,ab,ba,bb,aaa,aab,现在学习的是第22页，共67页现在学习的是第23页，共67页1、语言：由组成的集合，为一符号串集合。即：字母表上的一个语言是上的一些符号串的集合，是*的一个子集。 L=S|S* 、都是语言例如：字母表=a,b 集合 w|w*且w=anbn,n1为上的一个语言。 集合 w|w*且w=an,n1 为上的一个语言。现在学习的是第24页，共67页2、语言“并”运算：语言L和M的并为 LM，是一个语言: w|w is in L or is in M如： L1 =a,b,y,z ，M

13、1 =1,28,9 L1M1=a,b, y,z，1,28,9 设L是（上的）一个语言，M是（上的）一个语言， 语言L和M的“并”，“交”，“差”，“连接”运算结果是一个语言。现在学习的是第25页，共67页3、语言L和M的连接运算：记为 LM(可简记为LM)。 LM=st |sL且 tM 如： L =a,b,y,z ，M =1,28,9 LM =a1,b1,y1,z1,a2,b2a9z9 特别的：有L = L=L。 L的n次连接Ln= LL.L现在学习的是第26页，共67页4、语言L的 闭包：记为 L*， L*= L0 L1 L2 . L0= ， Ln= L Ln-1=Ln-1 L(n1)5、语

14、言L的正 闭包：记为 L+， L+= L1 L2 L3 . L+= LL*= L*L L*= L+ 如： L1 =a,b,y,z M1 =1,28,9 （L1M1）=a,b, y,z，1,28,9 （L1M1）*=a,b, y,z，1,28,9,aa,1a,xyz, 6789st. L1（L1M1）*=所有字母打头的字母和数字符号串现在学习的是第27页，共67页练习1：L=A,B,C,Z,a,b,cz D=0,1,2,3,4,5,6,7,8,9计算：LD， LD， L4 ， L*， L(L D)*， D+练习2：考虑一个文法G1: SbA AaA|a 它定义了一个什么语言呢？从开始符S出发，我

15、们可以推出如下句子： SbA ba SbA baA baa SbA baA baaa可以写为：L(G1)=ban|n1现在学习的是第28页，共67页一个一个上下文无关文法上下文无关文法G定义为四元组定义为四元组(VN，VT，P，S )其中：其中：非终结符号非终结符号(或语法实体，或变量或语法实体，或变量)集；集；终结符号集；终结符号集；产产生式生式(也称规则也称规则)的集合；的集合； A 其中，其中， (VN VT )* ， A VN VN，VT和和P是是 非空有穷集。非空有穷集。 称作识别符号或开始符号的一个非终结符，它至少要在一条产生称作识别符号或开始符号的一个非终结符，它至少要在一条产生

16、式中作为左部出现。式中作为左部出现。S VN VN和和VT不含公共的元素，即不含公共的元素，即VN VT = 用用V表示表示VN VT ，称为文法，称为文法G的字母表或字汇表的字母表或字汇表现在学习的是第29页，共67页例例 文法文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号为开始符号对此产生式可进行推导产生句子。对此产生式可进行推导产生句子。现在学习的是第30页，共67页l直接推导直接推导“” 是文法是文法G G的产生式，若有的产生式，若有v,wv,w满足：满足：v=,w= , v=,w= , 其中其中VV* *,V,V* * 则称

17、则称v v到到w,w,记作记作 v v w w； 也称也称w w到到v v例：例：G G： S0S1， S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S1现在学习的是第31页，共67页例：例：G G： S0S1， S01 S 0S1 00S11 000S111 00001111*S S 00S11 00S11S 00001111 推导长度为4 若存在v =w0 w1 . wn=w (n0) 则记为v w，称作v推导出w，或w归约到v 若有v w 或 v=w， 则记为v w*l 推导的长度（长度为n的推导）现在学习的是第32页，共67页例：例：G

18、： S0S1， S01S 0S1 00S11 000S111 00001111G的句型的句型 S，0S1，00S11，000S111，00001111G的句子的句子 00001111，01*l 句型 有文法GS，若S x， xV*，则称x是文法G的句型。l 句子 有文法GS，若S x，且xVT*，则称x是文法G的句子。*现在学习的是第33页，共67页例：例：GE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|a判断：判断：a+aa+a* *a a是否为该文法的句子是否为该文法的句子EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+

19、a*a句子：用符号a，+，*，(和)构成的算术表达式现在学习的是第34页，共67页语言中的每个句子可以由上下文无关文法的开始符号产生。例：G=（0，1，S，S，P） P: S0S1， S01 L(G)=0n1n|n1*L(G)=x|S x，S为文法的开始符号，且x VT*现在学习的是第35页，共67页q G生成的每个串都在L(G)中，L(G)中的每个串确实能被G生成。q 文法所产生的语言L(G)是无限语言，原因是所定义的文法中含有递归。现在学习的是第36页，共67页l递归、直接递归：递归、直接递归：如果文法中有形如如果文法中有形如AAA的产生式，其中的产生式，其中，不同时为不同时为，则称产生式

20、，则称产生式A 是直接递归。是直接递归。例：GE： EE+T|T TT*F|F F(E)|aA A，直接递归A A，递归 A 称为递归和直接递归的非终结符号*若存在 A A,则称A 是递归的。l 左递归、右递归 =， 左递归 ，= 右递归现在学习的是第37页，共67页 直接递归是递归的一种特殊情况，如果一个语言是无限的，则定义此语法的文法必然是递归的。 例：语言例：语言L=anbbn| n 1, 写出产生写出产生L的文法。的文法。 GS: S aAb A aAb|b现在学习的是第38页，共67页q 从语法定义的角度，递归定义是一种较好的方从语法定义的角度，递归定义是一种较好的方式，因为它不仅使

21、文法形式简练，而且也给无限式，因为它不仅使文法形式简练，而且也给无限语言的有限表示提供了一种有效的方法。语言的有限表示提供了一种有效的方法。q 然而左递归会影响某些语法分析方法实现，因然而左递归会影响某些语法分析方法实现，因此有时需要对文法进行等价改造，以便消除其中此有时需要对文法进行等价改造，以便消除其中的左递归。的左递归。现在学习的是第39页，共67页l 若若L（G1）=L（G2），则称文法），则称文法G1和和G2是是等价的。等价的。如文法如文法G G1AA：A0R A0R 与与G G2SS：S0S1 S0S1 等价等价 A01 S01A01 S01 RA1 RA1现在学习的是第40页，共

22、67页现在学习的是第41页，共67页例：例：GE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|a E判定a+a*a是否为文法的句子？E+T T+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a现在学习的是第42页，共67页GE E：EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|a 对句型T+a+T的推导：E E+T T*F+T T*a+T 现在学习的是第43页，共67页q 问题：对于推导中的每一步，S X,如果X 1| 2| 3| k，（，）V*，XVN，则面临选哪一个i去匹配当前串的问题。使用不当易引起回溯。l

23、自顶向下分析方法自顶向下分析方法 从文法的从文法的开始符号开始符号出发，反复使用出发，反复使用文法的产生式文法的产生式，寻找，寻找与与输入符号串输入符号串匹配匹配的的推导推导。例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子SSScAdcAd a b推导过程：S cAd cAd cabd现在学习的是第44页，共67页l自底向上分析方法自底向上分析方法 从从输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，直至，直至归约归约到到文法文法的的开始符号开始符号。例：文法例：文法G： S cAd A ab A a识别输入串识别输

24、入串w=cabd是否该文法的是否该文法的句子句子SAA c a b d c a b d c a b d 归约过程构造的推导： cAd cabd S cAd现在学习的是第45页，共67页现在学习的是第46页，共67页l语法树：语法树：设设G=( VN,VT,P,S)为一为一cfg，若一棵树满足下列，若一棵树满足下列4个个条件，则此树称作条件，则此树称作G的语法树：的语法树：q 每个结点都有一个标记，此标记是每个结点都有一个标记，此标记是V的一个符号；的一个符号；q 根的标记是根的标记是Sq 若某结点至少有一个子孙，并且该结点标记为若某结点至少有一个子孙，并且该结点标记为A，则，则AVVN N；q

25、 若某结点标记若某结点标记A，其直接子孙结点从左到右的次序是，其直接子孙结点从左到右的次序是n1，n2，nk，其标记分别为，其标记分别为A1，A2，Ak，那么，那么AA1A2，Ak定是定是P中的一个产生式中的一个产生式现在学习的是第47页，共67页语法树-句型推导的直观表示给定上下文无关文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之相关的语法树(推导树)n 定理：G为上下文无关文法，对于 ，有S =* ，当且仅当 文法G有以为结果的一棵语法树(推导树)现在学习的是第48页，共67页 例: GS:SaASASbAASSSaAba句子aabbaa的语法树（推导树）叶子结点：树中没有子

26、孙的结点。SaASSbAaaba现在学习的是第49页，共67页 推导过程中使用产生式的推导过程中使用产生式的顺序顺序 例: GS:SaASASbA|SS|baSaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa S a A S S b A a a b a现在学习的是第50页，共67页 一棵语法树可表示一个句子的多种可能的不同推导过程，包括最左(最右)推导。 一个句子是否只对应唯一的一棵语法树? 一个句子是否只有唯一的一个最左(最右)推导?现在学习的是第51页，共67页例：例：GE:GE:E i

27、E iE E+EE E+EE EE E* *E EE (E)E (E)句型 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 E E + E E * E i i i E E * E i E + E i i现在学习的是第52页，共67页l 二义性文法二义性文法q 若一个文法存在某个句子对应两棵不同的语法树，则称这个文法若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是是二义二义的。的。q 若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文若一个文法存在某个

28、句子有两个不同的最左（右）推导，则称这个文法是法是二义二义的的 注意：注意： 判定任给的一个上下文无关文法是否二义，或它是否产判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件。的，但可以为无二义性寻找一组充分条件。现在学习的是第53页，共67页 一个文法兼有左右递归是导致二义性的最常见原因。二义文法改造为无二义文法 GE: E i GE：E T|E+T E E+E T F|T*F E E*E F （E）|i E (E)改写文法，消除同时存在的左右递归。

29、现在学习的是第54页，共67页*S A且 A ，则称是句型相对于非终结符A的短语对于文法GS：n n 若有A ，则称是句型相对于非终结符A 的直接短语n 一个句型的最左直接短语称为该句型的句柄现在学习的是第55页，共67页i*i+i 的短语、直接短语和句柄 E E + T T FT * F i3 短语短语：i1* * i2+ + i3， i1* * i2 ，F i2 i1 ， i2 ， i3 。 i1 直接短语直接短语： i1 ， i2 ， i3 。句柄句柄：i1 例 ： GE： EE+T|T TT*F|F F(E)|i句型：i*i+i现在学习的是第56页，共67页GS:SaAS SaASbA

30、ASSAba句子aabbaa的最左推导，指出此句子的全部短语、各步直接推导所得句型的句柄、该句子的句柄 S1 a1 A1 S3 S2 b1 A2 a2 a3 b2 a4现在学习的是第57页，共67页通过对产生式施加不同限制通过对产生式施加不同限制，Chomsky将文法分为四类：将文法分为四类：l0型文法：型文法：对任一产生式对任一产生式，有，有V+，V*;l1型文法：型文法：对任一产生式对任一产生式，有，有| (, V+)， 仅仅 S除外。除外。 或者形如或者形如A 产生式产生式, AVN ,V+, ,V*l2型文法：型文法：对任一产生式对任一产生式A，都有，都有AVN V*;l3型文法：型文

31、法：任一产生式的形式都为任一产生式的形式都为AB或或A (右线性右线性)， AB或或A（左线性）其中（左线性）其中AVN ，BVN ，aV VT T + +现在学习的是第58页，共67页四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系0型文法1型文法2型文法3型文法现在学习的是第59页，共67页A hierarchy of grammarsType 0: free or unrestricted grammars These are the most general. Productions are of the form u v where both u and v are arbi

32、trary strings of symbols in V, with u non-null. There are no restrictions on what appears on the left or right-hand side other than the left-hand side must be non-empty.Type 1: context-sensitive grammars Productions are of the form uXw uvw where u , v and w are arbitrary strings of symbols in V, wit

33、h v non-null, and X a single nonterminal. In other words, X may be replaced by v but only when it is surrounded by u and w . 现在学习的是第60页，共67页Type 2: context-free grammars Productions are of the form X v where v is an arbitrary string of symbols in V, and X is a single nonterminal. Wherever you find X

34、, you can replace with v (regardless of context).Type 3: regular grammars Productions are of the form X a or X aY where X and Y are nonterminals and a is a terminal. That is the left-hand side must be a single nonterminal and the right-hand side can be either a single terminal by itself or with a si

35、ngle nonterminal. These grammars are the most limited in terms of expressive power.现在学习的是第61页，共67页例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS： SCDSCDAbbAAbbA CaCA CaCABaaBBaaB CbCB CbCBBbbBBbbBADaDADaD Ca CaBDbDBDbD Db DbAabDAabD现在学习的是第62页，共67页例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|13 3型文

36、法型文法GS： S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0现在学习的是第63页，共67页0型文法产生的语言称为型文法产生的语言称为0型语言型语言(递归可枚举语言递归可枚举语言)；1型文法或上下文有关文法（型文法或上下文有关文法（ CSG ）产生的语言称为）产生的语言称为1型语言型语言(上下文有关上下文有关语言（语言（CSL）)2型文法或上下文无关文法（型文法或上下文无关文法（ CFG ）产生的语言称为）产生的语言称为2型语言型语言(上下文上下文无关语言（无关语言（ CF L ）) 上下文无关文法有足够的能力描述程序设计语言的语法结构。上下文无关文

37、法有足够的能力描述程序设计语言的语法结构。3型文法或正则（正规）文法（型文法或正则（正规）文法（ RG ）产生的语言称为）产生的语言称为3型语言正则（正规）型语言正则（正规）语言（语言（ RL ） 3型文法常用来描述程序设计语言的单词结构，且型文法常用来描述程序设计语言的单词结构，且3型文法所描述语言可用型文法所描述语言可用有限自动机识别。有限自动机识别。现在学习的是第64页，共67页l1、名词解释：、名词解释： 文法、语言、句子、句柄、推导。文法、语言、句子、句柄、推导。l2、下述文法、下述文法G是二义的吗？为什么？是二义的吗？为什么？ i|() | + +| |- -| |* *| |/

38、/l3、考虑下面上下文无关文法：、考虑下面上下文无关文法：SSS*|SS+|a 为为aa+a* *该串构造推导树。该串构造推导树。l4 4、文法、文法GN为：为：N D|DN D 0|1|2|3|4|5|6|7|8|9 试问：试问：GN产生的语言是什么？产生的语言是什么？ 现在学习的是第65页，共67页l5、令文法、令文法GE为：为： E T|E+T|E-T TF|T*F|T/F F(E)|i证明证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语是它的一个句型，指出这个句型的所有短语、直接短语和句柄。和句柄。l6、一个上下文无关文法生成句子、一个上下文无关文法生成句子abbaa的推

39、导树如图：的推导树如图：(1)给出该句子最左推导、最右推导。给出该句子最左推导、最右推导。(2) 该文法的产生式集该文法的产生式集P有哪些元素？有哪些元素？(3) 找出该句子的所有短语、找出该句子的所有短语、 直接短语、句柄。直接短语、句柄。SABSaSBBAabba现在学习的是第66页，共67页l7、试构造语言、试构造语言L=anbnci | n=1, i=0的文法。的文法。 解解： G(Z): Z AB A aAb|ab B cB| l8、给出生成语言、给出生成语言anbnambm|n，m0的上下文无关文法的上下文无关文法 解解：GS：SAB AaAb | BaBb |l9、试写一文法，使其描述的语言、试写一文法，使其描述的语言L(G) 是能被是能被5整除的整数集合。整除的整数集合。 解：解：G(Z): Z (+|- )A(0|5) A 0|1|2|3|4|5|6|7|8|9|AA现在学习的是第67页，共67页