编译原理复习题附标准答案
编译原理复习题及答案
一、选择题
1．一个正规语言只能对应( B )
A 一个正规文法
B 一个最小有限状态自动机
2．文法G[A] ：A→ε A→aB B→Ab B→a是( A )
A 正规文法
B 二型文法
3．下面说法正确的是( A )
A 一个SLR( 1)文法一定也是LALR ( 1)文法
B 一个LR (1)文法一定也是LALR ( 1)文法
4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL (1)文法的( A )
A 必要条件
B 充分必要条件
5．下面说法正确的是( B )
A 一个正规式只能对应一个确定的有限状态自动机
B 一个正规语言可能对应多个正规文法
6．算符优先分析与规范归约相比的优点是( A )
A 归约速度快
B 对文法限制少
7．一个LR( 1)文法合并同心集后若不是LALR ( 1)文法( B )
A 则可能存在移进/归约冲突
B 则可能存在归约/ 归约冲突
C 则可能存在移进/归约冲突和归约/ 归约冲突
8．下面说法正确的是( A )
A Lex 是一个词法分析器的生成器
B Yacc 是一个语法分析器
9．下面说法正确的是( A )
A 一个正规文法也一定是二型文法
B 一个二型文法也一定能有一个等价的正规文法
10．编译原理是对(C) 。
A 、机器语言的执行
B 、汇编语言的翻译
C 、高级语言的翻译D、高级语言程序的解释执行11．(A) 是一种典型的解释型语言。
A ．BASIC
B ．CC．FORTRAND ．PASCAL
把汇编语言程序翻译成机器可执行的目标程序的工作12．
13．14．15．16．17．18．19．20．21．
22．23．24．25．
A. 编译器
B. 汇编器
C. 解释器
D. 预处理器
用高级语言编写的程序经编译后产生的程序叫(B)
A ．源程序B．目标程序C．连接程序D．解释程序
(C)不是编译程序的组成部分。
A. 词法分析程序
B. 代码生成程序
C.设备管理程序
D.语法分析程序
通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，
中间代码生成，代码优化，
目标代码生成等六个部分，还应包括(C)。矚慫润厲钐瘗睞枥庑赖。
A ．模拟执行器B．解释器C．表格处理和出错处理D．符号执行器
编译程序绝大多数时间花在(D) 上。
A ．出错处理B．词法分析C．目标代码生成D．表格管理
源程序是句子的集合，(B)可以较好地反映句子的结构。
A. 线性表
B. 树
C. 完全图
D. 堆栈
词法分析器的输出结果是(D)。
A 、单词自身值B、单词在符号表中的位置
C、单词的种别编码
D、单词的种别编码和自身值
词法分析器不能(D)
A. 识别出数值常量
B. 过滤源程序中的注释
C. 扫描源程序并识别记号
D. 发现括号不匹配
文法：G：S→ xSx | y 所识别的语言是(D)。
A 、xyx
B 、(xyx)*
C 、x*yx* D、x n yx n (n≥0) 如果文法G 是无二义的，则它的任何句子α(A)
A ．最左推导和最右推导对应的语法树必定相同
B ．最左推导和最右推导对应的语法树可能不同
C．最左推导和最右推导必定相同
D ．可能存在两个不同的最左推导，但它们对应的语法树相同
正则文法(A) 二义性的。
A. 可以是
B. 一定不是
C. 定是
(B) 这样一些语言，它们能被确定的有穷自动机识别，
但不能用正则表达式表示。
A. 存在
B. 不存在
C. 无法判定是否存在
给定文法 A → bA|ca，为该文法句子的是(C)
A. bba
B. cab
C. bca
D. cba
设有文法G[S] ：S S1|S0|Sa|Sc|a|b|c，下列符号串中是该文法的句子有(D)
(B)完成的。
是由
文法 G 产生的 (D) 的全体是该文法描述的语言。
描述一个语言的文法是 (B)
一个文法所描述的语言是 (A)
采用自上而下分析，必须 (A) 。
B 、消除左递归
D 、提取公共左因子
编译过程中，语法分析器的任务是 (A)
分析单词的构成
分析单词串如何构成语句 分析语句是如何构成程序 分析程序的结构
词法分析器的输入是 ( A)。
若 a 为终结符，则 A →α · 为a (βB) 项目。
A ．归约
B ．移进
C ．接受
D ．待约
在使用高级语言编程时 ,首先可通过编译程序发现源程序的全部和部分
乔姆斯基 (Chomsky)把文法分为四种类型，即 0 型、 1型、 2型、 3型。其中 3 型文法是 (B)
26．
27．
28． 29．
30．
31．
32．
33．
34．
35．
36．
37．
A. ab0
B. a0c01
C. a0b0a
D. bc10
A ．句型
B. 终结符集
C. 非终结符集
D.句子
若文法 G 定义的语言是无限集，则文法必然是 (A)
A ．递归的
B.上下文无关的
C.二义性的
D.无二义性的
A ．唯一的 B. 不唯一的
C. 可能唯一
A ．唯一的 B. 不唯一的 C. 可能唯一
A 、消除回溯 C 、消除右递归
A. ②③
B. ④
C. ①②③④
D. ②③④
A ．符号串
B ．源程序
C ．语法单位
D ．目标程序
两个有穷自动机等价是指它们的 (C)。
A ．状态数相等
B ． 有向弧数相等
C ．所识别的语言相等
D ． 状态数和有向弧数相等
若状态 k 含有项目“ A →α·”，且仅当输入符号
a ∈FOLLOW(A) 时，才用规则“ A →α ”
归约的语法分析方法是 (D) 。聞創沟燴鐺險爱氇谴净。
A ． LALR 分析法
B ．LR(0) 分析法
C ． L R(1) 分析法
D ．SLR(1)分析法
A.语法
B.语义
C.语用
D.运行
(A) 错误。
A. 非限制文法
B. 正则文法
C. 上下文有关文法
D. 上下文无关文法
一个句型中的 (A) 称为该句型的句柄。 A. 最左直接短语
B. 最右直接短语
C. 终结符
D.
非终结符
在自底向上的语法分析方法中，分析的关键是
(D)
A. 寻找句柄
B. 寻找句型
C. 消除递归
D.
选择候选式
在自顶向下的语法分析方法中，分析的关键是
(C)
A. 寻找句柄
B. 寻找句型
C. 消除递归
D.
选择候选式
在 LR 分析法中，分析栈中存放的状态是识别规范句型 (C) 的 DFA 状态。
A. 句柄
B. 前缀
C. 活前缀
D. LR(0) 项目 一个上下文无关文法 G 包括四个组成部分，它们是
一组非终结符号，一组终结符号，一个开 始符号，以及一组 (B) 残骛楼諍锩瀨濟溆塹籟。
A. 句子 词法分析器用于识别
B.
(C) 产生式
C. 单词
D. 句型
A. 句子
B.
产生式 C. 单词
D. 句型
编译程序是一种 (B)
A. 汇编程序
B.
翻译程序
C. 解释程序
D. 目标程序
按逻辑上划分，编译程序第三步工作是
(A)
A. 语义分析
B.
词法分析 C. 语法分析 D. 代码生成
在语法分析处理中， FIRST 集合、 FOLLOW 集合均是 (B)
A. 非终结符集
B.终结符集
C. 字母表
D. 状态集
编译程序中语法分析器接收以 (A) 为单位的输入。
A. 单词
B. 表达式
C. 产生式
D. 句子
编译过程中，语法分析器的任务就是 (B)
A. 分析单词是怎样构成的
B. 分析单词串是如何构成语句和说明的
C. 分析语句和说明是如何构成程序的
D. 分析程序的结构
若一个文法是递归的，则它所产生的语言的句子 (A) 。
A. 是无穷多个
B.是有穷多个
C.是可枚举的
D.个数是常量
识别上下文无关语言的自动机是 (C)
A. 下推自动机
B. NFA
C. DFA
D. 图灵机
编译原理各阶段工作都涉及 (B)
A. 词法分析
B.表格管理
C.语法分析
D.语义分析
正则表达式 R1 和 R2 等价是指 (C)
A.R1 和 R2 都是定义在一个字母表上的正则表达式
B. R1 和 R2 中使用的运算符相同
38．
39．
40．
41． 42．
43．
44．
45．
46．
47．
48．
49．
50．
51．
52．
C.R1 和 R2 代表同一正则集
D.R1 和 R2 代表不同正则集 文法 E →E+E|E*E|i 的句子 i*i+i*i 有(C) 棵不同的语法树。
A. 1
B.3
C. 5
D.7
文法 S → aaS|abc 定义的语言是 (C)。 A.{a2kbc|k>0}B.{akbc|k>0}C.{a2k-1bc|k>0}D.{akakbc|k>0}
彈贸摄尔霁毙攬砖卤庑。
若 B 为非终结符，则 A → .B 为(D) 。
A. 移进项目
B.归约项目
C.接受项目
D.待约项目
同心集合并可能会产生新的 (D) 冲突。
A.二义
B.移进/移进
C.移进 /归约
D.归约/归约
就文法的描述能力来说，有 (C)
A ． SLR(1) ? LR(0)
B ．LR(1) ? LR(0)
C ．SLR(1) ? LR(1)
D ．无二义文法 ? LR(1)謀荞抟箧飆鐸怼类蒋
如图所示自动机 M ，请问下列哪个字符串不是 M 所能识别的 (D)。
53．
54． 55．
56．
57． 58．
59． 60． 61．
62．
63． A. bbaa
B. abba
C. abab
D. aabb
已知文法 G[S]:S →A1， A → A1|S0|0。与 G A. 0(0|1)*B. 1*|0*1C. 0(1|10)*1D. 1(10|01)*0 与(a|b)*(a|b) 等价的正规式是 (C)。
A.a*| b*
B.(ab)*(a|b)
C. (a|b)(a|b)*
D.(a|b)* (D)文法不是 LL(1) 的。
A. 递归
B. 右递归
给定文法 A → bA|cc ，则符号串① cc ②
bcbc 是(D) 酽锕极額閉镇桧猪訣锥。 A. ① B. ③④⑤ LR(1) 文法都是 ()
A. 无二义性且无左递归 C. 无二义性但可能是左递归 等价的正规式是 (C)
C. 2 型
D. 含有公共左因子的
③ bcbcc ④ bccbcc ⑤ bbbcc 中，是该文法句子的
C. ②④
D. ①⑤
B. 可能有二义性但无左递归 D. 可以既有二义性又有左递归
64．有限状态自动机能识别(C)
A. 上下文无关语言
B.上下文有关语言
C.正规语言
65．已知文法G 是无二义的，则对G 的任意句型α (A)
A. 最左推导和最右推导对应的语法树必定相同
B.最左推导和最右推导
对应的语法树可能相同
C. 最左推导和最右推导必定相同
D. 可能存在两个不同的最左推导，但他们对应的语法树相同66．(B) 不是DFA 的成分
A. 有穷字母表
B.多个初始状态的集合
C.多个终态的集合67．与逆波兰式(后缀表达式)ab+c*d+ 对应的中缀表达式是(B)
A. a+b+c*d
B. (a+b)* c+d
C. (a+b)* (c+d)
D. a+b*c+d
68．后缀式abc-+-d+ 可用表达式(B) 来表示。
A．(- (a+b)-c)+d B ．- (a+(b-c))+d C ．- (a-(b+c))+d D ．(a-(-b+c))+d 69．表达式A*(B-C*(C/D)) 的后缀式为(B) 。
A ．ABC-CD/**
B ．ABCCD/*-*
C ．ABC-*CD/*
D ．以上都不对70．(D) 不是NFA 的成分。
A. 有穷字母表
B. 初始状态集合
C. 终止状态集合
二、问答题
1．将文法G[S] 改写为等价的G′ [S，] 使G′ [S不] 含左递归和左公共因子。
G[S] ：S→bSAe | bA
A→Ab | d
答：
文法G[S] 改写为等价的不含左递归和左公共因子的G'[S] 为：S→bB
B→SAe | A D.0 型文法定义的语言D.转换函数
厦礴恳蹒骈時盡继價骚。
D. 有限状态集合
A→d A'
A' →bA' | ε
2．将文法G[S] 改写为等价的G'[S]，使G'[S]不含左递归和左公共因子。
G[S]：S→SAe|Ae
A→dAbA |dA|d
答：
文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为：S →AeS'
S' →AeS'| ε
A →dA'
A' →AB|ε
B →bA |ε
3．将文法G[S] 改写为等价的G'[S]，使G'[S]不含左递归和左公共因子。
G[S]：S→[A
A→B]|AS
B→aB|a
答：
文法G[S] 改写为等价的不含左递归和左公共因子的G'[S]为：S →[A
A →B]A′
A′→SA′| ε
B →aB′
B′→ B|ε
4．判断下面文法是否为LL(1) 文法，若是,请构造相应的LL(1) 分析表。S→aH
H→aMd | d
M→Ab | ε
A→aM | e
答：首先计算文法的FIRST 集和FOLLOW 集如下表。
文法的FIRST 集和FOLLOW 集
由于predict（H→ aMd ）∩predict （H→d）={a} ∩{d }= predict （M→ Ab ）∩predict（M→ε）={a ，e} ∩{d ，b }= predict （A→ aM ）∩predict（A→e）={ a } ∩{ e }=
LL(1)LL(1)
5LL(1) LL(1)
S→aD
D→STe|ε
T→bH|H
H→d|ε
答：
首先计算文法的FIRST 集和FOLLOW 集如下表。
由于predict（D→STe ）∩predict （D→ε）={a} ∩{# ，b ，d ，e }= predict （T→ bH）∩predict （T→H）={b} ∩{e }=
predict （H→d）∩predict（H→ε）={ d } ∩{ e }=
所以该文法是 LL （1）文法， LL （1）分析表如下表：
6． 判断下面文法是否为 LL(1) 文法，若是，请构造相应的 LL(1) 分析表。
S →aD D →STe|ε T →bM M →bH H →M|ε
答：
文法的 FIRST 集和 FOLLOW 集
由于 predict （ D →STe ）∩predict （ D →ε） ={a} ∩{# ，
b}=
predict （ H →M ）∩predict （H →ε）={ b } ∩{ e }= 所以该文法是 LL （1）文法， LL （1）分析表如下
表：
7 ．某语言的拓广文法G′为：
(0) S ′→S
(1) S → Db|B
(2) D → d| ε
(3) B → Ba| ε
证明G 不是LR(0) 文法而是SLR(1)文法，请给出SLR(1)分析表。答：
拓广文法G'，增加产生式S' →S
在项目集I0 中：
有移进项目 D →· d
归约项目 D →·和 B →·
存在移进-归约和归约-归约冲突，所以G 不是LR(0) 文法。
若产生式排序
为
(0) S'→S
Db
(1) S
→
B
(2) S
→
d
(3) D
→
(4) D→ε
Ba
(5) B
→
ε
(6) B
→
G′的LR(0) 项目集族及识别活前缀的DFA 如下图：
由产生式知
Follow(S)={#}
Follow(D)= {b}
Follow(B)= {a ,#}
在I0 中:
Follow(D) ∩ {d}={ b} ∩{d}=
Follow(B) ∩{d}= { a ,#} ∩{d}=
Follow(D) ∩ Follow(B)= {b} ∩{a ,#} =
在I3 中:
Follow(S) ∩ {a}={#} ∩{a}=
所以在I0，I3中的移进-归约和归约-归约冲突可以由Follow 集解决,所以G是SLR(1)文法,构造的SLR(1) 分析表如下表：
4
r3
5
r1
6
r5 r5
8． 给出与正规式 R ＝(ab )*(a|b*)ba 等价的 NFA 。 答：
答：
与正规式 R 等价的 NFA 如下图
11． 将下图的 NFA 确定化为 DFA 。
与正规式 R 等价的 NFA 如下图
9． 给出与正规式 答：
答：
R ＝( (ab)*|b )*(a|(ba)*)a 等价的 NFA 。
与正规式 R 等价的
10． 给出与正规式
用子集法确定化如下表
状态
I Ia Ib
{X,1,2}{1,2}{1,2,3}X
{1,2}{1,2}{1,2,3}1
{1,2,3}{1,2,Y}{1,2,3}2
{1,2,Y}{1,2}{1,2,3}3
确定化后如下图：
12．将下图的
答：
用子集法确定化如下表
状态
I I a I b
{X,0,1,3}{0,1,3}{2,3,Y}X
{0,1,3}{0,1,3}{2,3,Y}1
{2,3,Y}{1,3}{Y}2
{1,3}{2,Y}3
{2,Y}{1,3}{Y}4
{Y}Y
确定化后如下图
13．某语言的拓广文法G′为：
(0) S ′→ T
(1) T → aBd| ε
(2) B →Tb| ε
证明G 不是LR(0)文法而是SLR(1)文法，请给出SLR(1)分析表。答：拓广文法G'，增加产生式S'→T
在项目集I0中：
有移进项目T →·aBd 和归约项目T →· 存在移进-
归约冲突，所以G 不是LR(0)文法。
若产生式排序为：
(0) S' →T
(1) T →aBd
(2) T →ε
(3) B →Tb
(4) B →ε
G'的LR(0)项目集族及识别活前缀的DFA 如下图所示：
识别G′活前缀的DFA
由产生式知：
Follow(T)={#,b}
Follow(B)= {d}
在I0 中：
Follow(T) ∩ {a}={# ，b} ∩ {a}=
在I2 中：
Follow(B) ∩{a}= {d} ∩{a}=
Follow(T) ∩ {a}={#，b} ∩ {a}=
Follow(B) ∩ Follow(T) = {d} ，∩b}={#
所以在I0，I2，中的移进-归约和归约-归约冲突可以由Follow 集解决，所以G 是SLR(1) 文法。构造的SLR(1) 分析表如下表。
SLR(1)
14．某语言的文法G 为： E → aTd| ε
T → Eb|a
证明G 不是LR(0)文法而是SLR(1)文法，请给出该文法的SLR(1) 分析表。答：拓广文法G'，增加产生式S'→E
在项目集I0中：有移进项目 E →·aTd 和归约项目E→·
存在移进-归约冲突，所以G 不是LR(0)文法。若产生式排序为：
(0) S ′→ E
(1) E → aTd
(2) E →ε
(3) T → Eb
(4) T → a
G′的LR(0)项目集族及识别活前缀的DFA 如下图：
由产生式知：
Follow(E)={# ，b}
Follow(T)= {d}
在I0 ，I2 中:
Follow(E) ∩ {a}={#，b} ∩ {a}=
在I5 中:
Follow(E) ∩ {a}={#，b} ∩ {a}=
Follow(T) ∩{a}= {d} ∩{a}=
Follow(T) ∩ Follow(E) = {d} ，b∩}={#
所以在I0 ，I2 ，I 5中的移进-归约和归约-归约冲突可以由Follow 集解决,所以G′是SLR(1) 文法。茕桢广鳓鯡选块网羈泪。
构造的SLR(1) 分析表如下表：
3
S6
4S7
5S5r2r4r243
6r1r1
7r3
G[S] 为：S → BD|D
B → aD|b
D →B
I0:
答：
16．给出文法G[S]的LR(1)项目集规范族中I0 项目集的全体项目。
G[S] 为：S →D;D|D
D → DB|B
B → a|b
I0:
答：
I0：
最新编译原理复习题及答案
编译原理复习题及答案 一、选择题 1．一个正规语言只能对应(B) A 一个正规文法 B 一个最小有限状态自动机 2．文法G[A]：A→εA→aB B→Ab B→a是(A) A 正规文法 B 二型文法 3．下面说法正确的是(A) A 一个SLR（1）文法一定也是LALR（1）文法 B 一个LR（1）文法一定也是LALR（1）文法 4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A) A 必要条件 B 充分必要条件 5．下面说法正确的是(B) A 一个正规式只能对应一个确定的有限状态自动机 B 一个正规语言可能对应多个正规文法 6．算符优先分析与规范归约相比的优点是(A) A 归约速度快 B 对文法限制少 7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B) A 则可能存在移进/归约冲突 B 则可能存在归约/归约冲突 C 则可能存在移进/归约冲突和归约/归约冲突 8．下面说法正确的是(A) A Lex是一个词法分析器的生成器 B Yacc是一个语法分析器 9．下面说法正确的是(A) A 一个正规文法也一定是二型文法 B 一个二型文法也一定能有一个等价的正规文法 10．编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行 11．用高级语言编写的程序经编译后产生的程序叫(B)
A．源程序 B．目标程序C．连接程序D．解释程序 12．(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 13．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器 C．表格处理和出错处理D．符号执行器14．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 15．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 16．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 17．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 18．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 19．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 20．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 21．给定文法A→bA | ca，为该文法句子的是(C) A. bba B. cab C. bca D. cba 22．设有文法G[S]：S S1|S0|Sa|Sc|a|b|c，下列符号串中是该文法的句子有(D) A. ab0 B. a0c01 C. a0b0a D. bc10 23．描述一个语言的文法是(B) A．唯一的 B. 不唯一的 C. 可能唯一 24．一个文法所描述的语言是(A) A．唯一的 B. 不唯一的 C. 可能唯一
编译原理期末复习题(包含上一份N多答案)
编译原理复习题 一、填空题： 1、编译方式与解释方式的根本区别在于（是否生成目标代码）。 2、对编译程序而言，输入数据是（源程序），输出结果是（目标程序）。 3、如果编译程序生成的目标程序是机器代码程序，则源程序的执行分为两大阶段：（编译阶段）和（运行阶段）。 4、如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分成三个阶段：（编译阶段）、（汇编阶段）和（运行阶段）。 5、自顶向下语法分析方法会遇到的主要问题有（回溯）和（（左递归带来的）无限循环）。 6、LL(k)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“k”的含义是（向输入串中查看K个输入符号）。 7、LL(1)分析法中，第一个L的含义是（从左到右进行分析），第二个L的含义是（每次进行最左推导），“1”的含义是（向输入串中查看1个输入符号）。8、自顶向下语法分析方法的基本思想是：从（识别符号）出发，不断建立（直接推导），试图构造一个推导序列，最终由它推导出与输入符号相同的（符号串）。 9、自底向上语法分析方法的基本思想是：从待输入的符号串开始，利用文法的规则步步向上进行（直接归约），试图（归约）到文法的（识别符号|开始符号）。
10、LR(0)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“0”的含义是（向貌似句柄的符号串后查看0个输入符号）。 11、LR(1)分析法的名字中，“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 12、SLR(1)分析法的名字中，“S”的含义是（简单的），“L”的含义是（从左到右进行分析），“R”的含义是（采用最右推导的逆过程---最左归约），“1”的含义是（向貌似句柄的符号串后查看1个输入符号）。 13、在编译过程中，常见的中间语言形式有（逆波兰表示）、（三元式）、（四元式）和（树形表示）。 14、在编译程序中安排中间代码生成的目的是（便于代码优化）和（便于目标程序的移植）。 15、表达式-a+b*(-c+d)的逆波兰表示为（a-bc-d+*+ ）。 16、表达式a+b*(c+d/e)的逆波兰表示为（abcde/+*+ ）。 17、表达式a:=a+b*c↑(d/e)/f的逆波兰表示为（aabcde/↑*f/+:= ）。 18、文法符号的属性有（继承属性）和（综合属性）两种。 19、一个文法符号的继承属性是通过语法树中它的（兄弟结点与父）结点的相应文法符号的属性来计算的。 20、一个文法符号的综合属性是通过语法树中它的（子）结点的属性来计算的。 21、语法制导的编译程序能同时进行（语法）分析和（语义）分析。 22、编译过程中扫描器所完成的任务是从（源程序）中识别出一个个具有（独
《编译原理》复习题及答案
《编译原理》课程复习资料 一、判断题： 1.一个上下文无关文法的开始符，可以是终结符或非终结符。 [ ] 2.一个句型的直接短语是唯一的。 [ ] 3.已经证明文法的二义性是可判定的。 [ ] 4.每个基本块可用一个DAG表示。 [ ] 5.每个过程的活动记录的体积在编译时可静态确定。 [ ] 6.2型文法一定是3 型文法。 [ ] 7.一个句型一定句子。 [ ] 8.算符优先分析法每次都是对句柄进行归约。 [ ] 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。 [ ] 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 [ ] 11.一个优先表一定存在相应的优先函数。 [ ] 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 [ ] 13.递归下降分析法是一种自下而上分析法。 [ ] 14.并不是每个文法都能改写成 LL(1)文法。 [ ] 15.每个基本块只有一个入口和一个出口。 [ ] 16.一个 LL(1)文法一定是无二义的。 [ ] 17.逆波兰法表示的表达试亦称前缀式。 [ ] 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 [ ] 19.正规文法产生的语言都可以用上下文无关文法来描述。 [ ] 20.一个优先表一定存在相应的优先函数。 [ ] 21.3型文法一定是2 型文法。 [ ] 22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 [ ] 二、填空题： 1. 称为规范推导。 2.编译过程可分为，，，和五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是。 4.从功能上说，程序语言的语句大体可分为语句和语句两大类。 5.语法分析器的输入是，其输出是。 6.扫描器的任务是从中识别出一个个。 7.符号表中的信息栏中登记了每个名字的有关的性质，如等等。 8.一个过程相应的DISPLAY表的内容为。 9.一个句型的最左直接短语称为句型的。 10.常用的两种动态存贮分配办法是动态分配和动态分配。 11.一个名字的属性包括和。 12.常用的参数传递方式有，和。 13.根据优化所涉及的程序范围，可将优化分成为，和三个级别。 14.语法分析的方法大致可分为两类，一类是分析法，另一类是分析法。 15.预测分析程序是使用一张和一个进行联合控制的。 16.常用的参数传递方式有，和。 17.一张转换图只包含有限个状态，其中有一个被认为是态；而且实际上至少要有一个态。 18.根据优化所涉及的程序范围，可将优化分成为，和三个级别。 19.语法分析是依据语言的规则进行。中间代码产生是依据语言的规则进行的。 20.一个句型的最左直接短语称为句型的。 21.一个文法G，若它的预测分析表M不含多重定义，则该文法是文法。 22.对于数据空间的存贮分配， FORTRAN采用策略， PASCAL采用策略。 23.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是。
编译原理复习题--有答案版
1、给出下面语言的相应文法。L1={a n b n c i|n≥1,i≥0} 答案： S→ AB|B A→ a|aA B→ bBc|bc 2．给出下面语言的相应文法 L1={a n b n c m d m| m,n≥1，n为奇数，m为偶数}。 答案：文法G(S):S→AC A→aaAbb/ab C→ccCcc/cc 3、构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。 （要求：先将正规式转化为NFA，再将NFA确定化，最小化） (一)相应的正规式为(a|b)*ab(a|b)* (二)①与此正规式对应的NFA为 答案；在自己写的纸上 4、对下面的文法G: E→TE’ E’→+E|ε T→FT’ T’→T|ε F→PF’ F’→*F’|ε P→(E)|a|b|∧ （1）证明这个文法是LL(1)的。 考虑下列产生式: E’->E|ε T’->T|ε F’->*F’ |ε P->(E) |∧a|b FIRST(+E)∩FIRST(ε)={+}∩{ε}=φ FIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φ
FIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φ FIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φ FIRST(*F')∩FIRST(ε)={*}∩{ε}=φ FIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φ FIRST((E))∩FIRST(a) ∩FIRST(b) ∩FIRST(^)=φ 所以,该文法式LL(1)文法. 计算这个文法的每个非终结符的FIRST和FOLLOW。（8分） 答案：FIRST(E)={(,a,b,^} FIRST(E')={+,ε} FIRST(T)={(,a,b,^} FIRST(T')={(,a,b,^,ε} FIRST(F)={(,a,b,^} FIRST(F')={*,ε} FIRST(P)={(,a,b,^} FOLLOW(E)={#,)} FOLLOW(E')={#,)} FOLLOW(T)={+,),#} FOLLOW(T')={+,),#} FOLLOW(F)={(,a,b,^,+,),#} FOLLOW(F')={(,a,b,^,+,),#} FOLLOW(P)={*,(,a,b,^,+,),#} （3）构造它的预测分析表。（6分） 答案；在手机上 写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。 答案：逆波兰式：(abcd-*+) 三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1)
编译原理复习题目集答案解析
第4章词法分析 重点内容：正规式转化为DFA a、正规式->NFA b、NFA -> DFA（子集法） c、DFA化简（分割法） 题目1：课件例题： a、为R=(a|b)*(aa|bb)(a|b)*构造NFA b、从NFA构造DFA的算法 c、化简
题目2： 4.7 例1：构造正规式相应的DFA：1(0|1)*101 按照以下三步： （1）由正规表达式构造转换系统（NFA） （2）由转换系统（NFA）构造确定的有穷自动机DFA （3）DFA的最小化 答：（1）构造与1(0|1)*101等价的NFA （2）将NFA转换成DFA：采用子集法，即DFA的每个状态对应NFA的一个状态集合： 除X，A外，重新命名其他状态：
1、将M 的状态分成非终态和终态集{X,A,B,C}和{D}。 2、寻找子集中不等价状态{X,A,B,C}=>{X}，{A,B}{C}=>{X}{A}{B}{C}，无需合并。 最后生成 DFA ： 题目3：自习、书本练习4.7，参考答案见《z4 书本练习4.7.doc 》 已知文法G[S]： S →aA|bQ A →aA|bB|b B →bD|aQ Q →aQ|bD|b E →aB|bF F →bD|aE|b 1、 构由于不可到达，去除E 、F 相关的多余产生式 2、 由新的G[S]构造NFA 如下
5、使用分割法化简以上DFA G： 5.1 令G={(0,1,3,4,6),(2,5)}// 分别为非终态和终态集 5.2 由{0,1,3,4,6}a={1,3}，{0,1,3,4,6}b={3,2,5,6,4} 将{0,1,3,4,6}划分为 {0,4,6}{1,3}，得G={(0,4,6),(1,3),(2,5)} 5.3 由{0,4,6}b={3,6,4}，将之划分为{0},{4,6}，得G={(0),(4,6),(1,3),(2,5)} 5.4 观察后，G中状态不可再分，为最小化DFA。 6、分别用 0，4，1，2代表各状态，DFA状态转换图如下： 造相应的最小的DFA 第5章自顶向下的语法分析 重点内容：LL（1）文法 a、去除左递归 b、LL（1）文法的判定（first、follow、select集） c、预测分析表 d、使用栈和预测分析表对输入串的分析 题目1：课件例题：消除左递归+判定+分析 算术表达式文法G E→E+T│T T→T*F│F F→(E)│I d、分析输入串i+i*i#
编译原理复习题及答案
1、试证明：任何LL(1)文法均为无二义性文法。 证：LL（1）文法的分析句子过程的每一步，永远只有唯一的分析动作可进行。现在，假设LL(1)文法G是二义性文法，则存在句子α，它有两个不同的语法树。即存在着句子α有两个不同的最左推导。从而可知，用LL（1）方法进行句子α的分析过程中的某步中，存在两种不同的产生式替换，且均能正确进行语法分析，即LL（1）分析动作存在不确定性。与LL（1）性质矛盾。所以，G不是LL(1)文法。 2、 LL （ 1 ）分析法对文法有哪些要求？ 对于 G 中的每个产生式 A →γ 1 | γ 2 | … | γ m ，其各候选式均应满足：（1）不同的候选式不能推出以同一终结符号打头的符号串，即 FIRST( γ i ) ∩ FIRST( γ j )= φ（ 1 ≤ i ， j ≤ m ； i ≠ j ） （2）若有γ j ε，则其余候选式γ i 所能推出的符号串不能以 FOLLOW(A) 中的终结符号开始，即有 FIRST( γ i ) ∩ FOLLOW(A)= φ（ i ≤ 1,2, … ,m ； i ≠ j ） 3、一个上下文无关文法生成句子abbaa的推导树如下： (1)给出串abbaa最左推导、最右推导。 (2)该文法的产生式集合P可能有哪些元素？ (3)找出该句子的所有短语、直接短语、句柄。 [答案] (1)串abbaa最左推导: S=>ABS=>aBS=>aSBBS=>aεBBS=>aεbBS=>aεbbS=>aεbbAa=>aεbbaa 最右推导： S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Aεbbaa=>aεbbaa
编译原理期末考试复习题(含答案)
编译原理期末考试复习题（含答案） 一、选择题 1.代码生成阶段的主要任务是（C）。 A.把高级语言翻译成汇编语言 B.把高级语言翻译成机器语言 C.把中间代码变换成依赖具体机器的目标代码 D.把汇编语言翻译成机器语言 2.文法G 所描述的语言是（ C ）的集合。 A.文法G 的字母表V 中所有符号组成的符号串 B.文法G 的字母表V 的闭包V* 中的所有符号串 C.由文法的开始符号推出的所有终结符串 D.由文法的开始符号推出的所有符号串 3.语言是（C）。 A.终结符与非终结符的符号串的集合 B.非终结符符号串的集合 C.终结符符号串的集合 D.产生式的集合 4.常用的中间代码形式不含（D）。 A.三元式 B.四元式 C.逆波兰式 D.语法树 5.四元式之间的联系是通过（B）实现的。 A.指示器 B.临时变量 C.符号表 D.程序变量 6．词法分析器的输出结果是（ C ）。 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．下推自动机识别的语言是（ C ） A．0型语言 B．1型语言 C．2型语言 D．3型语言 9. 在规范归约中，用（B）来刻画可归约串。 A．直接短语 B．句柄C．最左素短语 D．素短语 10．词法分析器用于识别（ C）。 A．字符串 B．语句 C．单词 D．标识符 11．一个句型中称为句柄的是该句型的最左（D） A．非终结符号 B．短语 C．句子 D．直接短语
12.文法 G[E] ： E→T∣E＋T T→F∣T * F F→a∣（E） 该文法句型 E ＋ F * (E ＋ T) 的简单短语是下列符号串中的（B）。 ①（E＋T）②E＋T ③F ④ F * (E＋T) A．①和③B．②和③C．③和④D．③ 13.通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括（C）。 A．模拟执行器 B．解释器 C．表格处理和出错处理 D．符号执行器 14. 基本块内的优化为（ B）。 A．代码外提，删除归纳变量B．删除多余运算，删除无用赋值 C．强度削弱，代码外提D．循环展开，循环合并 15. 语法分析器则可以发现源程序中的（D）。 A．语义错误 B．语法和语义错误 C．错误并校正 D．语法错误 16. 优化可生成（D）的目标代码。 A．运行时间较短 B．占用存储空间较小 C．运行时间短但占用内存空间大 D．运行时间短且占用存储空间小 17．下列（C）优化方法不是针对循环优化进行的。 A. 强度削弱 B．删除归纳变量 C．删除多余运算 D．代码外提 18. （ D）文法不是LL(1)的。 A. 递归 B. 右递归 C.2型 D. 含有公共左因子的 19.与编译系统相比，解释系统（ D ）。 A．比较简单 , 可移植性好 , 执行速度快B．比较复杂 , 可移植性好 , 执行速度快C．比较简单 , 可移植性差 , 执行速度慢D．比较简单 , 可移植性好 , 执行速度慢 20.通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括（ C ）。 A．模拟执行器 B．解释器 C．表格处理和出错处理 D．符号执行器 21．词法分析器用于识别（ C）。 A．字符串 B．语句 C．单词 D．标识符
编译原理习题及答案(整理后)
第一章 1、将编译程序分成若干个“遍”是为了。 b．使程序的结构更加清晰 2、构造编译程序应掌握。 a．源程序b．目标语言 c．编译方法 3、变量应当。 c．既持有左值又持有右值 4、编译程序绝大多数时间花在上。 d．管理表格 5、不可能是目标代码。 d．中间代码 6、使用可以定义一个程序的意义。 a．语义规则 7、词法分析器的输入是。 b．源程序 8、中间代码生成时所遵循的是- 。 c．语义规则 9、编译程序是对。 d．高级语言的翻译 10、语法分析应遵循。 c．构词规则 二、多项选择题 1、编译程序各阶段的工作都涉及到。 b．表格管理c．出错处理 2、编译程序工作时，通常有阶段。 a．词法分析b．语法分析c．中间代码生成e．目标代码生成 三、填空题 1、解释程序和编译程序的区别在于是否生成目标程序。 2、编译过程通常可分为5个阶段，分别是词法分析、语法分析中间代码生成、代码优化和目标代码生成。 3、编译程序工作过程中，第一段输入是源程序，最后阶段的输出为标代码生成程序。 4、编译程序是指将源程序程序翻译成目标语言程序的程序。
一、单项选择题 1、文法G：S→xSx|y所识别的语言是。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 2、文法G描述的语言L(G)是指。 a. L(G)={α|S+?α , α∈V T*} b. L(G)={α|S*?α, α∈V T*} c. L(G)={α|S*?α,α∈(V T∪V N*)} d. L(G)={α|S+?α, α∈(V T∪V N*)} 3、有限状态自动机能识别。 a. 上下文无关文法 b. 上下文有关文法 c.正规文法 d. 短语文法 4、设G为算符优先文法，G的任意终结符对a、b有以下关系成立。 a. 若f(a)>g(b)，则a>b b.若f(a) 第一章引论 1.编译过程的阶段 由词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段 2.编译程序的概念 3.编译程序的结构 例：（B）不是编译程序的组成部分。 A. 词法分析器； B. 设备管理程序 C. 语法分析程序； D. 代码生成程序 4.遍的概念 对源程序(或其中间形式)从头至尾扫描一次并进行有关加工处理，生成新的中间形式或最终目标程序，称为一遍。 5.编译程序与解释程序的区别 例：解释程序和编译程序是两类程序语言处理程序，它们的主要区别在于（D）。 A. 单用户与多用户的差别 B. 对用户程序的差错能力 C. 机器执行效率 D. 是否生成目标代码 第三章文法和语言 文法的概念 字母表、符号串和集合的概念及运算 例：(ab|b)*c 与下面的那些串匹配？（ACD） A. ababbc； B. abab； C. c； D. babc； E. aaabc 例：ab*c*(a|b)c 与后面的那些串匹配？（BC） A.acbbc B.abbcac C.abc D.acc 例：(a|b)a+(ba)*与后面的那些串匹配? （ADE） A.ba B.bba C.ababa D.aa E.baa 文法的定义（四元组表示） 文法G定义为四元组（V N，V T，P，S） V N：非终结符集 V T：终结符集 P：产生式（规则）集合 S：开始符号（或识别符号） 例：给定文法，A::= bA | cc，下面哪些符号串可由其推导出（①② ⑤）。 ①cc ②b*cc ③b*cbcc ④bccbcc ⑤bbbcc 什么是推导 例：已知文法G： E->E+T|E-T|T T->T*F|T/F|F F->(E)|i 试给出下述表达式的推导：i*i+i 推导过程：E->E+T ->T+T ->T*F+T ->F*F+T ->i*F+T ->i*i+T ->i*i+F ->i*i+i ●句型、句子的概念 例：假设G一个文法，S是文法的开始符 号，如果S=>*x，则称x是句型。 例：对于文法G，仅含终结符号的句型称 为句子。 ●语言的形式定义 例：设r=(a|b|c)(x|y|z)，则L(r)中元素为9 个。 例：文法G产生式为S→AB，A→aAb|ε， B→cBd|cd，则B∈L(G)。 A. ababcd； B. ccdd； C. ab； D. aabb ●等价文法 例：如果两个文法描述了同一个语言，则这两个文法是等价文法。 ●文法的类型 0型：左边至少有一个非终结符 1型：右边长度>=左边长度 2型：左边有且仅有一个非终结符 3型：形如：A->aB,A->a 各类型文法都是逐级包含关系， 例：文法S→abC|c，bC→d是几型文法？0 型 例：文法S→abC，bC→ad是几型文法？1 型 例：文法G[A]：A→ε，A→aB，B→Ab，B→a 是几型文法？2型 例：文法S→a|bC，C→d是几型文法？3 型 ●最左（右）推导 一、单选题（每题2分，共20分） 1. 编译器的（）阶段可将源程序的字符流收集到若干记号中。 A. 语法分析 B. 语义分析 C. 代码生成 D. 词法分析 2. 文法A aA | b属于正则文法，正则文法在乔姆斯基层次中对应于（）文法。 A. 1型 B. 2型 C. 3型 D. 0型 3. 某C语言源代码文件包含#include 中南大学网络教育课程考试复习题及参考答案 编译原理 一、判断题： 1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( ) 2.一个句型的直接短语是唯一的。 ( ) 3.已经证明文法的二义性是可判定的。 ( ) 4.每个基本块可用一个DAG表示。 ( ) 5.每个过程的活动记录的体积在编译时可静态确定。 ( ) 6.2型文法一定是3 型文法。 ( ) 7.一个句型一定句子。 ( ) 8.算符优先分析法每次都是对句柄进行归约。 ( ) 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。 ( ) 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( ) 11.一个优先表一定存在相应的优先函数。 ( ) 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 13.递归下降分析法是一种自下而上分析法。 ( ) 14.并不是每个文法都能改写成 LL(1)文法。 ( ) 15.每个基本块只有一个入口和一个出口。 ( ) 16.一个 LL(1)文法一定是无二义的。 ( ) 17.逆波兰法表示的表达试亦称前缀式。 ( ) 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ) 19.正规文法产生的语言都可以用上下文无关文法来描述。 ( ) 20.一个优先表一定存在相应的优先函数。 ( ) 21.3型文法一定是 2型文法。 ( ) 22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 ( ) 二、填空题： 1.( )称为规范推导。 2.编译过程可分为（），（），（），（）和（）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。 4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。 5.语法分析器的输入是（），其输出是（）。 6.扫描器的任务是从（）中识别出一个个（）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。 8.一个过程相应的DISPLAY表的内容为（）。 9.一个句型的最左直接短语称为句型的（）。 10.常用的两种动态存贮分配办法是（）动态分配和（）动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有（），（）和（）。 13.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。 14.语法分析的方法大致可分为两类，一类是（）分析法，另一类是（）分析法。 15.预测分析程序是使用一张（）和一个（）进行联合控制的。 16.常用的参数传递方式有（），（）和（）。 17.一张转换图只包含有限个状态,其中有一个被认为是（）态;而且实际上至少要有一个（）态。 18.根据优化所涉及的程序范围，可将优化分成为（），（）和（）三个级别。 19.语法分析是依据语言的（）规则进行。中间代码产生是依据语言的（）规则进行的。 20.一个句型的最左直接短语称为句型的（）。 21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（）文法。 22.对于数据空间的存贮分配， FORTRAN采用( )策略， PASCAL采用( )策略。 作业1 1. (单选题) ( )不是NFA的成分。(本题 2.0分) A、有穷输入字母表 B、文法符号集合 C、终止状态集合 D、有限状态集合 学生答案： A 标准答案：B 解析： 得分： 0 2. (单选题) 如果推导过程中任何一步,都是对中的最右非终结符进行替换,则称这种推导是( )。(本题2.0分) A、直接推导 B、最右推导 C、广义推导 D、最左推导 学生答案： C 标准答案：B 解析： 得分： 0 3. (单选题) 在递归子程序方法中,若文法存在左递归,则会使分析过程产生( )。(本题2.0分) A、回溯 B、非法调用 C、有限次调用 D、无限循环 学生答案： B 标准答案：D 解析： 得分： 0 4. (单选题) 已知文法G[S]:S→eT|RT T→DR|ε R→dR|ε D→a|bd ,则FIRST(S)=( )。(本题2.0分) A、{ e } B、{ e,d,a,b } C、{ e,d } D、{ e,d,a,b,ε} 学生答案： C 标准答案：D 解析： 得分： 0 5. (单选题) 递归下降分析法和预测分析法要求描述语言的文法是( )。(本题2.0分) A、正规文法 B、LR(1)文法 C、LL(1)文法 D、右线性文法 学生答案： B 标准答案：C 解析： 得分： 0 6. (单选题) 与下图所示FA等价的DFA是( )。 (本题2.0分) A、 B、 C、 D、其他三项都不是学生答案： A 标准答案：A 解析： 得分： 2 7. (单选题) 正规式的运算符“*”读作( )。(本题2.0分) A、或 B、闭包 C、乘 D、连接 学生答案： C 标准答案：B 解析： 得分： 0 8. (单选题) 编译程序是对( )程序进行翻译。(本题2.0分) A、高级语言 B、机器语言 C、汇编语言 D、自然语言 学生答案： D 标准答案：A 解析： 得分： 0 9. (单选题) 下列描述中不正确的是( )。(本题2.0分) A、在文法中使用递归规则,使得我们能用有限的规则去定义无穷集合的语言。 B、最左推导也称规范推导,用规范推导推导出的称为规范句型。 2022编译原理复习题及答案 一、选择题 1．一个正规语言只能对应(B) A一个正规文法 B一个最小有限状态自动机 2．文法G[A]：A→εA→aBB→AbB→a是(A) A正规文法 B二型文法 3．下面说法正确的是(A) A一个SLR（1）文法一定也是LALR（1）文法B一个LR（1）文法一定也是LALR（1）文法 4．一个上下文无关文法消除了左递归，提取了左公共因子后是满足LL（1）文法的(A必要条件 B充分必要条件 5．下面说法正确的是(B) A一个正规式只能对应一个确定的有限状态自动机B一个正规语言可能对应多个正规文法6．算符优先分析与规范归约相比的优点是(A) A归约速度快 B对文法限制少 7．一个LR（1）文法合并同心集后若不是LALR（1）文法(B) A则可能存在移进/归约冲突B则可能存在归约/归约冲突 C则可能存在移进/归约冲突和归约/归约冲突8．下面说法正确的是(A) ALe某是一个词法分析器的生成器BYacc是一个语法分析器 9．下面说法正确的是(A) A一个正规文法也一定是二型文法 B一个二型文法也一定能有一个等价的正规文法10．编译原理是对(C)。 A、机器语言的执行 B、汇编语言的翻译 C、高级语言的翻译 D、高级语言程序的解释执行11．用高级语言编写的程序经编译后产生的程序叫(B) A) A．源程序B．目标程序C．连接程序D．解释程序 12．(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 13．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化， 目标代码生成等六个部分，还应包括(C)。A．模拟执行器 B．解释器 C．表格处理和出错处理D．符号执行器 14．源程序是句子的集合，(B)可以较好地反映句子的结构。 A.线性表 B.树 C.完全图 D.堆栈 15．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置D、单词的种别编码和自身值 C、单词的种别编码16．词法分析器不能(D) A.识别出数值常量 B.过滤源程序中的注释D.发现括号不匹配 C.扫描源程序并识别记号 17．文法：G：S→某S某|y所识别的语言是(D)。 A、某y某 第八节习题一、单项选择题 1、将编译程序分成若干个“遍”是为了。 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、词法分析器的输入是。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循的是- 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序是对。 a．汇编程序的翻译b．高级语言程序的解释执行 c．机器语言的执行d．高级语言的翻译 10、语法分析应遵循。 a．语义规则b．语法规则 c．构词规则d．等价变换规则 解答 1、将编译程序分成若干个“遍”是为了使编译程序的结构更加清晰，故选b。 2、构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识，故选d。 3、对编译而言，变量既持有左值又持有右值，故选c。 4、编译程序打交道最多的就是各种表格，因此选d。 5、目标代码包括汇编指令代码、可重定位指令代码和绝对指令代码3种，因此不是目标代码的只能选d。 6、词法分析遵循的是构词规则，语法分析遵循的是语法规则，中间代码生成遵循的是语义规则，并且语义规则可以定义一个程序的意义。因此选a。 7、b 8、c 9、d 10、c 二、多项选择题编译原理复习(有答案)
编译原理复习题一(含答案)
编译原理复习题及参考答案
山东农业工程学院编译原理(高起专)复习题及参考答案
2022编译原理复习题及答案
编译原理期末复习题(含答案)