编译原理复习整理(重点含答案)
1、给出下面语言的相应文法。L1={a n b n c i|n≥1,i≥0}
从n，i的不同取值来把L1分成两部分：前半部分是anbn：A→aAb|ab后半部分是ci：B→Bc|ε所以整个文法G1[S]可以写为：G1(S):S→AB；A→aAb|ab；B→cB|ε
3、构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。
（要求：先将正规式转化为NFA，再将NFA确定化，最小化）
4、对下面的文法G:
E →TE ’ E ’→+E|ε T →FT ’ T ’→T|ε
F →PF ’ F ’ →*F ’|ε P →(E)|a|b|∧
（1）证明这个文法是LL(1)的。 （2）构造它的预测分析表。
(1)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,^,+,),#} (2)考虑下列产生式:
'→+'→'→'→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)文法. (3)
+ * (
) a b ^ # E
E TE →'
E TE →' E TE →' E TE →'
E' '→+E E
'→E ε
'→E ε
T
T F T →' T F T →' T F T →' T F T →' T' '→T ε
'→T T '→T ε '→T T '→T T '→T T '→T ε
F
F P F →'
F P F →' F P F →' F P F →'
F' '→F ε '→'F F * '→F ε '→F ε '→F ε '→F ε '→F ε '→F ε
P
P E →() P a → P b → P →^
5、考虑文法: S →AS|b A →SA|a （1）列出这个文法的所有LR(0) 项目。 0.'→?S S 1.'→?S S 2.S AS →? 3.S A S →? 4.S AS →? 5.S b →? 6.S b →?7.A SA →?8.A S A →? 9.A SA →? 10.A a →? 11.A a →? (2)给出识别文法所有活前缀的DFA 。
S A ε
S
εεε
ε a
εε ε
A S ε ε b
确定化：
S A a b {0,2,5,7,10} {1,2,5,7,8,10
} {2,3,5,7,10} {11} {6} {1,2,5,7,8,10
} {2,5,7,8,10} {2,3,5,7,9,10} {11} {6} {2,3,5,7,10} {2,4,5,7,8,10
} {2,3,5,7,10} {11} {6} {2,5,7,8,10} {2,5,7,8,10} {2,3,5,7,9,10} {11} {6} {2,3,5,7,9,10
} {2,4,5,7,8,10
} {2,3,5,7,10} {11} {6} {2,4,5,7,8,10
}
{2,5,7,8,10}
{2,3,5,7,9,10}
{11} {6} {11} φ φ φ φ {6} φ
φ
φ
φ
10
5
7 6
1 11
2 3 4
8 9
A S
S A a
b
S a A S b S A b a A
A S
b
a a
b b a
DFA
6、设有文法：P →P+Q|QQ →Q*R|RR →(P)|i
（1）证明Q*R+Q+Q 是它的一个句型。（3分) P=>P+Q=>P+Q+Q=>Q+Q+Q=>Q*R+Q+Q
（2）给出Q*R+Q+Q 的所有短语，直接短语和句柄。(4分) 短语: Q*R,Q*R+Q,Q*R+Q+Q 直接短语: Q*R 句柄: Q*R （3）给出句子ｉ+ｉ*ｉ的最右推导。(4分) （4）给出句子ｉ+ｉ*ｉ的最左推导。(4分) 7、设有文法：E →E+T|TT →T*F|FF →(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分)
0:'→?S S
S AS →? S b →? A SA →? A a →? 4:S A S →? S AS →? S b →?
A SA →? A a →? 3:'→?S S
A S A →? A SA →? A a →? S AS →?S b →?
2:S b →?
1:A a →? 5:A S A →? S AS →? S b →?
A SA →? A a →? 6:A SA →?
S A S →?
S AS →? S b →?
A SA →?
A a →?
7:S AS →? A S A →?
S AS →? S b →?
A SA →?
A a →?
11、构造下面正规式相应的DFA
1(0|1)*101
14、对下面的文法G:
Expr→- ExprExpr→(Expr)|Var ExprTailExprTail→- Expr|εVar→id VarTail VarTail→(Expr) |ε
（1）构造LL(1)分析表。（12分）
（2）给出对句子id—id((id))的分析过程。（8分）
16、已知文法G[S] 为： S->a|^|(T) T->T,S|S
①消除文法G[S]中的左递归，得文法G ′[S]。
ε
|,)
(||^)
(T S T T S T T a S S G '→''→→'
② 文法G ′[S]是否为LL(1)的？若是，给出它的预测分析表。
FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST()={,,} FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW()={)} 预测分析表
a
^
(
) , # S
T
是LL(1)文法
17、对下面的文法G:
S → S ∨ a T | a T | ∨ a TT →∧ a T | ∧ a (1) 消除该文法的左递归和提取左公因子；构造各非终结符的FIRST 和FOLLOW 集合；
'T ε'T S a →S →^S T →()T ST →'T ST →'T ST →''T '→T ε'→'T ST ,
18、文法G(S)及其LR分析表如下，请给出串baba#的分析过程。(1) S → DbB (2) D → d (3) D →ε
(4) B → a (5) B → Bba (6) B →ε
LR分析表
2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。答：逆波兰式： abc*bd*+:=
四元式序列：三元式序列: OP ARG1 ARG2 (1) (*， b，c， t
1
) (1) (*b，c )
(2) (*， b， d， t
2
) (2) (*b， d)
(3) (+，t1，t
2，t
3
) (3) (+(1)， (2))
(4) (:=，t3，/， a) (4) (:=(3)， a)
八、语义分析题
1、将语句
if ((A<0) (B>0)) then while (C>0) do C:=C-D
翻译成四元式
答案：100 (j<，A，0，104)
101 (j，-，-，102)
102 (j>，B，0，104)
103 (j，-，-，109)
104 (j>，C，0，106)
105 (j，-，-，109)
106 (-，C，D，T1)
107 (:=，T1，-，C)
108 (j，-，-，104)
109
2、写出下面语句经语法制导翻译后所生成的四元式代码序列。if x
答案：假设初始为100，则四元式代码序列为
100 if x<
y
goto 102
101 goto 107
102 if e>c goto 104 103 goto 109
104 M:=C+ 1
105 C:=M
106 goto 102
107 N:=X+ 5
108 X:=N
109
8、写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。
答案：逆波兰式：(abcd-*+)
三元式序列:
OP ARG1 ARG2
(1) - c d
(2) * b (1)
(3) + a (2)
1．编译程序是对高级语言程序的解释执行。(× )
2．一个有限状态自动机中，有且仅有一个唯一的终态。(×)
3．一个算符优先文法可能不存在算符优先函数与之对应。(√ )
4．语法分析时必须先消除文法中的左递归。(×)
5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√) 6．逆波兰表示法表示表达式时无须使用括号。(√ )
7．静态数组的存储空间可以在编译时确定。(×)
8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(×)
9．两个正规集相等的必要条件是他们对应的正规式等价。(× )
10．一个语义子程序描述了一个文法所对应的翻译工作。(×)
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、简要说明语义分析的基本功能：确定类型、类型检查、语义处理和某些静态语义检查。 1．词法分析：词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。
3．简述自下而上的分析方法。：所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。 2．LL(1)文法：若文法的任何两个产生式A →α |β都满足下面两个条件：（1）FIRST(α)?FIRST(β ) = φ；（2）若β?* ε，那么FIRST(α) ?FOLLOW( A ) =φ。我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L 代表从左向右扫描输入，第二个L 表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。
3．语法树：句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(V N ，V T ，P ，S)，对于G 的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S 。(2)每个节点的标记都是V 中的一个符号。(3)若一棵子树的根节点为A ，且其所有直接子孙的标记从左向右的排列次序为A 1A 2…A R ，那么A →A 1A 2…A R 一定是P 中的一条产生式。(4)若一标记为A 的节点至少有一个除它以外的子孙，则A ∈V N 。(5)若树的所有叶节点上的标记从左到右排列为字符串w ，则w 是文法G 的句型；若w 中仅含终结符号，则w 为文法G 所产生的句子。
4．LR(0)分析器：所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的 每一步，只须根据分析栈当前已移进和归约出的全部文法符号，并至多再向前查看0个输入符号，就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成，从而也就可以确定当前所应采取的分析动作 (是移进还是按某一产生式进行归约等)。
5．语言和文法：文法就是语言结构的定义和描述，是有穷非空的产生式集合。文法G 定义为四元组的形式：G=(V N ，V T ，P ，S)其中：V N 是非空有穷集合，称为非终结符号集合；V T 是非空有穷集合，称为终结符号集合；P 是产生式的集合(非空)；S 是开始符号(或识别符号)。这里，V N ∩V T =?，S ∈V N 。V=V N ∪V T ，称为文法G 的字母表，它是出现文法产生式中的一切符号的集合。
文法G 所描述的语言用L(G)表示，它由文法G 所产生的全部句子组成，即 L(G)={x| S ?*x ，其中S 为文法开始符号，且+
∈T V x }
简单的说，文法描述的语言是该文法一切句子的集合。 2.二义性文法：如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。
6.语法：一组规则，用它可形成和产生一组合式的程序。
7.文法:描述语言的语法结构的形式规则。12.规范句型------由规范推导所得到的句型。
15.句柄：一个句型的最左直接短语。21.语义：定义程序的意义的一组规则。
10.短语：令G是一个文法，S划文法的开始符号，假定αβδ是文法G的一个句型，如果有SαAδ且Aβ，则称β是句型αβδ相对非终结符A的短语。
1．编译程序和高级语言有什么区别?
用汇编语言或高级语言编写的程序，必须先送入计算机，经过转换成用机器语言表示的目标程序（这个过程即编译），才能由计算机执行。执行转换过程的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转换过的叫目标程序，也就是机器语言。
编译程序的工作情况有三种：汇编型、解释型和编译型。汇编型编译程序用来将汇编语言编写的程序，按照一一对应的关系，转换成用机器语言表示的程序。
解释型编译程序将高级语言程序的一个语句，先解释成为一组机器语言的指令，然后立即执行，执行完了，取下一组语句解释和执行，如此继续到完成一个程序止。用解释型编译程序，执行速度很慢，但可以进行人和计算机的"对话"，随时可以修改高级语言的程序。BASIC语言就是解释型高级语言。编译型编译程序将级语言编写的程序，一次就会部翻译成机器语言表示的程序，而且过程进行很快，在过程中，不能进行人机对话修改。FORTRAN语言就是编译型高级语言。
1．计算机执行用高级语言编写的程序主要有两种途径：___解释__和__编译___。
2．扫描器是__词法分析器___，它接受输入的__源程序___，对源程序进行___词法分析__并识别出一个个单词符号，其输出结果是单词符号，供语法分析器使用。
3．自上而下分析法采用___移进__、归约、错误处理、___接受__等四种操作。
4．一个LR分析器包括两部分：一个总控程序和___一张分析表__。
5．后缀式abc-/所代表的表达式是___a/(b-c)__。
6．局部优化是在__基本块___范围内进行的一种优化。
2.编译过程可分为（词法分析），（语法分析），（语义分析与中间代码生成），（优化）和（目标代码生成）五个阶段。
3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（二义性的）。
5.语法分析器的输入是（单词符号），其输出是（语法单位）。
6.扫描器的任务是从（源程序）中识别出一个个（单词符号）。
13.根据优化所涉及的程序范围，可将优化分成为(局部优化），（循环优化），（全局优化）三个级别。
14.语法分析的方法大致可分为两类，一类是（自上而下）分析法，另一类是（自下而上）分析法。
15.预测分析程序是使用一张（分析表）和一个（符号栈）进行联合控制的。
17.一张转换图只包含有限个状态,其中有一个被认为是（初）态;而且实际上至少要有一个（终）态。
19.语法分析是依据语言的（语法）规则进行。中间代码产生是依据语言的（语义）规则进行的。
21.一个文法G，若它的预测分析表M不含多重定义，则该文法是（LL(1) 文法）。
24.最右推导亦称为（规范推导），由此得到的句型称为（规范）句型。
26.对于文法G，仅含终结符号的句型称为( 句子)。
27.所谓自上而下分析法是指(从开始符号出发，向下推导，推出句子）
29.局限于基本块范围的优化称（局部优化）。
31.2型文法又称为（上下文无关）文法；3型文法又称为（正规）文法。
33.算符优先分析法每次都是对(最左素短语）进行归约。
L1:L2:L3:L4:
ε||cC C ab aAb A AC S →→→bc bBc B aA A AB S ||→→→εεε||aBb B aAb A AB S →→→A
B B A A B A S |01|10|→→→ε
编译原理期末复习
编译原理期末复习 鉴于编译原理马上就要期末考试，我将手中集中的一些资料上的题目进行了整理归类，每种类型题目给出了所涉及到的基本知识，然后对每类题目中的第一道例题进行了做法进行了讲解，剩下的例题请给大家作为练习，答案也都给出，希望对大家复习有所帮助，最后由于时间很紧，整理的有些仓促，整理中难免有遗漏或错误，请大家见谅。 注：下面出现的字母中，若无特别说明，小写英文字母为终结符，大写英文字母为非终结符，希腊字母为终结符与非终结符的任意组合。 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：产生式集合(有限)。
编译原理期末考试习题及答案
一、填空题|（每题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)
编译原理试题(卷)汇总-编译原理期末试题(卷)(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____。
最新编译原理试题汇总+编译原理期末试题(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．( ) 产生式
编译原理知识点
1.解释程序：不生成目标代码 编译程序：生成目标代码 2.编译程序组成：8个 分析< 前端>：(词法分析程序、语法分析程序、语义分析程序、中间代码生成程序) 综合< 后端>：（代码优化程序、目标代码生成程序） 贯穿始末：表格管理程序、出错处理程序 3.文法四元组： 终结符号集合Vt 、非终结符号集合Vn、产生式集合P、识别符号(开始符号)S V T∩V N＝Φ 文法-> 语言（推导、规约）唯一；语言-> 文法（凑规则）不唯一。 4.文法分类： 0型文法(短语结构文法)：左侧至少含有一个非终结符 1型文法(上下文有关文法)：左侧长度<= 右侧长度S->ε除外，S不能出现在右侧2型文法(上下文无关文法)：左侧只能有一个非终结符( 语法分析) 3型文法(正规文法)：A-> aB A->a 右线性；( 词法分析) A->Ba 或A->a 左线性（看非终结符位置） 5.A*＝A0 ∪A+ A0 ＝{ε} !={ } ＝Φ空集 A+ ＝AA* ＝A*A 6.句型：符号串x是从识别符号S推导出来的，x称为一个句型 句子：x仅由终结符号组成，仅含终结符号的句型是一个句子 短语：子树的末端（叶子）从左至右连成的串（包括整棵语法树） 简单子树：只含有单层分枝的子树 直接短语( 简单短语)：由简单子树的叶子组成 句柄：最左边的直接短语（不一定含终结符） 素短语：至少含有一个终结符的短语，并且除它自身之外不再含任何更小的素短语最左素短语：最左边的素短语 短语：P（相对于T、E）、P+T（相对于E）、i（相对于P、F）、P+T+i（相对于E）直接短语：P、i 句柄：P (最左边的直接短语) 素短语：P+T 、i （至少含有一个终结符的短语）最左素短语：P+T 7.二义性文法：有两个不同的最左推导或有两个不同的最右推导或能产生两棵语法树 8.文法产生式正规式 规则1 A→xB B→y A = xy
编译原理期末考试题目及答案
一、填空题（每空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 3．一个算符优先文法的每个非终结符号间都也可能存在优先关系。X 4．语法分析时必须先消除文法中的左递归。X 6．逆波兰表示法表示表达式时无须使用括号。R 9．两个正规集相等的必要条件是他们对应的正规式等价。 X 1．编译程序是对高级语言程序的编译执行。X
编译原理概念期末总结复习
翻译程序:把一种语言程序转换成另一种语言程序，且在功能上是相同的这样的程序。 编译程序：把高级语言转换成低级语言，且在功能上是相同的这样的程序。 解释程序：边解释边执行源程序的程序。区别：编译程序有中间代码，而解释程序没有。编译过程的五个阶段： 1、词法分析任务：对构成源程序的字符串进行扫描和分解，识别出一个个单词。 2、语法分析任务：在词法分析的基础上，根据语言规则，把单词符号串分解成各类语法 单位。 3、语义分析和中间代码产生任务：对语法分析所识别出的各类语法范畴，分析其含义， 并进行初步翻译。 4、优化任务：对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效 的目标代码。 5、目标代码生成任务：把中间代码变换成特定机器上的低级语言代码。 编译程序的七个部分词法分析器，语法分析器、语义分析与中间代码产生器、优化器、目标代码生成器、表格管理和出错处理。 编译程序生成的五个办法：机器语言、高级语言、移植、自编译方式和使用工具自动生成。词法规则：指单词符号的形成规则。（也就是正规式） 语法规则：规定了如何从单词符号形成更大的结构。就是语法单位的形成规则。 空字：不包含任何符号的序列。 闭包： 中所有的符号组成的集合。 上下文无关文法是指：所定义的语法范畴是完全独立于这种范畴可能出现的环境的文法。上下文无关文法的四个组成部分：一组终结符号、一组非终结符号、一个开始符号和一组产生式。 终结符号也就是不可再分的基本符号。 非终结符号是用来代表语法范畴，表示一定符号串的集合。 开始符号是语言中我们最感兴趣的语法范畴。 产生式是定义语法范畴的书写规则。 句子：文法中从开始符号推导的终结符号串。 句型：从开始符号推导的符号串。 语言：文法中所有句子的集合。 程序语言的单词符号分为五种：关键字、标识符、常数、运算符和界符。 二元式表示：（种类，属性） 正规式的运算符有三种：或，连接和闭包。优先顺序是：闭包，连接，或。 DFA怎么识别字：若存在一条从初态结点到某一终态结点的通路，且这条通路上所有弧的标记符连接成的字是a，则称a可为DFA所识别。 DFA怎么识别空字：若DFA的初态结点同时又是终态结点，则空字可为DFA所识别。NFA怎么识别字：若存在一条从某一初态结点到终态结点的通路，且这条通路上所有弧的标记字依序连接成的字等于a，则称a可为NFA识别。 NFA怎么识别空字：若M的某些结点即是初态又是终态结点，或者存在一条从某个初态结点到某个终态结点的空通路，那么，空字可为M所识别。 语言的语法结构是用上下文无关文法描述的。 语法分析分为两类：自上而下分析法，自下而上分析法。 自上而下分析法面临的问题：1.文法的左递归问题。2.回溯3.成功可能是暂时的，产生虚假匹配。4.难于知道输入串中出错的确切位置。5.效率低，代价高。
编译原理复习整理(重点含答案)
1、给出下面语言的相应文法。L1={a n b n c i|n≥1,i≥0} 从n，i的不同取值来把L1分成两部分：前半部分是anbn：A→aAb|ab后半部分是ci：B→Bc|ε所以整个文法G1[S]可以写为：G1(S):S→AB；A→aAb|ab；B→cB|ε 3、构造一个DFA，它接受 ={a，b}上所有包含ab的字符串。 （要求：先将正规式转化为NFA，再将NFA确定化，最小化）
4、对下面的文法G: E →TE ’ E ’→+E|ε T →FT ’ T ’→T|ε F →PF ’ F ’ →*F ’|ε P →(E)|a|b|∧ （1）证明这个文法是LL(1)的。 （2）构造它的预测分析表。 (1)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,^,+,),#} (2)考虑下列产生式: '→+'→'→'→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,^,+,),#}=φ
编译原理知识点汇总
编译原理的复习提纲 1.编译原理=形式语言+编译技术 2.汇编程序： 把汇编语言程序翻译成等价的机器语言程序 3.编译程序： 把高级语言程序翻译成等价的低级语言程序 4.解释执行方式： 解释程序，逐个语句地模拟执行 翻译执行方式： 翻译程序，把程序设计语言程序翻译成等价的目标程序 5.计算机程序的编译过程类似，一般分为五个阶段： 词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成 词法分析的任务： 扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等） 语法分析是： 在词法分析的基础上的，语法分析不考虑语义。语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。 语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。
语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序 代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码 编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序 编译程序结构包括五个基本功能模块和两个辅助模块 6.编译划分成前端和后端。 编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析 编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。 把编译程序分为前端和后端的优点是： 可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。 7.汇编器把汇编语言代码翻译成一个特定的机器指令序列 第二章 1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，Xn， 2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0 ={ε} 3.重写规则，简称规则。非xx（V
编译原理试题及答案3
编译原理复习题 一、填空题： 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、一个文法符号的综合属性是通过语法树中它的（子）结点的属性来计算的。
郑州大学编译原理试卷及答案(往年试题整合)(2)
二填空题 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) 栈式动态存储分配(2) 堆式动态存储分配 (3) 左(4) 语法分析(5) 目标代码生成 (6) 表格管理 (7) xyz*ab+/+ (8) 继承属性 (9) a+(i-1)*20+j-1 (10) 基本块 8 词法规则通常可以用____正规式________，正规文法、____自动机________描述；语法规则通常用___2型文法___来描述；语义规则通常用__属性文法_____来描述。
9 编译原理的工作过程一般划分为：词法分析、语法分析、语义分析、优化和目标代码生成五个阶段。 1.( )称为规范推导。 2.编译过程可分为（），（），（），（）和（）五个阶段。 3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（）。 4.从功能上说，程序语言的语句大体可分为（）语句和（）语句两大类。 5.语法分析器的输入是（），其输出是（）。 6.扫描器的任务是从（）中识别出一个个（）。 7.符号表中的信息栏中登记了每个名字的有关的性质，如（）等等。 8.一个过程相应的DISPLAY表的内容为（）。 9.一个句型的最左直接短语称为句型的（）。 10.常用的两种动态存贮分配办法是（）动态分配和（）动态分配。 11.一个名字的属性包括( )和( )。 12.常用的参数传递方式有（），（）和（）。 13.根据优化所涉及的程序范围，可将优化分成为（），（）
编译原理中重点整理
1.翻译程序：将某一种语言（源语言）程序转换为与其逻辑上等价的另一种语言（目标语言） 程序。 编译程序：源语言为高级语言，目标语言为汇编语言或机器语言的翻译程序。 汇编程序：源语言为汇编语言，目标语言为机器语言的翻译程序。 解释程序：源语言程序作为输入，但不产生目标程序，而是边解释边执行源程序本身。 2.解释器与编译器的主要区别在于：运行目标程序时的控制权在解释器而不在目标程序。 3.编译程序的工作过程可划分五个阶段： ①词法分析：从左到右一个字符一个字符的读入源程序，对构成源程序的字符串进行扫描 和分解，从而识别出一个个单词（也称单词符号或简称符号） ②语法分析：在词法分析的基础上将单词序列分解成各类语法短语，如“程序”，“语句”， “表达式”等等 ③语义分析和中间代码生成：语义分析是在语法分析程序确定出语法短语后，审查有无语义 错误，并为代码生成阶段收集类型信息。完成语法分析和语义 处理工作后，编译程序将源程序变成一种内部表示形式，这种 内部表示形式叫做中间语言或称中间代码，它是一种结构简单、 含义明确的记号系统。 ④代码优化：为了使生成的目标代码更为高效，可以对产生的中间代码进行变换或进行改造， 这就是代码的优化。 ⑤目标代码生成：目标代码生成阶段的任务就是是把中间代码变换成特定机器上的绝对指令 代码或可重定位的指令代码或汇编指令代码。 4.前端(Front-End)——与目标机无关的部分 后端(Back-End )——与目标机有关的部分 5.编译系统：编译程序与运行系统合称编译系统 6.遍：对源程序或源程序的中间结果从头到尾扫描一次，并做有关的加工处理，生成新的中 间结果或目标程序。 7.文法是一个四元组：G[S]=(VN, VT, P, S) VN：非终结符集合； VT ：终结符集合； P ：产生式集合（α→β或α∷=β）； S ：开始符号(或称根符号，识别符号)。 若S ->α,α∈V*，则称α为文法G的句型 若S ->α,α,α∈VT*，则称α为文法G的句子 语言是所有句子构成的集合，它是所有终结符号串所组成的集合VT*的子集，即L(G) VT* 8.0型文法又叫短语文法，它所确定的语言称为0型语言。 1型文法,上下文敏感文法或上下文有关文法。 2型文法,上下文无关文法 3型文法线性文法、正则文法或正规文法 规范(最右)推导即任何一步α->β都是对α中的最右非终结符进行替换的，规范(最左)归约文法可唯一地确定一个语言 子树与短语：在句型所对应的语法树中，若某些符号按从左到右的顺序组成某棵子树的末端结点，那么由这些末端结点所组成的符号串是相对于子树根结点的短语。 原则上语法树有多少棵子树，就有多少个短语。
编译原理试题及答案
参考答案 一、单项选择题(共10小题，每小题2分，共20分) 1．语言是 A ．句子的集合 B ．产生式的集合 C ．符号串的集合 D ．句型的集合 2．编译程序前三个阶段完成的工作是 A ．词法分析、语法分析和代码优化 B ．代码生成、代码优化和词法分析 C ．词法分析、语法分析、语义分析和中间代码生成 D ．词法分析、语法分析和代码优化 3．一个句型中称为句柄的是该句型的最左 A ．非终结符号 B ．短语 C ．句子 D ．直接短语 4．下推自动机识别的语言是 A ．0型语言 B ．1型语言 C ．2型语言 D ．3型语言 5．扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即 A ． 字符 B ．单词 C ．句子 D ．句型 6．对应Chomsky 四种文法的四种语言之间的关系是 A ．L 0?L 1?L 2?L 3 B ．L 3?L 2?L 1?L 0 C ．L 3=L 2?L 1?L 0 D ．L 0?L 1?L 2=L 3 7．词法分析的任务是 A ．识别单词 B ．分析句子的含义 C ．识别句子 D ．生成目标代码 8．常用的中间代码形式不含 A ．三元式 B ．四元式 C ．逆波兰式 D ．语法树 9． 代码优化的目的是 A ．节省时间 B ．节省空间 C ．节省时间和空间 D ．把编译程序进行等价交换 10．代码生成阶段的主要任务是 A ．把高级语言翻译成汇编语言 B ．把高级语言翻译成机器语言 C ．把中间代码变换成依赖具体机器的目标代码 装 订 线
D．把汇编语言翻译成机器语言 二、填空题（本大题共5小题，每小题2分，共10分） 1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。2．编译器常用的语法分析方法有(自底向上)和(自顶向下)两种。 3．通常把编译过程分为分析前端与综合后端两大阶段。词法、语法和语义分析是对源程序的(分析)，中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。 4．程序设计语言的发展带来了日渐多变的运行时存储管理方案，主要分为两大类，即(静态存储分配)方案和(动态存储分配)方案。 5．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。 三、名词解释题(共5小题，每小题4分，共20分) 1．词法分析 词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则 从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位， 并转换成统一的内部表示(token)，送给语法分析程序。 2．LL(1)文法 若文法的任何两个产生式A →α | β都满足下面两个条件： （1）FIRST(α) ? FIRST(β ) = φ； （2）若β?* ε，那么FIRST(α) ? FOLLOW( A ) = φ。 我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左 向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步 动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一 些明显的性质，它不是二义的，也不含左递归。 3．语法树 句子的树结构表示法称为语法树(语法分析树或语法推导树)。 给定文法G=(V N，V T，P，S)，对于G的任何句型都能构造与之关联的 语法树。这棵树具有下列特征： (1)根节点的标记是开始符号S。 (2)每个节点的标记都是V中的一个符号。 (3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列 次序为A1A2…A R，那么A→A1A2…A R一定是P中的一条产生式。
《编译原理》总复习-07级
《编译原理》总复习-07级 第一章编译程序的概述 （一）内容 本章介绍编译程序在计算机科学中的地位和作用，介绍编译技术的发展历史，讲解编译程序、解释程序的基本概念，概述编译过程，介绍编译程序的逻辑结构和编译程序的组织形式等。 （二）本章重点 编译（程序），解释（程序），编译程序的逻辑结构。 （三）本章难点 编译程序的生成。 （四）本章考点 全部基本概念。 编译程序的逻辑结构。 （五）学习指导 引论部分主要是解释什么是编译程序以及编译的总体过程。因此学习时要对以下几个点进行重点学习：翻译、编译、目标语言和源语言这几个概念的理解；编译的总体过程：词法分析，语法分析、语义分析与中间代码的生成、代码优化、目标代码的生成，以及伴随着整个过程的表格管理与出错处理。 第三章文法和语言课外训练 （一）内容 本章是编译原理课程的理论基础，主要介绍与课程相关的形式语言的基本概念，包括符号串的基本概念和术语、文法和语言的形式定义、推导与归约、句子和句型、语法分析树和二义性文法等定义、文法和语言的Chomsky分类。 （二）本章重点 上下文无关文法，推导，句子和句型，文法生成的语言，语法分析树和二义性文法。（三）本章难点 上下文无关文法，语法分析树，文法的分类。 （四）本章考点 上下文无关文法的定义。 符号串的推导。 语法分析树的构造。 （五）学习指导 要构造编译程序，就要把源语言用某种方式进行定义和描述。学习高级语言的语法描述是学习编译原理的基础。上下文无关文法及语法树是本章学习的重点。语法与语义的概念；程序的在逻辑上的层次结构；文法的定义，文法是一个四元组：终结符号集，非终结符号集，开始符号、产生式集；与文法相关的概念，字符，正则闭包，积（连接），或，空集，产生式，推导，直接推导，句子，句型，语言，最左推导，最右推导（规范推导）；学会用文法来描述语言及通过文法能分析该文法所描述的语言；语法树及二义性的概念、能通过画语法树来分析一个文法描述的语言是否具有二义性；上下文无关文法的定义和正规文法的定义，能判断一个语言的文法是哪一类文法。 附训练试题：
编译原理考试试题与答案(汇总)
《编译原理》考试试题及答案（汇总） 一、是非题（请在括号，正确的划√，错误的划×）（每个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．( ) 代码外提
编译原理期末复习总结
一、简答题 1.什么是编译程序 答：编译程序是一种将高级语言程序(源程序)翻译成低级语言(目标程序)的程序。 将高级程序设计语言程序翻译成逻辑上等价的低级语言(汇编语言,机器语言)程序的翻译程序。 2.请写出文法的形式定义 答：一个文法G抽象地表示为四元组?G=（Vn,Vt,P,S）? –其中Vn表示非终结符号 –Vt表示终结符号，Vn∪Vt=Ｖ(字母表)，Vn∩Vt=φ –S是开始符号， –P是产生式，形如：α→β(α∈V+且至少含有一个非终结符号，β∈V*) 3.语法分析阶段的功能是什么 答：在词法分析的基础上，根据语言的语法规则，将单词符号串分解成各类语法短语(例：程序、语句、表达式)。确定整个输入串是否构成语法上正确的程序。 4.局部优化有哪些常用的技术 答：优化技术1—删除公共子表达式 优化技术2—复写传播 优化技术3—删除无用代码 优化技术4—对程序进行代数恒等变换（降低运算强度） 优化技术5—代码外提 优化技术6—强度削弱 优化技术7—删除归纳变量 优化技术简介——对程序进行代数恒等变换（代数简化） 优化技术简介——对程序进行代数恒等变换（合并已知量） 5．编译过程分哪几个阶段 答：逻辑上分五个阶段：词法分析、语法分析、语义分析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。 6. 什么是文法 答：文法是描述语言的语法结构的形式规则。是一种工具，它可用于严格定义句子的结构； 用有穷的规则刻划无穷的集合；文法是被用来精确而无歧义地描述语言的句子的构成方式；文法描述语言的时候不考虑语言的含义。 7. 语义分析阶段的功能是什么 答：对语法分析所识别出的各类语法范畴分析其含义，进行初步的翻译(翻译成中间代码)； 并对静态语义进行审查。 8.代码优化须遵循哪些原则 答：等价原则：不改变运行结果 有效原则：优化后时间更短，占用空间更少 合算原则：应用较低的代价取得较好的优化效果 9.词法分析阶段的功能是什么 答：
编译原理习题及答案(整理后)
第一章 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)