编译原理计科07精选.

1、编译原理期中试卷（计科07）1、简答题（15分）（1） 简述编译原理的概念及构成。答：1）编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的 翻译程序。2）构成:表格-S理程斥什么是文法?出错燮理齐pr答：文法：描述语言语法结构的形式规则。文法一般用一个四元式表示：G=（Vt ,Vn ,S,P）,其中Vt：终结符集合（非空）Vn：非终结符集合（非空），且Vt Vn=S:文法的开始符号，S Vn P:产生式集合（有限）。（3）什么是PDA?（这个是上课老师补充的书上没有）答: PDA是下推自动机，PDA M用一个七元组表示（K,工,f,H,h0,S,Z）K：有穷状态集：输入字母

2、表（有穷）H:下推栈符号的有穷字母表h0 :H中的初始符号f: K （工 ） H - > K H* S :属于K是初始状态。乙包含于K,是终结状态集合。这个大家看看：下推自动机（PDA）是自动机理论中定义的一种抽象的计算模型。下推自动机比有限状态 自动机复杂：除了有限状态组成部分外，还包括一个长度不受限制的栈；下推自动机的状态迁移不但要参 考有限状态部分，也要参照栈当前的状态；状态迁移不但包括有限状态的变迁，还包括一个栈的岀栈或入 栈过程。下推自动机可以形象的理解为，把有限状态自动机扩展使之可以存取 一个栈。最好也把DFA,NFA的定义看看。2、给出LL（1）分析方法的总控流程图（5分）

3、这个流程图其实就是提纲中讲的根据LL（1）分析表判断输入语句是否正确的流程图（提纲的倒数第二页）下面给出两个参考图，其实本质都是一样的。IL LL(1)分析法控制程序:1 I把栈顶符 弹入到变 血中！ J开始PUSH(#/NEXT(w)POP(xjxFV*.PUSH一PUSH ( ip )ERROR结束查LU1)分析表: * L ( x t w )= ?# ,s进栈，当前终结符送把产生式i左部逆睜压栈，厂r空？ERROR 世将规贝则X1X2.X的右部逆序入栈MX, a非空 *否上托栈顶符号放入读指针后移出错是-结束E h出错3、按指定类型给出下列语言的文法，并指出语言的类型(10分)这种题目难

4、做，大家结合书后习题P36-11看看吧，对于文法类型可以参考提纲第二页。(1) L1= anbmcn| n 为,m>0 二型文法：aSc|B bB|b(2) L2= 0 na1nbmcm| n>0，m 为 二型文法：AB A0Al|0al BbBc| £第4题是第五章内容，课程还没讲到，本次考试不会涉及4、文法G(S)为：(10分)St SdT|TT<G|G A (S)|a试给出（SdG） <a的短语。简单（直接）短语、句柄和最左素短语。 下面给出的答案是网上提供的，网上有这题的原题，希望对期末考试有用。答：短语：G，SdG, (SdG), a, (SdG)&

5、lt;a直接短语：G，a 句柄：G 最左素短语：a5、将NFA确定化为DFA（10分）分析：这类题目是正则式、NFA DFA之间的转换问题，首先由于已给出 NFA就不需要再由正则式画NFA也没说要最小化，只需将NFA转换为DFA即可，对于NFA首先列表计算Ia和lb,具体请参见提纲第六页下面的总结，这里再简单 的叙述一下，首先找出与初始状态等价的状态X,0,1,3 （由初始状态X通过空字£胃亡到达的），然后计算la, X,0,1 , 3中0状态通过a能到达0, 1状态通过a能到达2,所以将 0和2加入到la中，然后0,2中的0通过空字能到达1和3,所以1也加入，所以Ia=0,2,1

6、, 3,同理计算lb,如果发现Ia和Ib未在第一例出现，就将Ia和Ib作为新的I依次计算直到Ia和Ib出现在第一例为止。NFA:DFA:IaIbX,0,1,30,2,1,33,Y0,2,1,30,2,1,31,3,Y3,丫Y1,3,Y2Y21,3Y1,32YabSABAACBECDEDFEFDE含有丫的状态子集为DFA的终态，上例中的终态有B,C,E.6、请判断下面文法是否为LL（1）文法，若是请构造 LL（1）分析表（10分）SfDDSTe| &TFMMTHHM| &分析：判断一个文法是否为LL(1)文法是否为LL(1)文法，首先看其是否左递归(具体参见提纲第8页，分为直接和

7、间接左递归)，若是左递归肯定不是LL(1)文法，第二步就是算Select集合。实际上LL(1)文法应满足书上 P73的三个条件，第一个就是判断是否左递归，第二个 和第三个合并为算 Select集合，具体的说就是若一个非终结符产生式右部有若干结果，分别算出他们的Select集合，若他们的 Select集合交集为空集则是 LL(1)文法，否则不是。至于如何算Select集合请参见提纲，其前提是要算出First集合和Follow集合，具体方法请参加提纲第十页的“直接收取”和“反复传送”方法，这里不再赘述。方法：求First，找形如“ Uta“和“ U宀P“并注意P能否为空字。求Follow,找形如“

8、Ua“、”UP”(并注意P能否为空字)和” UtP” 的产生式。当然这道题目肯定是 LL(1)文法，否则题目就不好往下做，没有意义。答：(1)经分析该文法无左递归；非终结符的First和Follow集合如下表所示非终结符XFirst(X)Follow(X)Sa# bD9 a# bTbeMbeH9 be求Select集合首先将文法分解为：STaDDste Dt£TbMM TbHHmHt£依次计算：Select(SaD)=First(aD)=aSelect(D Ste)=First(Ste)=aSelect(D 0=First( 9 u Follow(D)=# bSelect(

9、T bM)=First(bM)=bSelect(M bH)=First(bH)=bSelect(H M)=First(M)=bSelect(H 9=First( 9 u Follow(H)= e / Select(D Ste) A Select(D9=© Select(H M) A Select(H沪该文法是LL(1)文法LL(1)分析表如下：abe#SSaDDDSTeD9D9TT bMMM bHhHMH 97、为文法GE: (10分)Vt N|NEi V|V+ENt i构造递归下降识别程序分析：首先看有无左递归，有得话要消除，开始写程序，采用递归原则，对非终结符一 个个开始写。答：

10、说明： ADVANCE :把输入串指示器IP指向下一个输入符号，即读入一个单字符号SYM: IP当前所指的输入符号ERROR :出错处理子程序PROCEDURE V,PROCEDUPE E;ProcedureBKINBEGIKIFSYMUr THEN ADVANCE;站ELSE ERRORIFTHENIF STM-THENBEGINBEGINADVANCE;ADMAMCE；IFTHEN ADVAPKE;ELSE ERRORENDEND上述是用vb语言写的，大家可能不太熟悉，当然也可以用其他语言如C语言写（或者其他的），自己定义一下输入函数，当前符号和出错处理函数即可，下面给出用C语言的写法。g

11、etnext（）:输入下一个单字的函数error （）:出错处理函数symbol:当前输入的符号vui d V()<NO；i f (hyruljul二*)匕3 llEt 0；EC)；订=getritflstO；stTorQ;vuidFt)V();if一二<tid NtJ;gctncKtO；elseciTorf);&给指定的正规表达式 b*（b|ab） +构造其DFA M（10分）NFA然后按照第5题的做法转换分析：根据提纲上的第四页下面的四个图首先可以画出成DFA,最后最小化一下。 答：（1）NFA如下所示：(2) NFA化为 DFAIlaIbX,1,241,3,23,5,

12、Y1,3,241,3,2,5,Y3,5,Y65,Y1,3,2,5,Y4,61,3,5,2,Y65,Y5,Y65,Y4,63,5,YIIaIbABCBDCBEDFGEHEFGGFGHDD,E,G是终态。上面计算量较大，请大家帮忙看看，我可能会算错，如果有问题，还麻烦及时告诉我， 下面的答案也就错了。(3)下面最小化DFA这个地方要注意下，首先分成非终态集A,B,C,F,H和终态集 D,E,GA,Ca=B B,F,Ha4所以首先将A,B,C,F,H分成两个集合A,C和B,F,H D,E,Ga=F,H是A,B,C,F,H的 子集D,E,Gb=G,E是 D,E,G的 子集 所以用再分A,C集合中，Ab

13、=C是A,C的子集Cb=E是D,E,G的子集，不是同一集合的子集所以需分成A,C胆尸,日2=22是 D,E,G的子集，所以不需划分所以最终分成：A,C, B,F,H,D,E,G最后结果如下所示：第9题是第五章内容，课程还没讲到，本次考试不会涉及，还是给出网上原题的答案, 也许对期末考试有用。9、文法G(E)的产生式为：(10分)St S*aP|aP|*aPpi +aP|+a(1) 判断文法是否是算术优先文法？若是构造算术优先文法分析表。(2) 写出a+a*a+a的分析过程a*+$a >< >*B > >+B >< < < acc栈输入串优先

14、关系动作0$a+a*a+a$ < apush1$a+a*a+a$a < +push2$a+a*a+a$+ B apush3$a+a*a+a$a > *pop4$aS*a+a$a > *pop5$S*a+a$ < *push6$S*a+a$* B apush7$S*a+a$a < +push8$S*a+a$+ B apush9$S*a+a$a > $pop10$S*a+a$a > $pop11$S*aS$a > $pop12$S$ B $acc10、构造奇数个0和奇数个1组成的自动机。（10分）11 11这个是网上给的答案，设计的很巧妙，大家

15、可以分析一下，最终肯定能满足奇数个0和奇数个1 ;当然如果真正要做的话，首先要写出奇数个0和奇数个1的正则表达式，在画出NFAQFA以及最小化，那会相当繁琐。下面补充一道老师上课讲的关于怎么判断一个任意长的二进制数能否被3整除的自动机如图（a）所示，如果是十进制数能否被3整除答案如图（b）所示固b图( a)这是网上给的答案，具体分析如下：注意到，一个二进制数后面加一个“ 0”相当于该数乘以2，一个二进制数后面加一个“ 1”相当于该数乘2加1。设定三个状态，分别叫做0、1和 2，它们表示当前的数除以 3所得的余数。如果对于某个 i 和j，有i*2三j (mod 3)，就加一条路径i -j，路径上

16、标一个字符“ 0”；如果i*2+1三j (mod 3)，则在路 径i-j上标记“ 1”。状态0既是我们的初始状态，也是我们的最终状态。我们的自动机就做好了。现在， 假如二进制数 10010走进来了。从状态 0出发，机器首先读到一个“ 1”，于是当前位置挪到状态 1，表明 目前该数模 3 余 1 ；然后，系统读了一个“ 0”，我们紧跟着走到状态2，表明二进制数“ 10”被 3除余 2；下一步，我们回到状态 1，表明“100”除以 3余 1；再往后，我们得知“ 1001”能被 3整除。最后呢，我 们读到一个 0， “1001”的两倍当然还是能被 3整除，我们依旧停留在原位。 我们得到结论： 二进制

17、数 10010 能被 3 整除。有限状态自动机是可以转化为正则表达式的。上面的这个自动机转化起来非常容易。我们可以先 试着用自然语言叙述一下。首先，每个二进制数第一位必然为“1”。到达状态1 后，我们可以随意地、任意多次地在状态 1 周围绕圈圈，最终回到状态 1 。临近末尾，我们再读到一个“ 1”返回状态 0，这之后随 便读多少个“ 0”都可以了。 现在问题分解为： 我们又如何用正则表达式表述“从状态 1 出发随意地走最终 回到状态 1”呢？在本例中，这是很好描述的：它可以是字符串“1000.001 ”和“0111.110”的任意组合。把这些东西用正则表达式写出来，就是我们刚才那个神秘的式子：1