《编译原理 文法和语言》由会员分享，可在线阅读，更多相关《编译原理 文法和语言（59页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章文法和语言文法和语言 语言是一个记号系统，完整的定义包括语法和语语言是一个记号系统，完整的定义包括语法和语义两方面。语法是一组规则，用它可以形成和产义两方面。语法是一组规则，用它可以形成和产生一个合适的程序。文法就是阐明语法的一个重生一个合适的程序。文法就是阐明语法的一个重要的要的形式形式工具。语义包括静态语义和动态语义，工具。语义包括静态语义和动态语义，阐明语义要比语法困难的多。阐明语义要比语法困难的多。 本章主要讨论文法和语言的概念，上下文无关文本章主要讨论文法和语言的概念，上下文无关文法及其句型的分析。法及其句型的分析。1本章内容本章内容 3.1 文法的直观概念文法的直观概念
2、3.2 符号和符号串符号和符号串3.3 文法和语言的形式定义文法和语言的形式定义3.4 文法的类型文法的类型3.5 上下文无关文法及其语法树上下文无关文法及其语法树3.6 句型的分析句型的分析3.7 有关文法实用中的一些说明有关文法实用中的一些说明3.8 典型例题及解答典型例题及解答23.1 文法的直观概念文法的直观概念n 如何来描述一种语言？如果语言是有穷的(只含有有穷多个句子)，可以将句子逐一列出来表示；如果语言是无穷的，语言的有穷表示有两个途经:生成方式(文法):语言中的每个句子可以用严格定义的规则来构造。识别方式(自动机):用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就
3、会停止并回答“是”，若不属于，要么能停止并回答“不是”，要么永远继续下去。n参见课本句子组成的实例。33.2 符号和符号串符号和符号串1、字母表字母表是符号的非空有穷集合。任何程序语言都有自己的字母表，例如: 1.计算机语言：由符号“0”和“1”组成的字母表, =0，1 2. ASCII字符集； 3. Pascal字母表为： =AZ, az, 09, +, -, *, /, ,:, , ; ，.， , (, ), , , , 43.2 符号和符号串符号和符号串2、符号串一. 符号串的定义(1)是上的一个符号串。(2)若x是上的符号串，而a是的元素,则xa是 上的符号串。(3)y是上的符号串,当
4、且仅当它由(1)和(2)导出。由字母表中的符号所组成的的任何有穷序列被称之为该字母表上的符号串,也称作字。53.2 符号和符号串符号和符号串二 术语 设s是符号串前缀: 移走s的尾部的零个或多于零个符号后缀: 删去s的头部的零个或多于零个符号子串: 从s中删去一个前缀和一个后缀子序列: 从s中删去零个或多于零个符号(这些符号不要求是连续的）逆转: 将s中的符号按相反次序写出而得到的符号串。长度: 是该符号串中的符号的数目。例|aab|=3,|=0。6例 ：符号串s=banana前缀：,b,ba,ban,bana,banan,banana后缀：banana,anana,nana,ana,na,a
5、, 子串: banana,anana,banan,anan, 真前缀，真后缀，真子串: xsx 子序列: baa(这些符号不要求是连续的）逆转：ananab长度：banana=63.2 符号和符号串符号和符号串7三、符号串的运算1.连接：设x和y是符号串，它们的连接 xy是把y的符号写在x的符号之后得到的符号串。例如，x=ba,y=nana,xy=banana.2.方幂：x0=; x1=x; x2=xx; ; xn=xn-1x; 例: x=ba 则 x1= ba; x2=baba; x3=bababa;3.2 符号和符号串符号和符号串8四. 符号串集合(语言）的运算 设L和M是两个符号串集合，
6、则 1.合并：LMs|sL or sM 2.连接：LM st|sL and tM 3.方幂： L0=， L1L， L2LL, ., LnLn-1L 4. 语言L的闭包，记作L*， L*Li(i=0) =L0L1L2L3 5语言L的正闭包，记作L+（L+L L*） L+Li(i =1) =L1L2L3L43.2 符号和符号串符号和符号串9 例如：L=AZ,az D=09 1LD=AZ,az ,09 2LD是由所有用一个字母后跟一个数字组成的符号串所构成的集合。 3L4是由所有的四个字母的符号串构的集合。 4L（LD)* 是由所有的字母打头的字母和数字组成的符号串所构成的集合. 5D+是由所有的长
7、度大于等于1的数字串所构成的集合.3.2 符号和符号串符号和符号串10文法的定义文法的定义推导的概念推导的概念句型、句子和语言的定义句型、句子和语言的定义3. 3 文法和语言的形式定义文法和语言的形式定义11文法定义 文法文法G G 定义为四元组(VN，VT，P，S)，其中VN :非终结符号集；VT :终结符号集；P: 规则的集合；并且VN，VT和P是非空有穷集。S:称作开始符(识别符)，是一个非终结符，它至少要在一条产生式中作为左部出现。 注：注：VN和VT不含公共的元素，即VN VT = ，用V表示VN VT ，称为文法G的字母表规则规则(重写规则重写规则、产生式产生式或生成式生成式)，是
8、形如的(,)有序对,其中是字母表V的正闭包V+中的一个符号，是V*中的一个符号。 称为规则的左部， 称作规则的右部。12文法的定义文法的定义例例: 文法文法G=（VN，VT，P，S）VN = S , VT = 0, 1 P= S0S1, S01 S为开始符号为开始符号13例例: 文法文法G=（VN，VT，P，S）VN =标识符，字母，数字标识符，字母，数字VT =a,b,c,x,y,z,0,1,9P= a zz 00 99 S=14元符号元符号: : | | 一般不用将文法G的四元组显式的写出来，只写出产生式即可，并约定第一条产生式的左部为识别符。习惯上大写字母表示非终结符，小写字母表示终结符
9、，有时也将G写为GS(1) G(1) G：S SaaA Ab A Aabab A AaaA Ab A A (2) GS(2) GS：A Aabab A AaaA Ab A A S SaaS Sb (3) GS: (3) GS: A Aabab| |a aA Ab| | S SaaS Sb文法的写法文法的写法15推导的定义推导的定义直接推导直接推导“” 是文法G的产生式,若有v,w满足v=v=,w=,w=,其中V*,V*,则称v直接推导到w,记作 v w 也称w直接归约到v例：G：S0S1，S01 0S1 00S11 00S11 000S111 000S111 00001111 S 0S116推
10、导的定义推导的定义例：. ( . ). . ( ) VAR;BEGIN READ()END. VAR A;BEGIN READ( ) END. ( A)VAR A;BEGIN READ( ) END. VAR A;BEGIN READ( A) END. ( A)17推导的定义推导的定义若存在若存在v=w0w1.wn=w,(n0)则记为则记为v +w，称作称作v推导出推导出w，或，或w归约到归约到v若有若有v=+w或或v=w，则记为则记为v=*w18例：例：G G： S0S1， S010S100S1100S11000S111000S11100001111S 0S100S11000S1110000
11、1111S =+ 00001111 S =* S 00S11 =* 00S1119句型、句子的定义句型、句子的定义句型句型有文法G，若S =*x，则称x是文法G的句型。句子句子有文法G，若S =*x，且xVT*，则称x是文法G的句子。例：例：G G：S0S1， S01S 0S1 00S11 000S111 00001111G的句型S,0S1 ,00S11 ,000S111,00001111G的句子00001111, 0120句型、句子句型、句子例：例：GE E： EE+T|TEE+T|T TT*F|F TT*F|F FF(E)|a(E)|aE EE+TT+TF+Ta+Ta+T*Fa+F*Fa+
12、a*Fa+a*a句子：用符号句子：用符号a，+，*，(和和)构成的算术表达式构成的算术表达式21(文法生成的文法生成的)语言的定义语言的定义 由文法由文法G生成的语言记为生成的语言记为L(G),它是文法它是文法G的一切句子的集的一切句子的集合合: L(G)=x|S =* x,其中其中S为文法的开始符号为文法的开始符号,x VVT T* * 例：G: S0S1， S01 L(G)=0n1n|n122例例 文法文法GS：（1）SaSBE（2）SaBE（3）EBBE（4）aBab（5）bBbb（6）bEbe（7）eEeeL(G)= anbnen | n1 G生成的每个串都在生成的每个串都在L(G)中
13、中L(G)中的每个串确实能被中的每个串确实能被G生成生成 分析参见课本分析参见课本P37.P37.23文法的等价文法的等价若若L(G1)=L(G2)，则称文法，则称文法G1和和G2是等价的。是等价的。 例：文法例：文法G G1AA：A0R A0R 与与 G G2SS：S0S1 S0S1 等价等价 A01 S01 A01 S01 RA1 RA1 243.4 文法的类型文法的类型通过对产生式施加不同的限制，文法可分为以下四类：u0型文法型文法：对任一产生式，都有(VNVT)+， (VNVT)*。 0型文法的能力相当于图灵机，可以表征任何递归可枚举集，且任何0型语言都是递归可枚举的。0型文法描述的语
14、言为0型语言，用L0表示。例如 ： aSbcAd253.4 文法的类型文法的类型u 1型文法：对任一产生式，都有|， 仅仅 S除外。1型文法又称作上下文有关文法（context-sensitive)： 其产生式的形式为1A212，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。该文法描述的语言为1型语言或上下文有关语言,用L1表示。 例如：aUbaABBaab 263.4 文法的类型文法的类型u 2型文法：对任一产生式,都有VN , (VNVT)*2型文法又称作上下文无关文法（context-free)： 该文法相当于对1型文法中的规则形式加以限制，即要求1和2必须
15、为空。2型文法描述的语言为2型语言或上下文无关语言，用L2表示。其识别系统是不确定的下推自动机。273.4 文法的类型文法的类型例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|128u 3型文法：任一产生式的形式都为AaB或Aa，其中AVN ，BVN ，aVT*3型文法又叫正规文法，产生的语言为3型语言（正规语言），是有穷自动机所接受的集合。高级程序设计语言的单词符号，如标识符、无符号整数等都是采用3型文法来描述的。3.4 文法的类型文法的类型293.4 文法的类型文法的类型GS： S0A|1B|00A|1B|0A0A|1B|0
16、S0A|1B|0SB1B|1|01B|1|0GI： I lTlTI l lT lTlTT dTdTT l lT d d例：例： 3型文法型文法303.4 文法的类型文法的类型2型文法型文法1型文法型文法0型文法型文法四类四类文法文法之间之间的的逐级逐级“包含包含”关系关系3型文法型文法313.5上下文无关文法及其语法树上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的语法结构上下文无关文法有足够的能力描述程序设计语言的语法结构实例参见课本实例参见课本P39-40 例例3.6（描述表达式及各种语句）（描述表达式及各种语句）语法树：是描述上下文无关文法语法树：是描述上下文无关文法
17、句型推导句型推导的的直观工具。直观工具。32n语法树的定义语法树的定义 设G=( VN,VT,P,S)为一上下文无关文法，若一棵树满足下列4个条件，则此树为G的语法树(推导树)(派生树）1. 每个结点都有一个标记，此标记是V的一个符号2. 根的标记是S3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4. 如果结点n的直接子孙从左到右依次为n1，n2，nk，并且标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式3.5上下文无关文法及其语法树上下文无关文法及其语法树33n语法树的结果语法树的结果： 从左到右读出叶子的标记而构成的符号串即为语法树的结果3.5
18、上下文无关文法及其语法树上下文无关文法及其语法树构造句型构造句型aabbaa的的语法树语法树SaASSbAaaba例例:GS:1)SaAS2)ASbA3)ASS4)Sa5)Aba34句型句型aabbaa的可能的可能推导推导序列序列例例:GS:1)SaAS2)ASbA3)ASS4)Sa5)AbaSaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa3.5上下文无关文法及其语法树上下文无关文法及其语法树35n规范推导、规范句型：规范推导、规范句型：最左（最右）推导最左（最右）推导：在推导的任何一步，其中
19、，是句型，都是对中的最左（右）非终结符进行替换最右推导被称为规范推导规范推导。由规范推导所得的句型称为规规范句型范句型n给定文法给定文法G=(VN,VT,P,S)，对于对于G的任何句型都能构造与的任何句型都能构造与之关联的语法树之关联的语法树(推导树推导树)定理：定理：G为上下文无关文法，对于，有S =* ，当且仅当文法G有以为结果的一棵语法树(推导树)3.5上下文无关文法及其语法树上下文无关文法及其语法树36一棵一棵语语法法树树表示了一个句型的种种可能的表示了一个句型的种种可能的( (但未必是但未必是所有的所有的) )推推导过导过程，包括最左程，包括最左( (最右最右) )推推导导。一个句型
20、是否只一个句型是否只对应对应唯一的一棵唯一的一棵语语法法树树呢呢? ?一个句型是否只有唯一的一个最左一个句型是否只有唯一的一个最左( (最右最右) )推推导导呢呢? ?3.5上下文无关文法及其语法树上下文无关文法及其语法树37例：例：GE:GE:E E i 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+ii*i+i 有两种不同的最左推导：有两种不同的最左推导：推导推导1：EE+EE*E+Ei*E+Ei*
21、i+Ei*i+i推导推导2：EE*Ei*Ei*E+Ei*i+Ei*i+i3.5上下文无关文法及其语法树上下文无关文法及其语法树38若一个文法存在某个句子对应两棵不同的语法树，则称这若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是个文法是二义二义的的或者，若一个文法存在某个句子有两个不同的最左（右）或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是推导，则称这个文法是二义二义的的判定任给的一个上下文无关文法是否二义，或它是否产生判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可一个先天二义的上下文无关语言，这两个问题
22、是递归不可解的，但可以为无二义性寻找一组充分条件解的，但可以为无二义性寻找一组充分条件 n 文法的二义性和语言的二义性文法的二义性和语言的二义性3.5上下文无关文法及其语法树上下文无关文法及其语法树39文法的二义性和语言的二义性是不同的概念。因为可能有文法的二义性和语言的二义性是不同的概念。因为可能有两个不同的文法两个不同的文法G G和和G,G,其中其中G G是二义的是二义的, ,但有但有L(G)=L(G)L(G)=L(G)，也就是说，这两个文法所产生的语言是相同的。也就是说，这两个文法所产生的语言是相同的。如果产生上下文无关语言的每一个文法都是二义的，则说如果产生上下文无关语言的每一个文法都
23、是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。析是唯一的。 n 文法的二义性和语言的二义性文法的二义性和语言的二义性3.5上下文无关文法及其语法树上下文无关文法及其语法树40GE: E GE: E i i E E+E E E+E E E*E E E*E E (E) E (E) n 文法的二义性和语言的二义性文法的二义性和语言的二义性3.5上下文无关文法及其语法树上下文无关文法及其语法树二义文法改造为无二义文法二义文法
24、改造为无二义文法GEGE：E T|E+TE T|E+T T F|T*F T F|T*F F F （E E）|i|i规定算符优先性和结合性规定算符优先性和结合性ET+EiTF*TFiFi消除二义性后句子消除二义性后句子i*i+i对应的语法树对应的语法树413.6（上下文无关文法）上下文无关文法）句型的分析句型的分析句型分析句型分析就是就是识别识别一个符号串是否为某文法的一个符号串是否为某文法的句型句型，是某，是某个个推导推导的构造过程。的构造过程。在语言的编译实现中，把在语言的编译实现中，把完成句型分析完成句型分析的的程序程序称为称为分析程分析程序序或或识别程序识别程序。从左到右的分析算法从左到
25、右的分析算法，即，即总是从总是从左左到到右右地地识别输入符号串识别输入符号串，首先识别符号串中的首先识别符号串中的最左最左符号，进而符号，进而依次识别右边依次识别右边的一个的一个符号，符号，直到分析结束直到分析结束。(以后介绍的算法均属此类）以后介绍的算法均属此类）42n从左到右的句型分析算法分类从左到右的句型分析算法分类：自上而下分析法自上而下分析法：从文法的开始符号出发从文法的开始符号出发，反复使用文法的产生式，反复使用文法的产生式，寻找寻找与与输入符号串输入符号串匹配匹配的的推导，推导，或者说，为输入串寻找一个或者说，为输入串寻找一个最左推导。最左推导。自下而上分析法自下而上分析法：从从
26、输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，直至，直至归约归约到到文法的文法的开始符号开始符号。3.6句型的分析句型的分析43n从语法树的构造过程来理解两种句型分析方法从语法树的构造过程来理解两种句型分析方法1.自上而下方法自上而下方法从文法符号开始，将它做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串2.自下而上方法自下而上方法从输入符号串开始，以它做为语法树的结果，自底向上的构造语法树3.6句型的分析句型的分析44 1. 自上而下的语法分析自上而下的语法分析例：文法例：文法G：S cAdA abA a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的
27、句子句子SSScAdcAdab推导过程：推导过程：ScAdcAdcabd3.6句型的分析句型的分析45例：文法例：文法G：S cAdA abA a识别输入串识别输入串w=cabd是否该文法的是否该文法的句子句子SAAcabdcabdcabd归约归约过程构造的推导：过程构造的推导：cAdcabdScAd1.自下而上的语法分析自下而上的语法分析3.6句型的分析句型的分析46自上而下的语法分析自上而下的语法分析(1)S cAd(2)A ab(3)A a识别输入串识别输入串w=cad是否为该文法的是否为该文法的句子句子 串的第二个符号可以与叶子结点a得以匹配，但第三个符号却不能与下一叶子结点d匹配。宣
28、告分析失败(意味着，识别程序不能为串cad构造语法树，即cad不是句子): 显然是错误的结论。显然是错误的结论。导致失败的原因是在分析中对A的选择不是正确的。 S c A d a b这时应回溯回溯，把A为根的子树剪掉，扫描过的输入串中的a吐出来,再试探用产生式（3）若S cAd 后选择(2)扩展A，S cAd cabd 那将会？47自下而上的语法分析自下而上的语法分析(1)ScAd(2)Aab(3)Aa识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子 对串cabd的分析中，如果不用产生式(2的ab，而是用产生式(3) 将a归约到了A，则在cAbd 中无法找到一个可归约串了，
29、最终就达不到归约到S的结果，因而也无从知道cabd是一个句子c a b d c A b d a48句型分析的有关问题句型分析的有关问题1）在自上而下的分析方法中选择使用）在自上而下的分析方法中选择使用哪个哪个产生式进行产生式进行推导推导？假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是B，且有且有n条规则：条规则：BA1|A2|An，那么如何确定用哪个右部去替代那么如何确定用哪个右部去替代B？（回溯）？（回溯）2）在自下而上的分析方法中在自下而上的分析方法中如何如何识别可归约的串识别可归约的串？在分析程序工作的每一步，都是从当前串中在分析程序工作的每一步，都是从当前串中选择一选择一
30、个个子串子串，将它，将它归约归约到到某个非终结符号某个非终结符号，该子串称为，该子串称为“可归约串可归约串”。在规范归约中该可归约串称为句柄。在规范归约中该可归约串称为句柄。49句柄及其相关概念句柄及其相关概念1.短语短语：xuy是文法GS的一句型,如果有 S=*xUy且且U=+u ,其中UVN , uV+，则称u是句型xuy相对于非终结符号U的短语。 短语是在句型的推导过程中能由某个非终结符号推导出的子串。2.直直接接短短语语（简简单单短短语语）：若有 S=*xUy且且U=u，则称u是句型xuy相对于非终结符号U的直接短语。 直接短语则是能由某个非终结符号直接推导出的子串。3.句柄句柄：任一
31、句型的最左直接短语称为该句型句柄。 50句柄及其相关概念句柄及其相关概念例:写出GE中句型 i*i+i的所有短语、简单短语和句柄。GE: E T|E+T T F|T*F F （E）|i解：首先构造出句型 i1*i2+i3对应的语法树因为F=i，所以i1,i2,i3分别是句型i1*i2+i3相对于规则Fi的直接短语，而句柄是最左侧的直接短语即i1。因为T=+i1,所以i1是句型i1*i2+i3相对于T的短语，i3也是同样情况。ET+Ei2TF*TFi1Fi351句柄及其相关概念句柄及其相关概念注意：并不是句型中的任意子序列都可构成短语。如上例中的 i2+i3.因为T=+i1*i2，所以i1*i2
32、是句型i1*i2+i3相对于T的短语。因为E=+i1*i2，所以i1*i2是句型i1*i2+i3相对于E的短语。因为E=+ i1*i2+i3 ，所以i1*i2+i3是句型i1*i2+i3相对于E的短语。综上：i1，i2，i3， i1*i2， i1*i2+i3均是句型i1*i2+i3的短语，其中i1，i2，i3为直接短语， i1为句柄。ET+Ei2TF*TFi1Fi352直接短语：a2,b2a3,a4 短语：a2,b2a3,a4,a2b1b2a3,a1a2b1b2a3a4句柄：a2给出句型给出句型aabbaa的所有短语、直接短语和句柄的所有短语、直接短语和句柄Sa1ASSb1Aa4a2b2a3句
33、柄及其相关概念句柄及其相关概念例例:GS:1)SaAS2)ASbA3)ASS4)Sa5)Aba533.7有关文法实用中的一些说明有关文法实用中的一些说明n对文法进行限制对文法进行限制（目的是化简文法）文法中文法中不含有不含有有害规则有害规则和和多余规则多余规则有害规则有害规则：形如：形如UU的产生式。会引起文法的的产生式。会引起文法的二义性二义性多余规则多余规则：指文法中：指文法中任何句子的推导任何句子的推导都都不会用到的规则，不会用到的规则，它们以它们以不可到达不可到达和和不可终止不可终止两种情况出现两种情况出现1)文法中某些文法中某些非终结符不在任何规则的右部出现非终结符不在任何规则的右部
34、出现，该非，该非终结符称为终结符称为不可到达不可到达。2)文法中某些文法中某些非终结符非终结符，由它，由它不能推出终结符号串不能推出终结符号串，该，该非终结符称非终结符称为为不可终止不可终止。54对于文法对于文法GS，为了保证任一非终结符为了保证任一非终结符A在在句子句子推导中出推导中出现，必须满足如下两个条件：现，必须满足如下两个条件：1.A必须在某句型中出现必须在某句型中出现即有即有S=* A，其中其中，属于属于V V* *2.必须能够从必须能够从A推出终结符号串推出终结符号串t来来即即A=* t，其中其中tVT*3.7 有关文法实用中的一些说明有关文法实用中的一些说明55化简文法化简文法
35、例：例：GS：1) SBe2) BCe3) BAf4) AAe5) Ae6) CCf7) Df3.7有关文法实用中的一些说明有关文法实用中的一些说明D D为不可到达为不可到达,C,C为不可终止为不可终止, ,产生式产生式 2 2）6 6）7 7）为）为多余多余规则规则应去应去掉。掉。56n对文法的扩充：上下文无关文法中的对文法的扩充：上下文无关文法中的规则规则本书所给上下文无关文法的定义中，某些规则可以具有形本书所给上下文无关文法的定义中，某些规则可以具有形式式A，称这种规则为称这种规则为规则。有些教材对此进行了限制，规则。有些教材对此进行了限制，但这不牵扯到本质的问题。但这不牵扯到本质的问题
36、。两种定义的唯一差别是两种定义的唯一差别是句子在不在语言中句子在不在语言中如果语言如果语言L有一个有穷的描述，则有一个有穷的描述，则L1=L也同样有也同样有一个有穷的描述，并且可以证明，若一个有穷的描述，并且可以证明，若L是上下文有关语言、是上下文有关语言、上下文无关语言或正规语言，则上下文无关语言或正规语言，则L分别是上下文有分别是上下文有关语言、上下文无关语言和正规语言。关语言、上下文无关语言和正规语言。3.7有关文法实用中的一些说明有关文法实用中的一些说明573.8 典型例题例1：证明文法GE是二义的。P46例2：给出下述语言的上下文无关文法L1=anb2ncm|n,m=0L2=anbmc2m|n,m=0解：要产生形如anb2ncm的符号串，可分别产生形如 anb2n和cm的串，所以L1对应的文法为：SABA |aAbbB |cB同理可得L1对应的文法为：SABA |aA B |bBcc58作业作业 课本 P48: 1;2;3;5P48-49: 6.(1)(3)(5);11;1359
