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

华南农业大学期末考试试卷（A卷参考答案）2012学年第2学期 考试科目：编译原理 考试类型：（闭卷）考试 考试时间：120分钟学号 姓名 年级专业 题号一二三四总分得分评阅人得分一、简答题（本题共4小题，每小题5分，共20分）1、简述编译过程的5个阶段及各阶段的主要功能。编译过程即编译程序的工作过程，是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单词；语法分析，根据语言的语法规则，把单词符号串组合成各类语法单位；语义分析与中间代码产生，即对各类语法单位，分析其含义并进行初步翻译；代码优化，对代码进行等价变换，以期产生更高效的代码；目标代码生成，把中间代码变换成特定机器上的低级语言指令形式。2、简述语法制导翻译技术的基本思想。语法制导翻译技术的基本思想是，对文法中的每个产生式都附加一个语义动作或语义子程序，在执行语法分析的过程中，当运用该产生式进行推导或归约时，就执行相应的语义动作，从而完成预定的翻译工作。3、简述算符优先分析方法。算符优先分析方法是一种移进-归约的语法分析方法，这种分析方法首先要根据文法来确定终结符之间的优先关系，然后借助这种优先关系，在移进-归约过程中通过比较相邻终结符之间的优先关系来确定句型的可归约串（最左素短语）并进行归约。它不是一种规范归约的分析方法，只适用于分析算符优先文法。4、“含有优化部分的编译程序的执行效率更高。”这句话对吗？为什么？这句话是错的。优化不是编译程序必须的一个部分，含有优化的编译程序功能更强、算法更复杂，因而开发效率和执行效率低些，但得到的目标代码的效率通常更高。得分二、计算题（本题共5小题，共50分）1、将下图NFA确定化。（10分）bbb2a10bb3b23a确定化：（可以给状态换名）ba0,1,3a1,21,2，3bb（确定化后再化简也不扣分，但要有说明）2、将下图DFA化简。（5分）0100100DEABC11首先将DFA的状态集划分成终态集和非终态集E、A,B,C,D;由于A,B,C,D0=B,C,C,E，所以再分划成A,B,C、D;对于输入符号1，A,B,C1= ,D,D，所以再次分划成A、B,C; B,C0=C,C，B,C1=D,D，所以不用再分，B、C是等价状态。得到最小的DFA如下：010AE0DB1013有文法如下：S a | b | (T)T TeS | S S 句型(Sebe(a)的语法树和短语等如下：（10分）语法树：（5分）(2分)短语：(Sebe(a)、Sebe(a)、Seb、(a)、S、b、a(1分)直接短语：S、b、a(1分)素短语：b、a(1分)句柄：S)T(S)TeTSeT(bSSa4、有文法如下：(共15分)S aSe | ae (1).(6分)拓广文法并给产生式编号： SS S aSe Sae文法的识别规范句型活前缀的DFA：aI5: S aSe.I3: S aS.eaI4: S a e. eSeI2: S a.SeS a.eS .aSeS .aeSI1: S S . I0: S .S S . aSeS . ae(2).文法的所有规范句型的活前缀就是上一步DFA各状态所识别的符号串：| S | aa* | a*aS | a*ae | a*aSe （3分）(3). LR（0）分析表如下（6分）：ACTIONGOTOae#S0S211acc2S2S433S54r2r2r25r1r1r1空白处表示出错。5、有文法如下： （共10分）S aABB a | dA bB | eA | (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集两两不相交，所以文法是LL（1）文法，预测分析表如下：abde#SS aABBB aB dAA A bBA AeA得分三、证明题（本题共3小题，每小题5分，共15分）1、证明文法GS： S SS | a | b 是二义的。 （5分）SS对于文法的符号串aabb，有两棵不同的语法树如右，所以该文法是二义的。SSSSSSSSSSaSSbbaaabb2、证明下面的两个文法是等价的。 （5分）GS: S D0 | 0D S1 GA: A 0B | 0B 1C C 0B | 0 文法GA和文法GS定义的符号串集合都是0(10)*，所以两个文法是等价的。（用其他的等价正规式、DFA、改写文法也可以）GS: S (AS) | (b)A (SaA) | (a) 3、有文法如： 证明符号串(A(SaA)(b)是此文法的规范句型。（5分） 对于符号串(A(SaA)(b)存在如下最右推导（规范推导）：S(AS) (A(AS) (A(A(b) (A(SaA)(b)根据定义，符号串(A(SaA)(b)是此文法的规范句型。得分四、应用题（本题共15分）1、写一个文法，使其语言是二进制奇数的集合，且每个奇数不以0开头。（5分）或GS: S 1A | 1A 1| 1A | 0A GS: S 1 | 1A1A 0A | 1A | 或GS: S 1A1 | 1A | A0 | A1 或其他等价文法。 2、构造一个读取二进制串的有限自动机（要求是最小DFA），实现奇偶校验的奇校验。即，读入1的总数为奇数时则接受，读入1的总数