编译原理期中考试2009B.doc

云南大学 2009至2010学年 上学期 信息学院计算机科学与工程系 计算机科学与技术专业 2007级编译技术期中考试 B卷（闭卷）满分100分 考试时间：120分钟 任课教师：周小兵学院：_专业：_学号：_姓名：_题号一二三四总分得分一、选择题（本大题共4小题，每小题5分，共20分）1 词法分析器的任务是从源程序中识别_B_。A、句子 B、单词 C、字符 D、终结符号2. 文法SaSb|ab所产生的语言是什么_C_。 A、(ab)n B、anbm C、a n b n D、a和b的个数相等的a、b串3. 在源程序中，使用的某个变量没有声明，在编译的_C_阶段会报错。 A、词法分析 B、语法分析 C、语义分析 D、代码生成4 编译器在_C_阶段进行表达式的类型检查及类型转换。A、词法分析 B、语法分析 C、语义分析 D、目标代码生成二、分析题（本大题共2小题，每小题10分，共20分）1、一个上下文无关文法生成句子abbaa的推导树如下：(1)给出句子的最左推导。(2)该文法的产生式集合P可能有哪些元素？(3)找出该句子的所有短语、直接短语、句柄。解答：（1）句子abbaa最左推导:S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa注：应该用 =（表示推导），而不能用（表示定义）（2）产生式集合P可能：SABS |Aa| Aa BSBB|b（3）把abbaa表示成a1b1b2a2a3 短语：a1, a2, , b1, b2, b1b2, a2a3 , a1b1b2a2a3直接短语：a1, a2, , b1, b2, 句柄：a1注：由于有多个a和b，所以应该加上下标以示区别。2、将正规式r=a(b|c)*转换成相应的正规文法解答：令S是文法的开始符号，首先形成Sa(b|c)*，然后形成SaA和 A(b|c)*，再变换成：SaA A(b|c)B A B(b|c)B B进而变换为全部符合正规文法产生式的形式：SaA AbB|cB| BbB|cB|注：也可分开写成7个产生式三、设计题（本大题共2小题，每小题10分，共20分）对文法GA:A aABe|a B Bb|d 1. 文法GA是LL(1)文法吗？为什么？如果不是，请改写。2. 改写后的文法是LL(1)文法吗？请给出它的预测分析表。解答：1. 文法GS不是LL(1)文法，因为存在左公因子（A aABe|a）和左递归（B Bb|d）。2. 改写（即提取左公因子和消除左递归）后的文法如下： Aa N NA B e| BdN NbN |首先计算First集和Follow集对左部相同的产生式做如下运算：所以改写后的文法是LL(1)文法。预测分析表如下：通过预测分析表中无多重入口也可判定该文法是LL(1)文法。四、综合题（本大题共5小题，每小题8分，共40分）已知文法GS如下:S S; G | G G G(T) | H H a | (S) T T+S | S 请完成下列问题：1. 给出a(T+S);H;(S)的规范推导，并画出语法树。2. 给出1中句型的短语，直接短语，句柄，素短语，最左素短语。3. 计算GS的FIRSTVT和LASTVT集合。4. 构造GS的算符优先关系表。5. GS是否为算符优先文法？请说明理由。解答：1. S = S;G=S;H=S;(S)=S;G;(S)=S;H;(S) =G;H;(S)=G(T);H;(S)=G(T+S);H;(S) = H(T+S);H;(S)= a(T+S);H;(S)2. 短语：a、T+S、a(T+S)、a(T+S);H、H、(S)、a(T+S);H;(S) 直接短语：a、T+S、H、(S) 句柄：a 素短语：a、T+S、(S) 最左素短语：a3. FIRSTVT和LASTVT集合如下：FIRSTVTLASTVTS；( a；) aG ( a )