编译原理题库——简新答题.docVIP

PAGE  PAGE 207 编译原理A 简要说明语义分析的基本功能。 2. 考虑文法 G[S]: S → (T) | a+S | a T → T,S | S 消除文法的左递归及提取公共左因子。 3试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。 4. 按照三种基本控制结构文法将下面的语句翻译成四元式序列： while (AC ∧ BD) { if (A ≥ 1) C=C+1; else while (A ≤ D) A=A+2; }。 5. 已知文法 G[S] 为 S → aSb|Sb|b ，试证明文法 G[S] 为二义文法。 A答案 1答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检 查。 2解：消除文法G[S]的左递归： S→(T) | a+S | a T→ST′ T′→,ST′| ε 提取公共左因子： S→(T) | aS′ S′→+S | ε T→ST′ T′→,ST′| ε 3答：w a b + c d e 10 - / + 8 + * + 4答：该语句的四元式序列如下(其中E1、E2和E3分别对应A＜C∧B＜D、A≥1和A≤D，并且关系运算符优先级高)： 100 (j,A,C,102) 101 (j,_,_,113) 102 (j,B,D,104) 103 (j,_,_,113) 104 (j=,A,1,106) 105 (j,_,_,108) 106 (+, C, 1, C) 107 (j,_,_,112) 108 (j≤,A,D,110) 109 (j,_,_,112) 110 (+, A, 2, A) 111 (j,_,_,108) 112 (j,_,_,100) 113 5答：证明： 　　　　　由文法G[S]：S→aSb|Sb|b，对句子aabbbb对应的两棵语法树为：　　 因此，文法G[S]为二义文法。 　　 编译原理B 什么是句子？ 什么是语言 ? 2. 写一文法，使其语言是偶正整数的集合,要求： ???(1)允许0打头； ???(2) 不允许0打头。 3. 已知文法 G[E] 为： ????E→T|E+T|E-T ????T→F|T*F|T/F ????F→ （ E ） |i ① 该文法的开始符号（识别符号）是什么？ ② 请给出该文法的终结符号集合 VT 和非终结符号集合 VN 。 ③ 找出句型 T+T*F+i 的所有短语、简单短语和句柄。 4. 构造正规式相应的 NFA : 1(0|1)*101。 5. 写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示和三元式序列。 B卷答案 1答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。 (2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈VT*} 。 2解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S) P: S-PD|D P-NP|N D-0|2|4|6|8 N-0|1|2|3|4|5|6|7|8|9 (2)G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S) P: S-PD|P0|D P-NR|N R-QR|Q D-2|4|6|8 N-1|2|3|4|5|6|7|8|9 Q-0|1|2|3|4|5|6|7|8|9 3解：① 该文法的开始符号（识别符号）是E。 ②该文法的终结符号集合VT={+、-、*、/、（、）、i}。 非终结符号集合VN={E、T、F}。 ③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i; 简单短语为i、T*F、第一个T;句柄为第一个T。 4解：1(0|1)*101对应的NFA为 5解：逆波兰表示： 　　　　　abc*＋ab＋/d－　　　　 　　　　　三元式序列： 　　　　　 ① (*，b，c) 　　　　　 ② (＋，a，①) 　　　　　 ③ (＋，a，b) 　　　　　 ④ (/，②，③) 　　　　　 ⑤ (－，④，d) 编译原理C 1．(10分) 对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。 （1） else 没有匹配的if （2） 数组下标越界 （3） 使用的函数没有定义 （4） 在数中出现非数字字符 （5）函数调用时实参与形参类型不一致。 2．(15分) 构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1 都有0 直接跟在右边。并给出该语言的正规式 3．(10分) 为下面的语言设计文法： {ambn, 其中m ?