期中考试

期中考试西安邮电学院计算机学院联系方式：[e-mail]王春梅讲师编译原理期中考试一、填空题（15分，每空1分）1.一个典型的编译系统包括和两部分。2.编译方式与解释方式的根本区别在于。3.乔姆斯基将文法分为四种，其中，2型文法也称为，3型文法也称为。4.某文法产生的的全体是该文法描述的语言。5.确定的有限自动机（DFA）是一个五元组，它包括。6.设有文法G[S]：S→S*S|S+S|(S)|a，该文法二义性文法。编译程序运行系统是否有目标代码产生上下文无关文法正则文法/线性文法句子(S,∑,f,S0,{Z})是编译原理期中考试7.预测分析程序是一种自上而下的分析程序，预测分析要求文法是，它主要由、预测分析表和总控程序三部分组成。8.自下而上分析方法也称为“移进—归约”法，是指从.开始，查找当前句柄进行归约，直到最后归约为.的一种分析方法。9.给定文法G[S]：S→aAcBe，句型aAbcde的句柄为。A→b|AbB→d10.算符优先分析法每次都是对进行归约。11.设有文法G[S]：S→b|bB，该文法所描述的语言B→bS是。Ab最左素短语L(G[S])={b2i+1|i}LL(1)文法分析栈输入符号串开始符号编译原理期中考试②语法分析(SyntaxAnalysis)：在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”，“表达式”等等。①词法分析(LexicalAnalysis)：从左到右一个字符一个字符的读入源程序，对构成源程序的字符串进行扫描和分解，从而识别出一个个单词（也称单词符号或简称符号）。二、简答题（20分，每题5分）1.简述一个编译程序的工作过程可以划分为几个阶段，每个阶段的任务是什么？编译程序语法分析语义分析与中间代码生成优化目标代码生成词法分析编译原理期中考试⑤代码优化(Optimizationofcode)：为了使生成的目标代码更为高效，可以对产生的中间代码进行变换或进行改造，这就是代码的优化。⑥代码生成(Generationofcode)：目标代码生成是编译器的最后一个阶段。在生成目标代码时要考虑以下几个问题：计算机的系统结构、指令系统、寄存器的分配以及内存的组织等。④中间代码生成(Generationofintermediatecode)：完成语法分析和语义处理工作后，编译程序将源程序变成一种内部表示形式，这种内部表示形式叫做中间语言或称中间代码，它是一种结构简单、含义明确的记号系统。③语义分析(SyntacticAnalysis)：语义分析是在语法分析程序确定出语法短语后，审查有无语义错误，并为代码生成阶段收集类型信息。编译原理期中考试2.“文法规则的左部一定是非终结符号”，这句话对吗？说明理由。不对。对于上下文无关文法而言，非终结符号是只在规则左部出现的符号，对于其他类型的文法而言，并非所有在规则左部出现的内容都是非终结符号。3.什么是规范推导,规范归约？每个句型都有规范推导吗？说明理由。规范推导就是最右推导，即任何一步αβ都是对α中的最右非终结符进行替换的；规范归约就是最左归约,实质上就是最右推导的逆过程。对于文法中的每一个句子都必定有规范推导或最左推导，而对一句型则不一定。编译原理期中考试4.简述LR分析器的工作过程。在总控程序的控制下，从左到右扫描输入串根据分析栈和输入符号的情况，查分析表确定分析动作；分析表是LR分析器的核心，它跟文法有关，它包括动作表(Action)和状态转换表(Goto)两部分，总控程序根据分析表确定分析动作；分析栈包括文法符号栈X[i]和相应的状态栈S[i]两部分(状态是指能识别活前缀的自动机状态)，LR分析器通过判断栈顶元素和输入符号查分析表确定下一步分析动作。三、解答题（30分）1.已知文法G[S]：S→a|∧|(T)T→T，S|S写出句子((a，a)，a)的规范归约过程及每一步的句柄。编译原理期中考试句型归约规则句柄((a，a)，a)S→aa((S，a)，a)T→SS((T，a)，a)S→aa((T，S)，a)T→T，ST，S((S)，a)T→SS((T)，a)S→(T)(T)(S，a)T→SS(T，a)S→aa(T，S)T→T，ST，S(T)S→(T)(T)S编译原理期中考试2、消除下列文法的左递归。G[S]：S→Sa|Ab|b|cA→Bc|aB→Bb|bG[S]：S→(Ab|b|c)S’S’→aS’|εA→Bc|aB→bB|b3、给出描述语言L={a2m+1bm+1|m≥0}∪{a2mbm+2|m≥0}的文法。将语言的描述稍做变形，得：L={a2mabbm|m≥0}∪{a2mbbbm|m≥0}G[Z]：Z→aaZb得到文法如下：|ab|bb编译原理期中考试4、构造正规式（0|1）*0（0|1）对应的DFA。12(0|1)*3040|11ε5ε20|1304010041ε5ε23011001ε5ε230114①构造转换系统图：编译原理期中考试②状态转换矩阵001ε5ε230114II0I1{1,5,2}{5,2,3}{5,2}{5,2,3}{5,2,3,4}{5,2,4}{5,2}{5,2,3}{5,2}{5,2,3,4}{5,2,3,4}{5,2,4}{5,2,4}{5,2,3}{5,2}012121442412333编译原理期中考试I1I0I{1,5,2}{5,2,3}{5,2}{5,2,3}{5,2,3,4}{5,2,4}{5,2}{5,2,3}{5,2}{5,2,3,4}{5,2,3,4}{5,2,4}{5,2,4}{5,2,3}{5,2}0121214424123330011201400011131.首次划分：Π0=({0,1,2,3},{4})2.在G={0,1,2,3}中:f(0,0)=1f(2,0)=1f(1,0)=3f(3,0)=3f(0,1)=2f(2,1)=2f(1,1)=4f(3,1)=4（终态）（终态）编译原理期中考试0011201400011131.首次划分：Π0=({0,1,2,3},{4})2.在G={0,1,2,3}中:f(0,0)=1f(2,0)=1f(1,0)=3f(3,0)=3f(0,1)=2f(2,1)=2f(1,1)=4f(3,1)=4（终态）（终态）故{0,1,2,3}可划分为{0,2}和{1,3}Π1=({0,2},{1,3},{4})0,2等价故Π2=({0,2},{1},{3},{4})3.在{0,2}中:1,3不等价在{1,3}中:120140001113编译原理期中考试四、综合题1.已知文法G[E]：E→-E|(E)|VE’E’→-E|εV→iV’V’→(E)|ε求每个非终结符的FIRST集和FOLLOW集，并构造预测分析表。FIRST(E)={-,(,i}FIRST(E’)={-,ε}FIRST(V)={i}FIRST(V’)={(,ε}FOLLOW(E)={)}FOLLOW(E’)={)}FOLLOW(V)={-,)}FOLLOW(V’)={-,)}-()iEE’VV’E→-EE→(E)E→VE’E’→-EE→εV→iV’V’→εV’→(E)V’→ε编译原理期中考试2、已知文法G[S]:S→SaF|F构造该文法的算符优先关系矩阵。F→FbP|PP→c|dFIRSTVT(S)={a,b,c,d}FIRSTVT(F)={b,c,d}FIRSTVT(P)={c,d}LASTVT(S)={a,b,c,d}LASTVT(F)={b,c,d}LASTVT(P)={c,d}SaaFab,ac,ad...LASTVT(S)a.aa,ba,ca,da....aFIRSTVT(F).FbLASTVT(F)b.bb,cb,db...bPbc,bd..bFIRSTVT(P).S#LASTVT(S)#.a#,b#,c#,d#....#S#FIRSTVT(S).#a,#b,#c,#d....#S###.编译原理期中考试#dcba#dcba.....................编译原理期中考试3、试编写词法分析器中识别标识符的程序片段。intIsIdentifier(charstr[])//是返回1，否则回0{inti=0;//必须以字母或下划线开始if((str[0]='A'&&str[0]='Z')||(str[i]='a'&&str[i]='z')||(str[i]=='_')){i=1;while(str[i]!='\0'){if((str[0]='A'&&str[0]='Z')||(str[i]='a'&&str[i]='z')||(str[i]=='_')||(str[i]='0'&&str[i]='9')){i++;continue;}elsereturn0;}return1;}elsereturn0;}