编译原理试卷

1、单项选择题判断题应用综合题总分20201020100课程名称：编译原理专业班级：【本科】备注： 学生不得在试题纸上答题（含填空题、选择题等客观题）一、单项选择题（本题共10道小题，每小题2分，共20分）1、在产生式中，符号“一”（“： = ”）表示（D ）。A.等于 B.恒等于 C,取决于 D,定义为2、编译程序是对（D ）程序进行翻译。汇编语言B.机器语言C.自然语言D.高级语言3、合并表达式中的常量运算的目的是（C ）o合并常量，使表达式中的常量尽可能少合并常量，使表达式尽可能简短将可在编译时刻计算的运算在编译时刻计算出来，用所计算出来的值替换表达式中出现的所有这种运算，使得生成的代码指令

2、尽可能少以上都不是对应Chomsky四种文法的四种语言之间的关系是（B ）。B. LbuLyLiuLoD. LocLicL2=L3结点代表（D ）,用圆圈表示。B.向前搜索 C.字符串D.4、A.C.5、A.6、A.B.C.D.7、A.C.8、A.9、A.LoGLicL2aL3 L3=L2cLicLo 在状态转换图中， 输入缓冲区编译程序前三个阶段完成的工作是（C ）。 词法分析、 代码生成、 词法分析、 词法分析、语法分析和代码优化代码优化和词法分析语法分析、语义分析和中间代码生成 语法分析和代码生成D.状态自底向上语法分析法的原理是（C ）。“移进一一推导法”B. “最左推导法”“移进一一

3、归约法D, “推导一一归约法”无符号常数的识别与拼数工作通常在（C ）阶段完成。语法分析 B.语义分析 C.词法分析 D.代码优化 下述方法中，（C ）不是自底向上的语法分析方法。规范归约B.算符优先分析法C.递归下降分析法D.LR分析法10、算符优先分析法从左到右扫描输入串，当栈顶出现（D ）时进行归约。A.素短语 B.直接短语C.句柄 D.最左素短语二、判断题（本题共10道小题，每小题2分，共20分）正确的画“V ,错误的画“X”1、（错）对任何一个编译程序来说，产生中间代码是不可缺少的。2、（错）符号表的内容在词法分析阶段填入并在以后各阶段得到使用。3、（错）设有一个LR （0）项目集l

4、 = Xa.BB,Af a.,该项目集含有“归约一归约” 冲突。4、（错）对文法G中的一个句子，如果能够找到两种以上的推导，则该句子是二义性的。5、（对）一个句型的句柄一定是文法某产生式的右部。6、（对）设有一个LR （0）项目集li=Xa A-a . ,该项目集含有“归约-归约冲突，7、（对 ）LL （1）文法是无左递归、无二义性文法。8、（错）语法分析时必须先消除文法中的左递归。9、（错）包含公共左因子的文法也能直接用预测分析法来分析。10、（对 ）编译方式与解释方式的根本区别在于是否生成目标代码。三、应用（本题共4道小题，每小题10分，共40分）1、设有文法GS：S-var D:TDD,

5、 i iTreal I integer给出句子var iJJ: real的推导和语法树。1、S= varD:T= var D,i:T = var D,iJ:T = var J iJ:T = var J ij:real语法树(5分，每步1分)Svar D ： T z D , i realED , i/2、将赋值语句x=a*b/（c+2*d）+ e*f+g表示为相应的逆波兰式和四元式。3、在自底向上语法制导翻译中，在对一个产生式归约时，立即执行相应的语义动作。（print 东” ） print 南(print “西” B - Aa)print 北” 当分析器的输入为b(aa)a)a)b时，打印的字

6、符串是什么？写出分析过程。4、设有基本块： tl=3*At2 = 2*Ct3=tl + t2t4=t3 十 5t5 = 2*Ct6 = 3*At7=t6 + t5M=t7-1N=t4-M（1）画出DAG图;4、 DAG：请写出优化后的代码序列。（2）假设只有M, N在基本块后面还要被引用,优化后的代码:tl = 3*At2 = 2*Ct3=tl+t2t4=t3 + 5M=t3-1N=t4-M四、综合题（本题共1道小题，每小题20分，共20分）1、对于下述文法 G A： A-*cAb | cAd |s（1）构造识别其规范句型所有活前缀的DFA；（2）说明该文法是何种LR文法，并给出其相应的LR分析表。1、将文法拓广为G S：(0) S 一s(l)S-rD(2) DD, i(3) DiDFA： (10 分)GOTO因为上述DFA的13状态集中有移进归约冲突， 所以该文法不是LR(O)文法。 对于L中：归约项目移进项目DDi 而：i A FOLLOW(S)=