内容发布更新时间 : 2024/11/5 22:44:16星期一 下面是文章的全部内容请认真阅读。

编译原理A 1.

简要说明语义分析的基本功能。 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 | ε 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，并且关系运算符优先级高)：

1

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 1.

什么是句子？ 什么是语言 ?

2. 写一文法，使其语言是偶正整数的集合,要求：

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

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分) 为下面的语言设计文法：

（1） （2）

{ab, 其中m ? n }

{w | w?{a, b}，w的长度为奇数}

证明 E + T*（id）是文法的一个句型，指出该句型的所有短语、直接短语和句柄。 5．(15分) 给定文法：

*

mnE → E + T | E - T |T T → T * F | T / F |F F → (E) | id

4

C卷答案

1答案：（每小题2分） （1） 语法分析 （2） 语法分析 （3） 语义分析 （4） 词法分析 （5） 语义分析 2答案：

按题意相应的正规表达式是(010)0，或0(0 | 10)0 ，构造相应的DFA。

*

**

*

**

3答案：（每小题 10分）

（1）考虑在先产生同样数目的a,b，然后再生成多余的a。以下是一种解法：

S → aSb | aS | ε

（2） A → aB | bB B → aA | bA | ε

5证明 E + T*（id）是文法的一个句型，指出该句型的所有短语、直接短语和句柄。 答：E?E?T?E?T*F?E?T*(E)?E?T*(T)?E?T*(F)?E?T*(id)，

rmrmrmrmrmrm短语：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

5