编译原理考题
第一章引论
1. 解释下列术语：编译程序、编译程序的前端和后端
答：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器
语言，则此翻译程序称为编译程序。
（2）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与
目标机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶
段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符
号表管理等工作。
（3）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，
即目标代码生成，以及相关出错处理和符号表操作。
2.一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。答案：
一个典型的编译程序通常包含 8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下：
（1）词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。
（2）语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。
（3）语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。
（4）中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。
（5）中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。
（6）目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。
（7）表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。
（8）错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。
4.对下列错误信息，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分析、
代码生成）报告的。
（1）else 没有匹配的if
（2）数组下标越界
（3）使用的函数没有定义
（4）在数中出现非数字字符
答案：
（1）语法分析
（2）运行时或者语义分析
（3）语法分析
（4）词法分析
第三章文法和语言
1.文法G＝({A,B,S},{a,b,c},P,S)其中P 为：
S→Ac|aB
A→ab
B→bc
写出L(G[S])的全部元素。
答案：L(G[S])={abc}
2.文法G[N]为：
N→D|ND
D→0|1|2|3|4|5|6|7|8|9
G[N]的语言是什么？
答案：长度至少为 1 的任意的数字串。
3.为只包含数字、加号和减号的表达式，例如9-2＋5，3-1，７等构造一个文法。
答案：
G[S]:
S->S+D|S-D|D
D->0|1|2|3|4|5|6|7|8|9
4.已知文法G[Z]：
(1)Z：：= aZb
(2)Z：：= ab
写出L(G[Z])的全部元素。
答案：L(G[Z]) = { a n b n | n≥1 }
5.写一文法，使其语言是偶正整数的集合。要求：
(1) 允许0 打头；
(2)不允许0 打头。
答案：
(1)允许0 开头的偶正整数集合的文法
E→NT|D
T→NT|D
N→D|1|3|5|7|9
D→0|2|4|6|8
(2)不允许0 开头的偶正整数集合的文法
E→NT|D
T→FT|G
N→D|1|3|5|7|9
D→2|4|6|8
F→N|0
G→D|0
8.文法G[S]为：
S→Ac|aB
A→ab
B→bc
该文法是否为二义的？为什么？
答案：由于对于文法 G[S] 的一个句子abc ，存在以下两个不同的最右推导：
最右推导 1：
最右推导 2：
所以该文法为二义文法。
11.令文法G[E]为：
E→T|E+T|E-T
T→F|T*F|T/F
F→(E)|i
证明E+T*F 是它的一个句型，指出这个句型的所有短语、直接短语和句柄。
答案：按照句型的定义，由于存在推导，所以是该文法的一个句型。通过构造该句型的语法树，可以直观地看出句型的所有的短语、直接短语和句柄。该句型的语法树如下：
所有的短语：
所有的直接短语：
句柄：
13.一个上下文无关文法生成句子abbaa 的推导树如下：
(1)给出串abbaa 最左推导、最右推导。
(2)该文法的产生式集合P 可能有哪些元素？
(3)找出该句子的所有短语、直接短语、句柄。
(1)最左推导：
最右推导：
(2) 该文发的产生式集合 P 可能的元素：、、、、、。
(3) 所有短语：abbaa、a、bb、aa、ε、b；
所有直接短语：a、ε、b；
句柄：a。
第四章词法分析
2.已知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 确定化：
将x、z、xz、y、xy、xyz 重新命名，分别用A、B、C、D、E、F 表示。因为B、C、F
中含有z，所以它为终态。
DFA 的状态图：
3.将下图确定化：
答案：
用子集法将NFA 确定化：
0 1
S VQ QU
VQ VZ QU
QU V QUZ
VZ Z Z
V Z -
QUZ VZ QUZ
Z Z Z
重新命名状态子集，令VQ 为A、QU 为B、VZ 为C、V 为D、QUZ 为E、Z 为F。
0 1
-S A B
A C B
B D E
+C F F
D F -
+E C E
+F F F
DFA 的状态图：
7.给文法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 为：
a b
-S A Q
A A B,Z
B Q D
Q Q D,Z
D A B
E B F
F E D,Z
+Z - -
确定化：
a b
-S A Q
A A BZ
Q Q DZ
+BZ Q D
+DZ A B
D A B
B Q D
M = {S,A,Q,D,B} ∪ {BZ,DZ}
{S,A,Q,D,B}按照 b 可划分为 {S,D,B}∪{A,Q} M = {S,D,B} ∪ {A,Q} ∪ {BZ,DZ}
{S,D,B}按照 b 可划分为 {S}∪{D,B}
M = {S} ∪ {D,B} ∪ {A,Q} ∪ {BZ,DZ}
已不能再划分，所以，状态 D与 B、A 与 Q、BZ 与 DZ 分别为等价状态。
删除D、Q 和 DZ：
a b
-S A Q→A
A A BZ
Q Q DZ
+BZ Q→A D→B
+DZ A B
D A B
B Q→A D→B
8.给出下述文法所对应的正规式：
S→0A|1B
A→1S|1
B→0S|0
答案：
11.一种证明两个正则表达式等价的方法，那就是构造它们的最小 DFA，表明这两个 DFA 是一样的（当然状态名可以不同）。使用此方法，证明下面的正则表达式是等价的。
(1) (a|b)*
(2) (a*|b*)*
(3) ((|a)b*)*
解：（1）
（2）
a b
±SAB SAB SAB
（3）
a b
±SA SA SA
第五章自顶向下语法分析方法
例题1 已知文法 G[S]：
S → aH
H → aMd | d
M → Ab | ε
A → aM | e
①判断 G[S] 是否为 LL(1) 文法，若是，构造相应的预则分析表。
②若 G[S] 为 LL(1) 文法，给出输入串 aaabd# 的分析过程，并说明该串是否为 G[S] 的句子。解：①
【第 1 步】求出能推导出ε的非终结字符。
非终结字符S H M A
能否推导出ε不可不可可不可
【第 2.1 步】计算每一个终结或非终结字符 X 的 FIRST 集合：
First(S) = {a}
First(H) = {a,d}
First(M) = first(A)∪{ε} = {a,e,ε}
First(A) = {a,e}
【第 2.2 步】计算每一个产生式右部的 FIRST 集合：
First(aH) = {a}
First(aMd) = {a}
First(d) = {d}
First(Ab) = first(A) = {a,e}
First(ε) = {ε}
First(aM) = {a}
First(e) = {e}
【第 3 步】计算每一个非终结字符 X 的 FOLLOW 集合：
Follow(S) = {#}
Follow(H) = follow(S) = {#}
Follow(M) = {d}∪follow(A) = {b,d}
Follow(A) = {b}
【第 4 步】计算每一个产生式的 SELECT 集合：
Select(S→aH) = {a}
Select(H→aMd) = {a}
Select(H→d) = {d}
Select(M→Ab) = first(Ab) = {a,e}
Select(M→ε) = follow(M) = {b,d}
Select(A→aM) = {a}
Select(A→e) = {e}
【第 5 步】判别是否为 LL(1) 文法：
由于：
Select(H→aMd) ∩ Select(H→d) = Φ
Select(M→Ab) ∩ Select(M→ε) = Φ
Select(A→aM) ∩ Select(A→e) = Φ
所以，该文法为 LL(1) 文法。
a b d e #
S S→aH
H H→aMd H→d
M M→Ab M→εM→εM→Ab
A A→aM A→e ②
步骤分析栈
剩余输入串
（第 1 个字符为当前输入字符）
推导所用的产生式或匹配
1 #S aaabd# S→aH
2 #Ha aaabd# 匹配 a
3 #H aabd# H→aMd
4 #dMa aabd# 匹配 a
5 #dM abd# M→Ab
6 #dbA abd# A→aM
7 #dbMa abd# 匹配 a
8 #dbM bd# M→ε
9 #db bd# 匹配 b
10 #d d# 匹配 d
11 # # 接受（分析成功）
例题2.文法 G[S]：
①试对 G[S] 进行改写，并判断改写后的文法是否为 LL(1) 文法？
②通过这个例子，能够说明什么？
解：①文法存在间接左递归，应该先将间接左递归转换为直接左递归。有以下两种转换方法：
转换方法 1：将代入中的 A，将间接左递归转换为直接左递归后，文法转换为：消除关于 S 的直接左递归后，文法转换为：
由于
所以，改写以后的文法为 LL(1) 文法。
转换方法 2：
将代入中的 S，将间接左递归转换为直接左递归后，文法转换为：
消除关于 A 的直接左递归后，文法转换为：
由于
所以，改写以后的文法不是 LL(1) 文法。
②这个例子表明：
消除左递归后，文法不一定能够成为 LL(1) 文法，无左递归只是 LL(1) 文法的必要条件。以不同的消除左递归方法得到的各文法，有些是 LL(1) 文法，有些则不是。
1.★★★
对文法G[S]
S→a|∧|(T)
T→T,S|S
(1) 给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。
(2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。
(3) 经改写后的文法是否是LL(1)的?给出它的预测分析表。
(4) 给出输入串(a,a)#的分析过程，并说明该串是否为G 的句子。
答案：
（1）
附：第 2 个句子的语法树，其中红色边框节点表示叶子。
（2）文法中存在左递归，故 G 不是 LL(1) 文法。消除左递归后，文法为：
显然，所以改写以后的文法是LL(1)文法。
（3）
（4）
2.对下面的文法G：
（1）计算每个非终结字符的 FIRST 集和 FOLLOW 集。
（2）证明此文法为 LL(1) 文法。
（3）构造预测分析表。
解：
（1）
非终结字符 E E’T T’ F F’P 能否推导出ε不可可不可可不可可不可判断次序⑦①⑥②⑤③④
由于
First(E) = first(T)
First(E’) = {+,ε}
First(T) = first(F)
First(T’) = first(T)∪{ε}
First(F) = first(P)
First(F’) = {*,ε}
First(P) = {(,a,b,∧}
所以
First(E) = first(T) = first(F) = first(P) = {(,a,b,∧}
First(E’) = {+,ε}
First(T) = first(F) = first(P) = {(,a,b,∧}
First(T’) = first(T)∪{ε} = {(,a,b,∧,ε}
First(F) = first(P) = {(,a,b,∧}
First(F’) = {*,ε}
First(P) = {(,a,b,∧}
Follow(E) = follow(E’)∪{)}∪{#} = follow(E’)∪{),#}
Follow(E’) = follow(E)
Follow(T) = [(first(E’)-{ε})∪follow(E)]∪follow(T’) = {+}∪follow(E)∪follow(T’)
Follow(T’) = Follow(T)
Follow(F) = [(first(T’)-{ε})∪follow(T)] = {(,a,b,∧}∪follow(T)
Follow(F’) = Follow(F)∪Follow(F’) = Follow(F)
Follow(P) = (first(F’)-{ε})∪follow(F) = {*}∪follow(F)
第 1 次迭代，设 Follow(E) = {),#}
Follow(E’) = follow(E) = {),#}
Follow(T) = {+}∪follow(E)∪follow(T’) = {+,),#}∪follow(T’)
再设 Follow(T) = {+,),#}
Follow(T’) = Follow(T) = {+,),#}
Follow(F) = {(,a,b,∧}∪follow(T) = {(,a,b,∧,+,),#}
Follow(F’) = Follow(F) = {(,a,b,∧,+,),#}
Follow(P) = {*}∪follow(F) = {(,a,b,∧,+,*,),#}
第 2 次迭代
Follow(E) = follow(E’)∪{),#} = {),#}∪{),#} = {),#} 与第1次迭代结果相同
Follow(E’) = follow(E) = {),#} 与第1次迭代结果相同
Follow(T) = {+}∪follow(E)∪follow(T’) = {+}∪{),#}∪{+,),#} = {+,),#} 与第1次迭代结果相同Follow(T’) = Follow(T) = {+,),#} 与第1次迭代结果相同
Follow(F) = {(,a,b,∧}∪follow(T) = {(,a,b,∧}∪{+,),#} = {(,a,b,∧,+,),#} 与第1次迭代结果相同Follow(F’) = Follow(F) = {(,a,b,∧,+,),#} 与第1次迭代结果相同
Follow(P) = {*}∪follow(F) = {*}∪{(,a,b,∧,+,),#} = {(,a,b,∧,+,*,),#} 与第1次迭代结果相同
由于两次迭代结果相同，故迭代结束。
（2）
由于任何具相同左部的产生式的 select 集的交集均为空，所以，该文法为 LL(1) 文法。
（3）
第六章自底向上优先分析
例题1.已知布尔表达式文法 G[B] 为：
其中：o 表示 or；a 表示 and；n 表示 not；t 表示 true；f 表示 false。（1） G[B] 是否为算符优先文法？
（2）若 G[B] 是算符优先文法，给出串 ntofat 的分析过程。
（1）
优先关系：
o a n ( ) t f #
o > < < < > < < >
a > > < < > < < >
n > > < < > < < >
( < < < < = < <
) > > > >
t > > > >
f > > > >
# < < < < < < =
（2）
步骤分析栈S 优先关系
剩余输入串
（第1个字符为当前输入字符）
动作
1 #< n tofat# 移入
2 #n< t ofat# 移入
3 #n t> o fat# 归约
4 #n N > o fat# 归约
5 #N < o fat# 移入
6 #N o< f at# 移入
7 #No f> a t# 归约
8 #N o N < a t# 移入
9 #NoN a< t# 移入
10 #NoN a t > #归约
11 #NoN a N > #归约
12 #N o N > #归约
13 #N = #acc
第1题和第2题结合★★★★★★★
已知文法G[S]为：
S→a|∧|(T)
T→T,S|S
（2）构造 G[S] 的优先关系矩阵，并说明该文法是否为算符优先文法。（3）计算 G[S] 的优先函数。
（4）给出输入串 (a,a) 和 (a,(a,a)) 的算符优先分析过程。
（5）给出输入串 (a,a) 和 (a,(a,a)) 的最右推导和规范归约过程。（6）根据（4）和（5），说明算符优先归约和规范归约的区别。
解：（1）
（2）
a ^ ( ) , #
a > > >
^ > > >
( < < < = <
) > > >
, < < < > >
# < < < =
（3）
a ^ ( ) , #
f 2 2 1 2 2 1
g 3 3 3 1 1 1
（4）
步骤分析栈S
优先关
系
剩余输入串
1 # < (a,a)#
2 #( < a,a)#
3 #(a > ,a)#
4 #(N < ,a)#
5 #(N, < a)#
6 #(N,a > )#
7 #(N,N > )#
8 #(N = )#
9 #(N) > #
10 #N = # 步
骤
分析栈S
优先关
系
剩余输入串
1 # < (a,(a,a))#
2 #( < a,(a,a))#
3 #(a > ,(a,a))#
4 #(N < ,(a,a))#
5 #(N, < (a,a))#
6 #(N,( < a,a))#
7 #(N,(a > ,a))#
8 #(N,(N < ,a))#
9 #(N,(N, < a))#
10 #(N,(N,a > ))#
11 #(N,(N,N > ))#
12 #(N,(N = ))#
13 #(N,(N) > )#
14 #(N,N > )#
15 #(N = )#
16 #(N) > #
17 #N = #
（5）
（6） 区别在于：算符优先分析是将句型中的句柄（实际上是最左素短语）归约为一个任意的非终结字符，因而不存在单非终结字符的归约，所以归约速度要快于规范归约 。
第七章 LR 分析 例题1.设文法 G[S] 为：
（1）该文法是否为SLR(1)文法？ （2）若是，构造其 SLR(1) 分析表。 （3）给出输入串 baab 的分析过程。
解：得到该文法的拓广文法 G'[S'] 如下，
然后构造该文法的 LR(0) 项目集规范族：
I0 和 I5 均存在以下的移入-归约冲突：
由于所的冲突都可以由 SLR(1) 解决，所以该文法为 SLR(1) 文法。 SLR(1) 分析表 状态 ACTION GOTO a b # S A B 0 S3 r3
r3
1 2 1
acc
2 r5 S5 r5 4
3 r5 S5 r5 6
4 r1
5 S3 r3 r3 7
6 S8
7 S9
8 r2 r2
9 r4 r4
对输入串 baab 的分析过程
步骤状态栈符号栈输入串ACTION GOTO
1 0 # baab# r3 2
2 02 #A baab# S5
3 025 #Ab aab# S3
4 0253 #Aba ab# r
5 6
5 0253
6 #AbaB ab# S8
6 025368 #AbaBa b# r2 7
7 0257 #AbA b# S9
8 02579 #AbAb # r4 4
9 024 #AB # r1 1
10 01 #S # acc
例题2.证明文法 G[S] 为 SLR(1) 文法，并给出其分析表；求 LR(1) 的初始项目集。
解：G[S] 的拓广文法 G'[S'] 为：
存在冲突的项目集使用 SLR(1) 解决冲突
Follow(S’)={#}
Follow(S’)∩{;}=Φ
Follow(S)=follow(S’)∪{;,)}={#,;,)}
Follow(S)∩{b}=Φ
Follow(M)=follow(S)∪{b)}={#,;,),b}
Follow(M)∩{(}=Φ
Follow(S)={#,;,)}
Follow(S)∩{b}=Φ
Follow(M)= {#,;,),b}
Follow(M)∩{(}=Φ
SLR(1) 分析表
状态
ACTION GOTO
; b ( ) # S M D
0 r6 r6 r6 r6 r6 1 2 3
1 S4 acc
2 r2 S5 r2 r2
3 r
4 r4 S6 r4 r4
4 r6 r6 r6 r6 r6 7 3
5 r
6 r6 r6 r6 r6 8
6 r6 r6 r6 r6 r6 9 2 3
7 r1 S5 r1 r1
8 r3 r3 S6 r3 r3
9 S10
10 r5 r5 r5 r5 r5
****如果第2问求LR（1）项目集规范族中的Io,则写最后一个图
1.已知文法
A→aAd|aAb|ε
判断该文法是否是SLR(1)文法，若是构造相应分析表，并对输入串ab#给出分析过程。解：
在 I0 和 I2 中均存在以下的移入-归约冲突
计算 Follow(A) = {b,d,#}，
由于
所以，该文法为 SLR(1) 文法。
SLR(1)分析表
状态
ACTION GOTO a b d # A
0 S2 r3 r3 r3 1
1 acc
2 S2 r
3 r3 r3 3
3 S5 S4
4 r1 r1 r1
5 r2 r2 r2
对输入串 ab 的分析过程
步骤状态栈符号栈输入串ACTION GOTO
1 0 # ab# S2
2 02 #a b# r
3 3
3 023 #aA b# S5
4 023
5 #aAb # r2 1
5 01 #A # acc
2.定义二进制数的文法如下：
（1）为该文法构造 LR 分析表，并说明属于哪类 LR 分析表。（2）给出 101.110 的分析过程。
解：为避免与项目中的点混淆，以下拓广文法中的 d 表示小数点。
在 I2 中存在移入-归约冲突，
计算 follow(S)={#}，
由于
所以 I2 中的冲突可由 SLR(1) 解决。
在 I8 中也存在移入-归约冲突，
由于，
所以 I8 中的冲突也可由 SLR(1) 解决。SLR(1)分析表
状态
ACTION GOTO
0 1 . # S L B
0 S4 S5 1 2 3
1 acc
2 S4 S5 S6 r2 7
3 r
4 r4 r4 r4
4 r
5 r5 r5 r5
5 r
6 r6 r6 r6
6 S4 S5 8 3
7 r3 r3 r3 r3
8 S4 S5 r1 7
对输入串 101.110 的分析过程
步骤状态栈符号栈输入串ACTION GOTO
1 0 # 101.110# S5
2 05 #1 01.110# r6 3
3 03 #B 01.110# r
4 2
4 02 #L 01.110# S4
5 024 #L0 1.110# r5 7
6 02
7 #LB 1.110# r3 2
7 02 #L 1.110# S5
8 025 #L1 .110# r6 7
9 027 #LB .110# r3 2
10 02 #L .110# S6
11 026 #L. 110# S5
12 0265 #L.1 10# r6 3
13 0263 #L.B 10# r4 8
14 0268 #L.L 10# S5
15 02685 #L.L1 0# r6 7
16 02687 #L.LB 0# r3 8
17 0268 #L.L 0# S4
18 02684 #L.L0 # r5 7
19 02687 #L.LB # r3 8
20 0268 #L.L # r1 1
21 01 #S # acc
编译原理期末考试习题及答案
一、填空题|（每题4分，共20分） 1. 乔母斯基定义的3型文法（线性文法）产生式形式 A→Ba|a,或A→aB|a，A，B∈Vn, a,b∈Vt 。 2.语法分析程序的输入是单词符号，其输出是语法单位。 3 型为 B → .aB 的LR（0）项目被称为移进项目，型为 B → a.B 的LR（0） 项目被称为待约项目， 4.在属性文法中文法符号的两种属性分别为继承属性和综合属性。 5、运行时存贮管理方案有静态存储分配、动态存储分配和堆式存储分配和方案。 二.已知文法 G(S) (1) E → T | E+T (2) T → F | F*F (3) F →（E）| i （1）写出句型（T*F+i）的最右推到并画出语法树。（4分） （2）写出上述句型的短语，直接短语和句柄。（4分） 答：（1）最右推到（2分） E ==> T ==> F ==> (E) ==> (E+T) ==> (E+F) ==> (E+i) ==> (T+i) ==> (T*F+i) (2) 语法树（2分） （3）（4分） 短语：（T*F+i），T*F+i ，T*F ， i 直接短语：T*F ， i 句柄：T*F 三. 证明文法G(S) ：S → SaS |ε是二义的。（6分） 答：句子aaa对应的两颗语法树为：
因此，文法是二义文法 四.给定正规文法G（S）： (1) S → Sa | Ab |b (2) A → Sa 请构造与之等价的DFA。（6分） 答：对应的NFA为：（6分） 状态转换表： a b {F} Φ{S} {S} {S,A} Φ {S,A} {S,A} {S} 五. 构造识别正规语言b*a(bb*a)*b* 最小的DFA（要求写出求解过程）。（15分）答：（1）对应的NFA（5分） a b {0} {1，3} {0} {1,3} Φ{2，3} {2,3} {1,3} {2,3} （5分） 六. 已知文法G(S) : (1) S → ^ | a | (T) (2) T → T,S | S 试：（1）消除文法的左递归；（4分） （2）构造相应的first 和 follow 集合。（6分） 答：（1）消除文法的左递归后文法 G’（S）为： (1) S → ^ | a | (T)
编译原理试题
中间语言与语法制导翻译 重点与难点 重点：语法制导翻译的基本思想，属性文法，翻译模式，说明语句的翻译方案。 三地址码，各种语句的目标代码结构、属性文法与翻译模式。 难点：属性的意义，对综合属性，继承属性，固有属性的理解，属性计算，怎么通过属性来表达翻译。布尔表达式的翻译，对各种语句的目标代码结构、属性文法与翻译模式的理解。 基本要求 掌握语法制导翻译的基本思想，属性文法，综合属性，继承属性，固有属性，属性计算，S_属性文法，L_属性文法，说明语句的翻译方案，翻译模式、属性文法的实现掌握中间语言与语义分析的基本概念；熟练掌握语法（结构）树、三地址代码、赋值与控制语句的翻译、说明语句的翻译；掌握组合数据说明的翻译、过程调用翻译。 例题解析 例1 给定文法 E --> T { R.i := T.p } R { E.p := R.s } R --> addop T { R1.i := mknode( addop.val, R.i, T.p ) } R { R.s := R1.s } R --> { R.s := R1.s } T --> ( E ) { T.p := E.p } T --> id { T.p := mkleaf( id, id.entry ) } T --> num { T.p := mkleaf( num, num.val ) } (1) 指出文法中的各非终结符具有哪些综合属性和哪些继承属性 ⑵画出按本翻译模式处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树 【解】 (1)E的综合属性 p，R的继承属性i，综合属性s；T的综合属性p (2) 处理表达式 a + 20 + ( b - 10 ) 时所生成的语法树如下 + （NUM, 20） - ( ID, b) (NUM, 10) 例2 定义一个计算器的属性文法,完成一个输入表达式值的计算和显示, 【解】计算器的文法 L → E
编译原理期末复习
编译原理期末复习 鉴于编译原理马上就要期末考试，我将手中集中的一些资料上的题目进行了整理归类，每种类型题目给出了所涉及到的基本知识，然后对每类题目中的第一道例题进行了做法进行了讲解，剩下的例题请给大家作为练习，答案也都给出，希望对大家复习有所帮助，最后由于时间很紧，整理的有些仓促，整理中难免有遗漏或错误，请大家见谅。 注：下面出现的字母中，若无特别说明，小写英文字母为终结符，大写英文字母为非终结符，希腊字母为终结符与非终结符的任意组合。 1、简答题（或者名词解释） 下面涉及到的概念中，加下划线的都是在以往一些试卷中出现的原题，务必掌握。 注：这类题目老师说答案不会超过一百个字，否则写的再多也不给分，有些点到即可，不要重复啰嗦。（1）简述编译程序的概念及其构成 答：1）编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序。 2)构成： （2）简述词法分析阶段的主要任务（也有可能问语法分析阶段主要任务）答：词法分析的任务是输入源程序，对源程序进行扫描，识别其中的单词符号，把字符串形式的源程序转换成单词符号形式的源程序。 语法分析的主要任务是对输入的单词符号进行语法分析（根据语法规则进行推导或者归约），识别各类语法单位，判断输入是不是语法上正确的程序 (3) 简述编译程序的构造过程（这个大家看看，是对（1）和（2）的综合） 答：1）构造词法分析器：用于输入源程序进行词法分析，输出单词符号； 2）构造语法分析器：对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序 3）构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。 4）构造优化器：对中间代码进行优化。 5) 构造目标代码生成器：把中间的代码翻译成目标程序。 6) 构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况。 7)构造错误处理程序：对出错进行处理。 (4) 说明编译和解释的区别： 1)编译要程序产生目标程序，解释程序是边解释边执行，不产生目标程序； 2)编译程序运行效率高而解释程序便于人机对话。 （5）文法：描述语言语法结构的形式规则，一般用一个四元式表示： G=(V T，V N，S，P)，其中V T：终结符集合(非空) V N：非终结符集合(非空)，且V T ?V N=? S：文法的开始符号，S?V N P：产生式集合(有限)。
编译原理期末考题
2010-2011第一学期期末试题《山东理工大学》 一．（15） 1.乔姆斯基把文法分成__4__种类型，在编译原理中用来描述程序设计语言词法结构的___文法，用来描述程序设计语言语法结构的是______文法。 2.一个上下文无关文法G包括四个组成部分：一组终结符号，一组______，一个开始符号以及一组______。 3.自上而下语法分析法会遇到的主要问题有______和______。 4.最右推导也称______，最右推导的逆过程称为最左归约，也称为______。 5.一个文法符号的______属性是通过语法树中它的文结点和/或兄结点的相应文法符号和属性来计算的，而______属性是通过语法树中它的子结点的属性之值来计算的。 6.常用的两种动态存贮分配方法是______动态分配和______动态分配。 7.在PASCAL语言中，为了在过程的嵌套调用过程中实现对非局部名字的访问，可以采用______和活动记录，或______和活动记录的方式。 二．（15） 1.请画出编译程序的总框图。 2.请给出表达式(a+b)*c+c/d的后缀式，并将其表示成三元式、四元式和间接三元式。 3.设文法G(s):S→(A)|a A→A+s|s，请构造各非终结符的FIRSTVT集合和LASTVT 集合。 三．（10） 将下列语句翻译成四元式序列（假定地址从100开始） While(a>b and a
《编译原理》模拟期末试题汇总 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分)
编译原理考试试卷
一、填空题（每空 2 分，共 30 分） 1、编译程序的整个过程可以从逻辑上划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成等几个阶段，另外还有两个重要的工 作是表格管理和出错处理 2、规范规约中的可归约串是句柄，算符优先分析中的可归约串是最左素短语。 3、语法分析方法主要可分为自顶向下和自底向上两大类。 4、 LR （ 0）文法的项目集中不会出现移进 -归约冲突和归约 -归约冲突。 5、数据空间的动存态储分配方式可分为栈式和堆式两种。 6、编译程序是指能将源语言程序翻译成目标语言程序的程序。 7、确定有穷自动机DFA 是NFA的一个特例。 8、表达式 (a+b)*c的逆波兰表示为ab+c*。 二、选择题（每题 2 分，共 20 分） 1、 L R 语法分析栈中存放的状态是识别B的 DFA 状态。 A 、前缀B、可归前缀C、项目 D 、句柄 2、D不可能是目标代码。 A 、汇编指令代码 B 、可重定位指令代码 C、绝对机器指令代码 D 、中间代码 3、一个控制流程图就是具有C的有向图 A 、唯一入口结点B、唯一出口结点C、唯一首结点 D 、唯一尾结点 4、设有文法G[S] ： S→ b|bB B → bS ，则该文法所描述的语言是C。 A 、 L （ G）={b i|i≥ 0}B、 L （G） ={b 2i |i≥0} C、 L （ G）={b 2i+1|i≥ 0} D 、 L （ G）={b 2i+1|i ≥1} 5、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B完成的。 A 、编译器 B 、汇编器C、解释器D、预处理器6、在目标代码生成阶段，符号表用于D。 A 、目标代码生成 B 、语义检查C、语法检查D、预处理器地址分配0 7、规范归约是指B。 A 、最左推导的逆过程 B 、最右推导的逆过程C、规范推导D、最左归约逆过程 8、使用A可以定义一个程序的意义。 A 、语义规则B、词法规则C、语法规则D、左结合规则 9、经过编译所得到的目标程序是D。 A 、三元式序列B、四元式序列C、间接三元式 D 、机器语言程序或汇编语言程序 10、在一个基本块内进行的代码优化是B。 A 、全局优化B、局部优化C、循环优化D、代码外提 三、简答题（ 3 小题，共 30 分） 1、已知文法G[S]：S→Ac|aB A→ ab B→ bc 证明该文法具有二义性（本题 6 分） 证明：因为该文法的句型abc 存在如下两棵语法树： 所以，该文法具有二义性 一、填空题（每空 1分，共 20分） 1．编译过程一般分为、、中间代码生成、 和目标代码生成五个阶段。 2．语法分析最常用的两类方法是和分析法。 3．确定的有穷自动机是一个，通常表示为。
编译原理期末考试题目及答案
一、填空题（每空2分，共20分） 1．编译程序首先要识别出源程序中每个单词，然后再分析每个句子并翻译其意义。 2．编译器常用的语法分析方法有自底向上和自顶向下两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的分析，中间代码生成、代码优化与目标代码的生成则是对源程序的综合。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即静态存储分配方案和动态存储分配方案。 5．对编译程序而言，输入数据是源程序，输出结果是目标程序。 1．计算机执行用高级语言编写的程序主要有两种途径：解释和编译。 2．扫描器是词法分析器，它接受输入的源程序，对源程序进行词法分析并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。 3．自下而上分析法采用移进、归约、错误处理、接受等四种操作。 4．一个LL（1）分析程序需要用到一张分析表和符号栈。 5．后缀式abc-/所代表的表达式是a/(b-c)。 二、单项选择题（每小题2分，共20分） 1．词法分析器的输出结果是__C。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 2．正规式M 1 和M 2 等价是指__C_。 A．M1和M2的状态数相等 B．M1和M2的有向边条数相等 C．M1和M2所识别的语言集相等D．M1和M2状态数和有向边条数相等 3．文法G：S→xSx|y所识别的语言是_C____。 A．xyx B．(xyx)* C．xnyxn(n≥0) D．x*yx* 4．如果文法G是无二义的，则它的任何句子α_A____。 A．最左推导和最右推导对应的语法树必定相同B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同D．可能存在两个不同的最左推导，但它们对应的语法树相同5．构造编译程序应掌握____D__。 A．源程序B．目标语言C．编译方法D．以上三项都是 6．四元式之间的联系是通过__B___实现的。 A．指示器B．临时变量C．符号表D．程序变量 7．表达式(┐A∨B)∧(C∨D)的逆波兰表示为__B___。 A．┐AB∨∧CD∨B．A┐B∨CD∨∧ C．AB∨┐CD∨∧D．A┐B∨∧CD∨ 8. 优化可生成__D___的目标代码。 A．运行时间较短 B．占用存储空间较小 C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小 9．下列___C___优化方法不是针对循环优化进行的。 A. 强度削弱B．删除归纳变量C．删除多余运算D．代码外提 10．编译程序使用_B_区别标识符的作用域。 A. 说明标识符的过程或函数名B．说明标识符的过程或函数的静态层次 C．说明标识符的过程或函数的动态层次 D. 标识符的行号 三、判断题（对的打√，错的打×，每小题1分，共10分） 2．一个有限状态自动机中，有且仅有一个唯一的终态。x
最新编译原理试题汇总+编译原理期末试题(8套含答案+大题集)
编译原理考试题及答案汇总一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 12．编译程序是一种___C__。 A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 13．文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __D___。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式
编译原理试题
1997年编译原理试题 1．（10分）某操作系统下合法的文件名为 device:name.extension 其中第一部分（device:）和第三部分（.extension）可缺省，若device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。 2．（20分） a. 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。 S—> S and S | S or S | not S | p | q | (S) b. 下面文法是否为LL(1)文法？说明理由。 S—> A B | P Q x A—> x y B—> b c P—> d P | εQ—> a Q | ε 3．（10分）某些语言允许给出名字表的一个属性表，也允许声明嵌在另一个声明里面，下面文法抽象这个问题。 D —> attrlist namelist | attrlist (D) namelist —> id, namelist | id attrlist —> A attrlist | A A —> decimal | fixed | float | real D —> attrlist namelist的含义是：在namelist中的任何名字有attrlist 中给出的所有属性。D—> attrlist (D) 的含义是：在括号中的声明提到的所有名字有attrlist 中给出的所有属性，而不管声明嵌套多少层。写一个翻译方案，它将每个名字的属性个数填入符号表。为简单起见，若属性重复出现，则重复计数。4．（10分）把表达式 -(a+b)*(c+d)+(a+b+c) 翻译成四元式。 5．（10分）由于文法二义引起的LR（1）分析动作冲突，可以依据消除二义的规则而得到LR（1）分析表，根据此表可以正确识别输入串是否为相应语言的句子。对于非二义非LR（1）文法引起的LR（1）分析动作的冲突，是否也可以依据什么规则来消除LR（1）分析动作的冲突而得到LR（1）分析表，并且根据此表识别相应语言的句子？若可以，你是否可以给出这样的规则？ 6．（5分）UNIX 下的C编译命令cc的选择项g和O的解释如下，其中dbx 的解释是“dbx is an utility for source-level debugging and execution of programs written in C”。试说明为什么用了选择项g后，选择项O便被忽略。 -g Produce additional symbol table information for dbx(1) and dbxtool(1) and pass -lg option to ld(1) (so as to include the g library, that is:
期末考试编译原理试卷及答案
一． 填空题（每空2分，共20分） 1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静 态存储分配方案和动态存储分配方案，而后者又分为（1） 和 （2） 。 2. 规范规约是最（3）规约。 3. 编译程序的工作过程一般划分为5个阶段：词法分析、（4） 、语义分析与中间代码生成，代码优化及（5） 。另外还有（6）和出错处理。 4．表达式x+y*z/(a+b)的后缀式为 （7） 。 5．文法符号的属性有综合属性和 （8）。 6．假设二位数组按行存放，而且每个元素占用一个存储单元，则数组a[1..15,1..20]某个元素a[i ，j]的地址 计算公式为（9）。 7．局部优化是局限于一个（10）范围内的一种优化。 二． 选择题（1-6为单选题，7-8为多选题，每问2分，共20分） 1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一组 （ ）。 A ． 字符串 B ． 产生式 C ． 开始符号 D ． 文法 2.程序的基本块是指（ ）。 A ． 一个子程序 B ． 一个仅有一个入口和一个出口的语句 C ． 一个没有嵌套的程序段 D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。 A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析。 A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。 A ． 四元式序列 B ． 间接三元式序列 C ． 二元式序列 D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。 A ． 唯一的 B ． 不唯一的 C ． 可能唯一，也可能不唯一 7． 如果在文法G 中存在一个句子，当其满足下列条件（ ）之一时，则称该文法是二义文法。 A ． 其最左推导和最右推导相同 B ． 该句子有两个不同的最左推导 C ． 该句子有两个不同的最右推导 D ． 该句子有两棵不同的语法树
编译原理试题(卷)汇总-编译原理期末试题(卷)(8套含答案解析-大题集)
编译原理考试题及答案汇总 一、选择 1．将编译程序分成若干个“遍”是为了_B__。 A . 提高程序的执行效率 B.使程序的结构更加清晰 C. 利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2．正规式 MI 和 M2 等价是指__C__。 A . MI 和 M2 的状态数相等 B.Ml 和 M2 的有向弧条数相等。 C .M1 和 M2 所识别的语言集相等 D. Ml 和 M2 状态数和有向弧条数相等 3．中间代码生成时所依据的是 _C_。 A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 4．后缀式 ab+cd+/可用表达式__B_来表示。 A． a+b/c+d B．(a+b)/(c+d) C． a+b/(c+d) D． a+b+c/d 6．一个编译程序中，不仅包含词法分析，_A____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析 B．( )文法分析 C．( )语言分析 D．( )解释分析 7．词法分析器用于识别__C___。 A．( ) 字符串 B．( )语句 C．( )单词 D．( )标识符 8．语法分析器则可以发现源程序中的___D__。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正 D．( ) 语法错误 9．下面关于解释程序的描述正确的是__B___。 (1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1) C．( ) (1)(2)(3) D．( ) (2)(3) 10．解释程序处理语言时 , 大多数采用的是__B___方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 11．编译过程中 , 语法分析器的任务就是__B___。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4)C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 12．编译程序是一种___C__。 A. ( ) 汇编程序 B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 13．文法 G 所描述的语言是_C____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 14．文法分为四种类型，即 0 型、1 型、2 型、3 型。其中 3 型文法是___B__。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法15．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 __D___。 A．( ) 句子 B．( ) 句型 C．( ) 单词 D．( ) 产生式 16．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括_C____。
编译原理考试
编译原理考试
————————————————————————————————作者：————————————————————————————————日期：
一、判断对错：（对√；错 ；每小问2分共24分） <1>算符优先分析法是一种规范归约分析法。（ ） <2>若文法Gs中不含形如T→…BD…的产生式，T、B、D∈V N，则称Gs为算符文法。（√） <3>若一个语言是有穷集合，则定义该语言的文法一定是递归的。（ ） <4>若两个正规式所表示的正规集相同，则认为二者是等价的。（√） <5>LR分析法是一种规范归约分析法。（√） <6>一个LR(0)项目集I={B →α.bβ, P →aA.},则说I中含有“移进—归约”冲突。（√） <7>SLR(1)文法是无二义性文法。（√） <8>消除左递归后的文法一定是LL(1)文法。（ ） <9>对任何编译程序而言，代码优化是必不可少的。（ ） <10>编译程序与具体的机器无关。（ ） <11>在自动机的概念中，终态与非终态是可区别的。（√） <12>逆波兰式ab+cd+*所代表的中缀表达式是：(a+b)*(c+d)（√） 1. 一个语言有文法是不惟一的。（√） 2. 若一个语言是无穷集合，则定义该语言的文法一定是递归的。（√） 3. 紧跟在条件转移语句后面的语句是基本块的入口语句。（√） 4. 算符优先分析法是一种规范归约分析法。（ ） 5. 自下而上语法自导翻译的特点：当栈顶形成句柄时，在归约的同时执行其语义动作。（√） 6. LR(0)文法、SLR(1)文法都是无二义性文法。（√） 7．K、∑分别表示有限状态集和有穷字母表, DFA M的转换函数f是一个从K ?∑到K的单值映射。（√） 8. 对任何编译程序而言，代码优化是必不可少的。（ ） 9. 直接短语是某规则的右部，它对应简单子树叶结点从左到右排列形成的符号串。（√） 10. 两个有穷自动机等价是指它们的状态数和有向弧数相等。（ ） 11. 一个LR(0)项目集为：I={A→α.bβ, D→β.},则说I中含有“移进--归约”冲突。 （√） 12. 若两个正规式所表示的正规集相同，则认为二者是等价的。（√） 13. 无左递归的文法是LL(1)文法。（ ） 14. 逆波兰式abcde/+*+所代表的中缀表达式是：a+b*(c+d/e)（√） 15. 编译程序结构中，中间代码优化及目标代码生成两个阶段与具体的机器有关。（ ） 16. LALR分析法中，同心集的合并不会产生“移进--归约”冲突。（√）
《编译原理》期末考试复习题
《编译原理》期末考试复习题 一、是非题（请在括号内，正确的划√，错误的划×）（每个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．简单优先文法允许任意两个产生式具有相同右部。 () 三、填空题(每空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分，共20分） ×1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。() ×2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。() √3．递归下降分析法是自顶向上分析方法。() ×4．产生式是用于定义词法成分的一种书写规则。() √5．LR 法是自顶向下语法分析方法。() √6．在SLR （1 ）分析法的名称中，S的含义是简单的。() ×7．综合属性是用于“ 自上而下” 传递信息。() ×8．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。() ×9．程序语言的语言处理程序是一种应用软件。() ×10．解释程序适用于COBOL 和FORTRAN 语言。() 三、填空题(每空1分，共10分) 1．一个句型中的最左简单短语称为该句型的___句柄__。
编译原理考试试卷
南京工业大学继续教育学院编译原理期末考试试卷 (2012-2013学年) A卷 一、选择题（每题2分，共20分） 得分 1. 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个_____，以及一组产生式。 A．字符串 B．运算符号 C．开始符号 D．文法 2.程序的基本块是指_____。 A．一个子程序 B．一个仅有一个入口和一个出口的语句 C．一个没有嵌套的程序段 D．一组顺序执行的程序段，仅有一个入口和一 个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于_____分析方法。 A．自左向右 B．自顶向下 C．自底向上 D．自右向左 4．经过编译所得到的目标程序是_____。 A．四元式序列 B．间接三元式序列 C．二元式序列 D．机器语言程序或汇编语言程序 5．运行阶段的存储组织与管理的目的是_____。 ①提高编译程序的运行速度②节省编译程序的存储空间 ③提高目标程序的运行速度④为运行阶段的存储分配做准备 A. ①② B. ②③ C. ③④ D. ④②6．词法分析器的输出结果是_____。 A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值 7．正规式M 1 和M 2 等价是指_____。
A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等 C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等 8．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 9．语言是_____。 A．句子的集合B．产生式的集合 C．符号串的集合D．句型的集合 10．编译程序前三个阶段完成的工作是 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析 C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化 二、名词解释（每题2分，共20分） 得分 1.最左推导： 2.语法： 3.文法： 4.基本块： 5.语法制导翻译： 6.短语： 7.规范句型：
编译原理考试试题1
编译原理 一、(5×6分)回答下列问题： 1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？ 2．什么是句柄？什么是素短语？ 3．划分程序的基本块时，确定基本块的入口语句的条件是什么？ 4．运行时的DISPLAY 表的内容是什么？它的作用是什么？ 5．对下列四元式序列生成目标代码： A:=B*C D:=E+F G:=A+D H:=G*2 其中，H 是基本块出口的活跃变量， R0和R1是可用寄存器 二、(8分)设∑={0，1}上的正规集S 由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA 。 三、(6分)写一个文法使其语言为L(G)={ a n b m a m b n | m,n ≥1}。 四、(8分)对于文法G(E): E →T|E+T T →F|T* F F →(E)|i 1. 写出句型(T*F+i)的最右推导并画出语法树。 2. 写出上述句型的短语，直接短语、句柄和素短语。 五、(12分)设文法G(S)： ( |*)B B |B A A A |SiA S A →+→→ 1．构造各非终结符的FIRSTVT 和LASTVT 集合； 2．构造优先关系表和优先函数。 六、(9分)设某语言的do-while 语句的语法形式为 S → do S (1) While E 其语义解释为： 真 假 S (1)的代码 E 的代码
针对自下而上的语法分析器，按如下要求构造该语句的翻译模式： (1) 写出适合语法制导翻译的产生式； (2) 写出每个产生式对应的语义动作。 七、(8分)将语句if (A
编译原理试卷
一、填空题（每题3分，共15分） 1.编译原理是一种翻译程序，它将高级语言编写的源程序翻译成等价的机器语言或汇编 语言的目标程序 2.整个编译过程可以分为五个阶段，分别是：词法分析、语法分析、语义分析及中 间代码生成、代码优化和目标代码的生成。 3.设X是符号串，符号串的幂运算X0= ε 4.乔姆斯基把文法分为四种类型，即0型、1型、2型、3型文法。2型文法也称为 上下文无关文法 5.采用递归下降分析法进行语法分析，要求文法是文法。 二、选择题（每题3分，共15分） 1．若文法G定义的语言是无限集，则文法必然是（D）。 A.上下文无关文法 B.正规文法 C.二义性文法 D.递归文法 2．文法G产生的（）的集合是该文法的描述语言。 A.句型 B.终结符集 C.非终结符集 D.句子 3．通常程序设计语言的词法规则可用正规式描述，词法分析器可用（B）来实现。 A.语法树 B.有穷自动机 C.栈 D.数组 4．设有文法G[S]：S→Bb│b，B→bS，该文法所描述的语言是（C） A. b n，n≥0 B.b2n，n≥0 C.b2n+1，n≥0 D.b2n+1，n≥1 5．用1代表字母，d代表数字，则定义标识符单词的正规式是（C） A.1d* B.11* C.1(1│d)* D.11*│d* 三、判断题（每小题2分，共10分） （）给定一个文法，就能从结构上唯一地确定其语言，给定一种语言，就能唯一地确定其文法。 （）用二义性文法定义的语言也是二义性的。 （）正规式、正规文法、有穷自动机都是描述正规集的工具，它们的描述能力是等价的，它们之间是可以相互转换的。 （）采用自下而上分析法进行语法分析需要消除文法的递归性。 （）算符优先文法中，任何两个终结符对（a，b）在·>，<·和=·这三种关系中只有一种关系成立。
编译原理考试试题与答案(汇总)
《编译原理》考试试题及答案（汇总） 一、是非题（请在括号，正确的划√，错误的划×）（每个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．( ) 代码外提