资源描述：
《南信大编译原理期中试卷(软件工程)教学内容.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、南信大编译原理期中试卷(软件工程)精品文档编译原理期中试卷(软件工程)1．简答题（每题5分，共计15分）(1)简述编译程序与解释程序的区别。解释程序不生成目标代码，而编译程序生成目标代码(2)什么是句柄？令G[S]是一个文法，如果有S=>*αAδ且A=>*β则称β是一个关于非终结符号A的，句型αβδ的短语。其次如果有S=>αAδ且A=>β则称β是直接短语。一个句型的最左直接短语称为该句型的句柄。(3)自顶向下的语法分析和自底向上的语法分析解决的核心问题分别是什么？自顶向下的语法分析解决的核心问题是：（1）消除左递归(2)避免回溯自底
2、向上的语法分析解决的核心问题是：寻找句柄2．文法G[S]:S∷=a｜b｜(T)T∷=T,S｜S给出句型(a,(b,S))的短语与直接短语(简单短语)、句柄和最左素短语。（10分）短语：(a,(b,S))，a,(b,S)，a，(b,S)，b,S，b直接短语(简单短语)：a，b句柄：a最左素短语：a3．按指定类型给出下列语言的文法,并指出语言的类型。（每个5分，共10分）(1)L1={anbm
3、n≥0,m>0}S::=aS
4、bS
5、b(2)L2={0n1nbmcm
6、n>0，m≥0}S::=ABA::=0A1
7、01B::=bBc
8、ε4．构造
9、正则式ba*
10、(ab)*b对应的DFA并最小化。（要求步骤清楚，15分）b1ε0aεε6ε2a3b4b5ε收集于网络，如有侵权请联系管理员删除精品文档IaIb{0,2,4}{3}{1,5,6}{3}Φ{2,4}{1,5,6}{1,6}{5,6}{2,4}{3}{5,6}{1,6}{1,6}Φ{5,6}ΦΦbaabb5.请在划线处填空。（5分）BEGIN/*StartAlgorithms*/(1)PUSH(‘#’),PUSH(‘S’);把第一个输入符号读进b;FLAG=TRUE；WHILEFLAGDOBEGIN把栈顶符号上托出去并放在
11、X中；IFXÎVtTHENIFX==bTHEN把下一个输入符号读进aELSEERRORELSEIFX==‘#’THENFLAG=FALSEELSEERRORELSEIFM[X,b]={X→X1X2…XK}THEN(2)将XkXk-1…X1入栈ELSE ERROREND/*EndOfWhile*/END/*EndofAlgorithms*/6．为文法G[P]：P∷=beginSendS∷=A｜CA∷=V:=EC∷=ifEthenSE::=VE'E'::=+VE'
12、εV∷=i构造递归下降识别程序（15分）构造程序（略，注意判断预测的符号
13、）收集于网络，如有侵权请联系管理员删除精品文档7．请给出文法的First和Follow集合，给出分析表（15分）E∷=TE'E'∷=+E｜εT∷=FT'T'∷=/T｜εF∷=PF'F'∷=*F｜εP∷=(E)｜a｜b根据下列分析表，分析句子i+i*i。（10分）将分析过程填入如下的表格中。步骤栈输入串规则（动作）1#Ei+i*i#E::=TE’2#E’Ti+i*i#T::=FT’3#E’T’Fi+i*i#F::=i4#E’T’ii+i*i#弹栈5#E’T’+i*i#T::=ε6#E’+i*i#E’::=+TE’7#E’T++i*i#
14、弹栈8#E’Ti*i#T::=FT’9#E’T’Fi*i#F::=i10#E’T’ii*i#弹栈收集于网络，如有侵权请联系管理员删除精品文档11#E’T’*i#T’::=*FT’12#E’T’F**i#弹栈13#E’T’Fi#F::=i14#E’T’ii#弹栈15#E’T’#T’::=ε16#E’#E’::=ε17##Acc8．文法G[E]：(1)E→KFc(2)K→aK(3)K→d(4)F→b，对应的LR(0)分析表如图，ACTIONGOTO状态abcd#EFK0S3S4121acc2S653S3S474r3r3r3r3r35S8
15、6r4r4r4r4r47r2r2r2r2r28r1r1r1r1r1依据右边的表格格式，写出分析adbc的过程。（10分）答题格式如下：步骤符号栈状态栈输入串动作1#0adbc#ShiftS32#a03dbc#ShiftS43#ad034bc#ReduceR34#aK037bc#ReduceR25#K02bc#ShiftS66#Kb026c#ReduceR47#KF025c#ShiftS88#KFc0258#ReduceR19#E01#acc9.有穷状态自动机分为哪几种，主要区别是什么？（5分）有穷状态自动机分为：NFA和DFA收集于
16、网络，如有侵权请联系管理员删除精品文档主要区别：NFA的映射函数是K×∑→2K，而DFA的映射函数是K×∑→K收集于网络，如有侵权请联系管理员删除
