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

一、单项选择题
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 ）
A．xyx B．(xyx）＊ c．xnyxn（n≥0) d．x＊yx＊
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．用于解决机器硬件设计问题的语言 B．特定计算机系统所固有的语言
C．各种计算机系统都通用的语言 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） 多种推导过程 （2） 多种最左推导过程 （3)一种最左推导过程
（4）仅一种推导过程 （5）一种最左推导过程
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｜ e)定义的语言，并画出接受该语言的最简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", s=pi*r＊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 ｜
编译原理试卷八答案

start
1
a
b
b
2

1、由正规式b*(abb*）＊(a｜ e）定义的语言是字母表｛a， b｝上不含子串aa的所有串的集合。最简DFA如下：
2、先给出接受该文法活前缀的DFA如下:
E¢ ®·E
E ®·E + id
E ®·id
I0
E¢ ® E·
E ® E·+ id
I1
E ® id·
I2
E
id
+
E ® E +·id
I3
E ® E + id·
I4
id

I0和I3都只有移进项目,肯定不会引起冲突；I2和I4都无移进项目并仅含一个归约项目，也肯定不会引起冲突;在I1中，E¢的后继符号只有$，同第2个项目的展望符号“+"不一样，因此I1也肯定不会引起冲突。由此可以断定该文法是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如下：

start
2
a
b
b
1
0
a
b

7、 消除左递归后的文法：
B ® 1 B¢
B¢ ® 0 B¢ ｜ 1 B¢ ｜ e
相应的翻译方案如下：
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｝
| e ｛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, t1) （1) （＊ b， c ）
（2） (＊， b， d, t2) (2） （＊ b, d )
(3) （+， t1， t2,t3) （3） （+ （1）， (2））
(4) （:=, t3， /， a） (4) (:= (3)， a)
3、对于文法G(S)：
S
b
M
(
T
M
a
b
L
)
答：1)
2） 短语: Ma), （Ma）， b(Ma)b
直接短语： Ma） 句柄: Ma）
三、 设有字母表｛a,b｝上的正规式R=（ab|a）＊。
解：（1)
0
1
2
3
b
a
a
ε
ε
-
+

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

ε
a
b
—0
1

1
3
12

2

1
+3

a
b
-+013
123

+123
123
13
+13
123

0
1
2
a
a
b
a
-+
+
+

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

（4）令状态1和2分别对应非终结符B和A
G： A→aB|a|ε； B→aB｜bA|a｜b|ε；可化简为:G: A→aB|ε；B→aB｜bA｜ε

四、 设将文法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’

→aTS’

S’
→＊aTS’

→ε
T

→+aT’

T’
→ ε
→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]：
S→aA｜bQ； A→aA|bB|b;B→bD|aQ ；Q→aQ|bD|b；D→bB|aA ；E→aB|bF
F→bD｜aE｜b
构造相应的最小的DFA 。
解：先构造其NFA： 用子集法将NFA确定化：

a
b
S
A
Q
A
A
BZ
Q
Q
DZ
BZ
Q
D
DZ
A
B
D
A
B
B
Q
D
将S、A、Q、BZ、DZ、D、B重新命名，分别用0、1、2、3、4、5、6表示。因为3、4中含有z，所以它们为终态。

a
b
0
1
2
1
1
3
2
2
4
3
2
5
4
1
6
5
1
6
6
2
5
令P0＝(｛0,1，2，5,6}，{3,4｝）用b进行分割：
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。
最小化为右上图。
六、 对文法G(S）：S → a | ^ | （T）;T → T，S | S
答：（1)

a
^
（
)
，
＃
a

〉
>
〉
^

>
>
>
（
〈
<
<
=
<

）

〉
〉
〉
,
<
<
〈
〉
>

#
<
<

〈

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

)〉＃ 归约
10
＃N
#

接受
《编译原理》期末试题(四）
二、构造下列正规式相应的DFA(用状态转换图表示）(15)
（1） 1（0 ｜ 1）＊1
0,1
（2） 0＊10＊10＊10＊1
（3） letter（letter | digit）＊
3
1
0

2
1
（1）
0
0

5
1
（2)
1
0
4
1
3
0
2
1
1

letter
(3）

2
letter

1

digit

三、给出下面语言的相应文法:（15）
L1=｛an bn | n≥1｝ L2={anbm+nam ｜ n≥1，m≥0｝
G1：
S→AB
A→aAb | ab
B→bBa | ε
G1：
A→aAb |ab

四、对下面的文法G:
S→a ｜ b ｜ （T）
T→T，S ｜ S
（1) 消去文法的左递归,得到等价的文法G2；
(2） 判断文法G2是否LL(1）文法，如果是，给出其预测分析表。(15）
G2:
S→a ｜ b ｜ （T)
T→ ST’
T’→，S T’ ｜ ε
G2是LL（1）文法.

a
b
（
）
,
＃
S
S→a
S→b
S→（T)

T
T→ ST’
T→ ST'
T→ ST’

T’

T’→ ε
T'→，S T