软件学院编译原理试题1

《软件学院编译原理试题1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京工业大学2009∽2010年度第1学期软件学院【编译原理】考试卷（B）考试形式：一纸开卷考试时间：2010年月日学号姓名一二三四五六七总分分数一、选择题（16分）1、请从下列供选择的答案中选出与编译过程的各阶段对应的常用方法：（1）词法分析的常用方法有（）（2）语法分析的常用方法有（）（3）中间代码生成的常用方法有（）（4）优化的常用方法有（）可选项有：（1）a.有穷自动机理论b.图灵机c.图论d.无穷自动机理论（2）a.自顶向下匹配b.自底向上归约c.回溯法d.自顶向下匹配和自底向上归约（3）a.LR方法b.语法制导翻译方法c

2、.最优匹配法d.递归法（4）a.信息流分析法b.语义分析法c.数据流分析法d.结构图2、通常编译程序是把高级语言书写的源程序翻译为（(1)），它包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成、符号表格管理和出错处理等部分。其中代码优化的目的是加快（(2)）的执行速度，符号表存取方法则影响（(3)）的效率。可选项有：（1）a.BASIC语言程序b.中间语言程序c.另一种高级语言程序d.等价的机器语言程序（2）、（3）a.编译程序b.目标程序c.源程序d.编译程序和目标程序e.解释程序3、设有文法G[E]：E->E+E

3、E

4、*E

5、(E)

6、i在下述文法类中，文法G[E]属于（）。（1）算符文法（2）上下文无关文法（3）正规文法（4）二义文法可选项有：a.（1）（2）b.（1）（2）（4）c.（2）（4）d.（1）（4）一、自顶向下的语法分析(20分)给定文法G[S]:S→aSb

7、AA→bAc

8、bBcB→Ba

9、a试消除文法的左递归、提取左因子，并判断改写后的文法是否为LL(1)文法？并说明理由。三、自底向上的语法分析（20分）试证明下面的文法G[S]是SLR(1)但不是LR(0)的：G[S]:S→XX→Xb｜bYaY→aXc｜a｜aXb四、（7分）试证明（

10、说明）下面的文法G[S]是二义的：G[S]:S→iSeS｜iS｜i 考虑句子iiiei，存在如下两个最右推导：S=>iSeS=>iSei=>iiSei=>iiieiS=>iS=>iiSeS=>iiSei=>iiiei五、（7分）写出能产生字母表{a,b}上的不含两个相邻的a,且不含两个相邻的b的全体符号串的有限状态自动机。六、（16分）设文法G[E]:E→RP

11、PP→(E)

12、iR→RP+

13、RP*

14、P+

15、P*画出句子i+i*(i+i)的语法分析树，给出其最右推导和最左归约，并指出它的句柄。七、属性文法（14分）如图所示为一简单的台式计

16、算器的语法制导定义(n为换行符)产生式语义规则L->EnPrint(E.val)E->E+TE.val:=E.val+T.valE->TE.val:=T.valT->T*FT.val:=T.val×F.valT->FT.val:=F.valF->(E)F.val:=E.valF->digitF.val:=digit.lexval1、该语法制导定义中仅使用了何种属性定义？仅使用该种属性的语法制导定义又称为何种属性定义？2、写出句子（17+3）+10*2n的带注释分析树、或属性计算过程。3、给出处理该句子的结果（Print输出结果）。