您的当前位置：首页编译原理期末考试选择题汇总

编译原理期末考试选择题汇总

来源：花图问答

一、单项选择题

1、将编译程序分成若干个“遍”是为了( B ) A．提高程序的执行效率 B. 使程序的结构更加清晰

C．利用有限的机器内存并提高机器的执行效率

D．利用有限的机器内存但降低了机器的执行效率 2、不可能是目标代码的是( D ）

A．汇编指令代码 B．可重定位指令代码 C．绝对指令代码 D．中间代码 3、词法分析器的输入是( B ) A．单词符号串 B．源程序 C．语法单位 D．目标程序

4、编译程序中的语法分析器接受以 c 为单位的输入，并产生有关信息供以后各阶段使用。

可选项有：a、表达式 b、产生式 c、单词 d、语句

5、高级语言编译程序常用的语法分析方法中,递归下降分析法属于 b 分析方法。可选项有：a、自左至右 b、自顶向下 c、自底向上 d、自右向左 6、已知文法G［E］： E→TE’ E’ →+TE’∣ε T→FT’ T' →＊FT’∣ε F→（E）∣id

求：FOLLOW（F）=（1） d , FIRST(T'）=(2） b 可选项有： a、｛*,+｝ b、｛*,ε｝ c、｛+，#，）} d、｛*,+,＃，）｝ e、｛#，）｝ f、｛＊，+，#,id｝ 7、中间代码生成时所遵循的是( C ) A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 8、编译程序是对( D ）

A．汇编程序的翻译 B．高级语言程序的解释执行 C．机器语言的执行 D．高级语言的翻译 9、词法分析应遵循（ C )

A．语义规则 B．语法规则 C．构词规则 D．等价变换规则 10、词法分析器的输出结果是（ C )

A．单词的种别编码 B．单词在符号表中的位置 C．单词的种别编码和属性值 D．单词属性值 11、正规式M1和M2等价是指（ C )

A．M1和M2的状态数相等 B．M1和M2的有向弧条数相等

C．M1和M2所识别的语言集相等 D．M1和M2状态数和有向弧条数相等

12、词法分析器作为的阶段使整个编译程序结构更加简洁、明确，因此，( A ） A．词法分析器应作为的一遍 B．词法分析器作为子程序较好

C．词法分析器分解为多个过程，由语法分析器选择使用． D．词法分析器并不作为一个的阶段 13、如果L（M1）=L(M2），则M1与M2( A ) A．等价 B．都是二义的

C．都是无二义的 D．它们的状态数相等 14、文法G:S→xSx|y所识别的语言是（ C ）

＊nn＊＊

A．xyx B．(xyx） c．xyx（n≥0) d．xyx 15、文法G描述的语言L（G）是指（ A ) A． B． C． D．

16、有限状态自动机能识别( C )

A．上下文无关文法 B．上下文有关文法 C．正规文法 D．短语文法 17、编译过程中扫描器的任务包括 d 。

①组织源程序的输入 ②按词法规则分割出单词,识别出其属性，并转换成属性字的形式输出 ③删除注解 ④删除空格及无用字符 ⑤行计数、列计数 ⑥发现并定位词法错误 ⑦建立符号表

可选项有：a、②③④⑦ b、②③④⑥⑦ c、①②③④⑥⑦ d、①②③④⑤⑥⑦ 18、正则式的“∣\"读作（1） b ，“·\"读作（2) c ，“＊”读作(3） d 。可选项有:a、并且 b、或者 c、连接 d、闭包

19 、 b 这样一些语言,它们能被确定的有穷自动机识别，但不能用正则表达式表示。可选项有：a、存在 b、不存在 c、无法判定是否存在 20、编译过程中，语法分析的任务是 c 。

①分析单词是怎样构成的 ②分析单词是如何构成语句和说明的 ③分析语句和说明是如何构成程序的 ④分析程序的结构

可选项有：a、②和③ b、④ c、②③④ d、①②③④ 21、语法分析的常用方法有 b 。

①自顶向下 ②自底向上 ③自左向右 ④自右向左

可选项有：a、①②③④ b、①② c、③④ d、①②③ 22、如果文法G是无二义的，则它的任何句子( A ) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同

D．可能存在两个不同的最左推导，但它们对应的语法树相同

23、由文法的开始符经0步或多步推导产生的文法符号序列是( C ） A．短语 B．句柄 C．句型 D．句子 24、文法G：E→E+T｜T T→T＊P｜P P→（E）|i 则句型P+T+i的句柄为（ B )

A．P+T B．P C．P+T+i D．i 25、文法G：S→b｜∧｜(T) T→T∨S|S 则FIRSTVT(T)=（ C ）

A．{ b，∧，( } B．｛ b，∧，） } C．{ b，∧，(，∨ ｝ D．｛ b，∧，），∨ ｝ 26、产生正规语言的文法为（ D )

A．0型 B．1型 C．2型 D．3型 27、任何算符优先文法（ D ）优先函数。

A．有一个 B．没有 C．有若干个 D．可能有若干个 28、采用自上而下分析，必须（ C ) A．消除左递归 B．消除右递归 C．消除回溯 D．提取公共左因子 29、素短语是指 D 的短语。

①至少包含一个符号 ②至少包含一个终结符号 ③至少包含一个非终结符号 ④除自身外不再包含其他终结符号 ⑤除自身外不再包含其他非终结符号 ⑥除自身外不再包含其他短语 ⑦除自身外不再包含其他素短语

可选项有:

A、①④ B、①⑤ C、②④ D、②⑦

30、给定文法A→bA∣cc，下面的符号串中，为该文法句子的是 A 。 ①cc ②bcbc ③bcbcc ④bccbcc ⑤bbbcc 可选项有：

A、① B、①③④⑤ C、①④ D、①④⑤

31、已知文法 G[S]： S→eT∣RT T→DR∣ε R→dR∣ε D→a∣bd 则FOLLOW（T)= D . 可选项有: A、｛d｝ B、｛a，b｝ C、｛a,b,#｝ D、｛#｝ E、｛d，#｝ 32、正则式中的 “＊”读作 D 。可选项有：

A、并且 B、或者 C、连接 D、闭包 33、在规范归约中,用（ B )来刻画可归约串.

A．直接短语 B．句柄 C．最左素短语 D．素短语 34、有文法G:E→E*T｜T T→T+i｜i

句子1+2*8+6按该文法G归约，其值为（ B ) A．23 B．42 C．30 D．17

35、如果文法是无二义的,那么规范归约是指( B ) A．最左推导的逆过程 B．最右推导的逆过程 C．规范推导 D．最左归约的逆过程 36、文法G:S→S+T|T T→T*P|P P→（S）|i 句型P+T+i的短语有( B )

A．i，P+T B．P，P+T,i,P+T+i C．P+T+i D．P，P+T，i 37、高级语言编译程序常用的语法分析方法中，递归下降分析法属于 b 可选项有：

A、自左至右 B、自顶向下 C、自底向上 D、自右向左 38、一般程序设计语言的定义都涉及 A 三个方面。 ①语法 ②语义 ③语用 ④程序基本符号的确定可选项有：

A、①②③ B、①②④ C、①③④ D、②③④ 39、编译过程中,语法分析器的任务是 B 。

①分析单词是怎样构成的 ②分析单词串是如何构成语句和说明的 ③分析语句和说明是如何构成程序的 ④分析程序的结构可选项有:

A、②③ B、②③④ C、①②③ D、①②③④ 40、编译程序生成的目标程序 B 是机器语言的程序. 可选项有：

A、一定 B、不一定 C、无法判断 D、一定不

一、单项选择题（将正确答案的字母填入括号，每题1。5分，共30分） 1、一般程序设计语言的定义都涉及到（ 1.2.3)3个方面。（1)语法（2）语义（3）语用 (4)程序基本符号的确定 2、程序语言一般分为（ 1 ）和( 2 )。

(1)高级语言；（2）低级语言；（3）专用程序语言;(4)通用程序语言 3、面向机器语言指的是(

B ）。

分析方法。

A．用于解决机器硬件设计问题的语言 C．各种计算机系统都通用的语言

B．特定计算机系统所固有的语言 D．只能在一台计算机上使用的语言

4．面向机器语言的特点是（ D )。 A．程序的执行效率低，编制效率低,可读性差 B．程序的执行效率高，编制效率高，可读性强 C．程序的执行效率低,编制效率高，可读性强 D．程序的执行效率高，编制效率低，可读性差 5、程序设计语言常见的数据类型有:1。2.3.4

（1)数值型数据（2）逻辑数据（3）字符数据（4）指针类型 6、下列程序设计语言中是应用式语言的是：B A、PASCAL B、LISP C、VB D、PROLOG 7、任何语法结构都可以用（ C )来表示.

A、语法树 B、树 C、抽象语法树 D、二义文法树 8、字母表是符号的有穷集合,由（ C ）组成词和句子。 A、字符串 B、字符 C、符号 D、语言 9、下列符号是终结符的是（ A)。 A、c B、A C、S D、β

10、语法树用（ C )关系说明了句子中以操作符为核心的操作顺序，同时也说明了每一个操作符的操作对象.

A、上下 B、先后 C、层次 D、关联 11、循环语句的语法树为（ D ） A、 B、 C、 D、

12、表达式中间代码的生成可采用（ B ）。

A、三地址代码 B、四元式 C、三元式 D、间接三元式 13、下列文法中，赋值语句的文法是（ C ）。

A、 B、

C、 D、E→E op E 14、词法分析的任务是（ A ）

A、识别单词 B、分析句子的含义 C、识别句子 D、生成目标代码 15、常用的中间代码形式中不含( D )

A、三元式 B、四元式 C、逆波兰式 D、语法树 16、代码优化的目的是（ C ）

A、节省时间 B、节省空间 C、节省时间和空间 D、把编译程序进行等价转换 17、代码生成阶段的主要任务是（ C ）

A、把高级语言翻译成汇编语言 B、把高级语言翻译成机器语言

C、把中间代码变换成依赖具体机器的目标代码 D、把汇编语言翻译成机器语言 18、词法分析器的输入是（ B )

A、单词符号串 B、源程序 C、语法单位 D、目标程序 19、中间代码的生成所遵循的是（ C ）

A、语法规则 B、词法规则 C、语义规则 D、等价变换规则 20、编译程序是对（ D )

A、汇编程序的翻译 B、高级语言程序的解释并执行 C、机器语言的执行 D、高级语言的翻译 21、语法分析应遵循（ C ）

A、语义规则 B、语法规则 C、构词规则 D、等价变换规则 22、编译程序各阶段的工作都涉及到（ B ）

A、语法分析 B、表格管理、出错处理 C、语义分析 D、词法分析 23、编译程序工作时,通常有（ 1.2.3.4 ）阶段。

（1）词法分析（2）语法分析（3)中间代码生成（4)语义检查（5）目标代码生成 24、由文法的开始符经0步或多步推导产生的文法符号序列是 C 。

A、短语 B、句柄

C、句型

D、句子

25、产生正规语言的文法为 D 。 A、0型 B、1型

C、 2型 D、3型

26、对无二义性文法来说,一棵语法树往往代表了 D . （1）多种推导过程（4）仅一种推导过程

（2）多种最左推导过程

（5）一种最左推导过程

（3)一种最左推导过程

A、 B、(1）(3）（5) C、 D

27、如果文法G存在一个句子,满足下列条件之一时,则称该文法是二义文法。BCD a。该句子的最左推导与最右推导相同 b. 该句子有两个不同的最左推导 c。该句子有两棵不同的最右推导 d. 该句子有两棵不同的语法树 e。该句子的语法树只有一个

28、优化可生成( D ）的目标代码。

A、运行时间较短 B、占用存储空间较小 C、运行时间短且占用内存空间大 D、运行时间短且存储空间小

29、构造编译程序应掌握（ D )

A、源程序 B、目标程序 C、编译方法 D、以上三项都是 30、赋值语句x=a+b*c—d的逆波兰式为（ B）

A、xab+c*d-= B、xabc＊+d—= C、xabcd*+—= D、x=abc＊+d- 31、词法分析器的输出结果是（ C )

A、单词的种别编码 B、单词在符号表中的位置 C、单词的种别编码和自身值 D、单词自身值

《编译原理》期末试题（一）

一、是非题（请在括号内，正确的划√，错误的划×)(每个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、描述由正规式b＊(abb*)*(a｜ )定义的语言，并画出接受该语言的最简DFA。 2、证明文法E  E + id | id是SLR(1)文法。

5、下面C语言程序经非优化编译后,若运行时输入2，则结果是 area=12.566360, addr=—1073743076 经优化编译后，若运行时输入2，则结果是 area=12.566360, addr=-1073743068 请解释为什么输出结果有区别。

main（） {

float s， pi, r; pi=3。14159; scanf（\"％f”, ＆r）； printf（\"area=%f, addr=％d\\n\＊r, ＆r）;

}

6、描述由正规式ba(bba) b定义的语言，并画出接受该语言的最简DFA。 7、下面的文法产生代表正二进制数的0和1的串集： B  B 0 ｜ B 1 | 1 下面的翻译方案计算这种正二进制数的十进制值： B  B1 0 {B。val ：= B1。val  2 ｝ | B1 1 ｛B.val ：= B1。val  2 +1｝

｜ 1 ｛B.val ：= 1 ｝请消除该基础文法的左递归，再重写一个翻译方案，它仍然计算这种正二进制数的十进制值.

8、在C语言中,如果变量i和j都是long类型，请写出表达式&i和表达式&i＆j的类型表达式.为帮助你回答问题，下面给出一个程序作为提示，它运行时输出1。 main（）｛ long i, j； printf（“%d\\n”, ＆i&j)；｝

9、一个C语言的函数如下： func（i) long i； { long j； j = i – 1; func(j); ｝

下面左右两边的汇编代码是两个不同版本GCC编译器为该函数产生的代码。左边的代码在调用func之前将参数压栈,调用结束后将参数退栈.右边代码对参数传递的处理方式没有实质区别。请叙述右边代码对参数传递的处理方式并推测它带来的优点。 func： | func： pushl ％ebp | pushl ％ebp movl ％esp, ％ebp ｜ movl ％esp, %ebp subl ＄4, %esp ｜ subl ＄8，％esp movl 8(％ebp), %edx | movl 8(%ebp）, %eax decl ％edx | decl ％eax movl %edx， —4（％ebp）｜ movl ％eax, -4（%ebp） movl —4(％ebp)， %eax ｜ movl —4（％ebp)， %eax pushl %eax ｜ movl %eax，（％esp） call func ｜ call func addl ＄4，％esp ｜ leave leave | ret ret ｜

编译原理试卷八答案

1、由正规式b*(abb*）＊(a｜ ）定义的语言是字母表｛a， b｝上不含子串aa的所有串的集合。最简DFA如下：

start

b 1 11 b a 2

2、先给出接受该文法活前缀的DFA如下:

I0和I3都只有移

E E ·E E  E· 进项目,肯定不会引起

E ·E + id E  E·+ id 冲突；I2和I4都无移进

E ·id I1 项目并仅含一个归约

I0 项目，也肯定不会引起

+ 冲突;在I1中，E的后

id 继符号只有$，同第2个项目的展望符号“+\"E  E + id· E  E +·id id E  id· 不一样，因此I1也肯I4 I3 I2 定不会引起冲突。由此可以断定该文法是SLR(1）的。 3、语法制导定义如下。

S  id := E ｛ S.type ：= if (id.type = bool and E.type = bool） or (id。type = int and E.type = int)then type_ok else type_error ｝

E  E1 and E2 { E。type := if E1。type = bool and E2.type = bool then bool else type_error ｝

E  E1 + E2 ｛ E.type ：= if E1。type = int and E2.type = int then int else type_error ｝ E  E1 = E2 { E.type := if E1。type = int and E2.type = int then bool else type_error } E  id { E。type := lookup（id。entry）｝

4、对于函数f1，局部变量x声明的作用域是整个函数体，导致在函数体中不可能访问形式参数x。由于这是一个合法的C语言函数，因此编译器给出警告错误。

对于函数f2,由于局部变量x的作用域只是函数体的一部分，不会出现上述问题，因而编译器不报错。

5、使用非优化编译时,变量s， pi, r在局部数据区都分配4个字节的空间。使用优化编译时，由于复写传播，pi＊r*r 变成3.14159*r*r,pi=3.14159成为无用赋值而删去，函数中不再有pi的引用，因此不必为pi分配空间。类似地,s=3。14159＊r*r也是一个无用赋值(表达式要计算,但赋值是无用的），也不必为s分配空间。这样,和非优化情况相比，局部数据区少了8个字节，因此r的地址向高地址方向移动了8个字节。

6、正规式ba（bba) b体现的特点是，每个a的左边都有若干b，除非a是第一个字母。该正规式定义的语言是：至少含一个a，但不含子串aa的所有a和b的串集。最简DFA如下：

b 7、消除左递归后的文法： start 0 B  1 B

a b B  0 B ｜ 1 B ｜b  相应的翻译方案如下： a 2 1 B  1 ｛B。i := 1 }B｛B。val := B.val} B  0 ｛B1。i := B。i  2 } B1 ｛B.val := B1.val｝

| 1 ｛B1。i ：= B.i  2 +1} B1 ｛B.val ：= B1。val｝ |  ｛B。val := B.i｝

8、表达式＆i的类型表达式是pointer（long），表达式＆i&j的类型表达式是long。按照C语言的规定，指向同一个类型的两个指针可以相加减,它们值的差是它们之间的元素个数。 9、左边的编译器版本：一般只为局部变量分配空间.调用函数前，用若干次pushl指令将参数压栈，返回后用addl $n， %esp一次将所有参数退栈（常数n根据调用前做了多少次pushl来决定）. 右边的编译器版本：除了为局部变量分配空间外,同时还为本函数中出现的函数调用的参数分配空间，并且参数所用空间靠近栈顶。调用函数前，用movl指令将参数移入栈顶，调用结束后无需参数退栈指令。优点是每次函数调用结束后不需要执行addl $n, %esp指令，另外增加优化的可能性。

《编译原理》期末试题（三）

1、从优化的范围的角度，优化可以分哪两类？对循环的优化可以有哪三种？答：从优化的范围的角度，优化可以分为局部优化和全局优化两类；对循环的优化有三种：循环不变表达式外提、归纳变量删除与计算强度削减。 2、写出表达式a=b*c+b＊d对应的逆波兰式、四元式序列和三元式序列。答：逆波兰式： abc*bd*+：= 四元式序列：

三元式序列： OP ARG1 ARG2

（1) （＊ b， c ） (2）（＊ b, d )

（1) （*， b， c, t1)

（2） (＊， b， d, t2) (3) （+， t1， t2,t3) (4) （:=, t3， /， a）

（3）（+ （1）， (2）） (4) (:= (3)， a)

3、对于文法G(S)：

答：1)

2）短语: Ma), （Ma）， b(Ma)b

直接短语： Ma）句柄: Ma）

b S M b T L M a ) 三、设有字母表｛a,b｝上的正规式R=（ab|a）＊。 ( 13

解：（1)

2 - 0 ε a 1 a b ε + 3

(2）将（1）所得的非确定有限自动机确定化

ε a b —0 1 1 2 +3 3 12 1 2 +

-+ a 0 b a 1 + a

（3)对(2）得到的DFA化简，合并状态0和2 为状态2：

2 -+ b a 1 +

（4）令状态1和2分别对应非终结符B和A

a 四、设将文法G改写成等价的LL(1）文法，并构造预测分析表。

G：S→S*aT|aT｜＊aT； T→+aT|+a

解：消除左递归后的文法G'： S→aTS’｜＊aTS'

S’→*aTS’|ε

T→+aT｜+a

提取左公因子得文法G’’： S→aTS'|＊aTS’

S’→*aTS’｜ε T→+aT’

T'→T｜ε Select(S→aTS’)=｛a｝ Select(S→*aTS’）={＊｝

Select（S→aTS’)∩Select（S→*aTS’）=Ф Select（S’→＊aTS’）={＊}

Select（S’→ε）=Follow（s’)={＃｝

Select（S’→*aTS’)∩Select（S’→ε)= Ф Select（T→+aT'）=｛+}

Select(T’→T)=First（T) =｛+}

Select(T’→ ε）=Follow（T’）={*，＃}

Select（T’→T）∩Select(T’→ε)= Ф 所以该文法是LL（1）文法. 预测分析表： + a # ＊ S →＊aTS’ S’ →＊aTS’ T T’ → ε →aTS’ →ε → ε →+aT’ →T 6设文法G 为: S→A；A→BA｜ε；B→aB｜b

解：（1）拓广文法G’:(0） S’→S （1） S→A (2） A→BA(3) A→

ε(4) B→aB (5) B→b ； FIRST(A) = ｛ε， a， b｝;FIRST(B) = {a， b}

构造的DFA 如下:

项目集规范族看出，不存在冲突动作。∴该文法是LR（1)文法。

（2） LR(1）分析表如下:

(3)输入串abab 的分析过程为：

简答题 3、设有文法G［S]: S→S(S)S｜ε,该文法是否为二义文法？说明理由. 答：是二义的,因为对于（）(）可以构造两棵不同的语法树。 S S

S （ S ） S S ( S ） S ε ε S ( S ) S S （ S ) S ε ε ε ε ε ε ε ε

五、给定文法G[S]：

构造相应的最小的DFA 。

解：先构造其NFA：用子集法将NFA确定化：将S、A、Q、BZ、DZ、D、B重新命名，分别

用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。

令P0＝(｛0,1，2，5,6}，{3,4｝）用b进行

S A 分割：

P1＝(｛0，5， 6｝,{1,2｝,{3,4｝）再用

b进行分割：

P2＝（｛0｝，｛5, 6｝，{1，2｝，{3,4})

再用a、b 进行分割,仍不变。

再令{０｝为A，｛1,2｝为B，｛3,4｝为C,{5,6｝为D。最小化为右上图。

Q BZ DZ D B a A A Q Q A A Q b Q BZ DZ D B B D 六、对文法G(S）：S → a | ^ | （T）;T → T，S | S

答：（1)

（2）是算符优先文法，因为任何两个终结符之间至多只有一种优先关系.(2分） (3) 给出输入串(a，a）#的算符优先分析过程. a ^ a ^ （ ) ，＃〉 > 〉 > > > = （〈 < < = < ） , < < 〈〉 > # < < 〈〉〉〉步骤 1 2 3 4 5 6 7 8 9 10 栈 # ＃( ＃(a #(N #（N，＃（N,a #（N,N #（N #(N）＃N 当前输入字符剩余输入串动作 ( a,a# ＃〈( 移进 a ,a）＃（, 归约 , a）＃（<, 移进 a ）# ，) 归约）＃，>）归约） # (=) 移进＃ )〉＃归约 # 接受《编译原理》期末试题(四）

二、构造下列正规式相应的DFA(用状态转换图表示）(15)

（1） 1（0 ｜ 1）＊1 （2） 0＊10＊10＊10＊1 0,1 （3） letter（letter | digit）＊

（1）（2)

(3）

1 0 0 2 0 1 1 2 letter 1 3 0 1 3 17

0 1 4 1 5

letter 1 2 digit 三、给出下面语言的相应文法:（15） L1=｛an bn | n≥1｝ L2={anbm+nam ｜ n≥1，m≥0｝

G1： G1：四、对下面的文法G: SA→aAb |ab S→AB →a ｜ b ｜（T） A→aAb | ab T→T，S ｜ S

B→；bBa | ε （1) 消去文法的左递归,得到等价的文法G2

(2）判断文法G2是否LL(1）文法，如果是，给出其预测分析表。(15） G2:

S→a ｜ b ｜（T)

T→ ST’