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