编译原理复习题及答案
编译原理复习题及答案
一、选择题
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)
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、高级语言程序的解释执行C．FORTRAN
D．PASCAL
11．(A)是一种典型的解释型语言。A．BASICB．C
12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完
成的。A.编译器B.汇编器C.解释器D.预处理器13．用高级语言编写的程
序经编译后产生的程序叫(B)A．源程序B．目标程序C．连接程序14．(C)不是编译程序的组成部分。A.词法分析程序B.代码生成程序
D．解释程序D.语法分析程序
C.设备管理程序
15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。A．模拟执行器B．解释器C．表格处理和出错处理D．符号执行器16．编
译程序绝大多数时间花在(D)上。A．出错处理B．词法分析
C．目标代码生成
D．表格管理
17．源程序是句子的集合，(B)可以较好地反映句子的结构。A.线性表B.树C.完全图18．词法分析器的输出结果是(D)。A、单词自身值
C、单词的种别编码19．词法分析器不能(D)A.识别出数值常量
D.堆栈
B、单词在符号表中的位置D、单词的种别编码和自身值B.过滤源程序中的注释D.发现括号不匹配
C.扫描源程序并识别记号
20．文法：G：S→某S某|y所识别的语言是(D)。
A、某y某
B、(某y某)某21．如果文法G是无二义的，则它的任何句子α(A)A．最左推导和最右推导对应的语法树必定相同
B．最左推导和最右推导对应的语法树可能不同C．最左推导和最右推导必定相同
C、某某y某某
D、某ny某n(n≥0)
D．可能存在两个不同的最左推导，但它们对应的语法树相同22．正则文法(A)二义性的。
A.可以是
B.一定不是
C.一定是
23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。A.存在B.不存在C.无法判定是否存在24．给定文法
A→bA|ca，为该文法句子的是(C)A.bbaB.cabC.bca
D.cba
25．设有文法G[S]：SS1|S0|Sa|Sc|a|b|c，下列符号串中是该文法的句子有(D)A.ab0B.a0c01C.a0b0aD.bc1026．文法G产生的(D)的全体是该文法描述的语言。A．句型B.终结符集C.非终结符集27．若文法G定义的语言是无限集，则文法必然是(A)A．递归的B.上下文无关的C.二义性的28．描述一个语言的文法是(B)A．唯一的B.不唯一的29．一个文法所描述的语言是(A)A．唯一的B.不唯一的30．采用自上而下分析，必须(A)。A、消除回溯
C、消除右递归
C.可能唯一C.可能唯一
B、消除左递归
D.句子
D.无二义性的
D、提取公共左因子
31．编译过程中，语法分析器的任务是(A)①分析单词的构成②分析单词串如何构成语句③分析语句是如何构成程序④分析程序的结构
A.②③
B.④
C.①②③④
D.②③④32．词法分析器的输入是(A)。
A．符号串B．源程序C．语法单位D．目标程序33．两个有穷自动机等价是指它们的(C)。A．状态数相等
C．所识别的语言相等
B．有向弧数相等
D．状态数和有向弧数相等
34．若状态k含有项目“A→α·”，且仅当输入符号a∈FOLLOW(A)时，才用规则“A→α”归约的语法分析方法是(D)。A．LALR分析法B．LR(0)分析法C．LR(1)分析法D．SLR(1)分析法35．若a为终结符，则A→α·aβ为(B)项目。A．归约B．移进
C．接受
D．待约
36．在使用高级语言编程时,首先可通过编译程序发现源程序的全部和部分(A)错误。A.语法B.语义C.语用D.运行
37．乔姆斯基(Chomky)把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是(B)A.非限制文法B.正则文法C.上下文有关文法D.上下文无关文法38．一个句型中的(A)称为该句型的句柄。A.最左直接短语B.最右直接短语
C.终结符
D.非终结符
39．在自底向上的语法分析方法中，分析的关键是(D)
A.寻找句柄
B.寻找句型
C.消除递归40．在自顶向下的语法分析方法中，分析的关键是(C)A.寻找句柄B.寻找句型C.消除递归
D.选择候选式D.选择候选式
41．在LR分析法中，分析栈中存放的状态是识别规范句型(C)的DFA 状态。A.句柄B.前缀C.活前缀D.LR(0)项目
42．一个上下文无关文法G包括四个组成部分，它们是一组非终结符号，一组终结符号，一个开始符号，以及一组(B)A.句子B.产生式C.单词D.句型43．词法分析器用于识别(C)A.句子B.产生式
C.单词
D.句型D.目标程序D.代码生成D.状态集D.句子
44．编译程序是一种(B)A.汇编程序B.翻译程序
C.解释程序
45．按逻辑上划分，编译程序第三步工作是(A)A.语义分析B.词法分析C.语法分析46．在语法分析处理中，FIRST集合、FOLLOW集合均是(B)A.非终结符集B.终结符集C.字母表47．编译程序中语法分析器接收以(A)为单位的输入。A.单词B.表达式C.产生式48．编译过程中，语法分析器的任务就是(B)A.分析单词是怎样构成的
C.分析语句和说明是如何构成程序的
B.分析单词串是如何构成语句和说明的D.分析程序的结构
D.个数是常量D.图灵机D.语义分析
49．若一个文法是递归的，则它所产生的语言的句子(A)。A.是无穷多个B.是有穷多个C.是可枚举的50．识别上下文无关语言的自动机是(C)A.下推自动机B.NFA51．编译原理各阶段工作都涉及(B)A.词法分析B.表格管理
C.DFA
C.语法分析
52．正则表达式R1和R2等价是指(C)
A.R1和R2都是定义在一个字母表上的正则表达式
B.R1和R2中使用的运算符相同
C.R1和R2代表同一正则集
D.R1和R2代表不同正则集
53．已知文法G[S]:S→A1，A→A1|S0|0。与G等价的正规式是(C)
A.0(0|1)某
B.1某|0某1
C.0(1|10)某154．与(a|b)某(a|b)等价的正规式是(C)。A.a某|b某B.(ab)某(a|b)55．(D)文法不是LL(1)的。A.递归B.右递归
C.(a|b)(a|b)某C.2型
D.1(10|01)某0D.(a|b)某
D.含有公共左因子的
56．给定文法A→bA|cc，则符号串
①cc②bcbc③bcbcc④bccbcc⑤bbbcc中，是该文法句子的是
(D)A.①B.③④⑤C.②④D.①⑤57．LR(1)文法都是()
A.无二义性且无左递归
C.无二义性但可能是左递归
B.可能有二义性但无左递归D.可以既有二义性又有左递归
D.7
58．文法E→E+E|E某E|i的句子i某i+i某i有(C)棵不同的语法树。
A.1
B.3
C.559．文法S→aaS|abc定义的语言是(C)。
A.{a2kbc|k>0}
B.{akbc|k>0}
C.{a2k-1bc|k>0}C.接受项目C.移进/归
约
D.{akakbc|k>0}D.待约项目D.归约/归约
60．若B为非终结符，则A→.B为(D)。
A.移进项目
B.归约项目61．同心集合并可能会产生新的(D)冲突。A.
二义B.移进/移进
62．就文法的描述能力来说，有(C)
A．SLR(1)LR(0)B．LR(1)LR(0)C．SLR(1)LR(1)D．无二义文法
LR(1)63．如图所示自动机M，请问下列哪个字符串不是M所能识别的(D)。
A.bbaa
B.abba
C.abab
D.aabb
64．有限状态自动机能识别(C)
A.上下文无关语言
B.上下文有关语言
C.正规语言
D.0型文法定义的语言
65．已知文法G是无二义的，则对G的任意句型α(A)
A.最左推导和最右推导对应的语法树必定相同
B.最左推导和最右推导对应的语法树可能相同
C.最左推导和最右推
导必定相同
D.可能存在两个不同的最左推导，但他们对应的语法树相同66．(B)不是DFA的成分
A.有穷字母表
B.多个初始状态的集合
C.多个终态的集合
D.转换函数
D.a+b某c+d
D．(a(b+c))+d
67．与逆波兰式(后缀表达式)ab+c某d+对应的中缀表达式是(B)
A.a+b+c某d
B.(a+b)某c+d
C.(a+b)某(c+d)68．后缀式abc+d+可用表达式(B)来表示。A．((a+b)c)+dB．(a+(bc))+d69．表达式A某(B-C某(C/D))的后缀式为(B)。A．ABC-CD/某某B．ABCCD/某-某
C．(a(b+c))+d
C．ABC-某CD/某D．以上都不对
70．(D)不是NFA的成分。A.有穷字母表B.初始状态集合C.终止状态集合D.有限状态集合
二、问答题
1．将文法G[S]改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。G[S]：S→bSAe|bAA→Ab|d答：
文法G[S]改写为等价的不含左递归和左公共因子的G'[S]为：
S→bBB→SAe|AA→dA'
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→[AA→B]|ASB→aB|a答：
文法G[S]改写为等价的不含左递归和左公共因子的G'[S]为：
S→[AA→B]A′A′→SA′|εB→aB′
B′→B|ε
4．判断下面文法是否为LL(1)文法，若是,请构造相应的LL(1)分析表。S→aH
H→aMd|dM→Ab|εA→aM|e答：
首先计算文法的FIRST集和FOLLOW集如下表。
文法的FIRST集和FOLLOW集非终结符FIRST集FOLLOW集
S{a}.........{#}...H{#}...{a，d}.....M{a，e，ε}{d，b}A{b}....{a，e}.....由于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)分析表如下表。adbS→aH.H→aMd→d.M→Ab.→ε→εA→aM.5．判断下面
文法是否为LL(1)文法，若是，请构造相应的LL(1)分析表。
S→aDD→STe|εT→bH|HH→d|ε答：
首先计算文法的FIRST集和FOLLOW集如下表。非终结符FIRST集FOLLOW集S{a}{#，b，d，e}.D{a，ε}{#，b，d，e}
e→Ab→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，I5中的移进-归约和归约-归约冲突可以由Follow集解决,所以G′是SLR(1)文法。构造的SLR(1)分析表如下表：ACTIONGOTOnameabd#ET0S2r2r211acc2S5r2r2433S64S75S5r2r4r243
67r1r3r115．给出文法G[S]的LR(1)项目集规范族中I0项目集的全
体项目。G[S]为：S→BD|DB→aD|bD→B
I0:
答：I0：
16．给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。G[S]为：S→D;D|DD→DB|BB→a|b
I0:
答：I0:
17．给出文法G[S]的LR(1)项目集规范族中I0项目集的全体项目。G[S]为：S→S;V|VV→VaA|AA→b(S)|ε
I0:
答：I0:
18．文法G[M]及其LR分析表如下，请给出对串dbba#的分析过程。G[M]:1)M→VbA
2)V→d3)V→ε
4)A→a5)A→Aba
6)A→εACTIONGOTOnamebda#MA0r3S311acc2S43r24r6S5r665r4r46S7r 17S88r5r5答：对串dbba#的分析过程如下表步骤状态栈文法符号栈剩余输入符号动作#dbba#移进10#dbba#用V→d归约203#Vbba#移进
302#Vbba#用A→ε归约4024#VbAba#50246#VbAba#移进602467#VbAba#移进7024678#VbA#用A→Aba归约80246#M#用M→VbA归约901接受19．文法G[S]及其LR分析表如下，请给出对输入串da;aoa#的分析过程。
G[S]:0)S′→S
1)S→dSoS
2)S→dS
3)S→S;S
V2
4)S→aname012345678dS2S2S2S2aS3r4S7r3r1ACTION;S4r4S4r3S4aS3S 3S3S3#accr4r2r3r1GOTOS1568答：输入串da;aoa#的分析过程如下表：步骤状态栈文法符号栈
#10#d202#da3023#dS4025#dS;50254#dS;a602543#dS;S702546#dS8025#dSo 90257#dSoa1002573#dSoS1102578#S1201剩余输入符号
da;aoa#a;aoa#;aoa#;aoa#aoa#oa#oa#oa#a####动作移进移进用S→a归约移进移进用S→a归约用S→S;S归约移进移进用S→a归约用S→dSoS归约接受
20．文法G[M]及其LR分析表如下，请给出对串dada#的分析过程。
G[M]:1)S→VdB
2)V→e
3)V→ε
4)B→a
5)B→Bda
6)B→εACTION状态
dea#S0r3S311acc2S43r24r6S5r65r4r46S7r17S88r5r5答：对串dada#的分析过程如下表步骤状态栈文法符号栈剩余输入符号
10#dada#202#Vdada#3024#Vdada#40245#Vdada#50246#VdBda#
GOTOB6V2动作用V→ε归约移进移进用B→a归约678902467024678024601#VdBd#VdBda#VdB#Sa####移进移进用B→Bda归约
用S→VdB归约接受
21．文法G[E]为：E→E+T|TT→T某F|FF→(E)|i
试给出句型(E+F)某i的短语，简单(直接)短语,句柄和最左素短语。答：
短语有:(E+F)某i，(E+F)，E+F，F，i简单(直接)短语有：F，i句
柄是：F
最左素短语是：E+F
22．文法G[S]为：S→V
V→T|ViTT→F|T+FF→)V某|(
试给出句型ViFi(的短语，简单(直接)短语,句柄和最左素短语。答：短语有:ViFi(，ViF，F，(简单(直接)短语有:F，(句柄是:F
最左素短语是:ViF
23．文法G[S]为：S→SdT|TT→T
试给出句型(SdG)
句型(SdG)
短语：(SdG)
最左素短语：SdG
24．按指定类型给出下列语言的文法。
(1)L1={anbmc|n≥0，m>0}用正规文法。(2)L2={a0n1nbdm|n>0，m>0}用二型文法。答：
(1)描述L1语言的正规文法如下：S→aS|AA→bA|bBB→c
(2)描述L2语言的二型文法如下：
S→ABA→aTT→0T1|01B→bDD→dD|d
最新编译原理复习题及答案
编译原理复习题及答案 一、选择题 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. 可能唯一
编译原理复习题及参考答案
中南大学网络教育课程考试复习题及参考答案 编译原理 一、判断题： 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.一个上下文无关文法的开始符，可以是终结符或非终结符。 [ ] 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、试证明：任何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. 一个上下文无关文法的开始符，可以是终结符或非终结符。( ) 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．编译程序是一种常用的软件。 A) 应用B) 系统C) 实时系统D) 分布式系统 2．编译程序生成的目标代码程序是可执行程序。 A) 一定B) 不一定 3．编译程序的大多数时间是花在上。 A) 词法分析B) 语法分析C) 出错处理D) 表格管理4．将编译程序分成若干“遍”将。 A)提高编译程序的执行效率； B)使编译程序的结构更加清晰，提高目标程序质量； C)充分利用内存空间，提高机器的执行效率。 5．编译程序各个阶段都涉及到的工作有。 A) 词法分析B) 语法分析C) 语义分析D) 表格管理6．词法分析的主要功能是。 A) 识别字符串B) 识别语句C) 识别单词D) 识别标识符7．若某程序设计语言允许标识符先使用后说明，则其编译程序就必须。 A) 多遍扫描B) 一遍扫描 8．编译方式与解释方式的根本区别在于。 A) 执行速度的快慢B) 是否生成目标代码 C) 是否语义分析
9．多遍编译与一遍编译的主要区别在于。 A)多遍编译是编译的五大部分重复多遍执行，而一遍编译是五大部 分只执行一遍； B)一遍编译是对源程序分析一遍就立即执行，而多遍编译是对源程 序重复多遍分析再执行； C)多遍编译要生成目标代码才执行，而一遍编译不生成目标代码直 接分析执行； D)多遍编译是五大部分依次独立完成，一遍编译是五大部分交叉调 用执行完成。 10．编译程序分成“前端”和“后端”的好处是 A)便于移植 B)便于功能的扩充 C)便于减少工作量 D)以上均正确
第二章练习题（文法与语言） 一、选择题 1．文法 G 产生的 (1) 的全体是该文法描述的语言。 A.句型 B. 终结符集 C. 非终结符集 D. 句子 2．若文法 G 定义的语言是无限集，则文法必然是 (2) A递归的 B 上下文无关的 C 二义性的 D 无二义性的 3． Chomsky 定义的四种形式语言文法中， 0 型文法又称为(A)文法； 1 型文法又称为(C)文法； 2 型语言可由(G) 识别。 A 短语结构文法 B 上下文无关文法 C 上下文有关文法 D 正规文法 E 图灵机 F 有限自动机 G 下推自动机 4．一个文法所描述的语言是(A)；描述一个语言的文法是(B)。 A 唯一的 B 不唯一的 C 可能唯一，也可能不唯一 二、构造文法以生成下列语言： 1．{a n b n︱n≥0} G=（{S}，{a，b}，S，P），其中P = { S→ | aSb } 2．{a n b m︱n，m≥1} G=（{S，A，B}，{a，b}，S，P）， 其中P = { S→ AB，A→a︱aA，B→b︱bB} 3．{a n , b m︱n，m≥1} G=（{S，A，B}，{a，b}，S，P）， 其中P = { S→ A | B，A→a︱aA，B→b︱bB}
编译原理复习题一(含答案)
一、单选题（每题2分，共20分） 1. 编译器的（）阶段可将源程序的字符流收集到若干记号中。 A. 语法分析 B. 语义分析 C. 代码生成 D. 词法分析 2. 文法A aA | b属于正则文法，正则文法在乔姆斯基层次中对应于（）文法。 A. 1型 B. 2型 C. 3型 D. 0型 3. 某C语言源代码文件包含#include
编译原理期末考试复习题(含答案)
编译原理期末考试复习题（含答案） 一、选择题 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.编译过程的阶段 由词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段 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 型 ●最左（右）推导
编译原理复习题有答案版
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) (3) + a (2) 给出下面语言的相应文法 L1={a n b n a m b m|n,m≥0} 给出下面语言的相应文法 答案：S→AB|A|B|∑ A→aAb|ab B→aBb|ab L2={a n b n c i|n≥1,i≥0}
编译原理复习题答案
二、概念题 1、设有文法：P→P+Q|Q Q→Q*R|R R→(P)|i （1）证明Q*R+Q+Q是它的一个句型。（3分) （2）给出Q*R+Q+Q的所有短语，直接短语和句柄。(4分) （3）给出句子ｉ+ｉ*ｉ的最右推导。(4分) （4）给出句子ｉ+ｉ*ｉ的最左推导。(4分) 2、设有文法：E→E+T|T T→T*F|F F→(E)|i （1）证明E+T*F是它的一个句型。（3分) ⇒+⇒+* 答案：E E T E T F （2）给出E+T*F的所有短语，直接短语和句柄。(4分) 短语: E+T*F, T*F, 直接短语: T*F 句柄: T*F （3）给出句子ｉ+ｉ*ｉ的最右推导。(4分) 3、写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。答案：逆波兰式：(abcd-*+)
三元式序列: OP ARG1 ARG2 (1) - c d (2) * b (1) (3) + a (2) 三、词法分析题 给出下面语言的相应文法 L1={a n b n a m b m|n,m≥0} 答案：S→AB|A|B|∑ A→aAb|ab B→aBb|ab 给出下面语言的相应文法 L2={a n b n c i|n≥1,i≥0} 答案：S→AB|B A→a|aA B→bBc|bc 给出下面语言的相应文法 L3={a n b n c m| m,n≥1，n为奇数，m为偶数}。 答案：文法G(S):S→AC A→aaAbb/ab C→ccCcc/cc 四、词法分析题
1、构造下面正规式相应的DFA ((0|1)*|(11)*)* （要求：先将正规式转化为NFA，再将NFA确定化，最小化）2、构造下面正规式相应的DFA 1(0|1)*101 答案： I I0 I1 {X} Ф{A,B,C} {A,B,C} { B,C} { B,C,D} {B,C} { B,C} { B,C,D} {B,C,D} { B,C,E} { B,C,D} {B,C,E} { B,C} {B,C,D,y} {B,C,D,y} {B,C,E} { B,C,D} 3、构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化）答案：(一)相应的正规式为(a|b)*ab(a|b)* (二) ①与此正规式对应的NFA为 ②状态转换矩阵为：
编译原理复习题目集答案
第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 的一个状态集合： 0 1 X A A A AB AB AC AB AC A ABY ABY AC AB 除X ，A 外，重新命名其他状态： 0 1 X A A A B (0|1)* 1 1 1(0|1)*101 X Y X A B C D Y 1 X A B C Y 1 1 1 0,1
B C B C A D D C B 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如下 a b S A Q A A B,Z B,Z Q D Q Q D,Z D A B D,Z A D B Q D a b 00 1 3 1 1 2 2* 3 4 3 3 5 4 1 6 5* 1 4 6 3 4 X A B C D 1 1 0 1 1 1
编译原理复习题及答案
编译原理复习题及答案一、选择题 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．C C．FORTRAN D．PASCAL 12．把汇编语言程序翻译成机器可执行的目标程序的工作是由(B)完成的。 A. 编译器 B. 汇编器 C. 解释器 D. 预处理器 13．用高级语言编写的程序经编译后产生的程序叫(B) A．源程序B．目标程序C．连接程序D．解释程序14．(C)不是编译程序的组成部分。 A.词法分析程序 B.代码生成程序 C.设备管理程序 D.语法分析程序 15．通常一个编译程序中，不仅包含词法分析，语法分析，语义分析，中间代码生成，代码优化，目标代码生成等六个部分，还应包括(C)。 A．模拟执行器B．解释器C．表格处理和出错处理D．符号执行器16．编译程序绝大多数时间花在(D)上。 A．出错处理B．词法分析C．目标代码生成D．表格管理17．源程序是句子的集合，(B)可以较好地反映句子的结构。 A. 线性表 B. 树 C. 完全图 D. 堆栈 18．词法分析器的输出结果是(D)。 A、单词自身值 B、单词在符号表中的位置 C、单词的种别编码 D、单词的种别编码和自身值 19．词法分析器不能(D) A. 识别出数值常量 B. 过滤源程序中的注释 C. 扫描源程序并识别记号 D. 发现括号不匹配 20．文法：G：S→xSx | y所识别的语言是(D)。 A、xyx B、(xyx)* C、x*yx* D、x n yx n (n≥0) 21．如果文法G是无二义的，则它的任何句子α(A) A．最左推导和最右推导对应的语法树必定相同 B．最左推导和最右推导对应的语法树可能不同 C．最左推导和最右推导必定相同 D．可能存在两个不同的最左推导，但它们对应的语法树相同 22．正则文法(A)二义性的。 A. 可以是 B. 一定不是 C. 一定是 23．(B)这样一些语言，它们能被确定的有穷自动机识别，但不能用正则表达式表示。 A. 存在 B. 不存在 C. 无法判定是否存在 24．给定文法A→bA | ca，为该文法句子的是(C)
大学编译原理课程复习试题及答案
编译原理复习材料 选择题 1. 文法S→0S | S1 | 0的语言是( )。 A. { 0 m1m| m >=0 } B. { 0 m1m| m >=1 } C. { 0 m1n | m>=1,n>=0 } D. { 0 m1n | m>=0,n>=1 } 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. 在利用寄存器R生成T1:=C/B的目标代码同时,还应记录信息( )。 A. C/B在T1中 B. T1在C/B中 C. R含有T1, T1在R中 D. R含有C/B, C/B在R中 1.D 2.B 3.C 4.B 5.B 6.A 7.B 8.D 9.D 10.C
山东农业工程学院编译原理(高起专)复习题及参考答案
作业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、最左推导也称规范推导,用规范推导推导出的称为规范句型。