资源描述：
《西电软院编译原理试题By李欢》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、XidianUniversityLiHuan编译原理题目解1诗云：太初有道，道曰全真。全真七子，星聚软院。2重阳归天，分道七篇。各执一篇，授业终南。当是时也，正乃王道长献青真人讲道西电，秘授编译原理心法一篇，以飨众生。无量寿佛！今晚LiHuan1此处作者指的是目前西电软件学院七位有德道长：总掌教大护法武道长、首席副掌教顾道长、刘道长讳西洋、沈道长讳沛意、王道长讳献青、高道长讳海昌、陈道婆讳静玉。此乃huan说，另有其他版本。不再赘述。2此处指软件学院开山祖师陈真人讳平。归天意本离世，此处特指升仙为四大护
2、校法尊之一。XidianUniversityLiHuan1、填空题（30分）1.1以阶段划分的编译器中，语法分析阶段以记号流为输入，语义分析阶段以语法树为输入。1.2有正规式P=a
3、b和Q=cd则L(QP)={cda,cdb}，L((P
4、Q)Q)={acd,bcd,cdcd}。1.3有两个因素使得有限自动机是不确定的，一个是具有ε状态转移，另一个是对同一字符，可能有多于一个的下一状态转移。1.4词法分析器有四个作用，请给出其中的任意两个：识别记号并交给语法分析器/滤掉源程序中的无用成分/处理与具体平台有
5、关的输入/调用符号表管理器或出错管理器。1.5一个定义正确的上下文无关文法，非终结符集合和终结符集合的交集为空，所有出现在产生式左部的文法符号均是非终结符，仅出现在产生式右部的文法符号均是终结符。1.6编译源程序的过程中，发现函数定义末尾缺少花括号，该情况是语法错误；发现除数为0，该情况是语义错误。1.7推导S=>?H=>?FTP=>?FTc=>?Fbc=>?abc是最右/规范推导。1.8产生式F→A*F
6、A提取左因子的结果为F->AF'F'->*F
7、ε。1.9对于算术表达式“a*b+c”，当采用预测分
8、析方法时，接受格局中的“当前剩余输入”应该为空，初始格局中的“当前剩余输入”应该是a*b+c。1.10最左归约是最右推导/规范推导的逆过程，每步直接归约均是用产生式左部非终结符替换右句型中的句柄，直到归约为文法开始符号。1.11在引用调用的参数传递方式中，调用时传递的是实参的地址，要求实参必须是左值，过程内部对形参的修改等价于对实参的修改。XidianUniversityLiHuan1.12假定运算+与*都是左结合的，且运算*比运算+优先级高，则算术表达式x+y*(u+v)的后缀式是xyuv+*+。1.
9、13拉链-回填技术是语法制导翻译过程中使用的一种基本技术，其基本思想是当三地址码中的转向不确定时将所有转向同一地址的三地址码拉成一个链，而一旦所转向的地址被确定，则为此链上所有的三地址码回填入此地址。2、简答题（20分）2.1简述语言的语法和语义，并举一个实际的例子加以说明。答：语法规定了句子形成的规则，表述了语言的形式，或者说语言的样子和结构，也被称为语法规则。根据语法规则可以识别记号流中的语言结构，也被称为语法分析。语义揭示了语言本身的含义、施加于语言结构上的限制或要执行的动作。例如“猫吃老鼠”和“
10、老鼠吃猫”都是语法正确的句子，但后者表述的语义不对。（自己组织语言即可）2.2如果一个集合中的元素都是长度不小于1且均不以ab开始的a、b串，请给出描述该集合的正规式。*答：a
11、（aa
12、b）（a
13、b）2.3语法分析器在编译器中应完成什么任务？答：语法分析器根据语法规则识别出记号流中的结构，并构造一棵能够正确反映该结构的语法树。检查输入中的错误，调用出错管理器进行适当处理。2.4给定文法G：C→ChT
14、TT→TaF
15、FF→v请给出该文法的终结符集合、非终结符集合，并指出文法的开始符号。答：终结符：h、a、
16、v非终结符：C、T、F开始符号：C2.5给出下图中的树对应的三地址码序列。XidianUniversityLiHuan解：2.6假设数组下标从0开始，对于有5行6列的数组a[5][6]，已知该数组的存储空间首地址为a，每个元素占用存储空间大小为w，请给出数组以行为主存放时元素a[2][3]的地址。答：a+（2*6+3）*w=15w+a3、计算题（50分）*3.1给定正规式R=a(a
17、b)<1>用Thompson算法构造识别L(R)的NFAN；<2>用“子集法”把N确定化（写出完整过程），得到识别L(R)
18、的DFAD；<3>如果D不是最简DFA，请找出最简DFAD’。答：<1>笔误：红线一端从1开始。XidianUniversityLiHuan<2>E_闭包（{0}）={0}AE_闭包（smove(A,a)）={1,2,3,5,8}BE_闭包（smove(B,a)）={2,3,4,5,7,8}CE_闭包（smove(B,b)）={2,3,5,6,7,8}DE_闭包（smove(C,a)）={2,3,4,5,7,8}CE_闭包（smove(C,
