资源描述：
《2000级离散数学I试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2012-2013学年第1学期2010级《编译原理》期末考试试题(A卷)考试时间：2013年1月7日班级学号姓名²请将答案写在答题纸上，写明题号，不必抄题，字迹工整、清晰；²请在答题纸和试题纸上都写上你的班级，学号和姓名，交卷时请将试题纸、答题纸和草纸一并交上来。一、填空题（4小题，共20分，每题5分）1.判断布尔表达式文法G[B]符号间的优先关系(、、或表示无关系的)。G[B]:B->BoT
2、TT->TaF
3、FF->nF
4、(B)
5、t
6、f则下列符号之间的优先关系为B___#,o___B,n___n,t___a,(___(.2.设有一个文法G[S]:S->VV->T
7、ViTT->F
8、
9、T+FF->V*
10、[句型F+Fi[的短语，简单短语和句柄分别为____________,____________,____________。3.设语义分析中当前层数为L，偏移量为off，试写出以下程序点的层数和偏移变化情况。注意：约定基本类型bool,char,int,float,指针型分别分配1，2，4，8，2个存储单元。constintN=10;①typedefstructstudent{char*name;int[N][2]mark;}②studenta,b;boolave(student*s,③intn,floatx){boolsuccessful;intsum;④…}⑤v
11、oidmain(){…}4共4页第页1.设一个文法G[S’]：S’->SS->BBB->aBB->b其LR(1)活前缀状态机如下，请填写I3和I6状态。依据此状态机构造的LR(1)分析表当中，相应位置的内容为ACTION[I1,#]=______，ACTION[I3,b]=______，GOTO[I6,B]=______。I0：S’->.S,#S->.BB,#B->.aB,a/bB->.b,a/bI1：S’->S.,#I4：B->b.,a/bI5：S->BB.I7：B->b.,#I2：S->B.B,#B->.aB,#B->.b,#I3：I9：B->aB.,#I8：B->aB.,a/
12、bSbBabbBbBI6：Baaa一、计算题（4小题，每小题5分，共20分）1.求与Σ=｛a,b｝的正则表达式(a
13、b)*(aa*
14、b*b)(ab)*a等价的最简DFA。2.将以下文法等价变换为不含空产生式的文法。G[S]:S->aAbBcA->a
15、εB->AA
16、b3.将如下文法转换为等价的自动机。G[S]:S->aAS->bBA->aBcB->bAcS4共4页第页1.求与下面NFA等价的DFA。1a,bbb2435aaabba,b一、简答题（4小题，每小题5分，共20分）1.设计一个文法G描述语言{aibjcjdiek
17、i>=0,j>=1,k>=2}。2.请用正则表达式描述下面自
18、动机所接受的语言。1b23aabb4b3.分析LR族四种典型分析方法的异同。执行M判断E真假4.请给出运行时动态空间的内存存储区划分和典型过程活动记录内容。二、问答题（2小题，每小题5分，共10分）设高级程序设计语言中有Repeat语句的文法如下：G[S]:S->Repeat{M}Until(E)M->S;M
19、ε文法的语义如右图的流程图所示。1.请给出Repeat语句的四元式表示。2.采用语法制导的方式设计语义函数，构造Repeat语句的中间代码生成方法。4共4页第页一、问答题（2小题，每小题5分，共10分）1.以驻留法构造以下程序段的全局符号表（包括类型表、标识符表以及表之间的指
20、针）。2.比较说明单表结构下的驻留法管理和多表结构下的scope栈辅助管理方法的异同。#includeconstfloatE=2.718;typedefstructLn{floatbase;floatantilog};voidmain(){floatx;LnX;printf(“Pleaseinputthevalueofx:”);scanf(&x);X.base=E;X.antilog=power(E,x);printf(“Theantilogofthelogarithmsis:%f”,X.antilog);}二、问答题（2小题，每小题5分，共10分）1.通过文法等
21、价变换消除以下文法G[S]的左递归；2.判断变换后的文法是否为LL(1)文法。G[S]:S->Aa
22、bA->SBB->ab三、问答题（2小题，每小题5分，共10分）1.构造如下文法的NFA。G[A]：A->B0B->B0
23、A1
24、02.产生式形为A->a或A->Ba，A、B∈Vn，a∈Vt的文法是正则文法，称为左线性文法。设计构造与左线性文法等价的NFA算法。4共4页第页
