编译原理练习题及答案-高艳霞

一、 简答题（31分）1、 什么是编译程序？（3分）答：编译程序是指能把一种高级语言程序转换成一种低级语言程序的程序，而两者在逻辑上是等价的。2、 编译前端由哪些部分组成？（3分）答：词法分析、语法分析、语义分析与中间代码产生、优化3、 编译过程各阶段分别完成什么任务？（各用一句话简短回答）（5分）答：第一阶段，词法分析的任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。第二阶段，语法分析的任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。第三阶段，语义分析与中间代码产生的任务是：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。第四阶段，优化的任务是：对前段产生的中间代码进行加工变换，以期在最后阶段能产出更为高效（节省时间和空间）的目标代码。第五阶段，目标代码生成的任务是：把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。4、 请回答句子、句型和语言的定义。（6分）答：假定G是一个文法，S是它的开始符号。如果S=，则称是一个句型。仅含终结符号的句型是一个句子。文法G所产生的句子的全体是一个语言，将它记为L(G)。5、给出下面状态转换图的(S,d,s0,F)的具体组成（6分）答：状态集S：1，2，3，4输入字符集：0，1转换关系集d：d(1,0)=2, d(1,1)=3, d(2,0)=2, d(2,1)=4, d(3,0)=2, d(3,1)=3,d(4,0)=2, d(4,1)=3初态集S0：1终态集F：46、已知文法GZ：ZaAAbA|ab写出文法对应的语言（4分）答：ab(b)*ab7、请回答自上而下语法分析和自下而上语法分析有什么区别。（4分）答：自上而下的分析，是从文法的开始符号出发，试图推导出句子。它要解决的关键问题是在对某一个非终结符进行推导时，选择以它为左部的多个产生式中的哪一个。自下面上的分析，是从输入符号串出发，试图归约到文法的开始符号。分析过程中，每次选择与某个产生式右部符号串相同的一个子串进行归约。它要解决的关键问题是如何确定一个可归约的子串。二、已知文法G：Ta|e|(F)P FT+F|TP*P|T试给出式子(a+e)*a的最左推导及语法树（4分）答：最左推导：T=(F)P =(T+F)P =(a+F)P =(a+T)P =(a+e)P =(a+e)*P =(a+e)*T =(a+e)*a语法树：试给出式子(a)*e的最右推导及语法树（4分）答：最右推导：T=(F)P =(F)*P =(F)*T =(F)*e =(T)*e =(a)*e语法树： 指出句型(a+T)*P的所有短语、直接短语和句柄。（5分）答：先画出语法树短语：1,(a+T)*P相对于T的短语2,(a+T)相对于F的短语3,*P相对于P的短语4,a相对于T的短语5,T相对于F的短语直接短语：3，4，5句柄：4三、文法SAB|bBaAAab|cBdB|对文法G消除左递归（2分）答：公式：P P|P PPP|过程：=ab=cA c AA abA|对文法G消除左递归后得：SAB|bBaA c AA abA|BdB|对改写后的文法判断是否LL(1)文法，求相应FIRST和FOLLOW集合（7分）答：求FIRST:对S:FIRST(AB)=cFIRST(bBa)=bFIRST(S)=b,cFIRST(A)=cFIRST(A)=a, FIRST(B)=d, 每个非终结符 的各个产生式候选首符集两两不相交求FOLLOW:FOLLOW(S)=(#)FOLLOW(A)=(d,#)FOLLOW(A)=(d,#)FOLLOW(B)=(a,#)FIRST首符集合含的有FIRST(A)和FIRST(B)FIRST(A) FOLLOW(A) = FIRST(B) FOLLOW(B)= 由以上步骤得文法G满足LL(1)文法的3个条件，所以文法G是LL(1)文法。给出预测分析表（4分）答：如果FIRST包含的话，要看FOLLOW,若FOLLOW能推出该终结符，则填，否则不填abcd#SbBaABAcAAabABdB四、假设字母表是a,b，若要求所有以字母a开始，b结尾的符号串，写出相应正规式,并构造与之相对应的最小DFA.(10分)答：1. 正规式：a(