编译原理A 简要说明语义分析的基本功能。
2. 考虑文法 G[S]: S → (T) | a+S | a T → T,S | S
消除文法的左递归及提取公共左因子。 3试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。
4. 按照三种基本控制结构文法将下面的语句翻译成四元式序列： while (A 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 | ε 1.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的逆波兰表示和三元式序列。 1 1. B卷答案 1答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。 (2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈VT*} 。 b) ④ (/，②，③) ⑤ (－，④，d) 编译原理C 1．(10分) 对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、代码生成）报告的。 （1） else 没有匹配的if （2） 数组下标越界 2解：（3） 使用的函数没有定义 (1)G[S]=({S,P,D,N},{0,1,2,…,9（4） 在数中出现非数字字符 },P,S) （5）函数调用时实参与形参类型不一致。 P: 2．(15分) 构造一个DFA，它接收Σ={0,1} S->PD|D 上所有满足如下条件的字符串：每个1 都有 P->NP|N 0 直接跟在右边。并给出该语言的正规式 D->0|2|4|6|8 3．(10分) 为下面的语言设计文法： N->0|1|2|3|4|5|6|7|8|9 mn（1） {ab, 其中m ? n } *(2)G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},（2） {w | w?{a, b}，w的长度为奇数} P,S) 证明 E + T*（id）是文法的一个句型，指P: 出该句型的所有短语、直接短语和句柄。 S->PD|P0|D 5．(15分) 给定文法： P->NR|N E → E + T | E - T |T R->QR|Q T → T * F | T / F |F D->2|4|6|8 F → (E) | id N->1|2|3|4|5|6|7|8|9 C卷答案 Q->0|1|2|3|4|5|6|7|8|9 1答案：（每小题2分） 3解：① 该文法的开始符号（识别符号）是（1） 语法分析 E。 （2） 语法分析 ②该文法的终结符号集合VT={+、-、*、/、（3） 语义分析 （、）、i}。 非终结符号集合VN={E、T、（4） 词法分析 F}。 （5） 语义分析 ③句型T+T*F+I的短语为i、T*F、第一个T、2答案： ***T+T*F+i; 简单短语为i、T*F、第一个T;句按题意相应的正规表达式是(010)0，或 ***柄为第一个T。 0(0 | 10)0 ，构造相应的DFA。 4解：1(0|1)*101对应的NFA为 3答案：（每小题 10分） （1）考虑在先产生同样数目的a,b，然后再 5解：逆波兰表示： abc*＋ab生成多余的a。以下是一种解法： ＋/d－ S → aSb | aS | ε 三元式序列： ① (*，b，c) （2）A → aB | bB ② (＋，a，①) ③ (＋，a，B → aA | bA | ε 2 不仅仅是一个字符串，它还具有属性和值。 4解： （1）、1＋1*2↑*1↑2 = 2*2↑*1↑2 = ↑*1↑↑↑2 = E?E?T?E?T*F?E?T*(E)?E?T*(4T)?E2 = 4?T*(F)?E?T*(5证明 E + T*（id）是文法的一个句型，指出该句型的所有短语、直接短语和句柄。 答： rmrmrmrm， 短语：id，（id）， T*（id）， E+ T*（id）。 直接短语：id。 句柄是id。 编译原理D卷 3、何谓“标识符”，何谓“名字”，两者的区别是什么？ 4、令 ＋、* 和↑代表加、乘和乘幂，按如下的非标准优先级和结合性质的约定，计算1＋1*2↑*1↑2的值： （1）、优先顺序（从高至低）为＋、* 和↑，同级优先采用左结合。 （2）、优先顺序为↑、＋、*，同级优先采用右结合。 6、令文法G6为N→D∣ND，D→0∣1∣2∣3∣4∣5∣6∣7∣8∣9 （1）、G6的语言L(G6)是什么？ （2）、给出句子0127、34和568的最左推导和最右推导。 7、写一个文法，使其语言是奇数集，且每个奇数不以0开头。 8、令文法为E→T∣E+ T∣E-T T→F∣T*F∣T/F F→(E)∣i （1）1） 给出i+i*i、i*(i+i)的最左推导和最右推导； 给出i+i+i、i+i*i和i-i-i的语法树。 9、证明下面的文法是二义的：S→iSeS∣iS∣i 11、给出下面语言的相应文法： Lnni 1={abc∣n≥1，i≥0}， Linn 2={abc∣n≥1，i≥0} Lnnmm 3={abab∣n，m≥0} L={1n0m1m0n 4∣n，m≥0} 3解：标识符是高级语言中定义的字符串，一般是以英文字母（包括大小写字母）或下划线开头的，由数字、字母和下划线组成的一定长度的字符串，它只是一个标志，没有（2）其他含义。名字是用标识符表示的，但名字 rm（2）、1＋1*2rm↑*1↑2 = 6解： （1）、L(G6)是由0到9这10个数字组成的字符串。 （2）、句子0127、34和568的最左推导： N=>ND=>NDD=>NDDD=>DDDD=>0DDD=>01DD=>012D=>0127 N=>ND=>DD=>3D=>34 N=>ND=>NDD=>DDD=>5DD=>56D=>568 句子0127、34和568的最右推导： N=>ND=>N7=>ND7=>N27=>ND27=>N127=>D127=>0127 N=>ND=>N4=>D4=>34 N=>ND=>N8=>ND8=>N68=>D68=>568 7解： G(S)：A→2∣4∣6∣8∣D B→A∣0 C→CB∣A D→1∣3∣5∣7∣9 S→CD∣D 8解： 最左推导为： E => E+T => T+T => F+T => i+T => i+T*F => i+F*F => i+i*F => i+i*i E => T => T*F => F*F => i*F => i*(E) => i*(E+ T) => i*(T+ T) => i*(F+ T) => i*(i+ T) => i*(i+ F) => i*(i+ i) 最右推导为： E =>E+T =>E+T*F =>E+T*i =>E+F*i =>E+i*i => T+i*i => F+i*i => i+i*i E => T => T*F => F*F => F*(E) => F*(E+T) => F*(E+ F) => F*(E+ i) => F*(T+i) => F*(F+i) => F*(i+i) => i*(i+ i) 语法树： 3 （ E E + T 4、 将图3.18的（a）和（b）分别确定化和 最小化。 E E a E + T 0 F E E a，b a - (a) - 1 T F T + T F F i T T * F i F i i a F i b 0 a F i i i 2 b b 3 a i a 9解：考虑句子iiiei，存在如下两个最右a 推导： b S=>iSeS=>iSei=>iiSei=>iiiei 1 4 S=>iS=>iiSeS=>iiSei=>iiiei b b 由此该文法是二义的。 a 11解： (b) L1的文法：S→AC；A→aAb∣ab；C→cC ∣ε L2的文法：S→AB；A→aA∣ε；B→bBc5、 构造一个DFA，它接受∑={0，1}上所有∣bc 满足如下条件的字符串：每个1都有0直接 L3的文法：S→AB；A→aAb∣ε；B→aBb跟在右边。、 ∣ε 6、 给定右线性文法G： L4的文法： S→1S0∣A； A→0A1∣ε； S→0S∣1S∣1A∣0B A→1C∣1 编译原理E卷 B→0C∣0 1、 构造下列正规式相应的DFA C→0C∣1C∣0∣1 1(0∣1)*101 求出一个与G等价的左线性文法。 1(1010*∣1(010)*1)*0 文法G对应的状态转换图如下所示： 0*10*10*10* 0，1 (00∣11)*((01∣10)(00∣11)*(01∣ 10)(00∣11)*)* 1 1 2、 给出下面正规表达式： A S （1） 以01结尾的二进制数串； （2） 能被5整除的十进制整数； 0 1 0 包含奇数个1或奇数个0的二进制数串； 0 B 3、 对下面情况给出DFA及正规表达式： （1）{0，1}上不含子串010的所有串。 4 5 a 0，1 C 0，1 Z E卷答案 2解： (1)、1(0∣1)*101 第一步：根据正规式构造NFA，先引入初始状态X和终止状态Y： X 1(0∣1)*101 Y 再对该转换图进行分解，得到分解后的NFA如下图： 0 1 ε ε X 1 2 1 第二步：对NFA进行确定化，获得状态转换矩阵： 状态 {X} {1，2，3} {2，3} {2，3，4} {2，3，5} {2，3，4，Y} 0 ? {2，3} {2，3} {2，3，5} {2，3} {2，3，5} 首先根据是否终止状态将所有状态分为两个集合{0，1，2，3，4}和{5}，这里集合{5}已经不可划分，只需考虑集合{0，1，2，3，4}。 {0，1，2，3，4}0={2，4，-}，{0，1，2，3，4}1={1，3，5} 因为{1，3，5}和{2，4，-}不在一个集合里面，所以需要对集合{0，1，2，3，4}进行进一步的划分，检查其中的所有状态。状态0不能接受字符0，需要把状态0划分出来；另外，只有状态4读入字符1后进入状态5，因此将状态4划分出来，划分的结果为4个集合：{0}，{1，2，3}，{4}，{5}。 检查集合{1，2，3}，{1，2，3}0={2，4}，不属于同一个集合，因此要对集合{1，2，3}进行进一步划分，划分结果为5个集合：{0}，{1，2}，{3}，{4}1 ，{5}。 0 1 Y 5 ，4 {1，3 检查集合2}，{12}0={2}，{1，2}1=3，不需要进行进一步划分。所以最终划分结果为5个集合：{0}，{1，2}，{3}，{4}，{5}。 所以，最终所求DFA如下图示： 0 1 {1，2，3} 0 {2，3，4} {2，3，4} {2，3，4} 1 3 1 0 1 1 0 1 4 1 3解： （1）以01结尾的二进制数串； (1︱0)*01。 （2）能被5整除的十进制整数； (1︱2︱3︱4︱5︱6︱7︱8︱9) (0︱1︱2︱3︱4︱5︱6︱7︱8︱9)*(0︱5)(0︱1 5 4 5)。 0 （3）包含奇数个1或奇数个0的二进制数 1 串； 1*0（1︱01*0）*︱0*1 （0︱10*1）*。4解： （1）、直接写出满足条件的正规表达 5 {2，3，4，Y} {2，3，4} 0 5 根据转换矩阵获得相应的DFA： 0 1 0 0 1 2 1 3 0 0 1 1 第三步：化简该DFA，获得最简的DFA 即为所求。