编译原理A卷

第1页共4页安徽农业大学经济技术学院2012―2013学年第1学期《编译原理》试卷（A卷）考试形式:闭卷笔试，2小时适用专业：2009级计算机科学与技术专业试卷总分：100分考试日期：2012年12月题号一二三四五总分评阅人得分一、填空题（请将答案写在答题卡上，每空2分，共14分）1.最左推导是指（1）.2.设有文法G，S是它的开始符号。如S*α且α∈(V∪T)*，则称α是（2）；3.设有文法G[E]：E→E+TT→T*F|FF→i|(E)则非终结符号集V={（3）}，终结符号集T={（4）}；4.设∑={0，1}，则∑上所有以1开头，后跟若干个（最少为1个）010串的句子集合对应的正规式为（5）；5.词法分析器的输出结果是（6）；6.一个LR分析器包括两部分：一个总控程序和（7）；二、选择题（请将答案写在答题卡上，共10小题，每小题2分，共20分）1.作为编译程序的源程序不能是（）A、高级语言B、C语言C、低级语言D、Java语言2.词法分析所依据的是（）A、语义规则B、构词规则C、语法规则D、等价变换原则3.文法G产生的（）全体构成该文法描述的语言得分评阅人得分评阅人学院：专业班级：姓名：学号：装订线第2页共4页A、句型B、终结符集C、非终结符集D、句子4.给定文法A→bA|cc，下面的符号串中为该方法句子的是（）①cc②bcbc③bcbcc④bccbcc⑤bbbcc可选项有：A、①⑤B、①③④⑤C、①④D、①④⑤5.词法分析器的输入是A、单词符号串B、源程序C、语法单位D、目标程序6.编译过程中，语法分析器的任务是（）①分析单词是怎样构成的②分析单词串是如何构成语句和说明的③分析语句和说明是如何构成程序的④分析程序的结构可选项有A、②③B、②③④C、①②③D、①②③④7.（）不可能作为编译程序的目标代码A、汇编指令代码B、可重定位指令代码C、绝对指令代码D、中间代码8.下列语法分析方法中属于自底向上语法分析方法的有（）①算符优先分析法②LL(1)分析法③预测分析法④LR(0)分析法⑤SLR(1)分析法A、①④⑤B、③④⑤C、②④⑤D、②③9.一个文法所描述的语言是（）A、唯一的B、不唯一的C、可能唯一，也可能不唯一D、具有二义性的文法描述的语言是不唯一的10.下列能描述语言L(G)={0n|n≥0}的文法是（）A、S→0|0SB、S→|0SC、S→0SD、S→S0三、判断题（下列说法正确的打“√”错误的打“×”请将答案写在答题卡上。每小题1分，共10分）1.源程序与目标程序是等价关系（）2.多遍扫描的编译程序的多遍是指多次重复读取源程序（）得分评阅人第3页共4页3.正规文法产生的语言都可以用上下文无关文法来描述（）4.上下文无关文法的开始符号可以是终结符或非终结符（）5.“else没有匹配的if”的错误信息应是语法分析阶段报告的（）6.正整数中出现了非数字的错误信息应是词法分析阶段报告的（）7.有穷自动机只可能有一个初态（）8.正规文法与有穷自动机这两种表示方式之间是等价的（）9.每一个文法都能改造为LL(1)文法（）10.语义分析与中间代码生成时所依据的是语义规则（）四、简答题（请将答案写在答题卡上，共1小题，共6分）1．编译器处理语言的过程一般分为哪些阶段？五、解答题(请将答案写在答题卡上。共5小题，共50分)1．已知文法G[S]：S→0S|1S|，求该文法描述的语言。（6分）2．已知正则表达式(0|1)*00（1）根据正则表达式，画出相应的NFAM；（3分）（2）将NFAM确定化（3分）；（3）化简，并画出最简DFAN（3分）。得分评阅人得分评阅人第4页共4页3.设文法G[S]:S→S+aT|aT|+aTT→*aT|*a（1）写出句型aT+a*a*a的最右推导并画出语法树；（4分）（2）写出该句型中所有的短语、直接短语、句柄。（4分）4．已知文法G[E]：E→ETE|（E）|iT→*|+（1）将文法G改造成LL（1）文法；（5分）（2）求文法G中每个非终结符的FIRST集合及FOLLOW集合；（5分）（3）构造LL（1）分析表。（5分）5．已知文法G(S)：S*AA0A1|*(1)求文法G的各非终结符号的FIRSTVT和LASTVT集合。（6分）(2)构造文法G的优先关系矩阵，并判断该文法是否是算符优先文法。（6分）学院：专业班级：姓名：学号：装订线