《编译原理》模拟期末试题汇总 6套,含答案

《编译原理》模拟试题一

一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．计算机高级语言翻译成低级语言只有解释一种方式。(×) 2．在编译中进行语法检查的目的是为了发现程序中所有错误。(×)

3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 (√ )

4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、 b∈VT 。 (×) 5．每个文法都能改写为 LL(1) 文法。 (√)

6．递归下降法允许任一非终极符是直接左递归的。 (√) 7．算符优先关系表不一定存在对应的优先函数。 (×) 8．自底而上语法分析方法的主要问题是候选式的选择。 (×) 9．LR 法是自顶向下语法分析方法。 (×)

10．简单优先文法允许任意两个产生式具有相同右部。 (×)

二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)

1． 一个编译程序中，不仅包含词法分析，_____，中间代码生成，代码优化，目标代码生成等五个部分。

A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 2． 词法分析器用于识别_____。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 3． 语法分析器则可以发现源程序中的_____。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 4． 下面关于解释程序的描述正确的是_____。

(1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言

(3) 解释程序是为打开编译程序技术的僵局而开发的

A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 5． 解释程序处理语言时 , 大多数采用的是_____方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行

C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以

6． 编译过程中 , 语法分析器的任务就是_____。

(1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4) C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 7． 编译程序是一种_____。

A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 8． 文法 G 所描述的语言是_____的集合。

A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串

9． 文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_____。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法

10． 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式 三、填空题(每空1分，共10分)

1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__表格处理___和 ___出错处理__。 2．若源程序是用高级语言编写的,___目标程序__是机器语言程序或汇编程序,则其翻译程序称为 ___编译程序__ 。

3．编译方式与解释方式的根本区别在于__是否生成目标代码___。

4．对编译程序而言,输入数据是___源程序__, 输出结果是__目标程序___。 5．产生式是用于定义___语法成分__的一种书写规则。

6．语法分析最常用的两类方法是___自上而下__和___自下而上__分析法。 四、简答题（20分）

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

答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。

(2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈VT*} 。

2. 写一文法，使其语言是偶正整数的集合,要求： (1)允许0打头； (2) 不允许0打头。

解：(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. 已知文法 G[E] 为： E→T|E+T|E-T T→F|T*F|T/F F→ （ E ） |i

① 该文法的开始符号（识别符号）是什么？

② 请给出该文法的终结符号集合 VT 和非终结符号集合 VN 。 ③ 找出句型 T+T*F+i 的所有短语、简单短语和句柄。 解：① 该文法的开始符号（识别符号）是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. 构造正规式相应的 NFA : 1(0|1)*101 解

1(0|1)*101

对

应

的

NFA

为

5. 写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示和三元式序列。 逆波兰表示： abc*＋ab＋/d－

三元式序列： ① (*，b，c) ② (＋，a，①) ③ (＋，a，b) ④ (/，②，③) ⑤ (－，④，d)

五.计算题（10分）

构造下述文法 G[S] 的自动机： S->A0 A->A0|S1|0

该自动机是确定的吗？若不确定，则对它确定化。

解：由于该文法的产生式S->A0，A->A0|S1中没有字符集VT的输入，所以不是确定的自动机。 要将其他确定化，必须先用代入法得到它对应的正规式。把S?A0代入产生式A?S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入S->A0有该文法的正规式：0(0|01)*0，所以，改

写该文法为确定的自动机为：

为

由于状态A有3次输入0的重复输入，所以上图只是NFA，下面将它确定化： 下表由子集法将NFA转换DFA:

由上表可知DFA为：

《编译原理》模拟试题二

一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分）

1．“ 用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行 ”这种说法。(× )

2．若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。(× ) 3．一个句型的句柄一定是文法某产生式的右部。 (√) 4．在程序中标识符的出现仅为使用性的。 (× )

5．仅考虑一个基本块，不能确定一个赋值是否真是无用的。 (√ ) 6．削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。 (√ ) 7．在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。 (× )

《编译原理》模拟试题三

一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。(×)

2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。(× )

3．递归下降分析法是自顶向上分析方法。(√ ) 4．产生式是用于定义词法成分 的一种书写规则。 (×) 5．LR 法是自顶向下语法分析方法。 (√ )

6．在 SLR （ 1 ）分析法的名称中，S的含义是简单的。(√) 7．综合属性是用于 “ 自上而下 ” 传递信息。(× )

8．符号表中的信息栏中登记了每个名字的 属性和特征等有关信息 ，如类型、种属、所占单元大小、地址等等。 (×)

9．程序语言的语言处理程序是一种应用软件。 (×) 10．解释程序适用于 COBOL 和 FORTRAN 语言。 (×)

二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)

1． 文法 G 产生的_____的全体是该文法描述的语言。

A．( ) 句型 B．( ) 终结符集 C．( ) 非终结符集 D．( ) 句子 2． 若文法 G 定义的语言是无限集，则文法必然是 _____。 A．( ) 递归的 B．( ) 前后文无关的 C．( ) 二义性的 D．( ) 无二义性的

3． 四种形式语言文法中，1型文法又称为 _____文法。 A．( ) 短语结构文法 B．( ) 前后文无关文法 C．( ) 前后文有关文法 D．( ) 正规文法 4． 一个文法所描述的语言是_____。

A．( ) 唯一的 B．( ) 不唯一的 C．( ) 可能唯一，好可能不唯一 D．( ) 都不对 5． _____和代码优化部分不是每个编译程序都必需的。 A．( ) 语法分析 B．( ) 中间代码生成 C．( ) 词法分析 D．( ) 目标代码生成 6．_____是两类程序语言处理程序。

A．( ) 高级语言程序和低级语言程序 B．( ) 解释程序和编译程序 C．( ) 编译程序和操作系统 D．( ) 系统程序和应用程序 7． 数组的内情向量中肯定不含有数组的_____的信息。

A. ( ) 维数 B．( ) 类型 C．( ) 维上下界 D．( ) 各维的界差 8. 一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式

9． 文法分为四种类型，即0型、1型、2型、3型。其中2型文法是_____。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法 10．文法 G 所描述的语言是_____的集合。

A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 三、填空题(每空1分，共10分)

1．一个句型中的最左简单短语称为该句型的___句柄__。

2．对于文法的每个产生式都配备了一组属性的计算规则，称为 __语义规则___ 。 3．一个典型的编译程序中，不仅包括__词法分析___、__语法分析___、__中间代码生成___、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。

4． 从功能上说，程序语言的语句大体可分为__执行性___语句和__说明性___语句两大类。 5． 扫描器的任务是从__源程序___中识别出一个个___单词符号__。 6． 产生式是用于定义__语法范畴___的一种书写规则。 四、简答题（20分）

1. 写一个文法，使其语言是奇数集，且每个奇数不以0开头。 解：文法G(N)： N→AB|B A→AC|D B→1|3|5|7|9 D→B|2|4|6|8 C→0|D 2. 设文法G(S)： S→(L)|a S|a L→L，S|S (1) 消除左递归和回溯；

(2) 计算每个非终结符的FIRST和FOLLOW。

解：(1) S→(L)|aS' S'→S|ε L→SL' L'→SL'|ε (2)

FIRST)S)＝{(，a} FOLLOW(S)＝{#，，，)} FIRST(S')＝{，a,ε} FOLLOW(S')＝{#，，，)} FIRST(L)＝{(，a} FOLLOW(L)＝{ )} FIRST(L')＝{，，ε} FOLLOW(L'〕＝{ )}

3. 已知文法G(E)

E→T|E＋T

T→F|T *F

F→(E)|i

(1)给出句型(T *F＋i)的最右推导；

(2)给出句型(T *F＋i)的短语、素短语。

解：(1) 最右推导： E->T->F->(E)->(E＋T)->(E＋F)->(E＋i) ->(T＋i)->(T*F＋i)

(2) 短语：(T*F＋i)，T*F＋i，T*F，i 素短语：T*F,i

4. While a＞0 ∨ b＜0 do Begin

X：＝X＋1； if a＞0 then a：＝a－1 else b：＝b＋1 End；

翻译成四元式序列。 解：

(1) (j＞，a，0，5) (2) (j，－，－，3) (3) (j＜，b，0，5) (4) (j，－，－，15) (5) (＋，×，1，T1)

(6) (：＝，T1，－，×) (7) (j≥，a，0，9) (8) (j，－，－，12) (9) (－，a，1，T2) (10) (：＝，T2，－，a) (11) (j，－，－，1) (12) (＋，b，1， T3) (13) (：＝，T3，－，b) (14) (j，－，－，1) (15)

五.计算题（10分）

已知 NFA= （ {x,y,z},{0,1},M,{x},{z} ），其中：

M(x,0)={z},M(y,0)={x,y},M(z,0)={x,z},M(x,1)={x}, M(y,1)= φ ,M(z,1)={y}, 构造相应的DFA并最小化。

解：根据题意有NFA图:下

表

由

子

集

法

将

NFA

转

换

为

DFA

：

下面将该DFA最小化：

(1) 首先将它的状态集分成两个子集：P1={A,D,E},P2={B,C,F}

(2) 区分P2:由于F(F,1)=F(C,1)=E,F(F,0)=F并且F(C,0)=C,所以F，C等价。由于F(B,0)=F(C,0)=C, F(B,1)=D,F(C,1)=E,而D，E不等价（见下步），从而B与C，F可以区分。有P21={C,F},P22={B}。

(3) 区分P1:由于A，E输入0到终态，而D输入0不到终态，所以D与A，E可以区分，有P11={A,E},P12={D}。

(4) 由于F(A,0)=B,F(E,0)=F,而B，F不等价，所以A，E可以区分。

(5) 综上所述，DFA可以区分为P={{A}，{B}，{D}，{E}，{C，F}}。所以最小化的DFA如下：

《编译原理》模拟试题四

一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．一个 LL(l)文法一定是无二义的。 (× )

2．正规文法产生的语言都可以用上下文无关文法来描述。 (× )

3．一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。 (√) 4．目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 (× ) 5．逆波兰法表示的表达式亦称前缀式 。 (√ )

6．如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。 (√ ) 7．LR 法是自顶向下语法分析方法。 (× )

8．数组元素的地址计算与数组的存储方式有关。(× )

9．算符优先关系表不一定存在对应的优先函数。 (×)

10．对于数据空间的存贮分配， FORTRAN 采用动态贮存分配策略。 (×)

二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)

1．词法分析器用于识别_____。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符

2．文法分为四种类型，即0型、1型、2型、3型。其中0型文法是_____。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法

3．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。

A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式 4．_____是一种典型的解释型语言。

A．( ) BASIC B．( ) C C．( ) FORTRAN D．( ) PASCAL 5．与编译系统相比，解释系统_____。

A．( ) 比较简单 , 可移植性好 , 执行速度快 B．( ) 比较复杂 , 可移植性好 , 执行速度快 C．( ) 比较简单 , 可移植性差 , 执行速度慢 D．( ) 比较简单 , 可移植性好 , 执行速度慢

6．用高级语言编写的程序经编译后产生的程序叫_____。

A．( ) 源程序 B．( ) 目标程序 C．( ) 连接程序 D．( ) 解释程序 7．词法分析器用于识别_____。

A. ( ) 字符串 B．( ) 语句 C．( ) 单词 D．( ) 标识符

8．编写一个计算机高级语言的源程序后 , 到正式上机运行之前，一般要经过_____这几步: (1) 编辑 (2) 编译 (3) 连接 (4) 运行

A. ( ) (1)(2)(3)(4) B．( ) (1)(2)(3) C．( ) (1)(3) D．( ) (1)(4)

9．把汇编语言程序翻译成机器可执行的目标程序的工作是由_____完成的。 A．( ) 编译器 B．( ) 汇编器 C．( ) 解释器 D．( ) 预处理器 10．文法 G 所描述的语言是_____的集合。

A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 三、填空题(每空1分，共10分)

1．语法分析是依据语言的__语法___规则进行的，中间代码产生是依据语言的__语义___规进行的。

2．语法分析器的输入是__单词符号串___，其输出是__语法单位___。 3．一个名字的属性包括__类型___和__作用域___。 4．产生式是用于定义___语法成分__的一种书写规则。

5．逆波兰式 ab+c+ d*e- 所表达的表达式为__(a+b+c)*d-e___ 。

6．语法分析最常用的两类方法是__自上而下___和__自下而上___分析法。 四、简答题（20分）

1. 写出下列表达式的三地址形式的中间表示。

(1) 5+6 *(a + b);

(2)for j:=1 to 10 do a[j + j]:=0。 答： (1)100: t1:=a+b 101: t2:=6*t1 102: t3:=5+t2 (2)100: j:=1

101: if j>10 goto NEXT 102: i:=j+j 103: a[i]:=0

2. 设基本块p由如下语句构成： T 0 : =3.14; T 1 :=2*T 0 ; T 2 :=R+r; A:=T l *T 2 ； B:=A; T 3 :=2*T 0 ; T 4 :=R+r; T 5 :=T 3 *T 4 ; T 6 :=R-r ； B:=T 5 *T 6 ；

试给出基本块p的 DAG 。

解：基本块p的DAG图:

3. 写出表达式(a+b)/(a-b-(a+b*c)的三元序列及四元序列。 解：（1）三元式： ①（＋，a，b） ②（－，a，b） ③（/，①，②） ④（*，b，c） ⑤（＋，a，④） ⑥（－，③，⑤） （2）四元式：

①（＋，a，b，T1） ②（－，a，b，T2） ③（/，T1，T2，T3） ④（*，b，c，T4） ⑤（＋，a，T4，T5） ⑥（－，T3，T5，T6）

4. 写一个文法使其语言为偶数集，且每个偶数不以0开头。 解：文法G（S）： S→AB|B|A0 A→AD|C B→2|4|6|8 C→1|3|5|7|9|B D→0|C

5. 设文法 G （ S ）： S→S ＋ aF|aF| ＋ aF

F→*aF|*a

（1）消除左递归和回溯；

（2）构造相应的 FIRST 和 Follow 集合。

1）

S->aFS'|＋aFS' S'->＋aFS'|ε F->*aF' F'->F|ε （2）

FIRST（S）＝｛a，+｝ FOLLOW（S）＝｛＃｝ FIRST（S'）＝｛+，ε ｝ FOLLOW（S'）＝｛＃｝ FIRST（F）＝｛*｝ FOLLoW（F）＝（+，＃｝ FIRST（F'）＝｛*，ε｝ FOLLOW（+，＃｝

五.计算题（10分） 已知文法为： S->a|^|(T) T->T,S|S

构造它的 LR(0)分析表。

解：加入非终结符S'，方法的增广文法为： S'->S S->a S->^ S->(T) T->T,S

T->S 下面构造它的LR(0)项目集规范族为：

从上表可看出,不存在移进-归约冲突以及归约归约冲突，该文法是LR(0)文法。 从而有下面的LR(0)分析表：

《编译原理》模拟试题五

一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．编译程序是对高级语言程序的解释执行。(× )

2．一个有限状态自动机中，有且仅有一个唯一的终态。(×) 3．一个算符优先文法可能不存在算符优先函数与之对应。 (√ ) 4．语法分析时必须先消除文法中的左递归 。 (×)

5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 (√) 6．逆波兰表示法表示表达式时无须使用括号。 (√ ) 7．静态数组的存储空间可以在编译时确定。 (×)

8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。 (×)

9．两个正规集相等的必要条件是他们对应的正规式等价。 (× ) 10．一个语义子程序描述了一个文法所对应的翻译工作。 (×)

二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)

1．词法分析器的输出结果是_____。

A．( ) 单词的种别编码 B．( ) 单词在符号表中的位置 C．( ) 单词的种别编码和自身值 D．( ) 单词自身值 2． 正规式 M 1 和 M 2 等价是指_____。

A．( ) M1和M2的状态数相等 B．( ) M1和M2的有向边条数相等 C．( ) M1和M2所识别的语言集相等 D．( ) M1和M2状态数和有向边条数相等 3． 文法G：S→xSx|y所识别的语言是_____。

A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 4．如果文法G是无二义的，则它的任何句子α_____。 A．( )最左推导和最右推导对应的语法树必定相同 B．( ) 最左推导和最右推导对应的语法树可能不同 C．( ) 最左推导和最右推导必定相同

D．( )可能存在两个不同的最左推导，但它们对应的语法树相同 5．构造编译程序应掌握______。

A．( )源程序 B．( ) 目标语言 C．( ) 编译方法 D．( ) 以上三项都是 6．四元式之间的联系是通过_____实现的。 A．( ) 指示器 B．( ) 临时变量 C．( ) 符号表 D．( ) 程序变量

7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为_____。 A. ( ) ┐AB∨∧CD∨ B．( ) A┐B∨CD∨∧ C．( ) AB∨┐CD∨∧ D．( ) A┐B∨∧CD∨ 8. 优化可生成_____的目标代码。

A．( ) 运行时间较短 B．( ) 占用存储空间较小

C．( ) 运行时间短但占用内存空间大 D．( ) 运行时间短且占用存储空间小 9．下列______优化方法不是针对循环优化进行的。

A. ( ) 强度削弱 B．( ) 删除归纳变量 C．( ) 删除多余运算 D．( ) 代码外提 10．编译程序使用_____区别标识符的作用域。 A. ( ) 说明标识符的过程或函数名

B．( ) 说明标识符的过程或函数的静态层次 C．( ) 说明标识符的过程或函数的动态层次 D. ( ) 标识符的行号

三、填空题(每空1分，共10分)

1．计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。 2．扫描器是__词法分析器___，它接受输入的__源程序___，对源程序进行___词法分析__并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自上而下分析法采用___移进__、归约、错误处理、___接受__等四种操作。 4．一个LR分析器包括两部分：一个总控程序和___一张分析表__。 5．后缀式abc-/所代表的表达式是___a/(b-c)__。 6．局部优化是在__基本块___范围内进行的一种优化。 四、简答题（20分）

1. 简要说明语义分析的基本功能。

答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检 查。

2. 考虑文法 G[S]: S → (T) | a+S | a T → T,S | S

消除文法的左递归及提取公共左因子。

解：消除文法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) 写出相应的逆波兰表示。 解： w a b + c d e 10 - / + 8 + * +

4. 按照三种基本控制结构文法将下面的语句翻译成四元式序列： while (A

if (A ≥ 1) C=C+1; else while (A ≤ D) A=A+2; }。

解：该语句的四元式序列如下(其中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 ，试证明文法 G[S] 为二义文法。 证明：

由文法G[S]：S→aSb|Sb|b，对句子aabbbb对应的两棵语法树为：

因此，文法G[S]为二义文法。

五.计算题（10分） 已知文法 A->aAd|aAb| ε

判断该文法是否是 SLR(1) 文法，若是构造相应分析表，并对输入串 ab# 给出分析过程。 解：增加一个非终结符S/后，产生原文法的增广文法有：

S'->A

A->aAd|aAb|ε 下面构造它的LR(0)项目集

规范族为：

从上表可看出,状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。对于I0来说有：FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ，所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。 其SLR(1)分析表为：

对输入串ab#给出分析过程为：

《编译原理》模拟试题六

一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） 1．设r和s分别是正规式，则有L(r|s)=L(r)L(s)。(×)

2．确定的自动机以及不确定的自动机都能正确地识别正规集。(√) 3．词法分析作为单独的一遍来处理较好。 (× ) 4．构造LR分析器的任务就是产生LR分析表。 (√) 5．规范归约和规范推导是互逆的两个过程。 (× )

6．同心集的合并有可能产生新的“移进”/“归约”冲突。 (× ) 7．LR分析技术无法适用二义文法。 (× )

8．树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。 (×) 9．程序中的表达式语句在语义翻译时不需要回填技术。 (√) 10．对中间代码的优化依赖于具体的计算机。 (× )

二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分)

1．编译程序绝大多数时间花在_____ 上。

A．( ) 出错处理 B．( ) 词法分析

C．( ) 目标代码生成 D．( ) 表格管理 2． 编译程序是对_____。

A．( ) 汇编程序的翻译 B．( ) 高级语言程序的解释执行 C．( ) 机器语言的执行 D．( ) 高级语言的翻译 3． 采用自上而下分析，必须_____。

A．( ) 消除左递归 B．( ) 消除右递归 C．( ) 消除回溯 D．( ) 提取公共左因子 4．在规范归约中，用_____来刻画可归约串。 A．( )直接短语 B．( )句柄 C．( )最左素短语 D．( )素短语 5． 若a为终结符，则A->α · aβ为_____项目。

A．( )归约 B．( ) 移进 C．( ) 接受 D．( ) 待约 6．间接三元式表示法的优点为_____。

A．( ) 采用间接码表，便于优化处理 B．( ) 节省存储空间，不便于表的修改 C．( ) 便于优化处理，节省存储空间 D．( ) 节省存储空间，不便于优化处理 7．基本块内的优化为_____。

A. ( ) 代码外提，删除归纳变量 B．( ) 删除多余运算，删除无用赋值 C．( ) 强度削弱，代码外提 D．( ) 循环展开，循环合并 8. 在目标代码生成阶段，符号表用_____。 A．( ) 目标代码生成 B．( ) 语义检查 C．( ) 语法检查 D．( ) 地址分配

9．若项目集Ik含有A->α · ，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A->α · ”动作的一定是_____。

A. ( ) LALR文法 B．( ) LR(0)文法 C．( ) LR(1)文法 D．( ) SLR(1)文法 10．堆式动态分配申请和释放存储空间遵守_____原则。 A. ( ) 先请先放 B．( ) 先请后放 C．( ) 后请先放 D. ( ) 任意 三、填空题(每空1分，共10分)

1．词法分析基于__正则___文法进行，即识别的单词是该类文法的句子。

2．语法分析基于__上下文无关___文法进行，即识别的是该类文法的句子。语法分析的有效工具是__语法树___。

3．分析句型时，应用算符优先分析技术时，每步被直接归约的是__最左素短语___，而应用LR分析技术时，每步被直接归约的是___句柄__。

4．语义分析阶段所生成的与源程序等价的中间表示形式可以有__逆波兰___、___四无式表示__与___三元式表示__等。

5．按Chomsky分类法，文法按照___规则定义的形式__进行分类。

6．一个文法能用有穷多个规则描述无穷的符号串集合（语言）是因为文法中存在有___递归__定义的规则。 四、简答题（20分） 1. 文法 G[S] 为： S->Ac|aB A->ab

B->bc

写出 L(G[S]) 的全部元素。 解：S=>Ac=>abc 或S=>aB=>abc 所以L(G[S])={abc}

2. 构造正规式 1(0|1)*101 相应的DFA。 解：先构造NFA：

确定化：

重新命名，令AB为B、AC为C、ABY为D得：

所以，可得DFA为：

3. 文法 S->a|^|(T) T->T,S|S

对 (a,(a,a) 和 (((a,a),^,(a)),a) 的最左推导。

解： 对(a,(a,a)的最左推导为： S=>(T) =>(T,S) =>(S,S) =>(a,S) =>(a,(T)) =>(a,(T,S)) =>(a,(S,S)) =>(a,(a,S)) =>(a,(a,a))

对(((a,a),^,(a)),a) 的最左推导为： S=>(T) =>(T,S) =>(S,S) =>((T),S)

=>((T,S),S) =>((T,S,S),S) =>((S,S,S),S)

=>(((T),S,S),S) =>(((T,S),S,S),S) =>(((S,S),S,S),S) =>(((a,S),S,S),S) =>(((a,a),S,S),S) =>(((a,a),^,S),S) =>(((a,a),^,(T)),S) =>(((a,a),^,(S)),S) =>(((a,a),^,(a)),S) =>(((a,a),^,(a)),a)

4. 文法： S->MH|a H->LSo| ε K->dML| ε L->eHf M->K|bLM

判断 G 是否为 LL(1) 文法，如果是，构造 LL(1) 分析表。 解：各符号的FIRST集和FOLLOW集为：

预测分析表为：

由于预测分析表中无多重入口，所以可判定文法是LL(1)的。

五.计算题（10分） 已知文法 G[S] 为： S->a|^|(T) T-> T,S|S

(1) 计算 G[S] 的 FIRSTVT 和 LASTVT 。

(2) 构造 G[S] 的算符优先关系表并说明 G[S] 是否未算符优先文法。 (3) 计算 G[S] 的优先函数。

(4) 给出输入串 (a,a)# 的算符优先分析过程。

解：（1）各符号的FIRSTVT和LASTVT：

（2）算符优先关系表：

（3）对应的算符优先函数为：

（4）句子(a,a)#分析过程如下：

本文来源：https://www.bwwdw.com/article/q6n.html