资源描述：
《编译原理期末试卷》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、编译原理期中试卷1．简答题（每题5分，共计15分）(1)简述编译程序的概念及构成。编译程序是将高级语言程序翻译成等价的低级语言的翻译程序程序。编译程序的构成:(2)什么是文法？（在编译原理课程中，文法可以认为是上下文无关文法）一个文法G是一个四元组(VN，VT，P，S)，其中：(1)VT是一个非空有穷终结符号集合；(2)VN是一个非空有穷的非终结符号集合，且VT∩VN＝Φ；(3)SÎVN开始符号。(4)P是一个规则的非空有穷集合，每个产生式的形式是A::=α，其中A∈VN，α∈(VT∪VN)*，开始符号S
2、至必须在某个产生式的左部出现一次。(3)自顶向下的语法分析和自底向上的语法分析解决的核心问题分别是什么？自顶向下的语法分析解决的核心问题是：（1）消除左递归(2)避免回溯自底向上的语法分析解决的核心问题是：寻找句柄2．文法G[E]:E::=T
3、E+T
4、E-TT::=F
5、T*F
6、T/FF::=(E)
7、i给出句型i+T*F*i的短语与直接短语(简单短语)、句柄和最左素短语。（10分）短语：i+T*F*i，T*F,T*F*i,i1,i2直接短语(简单短语)：i1,i2句柄：i1最左素短语：i13．按指定类型给出
8、下列语言的文法,并指出语言的类型。（每个5分，共10分）(1)L1={anbm
9、n≥0,m>0}S::=aS
10、bS
11、b(2)L2={0na1nbmcm
12、n>0，m≥0}S::=ABA::=0A1
13、0a1B::=bBc
14、ε4．构造正则式a*b
15、(ab)*b对应的DFA并最小化。（要求步骤清楚，15分）ε1b0aεε6ε2a3b4b5abSABACDBΦΦCCΦDEBEΦFFEFεIaIb{0,1,2,4}S{1,3}{5,6}{1,3}A{1}{2,4,6}{5,6}BΦΦ{1}C{1}Φ{2,4,6}D{
16、3}{5,6}{3}EΦ{2,4}{2,4}F{3}{5,6}5.请在划线处填空。（5分）BEGIN/*StartAlgorithms*/(1)PUSH(‘#’),PUSH(‘S’);把第一个输入符号读进b;FLAG=TRUE；WHILEFLAGDOBEGIN把栈顶符号上托出去并放在X中；IFXÎVtTHENIFX==bTHEN把下一个输入符号读进aELSEERRORELSEIFX==‘#’THENFLAG=FALSEELSEERRORELSEIFM[X,b]={X→X1X2…XK}THEN(2)将XkX
17、k-1…X1入栈ELSE ERROREND/*EndOfWhile*/END/*EndofAlgorithms*/6．为文法G[E]：E::=E+V
18、VV::=Na
19、N[E]N::=i构造递归下降识别程序（15分）构造程序（略，注意判断预测的符号）7．请给出文法的First和Follow集合，若是LL(1)文法，给出分析表并分析句子abbe。（15分）G[S]:S::=aDD::=Te
20、εT::=bHH::=D
21、ε略8．文法G[E]：(1)E→T+T(2)E→TorT(3)T→n(4)T→b，对应的LR(
22、0)分析表如图，状态ActionGOTO+ornb#ET0s4s3121acc2s5s73r4r4r4r4r44r3r3r3r3r35s4s366r1r1r1r1r17s4s388r2r2r2r2r2依据右边的表格格式，写出分析n+born的过程。（10分）答题格式如下：步骤符号栈状态栈输入串动作1#0n+born#ShiftS42#n04+born#ReduceR33#T02+born#ShiftS54#T+025born#ShiftS35#T+b0253orn#ReduceR46#T+T0256orn
23、#ReduceR17#E01Error9.Chomsky文法分类将文法分为几类，分别什么文法？（5分）0型文法(短语结构文法PSG):u::=v，其中:u∈(VN∪VT)+,v∈(VN∪VT)*1型文法(上下文有关文法CSG):xUy::=xuy，其中:U∈VN,x,y∈(VN∪VT)*,u∈(VN∪VT)+2型文法(上下文无关文法CFG):U::=xuy，其中:U∈VN,x,y∈(VN∪VT)*,u∈(VN∪VT)+3型文法(正则文法RG):左线性：U::=Va或U::=a，右线性：U::=aV或U::
24、=a，其中:U,V∈VN,a∈VT
