编译原理试题汇总+编译原理期末试题(8套含答案+大题集)(完整资料).doc

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