华农2013春编译原理试卷(参考答案)

《华农2013春编译原理试卷(参考答案)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、华南农业大学期末考试试卷（A卷参考答案）2012学年第2学期　考试科目：　编译原理　　考试类型：（闭卷）考试　　　考试时间：　120　分钟学号姓名年级专业题号一二三四总分得分评阅人得分一、简答题（本题共4小题，每小题5分，共20分）1、简述编译过程的5个阶段及各阶段的主要功能。编译过程即编译程序的工作过程，是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：①词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单词；②语法分析，根据语言的语法规则，把单词符号串组合成各类语法单位；③语义分析与中间代码产生，即对各类语法

2、单位，分析其含义并进行初步翻译；④代码优化，对代码进行等价变换，以期产生更高效的代码；⑤目标代码生成，把中间代码变换成特定机器上的低级语言指令形式。2、简述语法制导翻译技术的基本思想。语法制导翻译技术的基本思想是，对文法中的每个产生式都附加一个语义动作或语义子程序，在执行语法分析的过程中，当运用该产生式进行推导或归约时，就执行相应的语义动作，从而完成预定的翻译工作。3、简述算符优先分析方法。算符优先分析方法是一种移进-归约的语法分析方法，这种分析方法首先要根据文法来确定终结符之间的优先关系，然后借助这种优先关系，在移进-归约过程中通过比较相邻终结符之间的优先关系来确定句型的可归

3、约串（最左素短语）并进行归约。它不是一种规范归约的分析方法，只适用于分析算符优先文法。4、“含有优化部分的编译程序的执行效率更高。”这句话对吗？为什么？这句话是错的。优化不是编译程序必须的一个部分，含有优化的编译程序功能更强、算法更复杂，因而开发效率和执行效率低些，但得到的目标代码的效率通常更高。得分二、计算题（本题共5小题，共50分）1、将下图NFA确定化。（10分）bεbb2aε10bb3b{2}{3}a确定化：（可以给状态换名）ba{0,1,3}a{1,2}{1,2，3}bb（确定化后再化简也不扣分，但要有说明）2、将下图DFA化简。（5分）0100100DEABC11首

4、先将DFA的状态集划分成终态集和非终态集{E}、{A,B,C,D};由于{A,B,C,D}0={B,C,C,E}，所以再分划成{A,B,C}、{D};对于输入符号1，{A,B,C}1={Φ,D,D}，所以再次分划成{A}、{B,C};{B,C}0={C,C}，{B,C}1={D,D}，所以不用再分，B、C是等价状态。得到最小的DFA如下：010AE0DB1013．有文法如下：S→a

5、b

6、(T)T→TeS

7、SS句型(Sebe(a))的语法树和短语等如下：（10分）语法树：（5分）(2分)短语：(Sebe(a))、Sebe(a)、Seb、(a)、S、b、a(1分)直接短语：S、b、

8、a(1分)素短语：b、a(1分)句柄：S)T(S)TeTSeT(bSSa4、有文法如下：(共15分)S→aSe

9、ae(1).(6分)拓广文法并给产生式编号：S’→S①S→aSe②S→ae文法的识别规范句型活前缀的DFA：aI5:S→aSe.I3:S→aS.eaI4:S→ae.eSeI2:S→a.SeS→a.eS→.aSeS→.aeSI1:S’→S.I0:S’→.SS→.aSeS→.ae(2).文法的所有规范句型的活前缀就是上一步DFA各状态所识别的符号串：ε

10、S

11、aa*

12、a*aS

13、a*ae

14、a*aSe（3分）(3).LR（0）分析表如下（6分）：ACTIONGOTOae#S0

15、S211acc2S2S433S54r2r2r25r1r1r1空白处表示出错。5、有文法如下：（共10分）S→aABB→a

16、dA→bB

17、eA

18、ε(1)计算文法的每个候选产生式的SELECT集合；(5分)(2)说明文法是LL（1）文法的理由，并给出其预测分析表。(5分)(1)SELECT(S→aAB)={a}SELECT(B→a)={a}SELECT(B→d)={d}SELECT(A→bB)={b}SELECT(A→eA)={e}SELECT(A→ε)={a，d}(2)文法不含左递归，定义B的两条产生式的SELECT集没有交集，定义A的三条产生式的SELECT集两两不相交，所以文法

19、是LL（1）文法，预测分析表如下：abde#SS→aABBB→aB→dAA→εA→bBA→εA→eA得分三、证明题（本题共3小题，每小题5分，共15分）1、证明文法G[S]：S→SS

20、a

21、b是二义的。（5分）SS对于文法的符号串aabb，有两棵不同的语法树如右，所以该文法是二义的。SSSSSSSSSSaSSbbaaabb2、证明下面的两个文法是等价的。（5分）G[S]:S→D0

22、0D→S1G[A]:A→0B

23、0B→1CC→0B

24、0文法G[A]和文法G[S]定义的符号串集合都是0(10)*，所