资源描述：
《各章练习题(编译原理)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第三章复习重点：1.文法与语言的对应关系语言L(G)=L(G’)文法G文法G’{bnn>0}B→bBbB→Bbb{bnn≥0}P→bPεP→Pbε{abnn>0}S→DBD→aB→bBbS→aBB→Bbb{bnan≥0}T→PDD→aP→bPεT→PaP→Pbε{(ab)nn>0}U→EUEE→abU→Uabab{ambnm>0,n>0}V→ABA→aAaB→bBbV→aVaBB→bBb{ambnm≥0,n>0}W→ABA→aAεB→bBbW→aWBB→bBb{anbnn>0}X→aXbab{(akcd)nbnk,n>0}X→DXHDHD→Ac
2、dA→aAaH→b{a2n+1bnn>=0}Y→aaYbaY→KYHaK→aaH→b思路要点：注意结构拆分技巧：如何将表示语言的通用字符串形式作适当的“切割”？例：已知语言：L1={axb2xcyx,y>=0}，给出此语言的文法，并证明此语言是上下文无关语言。提示：该题实际上要求为相应语言设计上下文无关文法。一个文法设计好后，严格来说应当证明此文法是否对应于该语言。解：G[S]：S→ABA→eaAbbB→ecB推导过程：SÞAB+ÞaxAb2xB/使用A→aAbbx次/Þaxb2xB/使用A→e一次/Þaxb2xcxB/使用B→cBx次/Þax
3、b2xcx/使用B→e一次/举一反三：已知语言L2={axb2ycyx,y>=0}，给出此语言的文法，并证明此语言是上下文无关语言。解：G[S]：S→ABA→eaAB→ebBcc练习：14：写出下列语言对应的文法(1).{anbnambmn,m≥0}2.{1n0m0m0nn,m≥0}3.{1n0m0m0nn≥0,m>0}4.{anbmckn,m,k≥0}G1:S—>AAG2:S—>ABA—>aAbεA—>aAbεB—>aBbεG:S—>1S0S—>AA—>0A1A—>εG:Sà1S0ASà1S00A1Aà0A101Aà0A1ε2.给出文法，证明
4、文法符号串是否为文法的句型，若是句型，找出这个句型的所有短语、直接短语、句柄。1.令文法G［E］为：Z→bMbM→a(LL→Ma）①符号串b(Ma)b是否为该文法的一个句型，并证明。②若此符号串是句型，指出这个句型的所有短语、直接短语、句柄。1）（5分）证明：S=>bMb=>b(Lb=>b(Ma)b所以，符号串b(Ma)b是该文法的一个句型。（2）（5分）短语:Ma)，(Ma)，b(Ma)b直接短语:Ma)句柄:Ma)练习：（10分）已知文法G[T]：T→TFF；F→F↑PP；P→(T)i（1）用最右推导法证明β：TP↑(TF)是G[T]的一个
5、句型；（2）画出β的语法树；（3）写出β的全部短语、直接短语和句柄。(1)T=>TF=>TF↑P=>TF↑(T)=>TF↑(TF)=>TP↑(TF)证毕。(2)如图（3）短语：TP↑(TF)；P↑(TF)；(TF)；TF；P直接短语：TF；P句柄：P3.证明一个文法是二义性文法。证明下述文法G［S］是二义的。（5分）S->iSeSiSi解：SSiSeSiSiSiSeS可见，句型iises有两种不同的语法树，所以G[S]是二义的。练习：证明下述文法G：S®aSbSaSd是二义性文法。解：一个文法，如果存在某个句子有不只一棵语法分析树与之对应，那么
6、称这个文法是二义性文法。SaSSabSdd句子aadbd有两棵语法树。如下图：dSSabSSad(1)(2)由此可知，S®aSbSaSd定义的文法是二义性文法。第四章:重点：1.NFAàDFA的确定化及DFA的最小化。2.试写出描述语言L的正规式，构造能识别该语言L等价的NFA，再确定化将下图所示的NFA确定化，再最小化。(2010年出过)X431baaeeaee2Y用子集法确定化如下表:编号IIaIbAA{X,1,2,4}B{1,2,3,4}C{1,2,4,Y}BB{1,2,3,4}B{1,2,3,4}C{1,2,4,Y}CC{1,2,4,Y
7、}B{1,2,3,4}C{1,2,4,Y}由于对于非终态的状态A和B来说，它们输入a、b的下一个状态都是一样的，故状态A和B可以合并，将合并后的状态重命名为A，而终态则重命名为B，则合并后的状态转换矩阵为：SabAABBAB由此可以得到最小化的DFA，如下图所示：ABab练习1：给出接受字母表å={a，b}，语言为以b开头，以aa结尾的字符串集合的正规表达式，并构造与之等价状态的DFA。（2010年出过）答：依题意，以b开头，以aa结尾的字符串集合的正规表达式可写为：b(ab)aa画NFA，如下图所示X12baYa0ba用子集法确定化如下表II
8、aIb{X}A{1}B{1,2}C{1,2,Y}D-{1,2}C{1,2,Y}D{1,2,Y}D.{1}B{1}B{1}B{1}BABCbaDabab
