编译原理超强复习纲领
编译原理课程英文词汇
alphabet字母表symbol符号string串length长度catenation连接
power方幂gather集合product乘积empty set空集closure 闭包
program程序logic structure逻辑结构generating产生executing执行
machine language机器语言instruction指令function函数assembler汇编程序interpreter解释程序translator翻译程序source language源语言finite有穷的
source program源程序target language目标语言attribute属性possess占有preprocess预处理compiler编译程序break中断Intermediate language中间语言definition定义reconstructed重构normal正规character sequences 符号序列programming language程序设计语言operand操作数instead替换memory内存element元素high-level language高级语言object program目标程序
address地址input输入output输出terminal终结符compilation编辑equivalence等价nonterminal非终结符recursion递归deterministic确定的nondeterministic非确定的Backus-Normal Form巴科斯范式syntax语法
tree树expression表达式grammar文法automata自动机prefix前缀
suffix后缀infix中缀identify识别identifier标识符analyses分析
predigest化简symbol set符号集performed执行forecast预测state状态
formula产生式conversion变换precedence优先simple简单handle句柄operator算符terminal state终态first state初态optimizer优化程序concatenation连接word单词alphabet字母表lexical词法scanner扫描器
analyzer分析器syntax tree语法树symbol table符号表pass趟，遍
regular expression正规表达式code generator代码生成器backdate回溯
derivation推导educe推导derivation tree推导树path路径ambiguous二义性
simple phrase简单短语context-sensitive上下文有关context-free上下文无关
right-linear 右线形phrase-structured短语结构regular grammar文法
direct derivation直接推导sentence句子sentential form句型root node根结点subtree子树semantic语义的terminal node端末结点attribute grammar属性文法canonical derivation规范推导top-down自上而下bottom-up自下而上
viable prefix活前缀nondeterminate finite automata非确定的有穷自动机
编译复习：一．专业术语英汉对译：复习老师给出的编译原理课程英文词汇
二、概念题(单项选择题、填空题、判断正误题、名词解释题、简答题)
1. 翻译程序的种类有哪些？把汇编语言程序翻译成机器可执行的目标程序的工作是由什么来完成的？
2. 编译程序生成的结果是什么？目标程序；不一定是机器语言的程序。
3．高级语言的翻译处理只有编译一种方式？
4. 在LR分析法中，分析栈中存放的状态是识别规范句型的什么状态？
5. 词法分析器用于识别什么？语法分析器接收以什么为单位的输入？
6．在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是什么集合？
7．若一个文法是递归的，则它所产生的语言的句子有多少？
8．按逻辑上划分，一个编译程序的组成部分有哪些？它的工作过程由哪几部分来完成的？各部分的任务是什么？
9．属性有哪些分类？它们如何传递信息？
10．乔姆斯基（Chomsky）把文法分为几种类型？各是什么名称？
11．无符号常数的识别和拼数工作通常是在什么阶段完成？
12．在语法分析方法中，自底向上的分析的关键是什么？自顶向下的分析的关键是什么？13．一个上下文无关文法G的定义是什么？语义规则的定义是什么？语法分析的定义是什么？
四元式的定义是什么？语言的定义是什么？可归前缀的定义是什么？句型的定义是什么？句子的定义是什么？后缀式的定义是什么？扫描遍的定义是什么？活前缀的定义是什么？句柄定义14．源程序经翻译后能直接运行的目标程序是什么程序？
15. 正则文法产生的语言是否都可以用上下文无关文法来描述？
16. 编译程序在优化阶段是否要用到源程序中的注释？
17. 用高级语言书写的源程序是否都必须通过编译产生目标代码后才能投入运行？
18. 解释与编译方式的区别是否是解释方式对源程序没有真正进行翻译？
19. 对任何NFA M，是否都存在一个正则表达式e或正则文法与之等价? 对任何正则表达式e，是否都存在一个NFA M,满足L（M）=L(e)？对任何正则文法G，都存在一个NFA M,满足L（M）=L(G)？
20. 任何句型是否都存在一个规范推导，任何句子是否也都存在一个规范推导？
21. 定义一个语言的文法是否是唯一的？
22. 对任一编译程序来说，产生中间代码是不是必要的？
23. 具有优化功能的编译程序的效率是否较高？
24. 符号表由词法分析程序建立，是否只能由语法分析程序使用？
25. 一个句型的句柄与文法某产生式的右部是什么关系？
26. 数组元素的地址计算与数组的存储方式是否有关？
27. 每个文法是否都能改写为LL(1)文法？
28. 在中间代码优化中循环的优化包含哪些优化工作？
29. 语义分析过程中的主要问题是否是候选式的选择？
30. 在程序中出现的标识符仅为使用性出现的？
31. 在编译中进行语法检查的目的仅是为了发现程序中各种错误？
32. 递归下降法是否允许任一非终极符是直接左递归的？
33. 自顶向下语法分析的思想是什么？自底向上语法分析的思想是什么？
34. 代码生成是否与具体的机器硬件无关？
35. 基本块的定义是什么？
36. 何谓语法制导翻译?目标代码有哪几种形式？
37. 什么是文法的二义性？证明给定文法G[N]的二义性。
38. DFA与NFA有何区别 ?
39．在规范归约中，用什么来刻画可归约串？
40．四元式之间的联系是通过什么实现的？
41．过程的DISPLAY表中记录了过程的什么？
三．自动机转换题
给定一个NFA M：（此处自动机略）
1.把此自动机转换为等价的确定自动机DFA。
2.给出与此DFA等价的正则表达式。
四．给定中缀式，写出它们等价的后缀式和四元式。
五．给出一个三地址代码序列，请用DAG进行局部优化：
（此处三地址代码序列略）
1.画出DAG图；
2.假设基本块出口时只有某些变量还被引用，写出优化后的三地址代码序列。六．给定文法G[S]：（此处文法略）
1.文法G属于chomsky哪一型文法？
2.给定符号串，判定该符号串是不是该文法的一个句子，请证实。
3.若是句子，写出该句型的所有短语、简单短语，以及句柄。
4.构造识别该文法的活前缀的DFA。
5.判断该文法是LR（0）还是SLR（1），并构造其分析表？
6.对于给定的属性文法和输入符号串α，该翻译方案的输出是什么？（需要给出解题过程）
* ? 一.名词解释： 1)前缀
答：前缀——是指符号串任意首部。 2)可归前缀
答：可归前缀——是指规范句型的一个前缀，这种前缀包含句柄且不含句柄之后的任何符号。 3)活前缀
答：活前缀——规范句型的一个前缀，这种前缀不含句柄之后的任何符号。 或给定文法规范句型的可归前缀的任意首部。 4)简单短语
答：简单短语——设G[Z]是给定文法,w=xuy ∈V +
，为该文法的句型,如果满足下面两个条件:
① Z xUy ； ② U ?u ；
则称句型xuy 中的子串u 是句型xuy 的简单短语。 5)扫描遍
答：扫描遍——指编译程序对源程序或中间代码程序从头到尾扫描一次。 6)句柄
答：句柄——给定句型中的最左简单短语就是句柄。 7)句型
答：句型——设G 是一个给定的文法，S 是文法的开始符号，如果S x(其中x ∈V *
),则称x 是文法的一个句型。 8)句子
答：句子——设G 是一个给定的文法，S 是文法的开始符号，如果S x （其中x ∈V T *
），则称x 是文法的一个句子。 9)非终结符 答：非终结符—出现在文法产生式的左部且能派生出符号或符号串的那些符号称为非终结符号。 10)终结符 答：终结符——出现在文法产生式的右部且不能派生出符号或符号串的那些符号称为终结符号。 11）属性文法
答：一个属性文法形式的定义为一个三元组AG ，AG=（G ，V ，E ）。
其中G 为一个上下文无关文法；V 为属性的有穷集；E 为一组语义规则。 12）语法制导翻译
答：语法制导翻译——语法制导翻译就是在语法分析的过程中，当进行推导或归约时同步完成附加在所使用的产生式上的语义规则描述的动作，从而实现语义处理。 13）后缀式
答：后缀式——一种把运算量（操作数）写在前面，把算符写在后面（后缀）的表示法。 14）短语
答：短语——设G[Z]是给定文法,w=xuy ∈V +
，为该文法的句型,如果满足下面两个条件:
① Z xUy ； ② U u ；
则称句型xuy 中的子串u 是句型xuy 的短语。
或：句型语法树的全部子树的叶从左到右排列起来构成的符号串均是句型的短语。 15）基本块
答：基本块——源程序或者中间代码程序中只有一个入口和一个出口的顺序执行的代码段。 16）语义规则
答：对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。 17）语法分析
答：语法分析——按文法的产生式识别输入的符号串是否为一个句子的分析过程。 18）四元式
答：四元式——是一个带有四个域的记录结构，这四个域分别称为操作符域、左运算对象域、
*
右运算对象域及运算结果域。 二．简答题：
1) 什么是句子？ 什么是语言?
解答：句子——设G 是一个给定的文法，S 是文法的开始符号，如果S x （其中x ∈V T *
），则称x 是文法的一个句子。 语言——语言是句子的集合。
或——设G[S]是给定文法，则由文法G 所定义的语言L(G)可描述为：L(G)＝{x │S x,x ∈V T *
} 。
2) DFA 与NFA 有何区别 ?
解答:DFA 与NFA 的区别表现为两个方面:一是NFA 可以有若干个开始状态，而DFA 仅只有一个
开始状态。另一方面，DFA 的映象M 是从K ×∑到K ，而NFA 的映象M 是从K ×∑到K 的子集，即映象M 将产生一个状态集合（可能为空集），而不是单个状态。 3) 自顶向下的语法分析方法的基本思想是什么? 解答:从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接
推导，试图推导出文法的句子，使之与给定的输入串匹配。 4) 自底向上的语法分析方法的基本思想是什么?
解答:从给定的输入串（终结符串）开始，根据文法的规则一步一步的向上进行直接归约，试图
归约到文法的开始符号。
5) 一个上下文无关文法G 包括哪四个组成部分？
解答:一组非终结符号，一组终结符号，一个开始符号，以及一组产生式。 6) 在自底向上的语法分析方法中，分析的关键是什么？ 解答:关键是寻找句柄。
7) 在自顶向下的语法分析方法中，分析的关键是什么？ 解答:关键是选择候选式。
8) 编译程序中语法分析器接收以什么为单位的输入？ 解答: 接收以单词为单位的输入。
9) 若一个文法是递归的，则它所产生的语言的句子是可枚举的吗？ 解答: 它所产生的语言的句子不是可枚举的，而是无穷多个。 10) 编译程序生成的目标程序是不是一定是机器语言的程序？ 解答:不一定是机器语言的程序。 11) 词法分析器是用于做什么的？ 解答:词法分析器是用于识别单词的。
12) “用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法正确
吗？
解答: 不正确。
13) 把汇编语言程序翻译成机器可执行的目标程序的工作是由什么完成的？
解答: 由汇编器（汇编程序）完成的。
14)图示运行时存储空间的划分（分为哪几个区）。
解答: 一般分为静态区和动态区：
程序代码区、静态数据区、栈区和堆区 15)词法分析的主要任务是什么？
解答:词法分析器的任务是对构成源程序的字符串从左到右逐个字符逐个字符地进行扫描，依次
把它们识别为一个一个具有独立意义的单词，并确定其属性，再转换为长度统一的属性字并输出。
16)常用的中间语言种类有哪几种？
解答: 常用的中间语言种类有逆波兰表示、三元式、四元式和树形表示。 17）文法G 所描述的语言是什么的集合？
解答:是由文法的开始符号推出的所有终结符串的集合。或说是句子的集合。
18）乔姆斯基把文法分为四种类型，即0型、1型、2型、3型。其中2型文法叫什么？
解答: 2型文法叫上下文无关文法。
19）编译程序是一种解释程序吗？还是什么程序？
解答:编译程序是一种翻译程序。
20）按逻辑上划分，编译程序第二步工作是什么？
解答: 编译程序第二步工作是语法分析。
21）源程序是用高级语言编写的，目标程序是机器语言程序或汇编语言程序，则其翻译程序称为什么？
解答: 其翻译程序称为编译程序。
22）编译方式与解释方式的根本区别为什么？
解答:编译方式与解释方式的根本区别在于是否生成目标代码。
23）常见的动态存贮分配策略有哪两种？
解答:常见的两种动态存贮分配策略是栈式动态分配策略和堆式动态分配策略。
24）常用的参数传递方式有哪三种？
解答:常见的参数传递方式有传地址、传值和传名三种方式。
25）语法分析的任务是什么？
解答:语法分析的任务是识别给定的终结符串是否为给定文法的句子。
26）局部优化是局限于一个什么范围内的一种优化？
解答:是局限于一个基本块范围内的一种优化。
27）文法等价的定义是什么？
解答:设G1和G2是给定的文法，如果有L（G1）= L（G2），则称G1与G2等价。
28）在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是什么集合？
解答:均是终结符集。
29）通常一个编译程序中应包括哪七个部分？
解答:通常一个编译程序中应包含词法分析，语法分析，语义分析与中间代码生成，代码优化，目标代码生成以及表格处理和出错处理等七个部分。
32）如果编译程序生成的目标程序是汇编语言程序，则源程序的执行分为哪三个阶段？
解答: 源程序的执行分为三个阶段: 编译阶段，汇编阶段和运行阶段。
33）翻译程序是这样一种程序，它能够将用什么转换成与其等价的用乙语言书写的程序？
解答:能够将用甲语言书写的程序转换成与其等价的用乙语言书写的程序。
34）说明下面文法G[S]是二义性文法：S→SaS|SbS|cSd|eS|f
解答:fafbf是文法G[S]的一个句子，并且有两个不同的最右推导。
（1）S => SaS => SaSbS => SaSbf=> Safbf=> fafbf
（2）S => SbS => Sbf=> SaSbf => Safbf=> fafbf
因此说明此文法有二义性。
35）在属性文法中，综合属性与继承属性是如何传递信息的？
解答: 综合属性用于自下而上传递信息，继承属性用于自上而下传递信息。
36）代码优化的主要目标是什么？
解答: 代码优化的主要目标是如何提高目标程序的运行速度和如何减少目标程序运行时所需的空间。
37）写一个文法，使其语言是无符号二进制实数（不含指数）。
解答:文法G(N)：
N→L.L|L
L→LB|B
B→0|1
三．应用题
其中：开始状态：0
终止状态：2 1）消除下列文法G[A]的左递归。
E→E-T∣T
T→T/F∣F
F→( E )∣i
解答：消除文法G[E]
的左递归后得到：
E→TE′
E’→-T E′∣ε
T→FT′
T’→/FT′∣ε
F→( E )∣i
2）消除下列文法G[A]的左递归。
A→AaB∣B
B→BbC
∣C
C→eD∣D
D→(A)∣d
解答：消除文法G[A]的左递归后得到：
A →BAˊ
Aˊ→aBAˊ∣ε
B →CBˊ
Bˊ→bcBˊ∣ε
C→eD∣D
D→(A)∣d
3）给定下列自动机：
解答：
从而可得DFA如图：
4）正规式（a|b）*a(a|b) 构造一个等价的有限自动机。
解答：
a
1．S '→S {print:“a ”} 2．S →r D {print:“b ”} 3．D →D ，i {print:“c ”}
4．D →i {print:“d ”}
四．设计题
（1）给定文法G[S ′] 及相应翻译方案为：
a. 按chomsky 分类法，文法G 属于哪一型文法？
b. 符号串ri,i,i 是不是该文法的一个句型，请证实。
c. 若是句型，写出该句型的所有短语、简单短语，以及句柄。
d. 构造识别该文法的活前缀的DFA 。
e. 判断该文法是LR （0）还是SLR （1），并构造其相应的语法分析表。
f. 对于ri,i,i 这个输入符号串，经该翻译方案翻译后的输出是什么？ 解答：
a ．文法G 属于2型(上下文无关)文法。
b ．符号串r i,i,i 是该文法的一个句型。
证：S '?S ?rD ?rD ，i ? rD ，i ，i ? r i ，i ，i ，得证。
或证：构造语法树见图4，可知符号串r i,i,i 是该文法的一个句型。 c ．句型r i,i,i 的短语有：①r i,i,i ；② i,i,i ；③i,i ；④ 第一个i
简单短语有：第一个i
句柄有：第一个i
d ．求得文法G 的识别全部活前缀的DFA 见图3：
e FOLLOW(S ')={#} FOLLOW(S)={#} FOLLOW(D)={ ，,#}
而由于{ ，}∩FOLLOW(S)={ ，}∩{#}=Φ，所以文法G 是SLR （1）文法。 求得文法G 的SLR （1）分析表见表1：
图3 识别全部活前缀的DFA
S '
r S D D i ， D i ， 表1 SLR （1）分析表
f．可以先求得该句子的语法树（见图4），然后通过剪枝的方式进行归约，
最后归约到文法的开始符号，在归约的过程中同步产生输出符号串dccba。
即对于r i,i,i这个输入符号串，该翻译方案的输出是：dccba
（2）给定文法:
（1）S→bTc
（2）S→a
（3）T→R
（4）R→R/S
（5）R→S
a)符号串ba/ac是不是该文法的一个句子，请证实。
b)若是句子，写出该句子的所有短语、简单短语和句柄。
c)为该文法设计翻译方案，使句型bR/bTc/bSc/ac经该翻译方案翻译后,输出下列串：
0342031320 Array解答：
a) 符号串ba/ac是该文法的一个句子。
∵S?bTc?bRc?bR/Sc?bS/Sc?ba/Sc?ba/ac，
∴得证。
或：给出符号串ba/ac的语法树如右图，则判定
符号串ba/ac是该文法的一个句子。
b)给出句型ba/ac的语法树如右图：
则可求得句型adbb的短语有：ba/ac,a/a,第1个a, 第2个a
简单短语有：第1个a, 第2个a
句柄有：第1个a
c)给出句型bR/bTc/bSc/ac的语法树如右图：
（1）S→bTc {print(“0”)}
（2）S→a {print(“1”)}
（3）T→R {print(“2”)}
（4）R→R/S {print(“3”)}
（5）R→S {print(“4”)}
（3）设有基本块：
t1:=3*A
t2:=2*C
t3:=t1+t2
t4:=t3+5
t5:=2*C
t6:=3*A t7:=t6+t5 E:=t7-1 F:=t4-E
a)画出DAG 图；
b)假设基本块出口时只有E ，F 还被引用，请写出优化后的三地址代码序列。 解答：
a)构造DAG ：见右图。
b)
t1:=3*A
t2:=2*C t3:=t1+t2
t4:=t3+5 E:=t3-1 F:=t4-E
五．转换题：
给定下列中缀式 (运算符优先级按常规理解) ，分别写出等价的逆波兰式和四元式。 1）a ≤b ∧a ＞0∨b ＜0
解答：逆波兰式为：ab ≤a0＞∧b0＜∨
写出等价的四元式表示 1. (≤,a ,b ,T1) 2. (＞,a ,0 ,T2) 3. (∧,T1,T2,T3) 4. (＜,b ,0 ,T4) 5. (∨,T3,T4,T5)
2）―a ＋b ≤0∨a ＜
四元式为： 3.( ≤,T2,0 ,T3) 4.( ＜,a ,0 ,T4) 5.( ―,a ,b ,T5) 6.( ＞,T5,2 ,T6) 7.( ∧,T4,T6,T7)
8.( ∨,T3,T7,T8)
一、填空题:
1-01.编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析，之间代码生成,代码
优化等几个基本阶段,同时还会伴有表格处理和出错处理 .
1-02.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序 ,则其翻译程序称
为编译程序.
1-03.编译方式与解释方式的根本区别在于是否生成目标代码 .
1-04.翻译程序是这样一种程序,它能够将用甲语言书写的程序转换成与其等价的用乙语言
书写的程序 .
1-05.对编译程序而言,输入数据是源程序 ,输出结果是目标程序 .
1-06.如果编译程序生成的目标程序是机器代码程序,则源程序的执行分为两大阶段: 编译阶段
和运行阶段 .如果编译程序生成的目标程序是汇编语言程序,则源程序的执行分为三个阶段: 编译阶段 , 汇编阶段和运行阶段 .
1-07.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称
为编译程序。
1-08.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标
代码生成等五个部分，还应包括表格处理和出错处理。其中，词法分析器用于识别单词。
1-09.编译方式与解释方式的根本区别为是否生成目标代码。
2-01.所谓最右推导是指：任何一步α β都是对α中最右非终结符进行替换的。
2-02.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。
2-03.产生式是用于定义语法成分的一种书写规则。
2-04.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈V T*} 。
2-05.设G是一个给定的文法，S是文法的开始符号，如果S x（其中x∈V*），则称x是文法
的一个句型。
2-06.设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V T*),则称x是文法的
一个句子。
3-01.扫描器的任务是从源程序中识别出一个个单词符号。
4-01.语法分析最常用的两类方法是自上而下和自下而上分析法。
4-02.语法分析的任务是识别给定的终极符串是否为给定文法的句子。
4-03.递归下降法不允许任一非终极符是直接左递归的。
4-04.自顶向下的语法分析方法的关键是如何选择候选式的问题。
4-05.递归下降分析法是自顶向上分析方法。
4-06.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并
按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的
输入串匹配。
5-01.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一步一
步的向上进行直接归约，试图归约到文法的开始符号。
5-02.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行直接归约，力求归约到文法的开始符号。
5-03.简单优先方法每次归约当前句型的句柄，算符优先方法每次归约当前句型的最左素短语，二者都是不断移进输入符号，直到符号栈顶出现可归约串的尾，再向前找到可归约串的头，然后归约。
5-04.在LR（0）分析法的名称中，L的含义是自左向右的扫描输入串，R的含义是最左归约，0 的含义是向貌似句柄的符号串后查看0个输入符号。
5-05.在SLR（1）分析法的名称中，S的含义是简单的。
6-01.所谓属性文法是一个属性文法是一个三元组：A＝（G，V，F），一个上下文无关文法G；
一个属性的有穷集V和关于属性的断言或谓词的有穷集F。每个断言与文法的某产生式相联。
6-02.综合属性是用于“自下而上”传递信息。
6-03.继承属性是用于“自上而下”传递信息。
6-04.终结符只有综合属性，它们由词法分析器提供。
7-01.在使用高级语言编程时,首先可通过编译程序发现源程序的全部 A 错误和 B 部分
错误.
a.语法
b.语义
c.语用
d.运行
8-01.符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。
8-02.一个过程相应的DISPLAY表的内容为现行活动记录地址和所有外层最新活动记录的地址。
9-01.一个过程相应的DISPLAY表的内容为现行活动记录地址和所有外层最新活动记录的地址。
9-02.常用的两种动态存贮分配办法是栈式动态分配和堆式动态分配。
9-03.常用的参数传递方式有传地址，传值和传名。
10-01.局部优化是局限于一个基本块范围内的一种优化。
10-02.代码优化的主要目标是如何提高目标程序的运行速度和如何减少目标程序运行时所需的空间。
二、单选题:
1-10.一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括 (1)c .其中, (2)b 和代码优化部分不是每个编译程序都必需的.
词法分析器用于识别 (3)c ,语法分析器则可以发现源程序中的 (4)d .
(1) a.模拟执行器 b.解释器 c.表格处理和出错处理 d.符号执行器
(2) a.语法分析 b.中间代码生成 c.词法分析 d.目标代码生成
(3) a.字符串 b.语句 c.单词 d.标识符
(4) a.语义错误 b.语法和语义错误 c.错误并校正 d.语法错误
1-11.程序语言的语言处理程序是一种 (1)a . (2)b 是两类程序语言处理程序,他们的主
要区别在于 (3)d .
(1) a.系统软件 b.应用软件 c.实时系统 d.分布式系统
(2) a.高级语言程序和低级语言程序 b.解释程序和编译程序
c.编译程序和操作系统
d.系统程序和应用程序
(3) a.单用户与多用户的差别 b.对用户程序的查错能力
c.机器执行效率
d.是否生成目标代码
1-12.汇编程序是将 a 翻译成 b ,编译程序是将 c 翻译成 d .
a.汇编语言程序
b.机器语言程序
c.高级语言程序
d. a 或者 b
e. a 或者 c
f. b 或者 c
1-13.下面关于解释程序的描述正确的是 b .
(1) 解释程序的特点是处理程序时不产生目标代码
(2) 解释程序适用于COBOL 和 FORTRAN 语言
(3) 解释程序是为打开编译程序技术的僵局而开发的
a. (1)(2)
b. (1)
c. (1)(2)(3)
d.(2)(3)
1-14.高级语言的语言处理程序分为解释程序和编译程序两种.编译程序有五个阶段，而解释程序通常缺少 (1)e 和 (1)b .其中， (1)e 的目的是使最后阶段产生的目标代码更为高效.
与编译系统相比，解释系统 (2)d .解释程序处理语言时,大多数采用的是 (3)b 方法.
(1): a. 中间代码生成 b.目标代码生成 c.词法分析 d.语法分析 e.代码优化
(2): a.比较简单,可移植性好,执行速度快
b.比较复杂,可移植性好,执行速度快
c.比较简单,可移植性差,执行速度慢
d.比较简单,可移植性好,执行速度慢
(3): a.源程序命令被逐个直接解释执行 b.先将源程序转化为之间代码,再解释执行
c.先将源程序解释转化为目标程序,在执行
d.以上方法都可以
1-15.用高级语言编写的程序经编译后产生的程序叫 b .用不同语言编写的程序产生 b 后,可用 g 连接在一起生成机器可执行的程序.在机器中真正执行的是 e .
a. 源程序
b. 目标程序
c. 函数
d. 过程
e. 机器指令代码
f. 模块
g. 连接程序
h.程序库
1-16.要在某一台机器上为某种语言构造一个编译程序,必须掌握下述三方面的内容: c ,
d , f .
a. 汇编语言
b. 高级语言
c. 源语言
d. 目标语言
e. 程序设计方法
f. 编译方法
g. 测试方法
h. 机器语言
1-17.由于受到具体机器主存容量的限制,编译程序几个不同阶段的工作往往被组合成
(1)d ,
诸阶段的工作往往是 (2)d 进行的.
(1) a. 过程 b. 程序 c. 批量 d.遍
(2) a. 顺序 b. 并行 c. 成批 d.穿插
1-18.编译程序与具体的机器 a , 与具体的语言 a .
a. 有关
b.无关
1-19.使用解释程序时,在程序未执行完的情况下， a 重新执行已执行过的部分.
a. 也能
b.不可能
1-20.编译过程中,语法分析器的任务就是 b .
(1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的
(3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构
a. (2)(3)
b. (2)(3)(4)
c. (1)(2)(3)
d.(1)(2)(3)(4)
1-21.编译程序是一种常用的 b 软件.
a. 应用
b. 系统
1-22.编写一个计算机高级语言的源程序后,到正式上机运行之前，一般要经过 b 这几步.
(1) 编辑 (2) 编译 (3) 连接 (4) 运行
a. (1)(2)(3)(4)
b. (1)(2)(3)
c. (1)(3)
d.(1)(4)
1-23.编译程序必须完成的工作有 a .
(1) 词法分析 (2) 语法分析 (3) 语义分析
(4) 代码生成 (5) 之间代码生成 (6) 代码优化
a. (1)(2)(3)(4)
b. (1)(2)(3)(4)(5)
c. (1)(2)(3)(4)(5)(6)
d. (1)(2)(3)(4)(6)
e. (1)(2)(3)(5)(6)
1-24.“用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行”这种说法a .
a. 不正确
b.正确
1-25.把汇编语言程序翻译成机器可执行的目标程序的工作是由 b 完成的.
a. 编译器
b. 汇编器
c. 解释器
d. 预处理器
1-26.编译程序生成的目标程序 b 是机器语言的程序.
a. 一定
b. 不一定
1-27.编译程序生成的目标程序 b 是可执行的程序.
a. 一定
b. 不一定
1-28．编译程序是一种 B 。
A. 汇编程序
B. 翻译程序
C. 解释程序
D. 目标程序
1-29．按逻辑上划分，编译程序第二步工作是 C 。
A. 语义分析
B. 词法分析
C. 语法分析
D. 代码优化
1-30．通常一个编译程序中，不仅包含词法分析，语法分析，中间代码生成，代码优化，目标代码生成等五个部分，还应包括 C 。
A.模拟执行器
B.解释器
C.表格处理和出错处理
D.符号执行器
2-06．已知语言L={ xnyyn | n>=1}，则下述文法中， D 可以产生语言L。
A 1.Z→xZy|xAy|y
B 1.A→xAy
2. A→xAy|x 2.A→x
C 1.Z→AyB
D 1.Z→xAy
2.A→xA|x 2.A→xAy|y
3.B→yB|y
2-07．文法G所描述的语言是 C 的集合。
A.文法G的字母表V中所有符号组成的符号串
B.文法G的字母表V的闭包V*中的所有符号串
C.由文法的开始符号推出的所有终极符串
D.由文法的开始符号推出的所有符号串
2-08．乔姆斯基（Chomsky）把文法分为四种类型，即0型、1型、2型、3型。其中3型文法是 B 。
A.短语文法
B.正则文法
C.上下文有关文法
D.上下文无关文法
2-09.文法G[N]=（{b}，{N，B}，N，{N→b│bB，B→bN}），该文法所描述的语言是
C 。
A. L(G[N])={b i│i≥0}
B. L(G[N])={b2i│i≥0}
C. L(G[N])={b2i+1│i≥0}
D. L(G[N])={b2i+1│i≥1}
2-10．一个句型中的最左 B 称为该句型的句柄。
可选项有：
A. 短语
B. 简单短语
C. 素短语
D. 终结符号
2-11．设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V*),则称x是文法G 的一个 B 。
A. 候选式
B. 句型
C. 单词
D. 产生式
2-12．一个上下文无关文法G包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 D 。
A. 句子
B. 句型
C. 单词
D. 产生式
2-13.文法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) ③
2-14．若一个文法是递归的，则它所产生的语言的句子 A 。
A.是无穷多个
B.是有穷多个
C.是可枚举的
D.个数是常量
2-15．文法的二义性和语言的二义性是两个 A 的概念。
A 不同
B 相同
C 无法判断
D 不存在
3-02．词法分析器用于识别 C 。
A. 句子
B. 句型
C. 单词
D. 产生式
4-07.在语法分析处理中，FIRST集合、FOLLOW集合、SELECT集合均是 B 。
A. 非终极符集
B.终极符集
C. 字母表
D. 状态集
4-08.编译程序中语法分析器接收以 A 为单位的输入。
A. 单词
B. 表达式
C. 产生式
D. 句子
5-06．在自底向上的语法分析方法中，分析的关键是 D 。
A. 寻找句柄
B. 寻找句型
C. 消除递归
D. 选择候选式
5-07. 在LR分析法中，分析栈中存放的状态是识别规范句型 C 的DFA状态。
A.句柄
B. 前缀
C. 活前缀
D. LR(0)项目
三、是非题(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。)
1-31.计算机高级语言翻译成低级语言只有解释一种方式。（×）
1-32.在编译中进行语法检查的目的是为了发现程序中所有错误。（×）
1-34.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。（×）
2-15.正则文法其产生式为A→a，A→Bb, A,B∈V N，a、b∈V T。（√）
4-09.每个文法都能改写为LL(1)文法。（×）
4-10.递归下降法允许任一非终极符是直接左递归的。（√）
5-08.算符优先关系表不一定存在对应的优先函数。（√）
5-09.自底而上语法分析方法的主要问题是候选式的选择。（×）
5-10.LR法是自顶向下语法分析方法。（×）
5-11.简单优先文法允许任意两个产生式具有相同右部。（×）
5-12.若一个句型中出现了某产生式的右部，则此右部一定是该句型的句柄。（×）
5-13.一个句型的句柄一定是文法某产生式的右部。（√）
7-02.数组元素的地址计算与数组的存储方式有关。（√）
8-03.在程序中标识符的出现仅为使用性的。（×）
9-04.对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。（×）
9-05.在程序中标识符的出现仅为使用性的。（×）
10-03.仅考虑一个基本块，不能确定一个赋值是否真是无用的。（√）
10-04.削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性。（×）
R
10-05.在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度。 （√） 四、名词解释
1-35. 扫描遍____指编译程序对源程序或中间代码程序从头到尾扫描一次。
2-16.短语——设G[Z]是给定文法, w=xuy ∈V +，为该文法的句型,如果满足下面两个条件:
① Z xUy ； ② U
u ；
则称句型xuy 中的子串u 是句型xuy 的短语。 2-17.简单短语——设G[Z]是给定文法, w=xuy ∈V +，为该文法的句型,如果满足下面两个条件:
① Z
xUy ；
② U ? u ；
则称句型xuy 中的子串u 是句型xuy 的简单短语（或直接短语）。 2-18.句柄——一个句型中的最左简单短语称为该句型的句柄。
2-19.答：规范推导——如果在任一步推导v ?w 中，都是对符号串v 的最右非终结
符进行替换，则称其为规范推导。
2-21.答：语言—— L （G[Z]）={x| Z ? x ， x ∈V T * }。 4-11.语法分析－－按文法的产生式识别输入的符号串是否为一个句子的分析过程。 4-12.选择符集合SELECT －－给定上下文无关文法的产生式A →α, A ∈V N ,α∈V *
, 若
α
ε,
则SELECT(A →α)=FIRST(α),其中如果
α
ε，则SELECT(A →α)=FIRST(α\ε)∪
FOLLOW(A),FIRST(α\ε)表示FIRST(α)的非{ε}元素。
5-14.活前缀——若S ′ αA ω αβω是文法G ′中的一个规范推导，G ′是G 的拓广文法，
符号串γ是αβ的前缀，则称γ是G 的，也是G ′的一个活前缀。其中 S'为文法开始符
号。或：可归前缀的任意首部。
5-15.可归前缀——是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。
5-16.LR(0)项目——把产生式右部某位置上标有圆点的产生式称为相应文法的一个LR(0)项目。 5-17.算符优先文法——设有一不含ε产生式的算符文法G ，如果对任意两个终结符对a ，b 之
间至多只有
、
和
三种关系中的一种成立，则称G 是一个算符优先文法。
5-18.最左素短语——设有文法G[S],其句型的素短语是一个短语,它至少包含一个终结符，并
除自身外不包含其它素短语，最左边的素短语称最左素短语。
6-05.语义规则——对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。 6-06.翻译方案——将属性文法中的语义规则用花括号{ }括起来，插在产生式右部的合适地方，指明语义规则的计算次序，陈述一些细节，得到一种语义动作与语法分析交错的表示方法，以表述语义动作在语法分析过程中的执行时刻，称之为翻译方案。
6-07.语法制导翻译——为文法中每个产生式配上一组语义规则，并且在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。
7-03.后缀式—— 一种把运算量（操作数）写在前面把算符写在后面（后缀）的表示法。即
R *
一个表达式E的后缀形式可以如下定义：
(1)如果E是一个变量或常量，则E的后缀式是E自身。
(2)如果E是E1op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1’ E2’
op，这里E1’和E2’分别为E1和E2的后缀式。
(3)如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式。
7-04.四元式——一个四元式是一个带有四个域的记录结构，这四个域分别称为op、arg1、arg2及result。域op包含一个代表运算符的内部码。
9-06.活动
答：一个过程的活动指的是该过程的一次执行。就是说，每次执行一个过程体，产生该过程体的一个活动。
9-07.活动记录
答：为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，这样一个连续的存储块称为活动记录。
9-08.活动的生存期
答：指的是从执行某过程体第一步操作到最后一步操作之间的操作序，包括执行过程时调用其它过程花费的时间。
10-02.答：基本块——源程序中只有一个入口和一个出口的顺序执行的代码段。
10-06. 基本块的DAG。
答：一个基本块的DAG是一种其结点带有下述标记或附加信息的DAG。
(1)图的叶结点（没有后继的结点）以一标识符（变量名）或常数作为标记，表示该结点代表该变量或常数的值。如果叶结点用来代表某变量A的地址，则用addr（A）作为该结点的标记。通常把叶结点上作为标记的标识符加上下标0，以表示它是该变量的初值。
(2)图的内部结点（有后继的结点）以一运算符作为标记，表示该结点代表应用该运算符对其后继结点所代表的值进行运算的结果。
(3)图中各个结点上可能附加一个或多个标识符，表示这些变量具有该结点所代表的值。
五、简答题：
2-19什么是句子？什么是语言?
答：设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈V T*),则称x是文法的一个句子。
设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为： L(G)＝{x│S x,x∈V T*} 。
2-20.已知文法G[E]为：
E→T|E+T|E-T
T→F|T*F|T/F
F→（E）|i
①该文法的开始符号（识别符号）是什么？
②请给出该文法的终结符号集合V T和非终结符号集合V N。
③找出句型T+T*F+i的所有短语、简单短语和句柄。
解：①该文法的开始符号（识别符号）是E。
②该文法的终结符号集合V T={+、-、*、/、（、）、i}。
非终结符号集合V N={E、T、F}。
③句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i;
简单短语为i、T*F、第一个T;句柄为第一个T。
2-21.已知文法G[S]为：
S→dAB
A→aA|a
B→Bb|ε
① G[S]产生的语言是什么？
② G[S]能否改写为等价的正规文法？
解：① G[S]产生的语言是L(G[S])={da n b m│n≥1,m≥0}。
② G[S]能改写为等价的正规文法,其改写后的等价的正规文法G[Sˊ]为：
Sˊ→dA
A →aA|aB|a
B →bB|b
2-22.设有语言L(G)={ada R | a∈(a,b)*,a R 为a之逆}，试构造产生此语言的上下文无关文法G。解：根据题义，可知a R 为a之逆的含义就是句子中的符号a、b以d为中心呈左右对称出现；由于a∈(a,b)*，所以a、b的个数可以为零。所以可构造产生此语言的上下文无关文法G[S]为：
S→aSa|bSb|d
2-23.证明下面文法G[N]是二义性文法。
G[N]： N →SE∣E
S →SD∣D
E →0∣2∣10
D →0∣1∣2
答：10是文法G[N]的一个句子，并且有两个不同的最右推导。
（1）1S => E => 10
（2）S => SE => S0 => D0 => 10
因此说明此文法有二义性。
3-03．简述DFA与NFA有何区别 ?
答：DFA与NFA的区别表现为两个方面:一是NFA可以若干个开始状态，而DFA仅只一个开始状态。另一方面，DFA的映象M是从K×∑到K，而NFA的映象M是从K×∑到K的子集，即映象M将产生一个状态集合（可能为空集），而不是单个状态。
3-04.试给出非确定自动机的定义。
答：一个非确定的有穷自动机（NFA）M是一个五元组：M=（K，Σ，f，S ，Z）。
其中:
1. K 是一个有穷集，它的每个元素称为一个状态；
2. Σ是一个有穷字母表，它的每个元素称为一个输入符号，所以也称Σ为输入符号表；
3. f 是状态转换函数，是在K ×Σ*→K 的子集的映射，即，f: K ×Σ*→2K ；表明在某状
态下对于某输入符号可能有多个后继状态； 4. S ﹙K 是一个非空初态集； 5. Z ﹙K 是一个终态集（可空）。
3-05. 为正规式（a|b ）*
a(a|b) 构造一个等价的确定的有限自动机。
解答： 3-06. 给定下列自动机，将其转换为确定的自动机。
解答：(1)消除ε边，得到NFA ：
带―号的结点为终止状态
―
― 带―号的结点为终止状态
2
(1)把此自动机转换为确定自动机DFA 。
(2)给出此DFA 的正则表达式。 解答：（1）： 有状态矩阵如图：
从而可得DFA 如图：
（2）此DFA b)(b ∣ab)* 或 a *b （b ∣ab ）*。 ― 注：带＋号的结点为初始状态； 带―号的结点为终止状态
a b ?0 01 2 01 01 2 －2 1 2 1 2
a b
?0 0,1 2 1 2 －2 1 2
?
a
极小化后：
a
编译原理复习资料
(1) 简述规范归约的基本思想。（第五章课件第5张） 用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。 (2) 阐述编译程序各个组成部分主要完成的工作。（课本P2~P4） 词法分析的任务:输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词。 语法分析：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位。 语义分析与中间代码产生：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译。 优化：在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效的目标代码。 目标代码生成：把中间代码变换成特定机器上的低级语言代码。 (3) 什么是编译器的前端和后端，这样划分有何意义？（课本P7） 编译器粗略分为 词法分析，语法分析，类型检查，中间代码生成， 代码优化，目标代码生成，目标代码优化。 把中间代码生成及之前阶段划分问编译器的前端，那么后端与前端是独立的。后端只需要一种中间代码表示，可以是三地址代码或四元式等，而这些都与前端生成的方式无关。也就是不论你前端是用fortran 还是c/c++,只要生成了中间代码表示就可以了，后端是不管你是用哪种语言生成的。 (4) 乔姆斯基把文法分为哪几种类型？对这几种类型文法作简要说明。（课本P34） 把文法分成四种类型：0，1，2，3型。与上下文无关文法一样，它们都由四部分组成，但对产生式的限制有所不同。 0型(短语文法，图灵机)：产生式形如：α→β其中：∈α (VT ? VN)*且至少含有一个非终结符；∈β (VT ? VN)* 1型(上下文有关文法，线性界限自动机)：产生式形如：α→β其中：|α| ≤ |β|。仅Sε→例外，但此时S不得出现在任何产生式的右部。 2型(上下文无关文法，非确定下推自动机)：产生式形如： A →β其中：A∈ VN；∈β (VT ? VN)*。 3型(正规文法，有限自动机)：产生式形如：A → aB 或A → a其中：a∈ VT ? {ε}；A，B∈VN产生式形如： A → Ba 或 A → a 其中：a∈ VT ? {ε}；A，B∈VN。 (5) 简述编译过程中遍的概念以及遍数的多少对编译器设计的影响。（参考课本P7） 遍的概念：对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。 遍可以和阶段相应，也可无关——遍中通常含有若干个阶段。实际上，根据语言的不同，编译器可以是一遍（onepass）——所有的阶段由一遍完成，其结果是编译得很好，但（通常）代码却不太有效。Pascal 语言和C语言均允许单遍编译。（Modula-2语言的结构则要求编译器至少有两遍）。大多数带有优化的编译器都需要超过一遍：典型的安排是将一遍用于扫描和分析，将另一遍用于语义分析和源代码层优化，第3遍用于代码生成和目标层的优化。更深层的优化则可能需要更多的遍： 5遍、6遍、甚至8遍都是可能的。 备注：由于最后一道没有找到比较好的答案，欢迎大家补充。 1) 什么是句子？什么是语言?
编译原理课程设计
《编译原理》课程设计大纲 课程编号： 课程名称：编译原理/Compiler Principles 周数/学分：1周/1学分 先修课程：高级程序设计语言、汇编语言、离散数学、数据结构 适用专业：计算机科学与技术专业、软件工程专业 开课学院，系或教研室：计算机科学与技术学院 一、课程设计的目的 课程设计是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，设计题中的问题比平时的练习题要复杂，也更接近实际。编译原理这门课程安排的课程设计的目的是旨在要求学生进一步巩固课堂上所学的理论知识，深化理解和灵活掌握教学内容，选择合适的数据逻辑结构表示问题，然后编制算法和程序完成设计要求，从而进一步培养学生独立思考问题、分析问题、解决实际问题的动手能力。 要求学生在上机前应认真做好各种准备工作，熟悉机器的操作系统和语言的集成环境，独立完成算法编制和程序代码的编写。 设计时间： 开发工具： （1） DOS环境下使用Turbo C； （2） Windows环境下使用Visual C++ 。 （3） 其它熟悉语言。 二、课程设计的内容和要求 设计题一：算术表达式的语法分析及语义分析程序设计。 1.目的
通过设计、编制、调试一个算术表达式的语法及语义分析程序，加深对语法及语义分析原理的理解，并实现词法分析程序对单词序列的词 法检查和分析。 2.设计内容及要求： 算术表达式的文法： 〈无符号整数〉∷＝ 〈数字〉{〈数字〉} 〈标志符〉∷＝ 〈字母〉{〈字母〉｜〈数字〉} 〈表达式〉∷＝ [＋｜－]〈项〉{〈加法运算符〉〈项〉} 〈项〉∷＝ 〈因子〉{〈乘法运算符〉〈因子〉} 〈因子〉∷＝ 〈标志符〉｜〈无符号整数〉｜‘（’〈表达式〉‘）’ 〈加法运算符〉∷＝ ＋｜－ 〈乘法运算符〉∷＝ ＊｜／ （1） 分别选择递归下降法、算符优先分析法（或简单优 先法）完成以上任务，中间代码选用逆波兰式。 （2） 分别选择LL（1）、LR法完成以上任务，中间代码选 用四元式。 （3） 写出算术表达式的符合分析方法要求的文法，给出 分析方法的思想，完成分析程序设计。 （4） 编制好分析程序后，设计若干用例，上机测试并通 过所设计的分析程序。 设计题二：简单计算器的设计 1．目的 通过设计、编制、调试一个简单计算器程序，加深对语法及语 义分析原理的理解，并实现词法分析程序对单词序列的词法检 查和分析。 2.设计内容及要求 算术表达式的文法：
编译原理试题(卷)汇总-编译原理期末试题(卷)(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____。
编译原理复习题
编译原理复习题 一、填空题 1.编译程序的工作过程一般可以划分为词法分析，语法分析，语义分析，中间代码优化，代码优化等几个基本阶段。 2.若源程序是用高级语言编写的，目标程序是汇编程序或机器语言程序，则其翻译程序称为编译程序. 3.编译方式与解释方式的根本区别在于是否生成目标代码. 5.对编译程序而言，输入数据是源程序，输出结果是目标程序. 7.若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。 8.一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格管理和出错处理。其中，词法分析器用于识别单词。 10.一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。 12.产生式是用于定义语法成分的一种书写规则。 13.设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)={x|Sx，x∈VT*}。 14.设G是一个给定的文法，S是文法的开始符号，如果S * ?x（其中x∈V*），则称x是 文法的一个句型。 15.设G是一个给定的文法，S是文法的开始符号，如果S * ?x(其中x∈V T*)，则称x是文 法的一个句子。 16.扫描器的任务是从源程序中识别出一个个单词符号。 17.语法分析最常用的两类方法是自顶向下和自底向上分析法。 18.语法分析的任务是识别给定的终结符串是否为给定文法的句子。 19.递归下降法不允许任一非终结符是直接左递归的。 20.自顶向下的语法分析方法的关键是如何选择候选式的问题。 21.递归下降分析法是自顶向下分析方法。 22.自顶向下的语法分析方法的基本思想是：从文法的开始符号开始，根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导，试图推导出文法的句子，使之与给定的输入串匹配。 23.自底向上的语法分析方法的基本思想是：从给定的终结符串开始，根据文法的规则一步一步的向上进行直接归约，试图归约到文法的开始符号。 24.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地 向上进行直接归约，力求归约到文法的开始符号。 26.在LR（0）分析法的名称中，L的含义是自左向右的扫描输入串，R的含义是最左归约， 0 的含义是向右查看输入串符号的个数为0。 31.终结符只有，它们由词法分析器提供。 32.在使用高级语言编程时，首先可通过编译程序发现源程序的全部语法错误和语义部分错误. 34．一个句型中的最左简单短语称为该句型的句柄。 36．从功能上说，程序语言的语句大体可分为执行性语句和说明性语句两大类。
编译原理期末考试题目及答案
一、填空题（每空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、给出下面语言的相应文法。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)
编译原理课程设计
编译原理课程设计报告 课题名称： C-语言编译器设计（scanner和parser） 提交文档学生姓名： 提交文档学生学号： 同组成员名单：无 指导教师姓名：金军 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间： 2011年 6 月 17 日
1.课程设计目标 设计C-Minus编译器分为scanner和parser两个部分。scanner主要作用是对目标代码进行扫描，列出关键字，变量等内容；parser主要对语法进行分析并生成语法树。 2.分析与设计 ●实现方法：代码用C语言编译而成。其中scanner为手工实现，主要采用switch-case结构实现 状态转换；parser部分采用递归下降分析方法实现。 ●扫描器：C-的词法如下： 1、语言的关键字：i f el se i nt return void while 2、专用符号：+ - * /< <= > >= == != =; , ( ) [ ] { } /* */ 3、其他标记是变量（ID）和数字（NUM），通过下列正则表达式定义： ID = letter letter* NUM = di git digi t* letter = a|..|z|A|..|Z digi t = 0|..|9 4、空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM关键字 5. 注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在 标记内)上，且可以超过一行。注释不能嵌套 其DFA图如下：
分析器：以下为C-的语法规则BNF:
编译原理复习题及答案
编译原理复习题及答案 一、选择题 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) A. bba B. cab C. bca D. cba
CMinus词法分析和语法分析设计编译器编译原理课程设计报告书
编译原理课程设计报告 课题名称：C- Minus词法分析和语法分析设计 提交文档学生姓名：X X X 提交文档学生学号：XXXXXXXXXX 同组成员名单：X X X 指导教师姓名：X X 指导教师评阅成绩： 指导教师评阅意见： . . 提交报告时间：2015年6月10日
1.课程设计目标 实验建立C-编译器。只含有扫描程序（scanner）和语法分析（parser）部分。 2.分析与设计 C-编译器设计的整体框架，本实验实现扫描处理和语法分析程序（图中粗黑部分）。 2.1 、扫描程序scanner部分 2.1.1系统设计思想 设计思想：根据DFA图用switch-case结构实现状态转换。 惯用词法：
①语言的关键字：else if int return void while ②专用符号：+ - * / < <= > >= == != = ; , ( ) [ ] { } /* */ ③其他标记是ID和NUM，通过下列正则表达式定义： ID = letter letter* NUM = digit digit* letter = a|..|z|A|..|Z digit = 0|..|9 大写和小写字母是有区别的 ④空格由空白、换行符和制表符组成。空格通常被忽略，除了它必须分开ID、NUM 关键字。 ⑤注释用通常的C语言符号/ * . . . * /围起来。注释可以放在任何空白出现的位置(即注释不能放在标记内)上，且可以超过一行。注释不能嵌套 scanner的DFA
说明：当输入的字符使DFA到达接受状态的时候，则可以确定一个单词了。初始状态设置为START，当需要得到下一个token时，取得次token的第一个字符，并且按照DFA与对此字符的类型分析，转换状态。重复此步骤，直到DONE为止，输出token类型。当字符为“/”时，状态转换为SLAH再判断下一个字符，如果为“*”则继续转到INCOMMENT，最后以“*”时转到ENDCOMMENT状态，表明是注释，如果其他的则是字符停滞于当前字符，并且输出“/”。 2.1.2程序流程图
郑州大学编译原理试卷及答案(往年试题整合)(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、设有文法：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为 ②状态转换矩阵为：
编译原理课程设计
编译原理课程设计 自顶向下语法分析器 学院（系）：计算机科学与技术学院学生姓名：xxxxxxxxx 学号：xxxxxxxxx 班级：电计1102 大连理工大学 Dalian University of Technology
目录
1 系统概论 语法分析是编译过程的核心部分。它的任务是在词法分析识别出单词符号串的基础上，分析并判定程序的语法结构是否符合语法规则。语法分析器在编译程序中的地位如图1所示： 图1 语法分析器在编译程序中的地位 语言的语法结构是用上下文无关文法描述的。因此，语法分析器的工作本质上就是按文法的产生式，识别输入符号串是否为一个句子。这里所说的输入串是指由单词符号（文法的终结符）组成的有限序列。对一个文法，当给你一串（终结）符号时，怎样知道它是不是该文法的一个句子呢？这就要判断，看是否能从文法的开始符号出发推导出这个输入串。或者，从概念上讲，就是要建立一棵与输入串相匹配的语法分析树。 自顶向下分析法就是语法分析办法中的一类。顾名思义，自顶向下就是从文法的开始符号出发，向下推导，推出句子。这种方法是带“回溯”的。 自顶向下分析的主旨是，对任何输入串，试图用一切可能的办法，从文法开始符号（根结）出发，自上而下地为输入串建立一棵语法树。或者说，为输入串寻找一个最左推导。这种分析过程本质上是一种试探过程，是反复使用不同产生式谋求匹配输入串的过程。 实现这种自顶向下的带回溯试探法的一个简单途径是让每个非终结符对应一个递归子程序。每个这种子程序可作为一个布尔过程。一旦发现它的某个候选与输入串相匹配，就用这个候选去扩展语法树，并返回“真”值；否则，保持原来的语法树和IP值不变，并返回“假”值。 2 需求分析 以前，人们对语法的分析都建立在人工的基础上，人工分析虽然能够做到侧类旁推，但终究人力有限，再精密的分析都会出现或多或少的错误。为减少因人为产生的错误，并加快
编译原理试题及答案
参考答案 一、单项选择题(共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中的一条产生式。
编译原理期末考试复习题
选择： 1.编译程序绝大多数时间花在 D 上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 3.如果文法G是无二义的，则它的任何句子α A 。 a. 最左推导和最右推导对应的语法树必定相同 b. 最左推导和最右推导对应的语法树可能不同 c. 最左推导和最右推导必定相同 d. 可能存在两个不同的最左推导，但它们对应的语法树相同 4.在规范归约中，用 B 来刻画可归约串。 a. 直接短语 b. 句柄 c. 最左素短语 d. 素短语 5.若a为终结符，则A→α·aβ为 B 项目 a.归约 b.移进 c.接受 d.待约 6.间接三元式表示法的优点为（A） A.采用间接码表，便于优化处理 B.节省存储空间，不便于表的修改 C.便于优化处理，节省存储空间 D.节省存储空间，不便于优化处理 7.下列C优化方法不是针对循优化进行的。 a．强度削弱b．删除归纳变量c．删除多余运算d．代码外提 8.过程P1调用P2时，连接数据不包含 A 。 a. 嵌套层次显示表 b. 老SP c. 返回地址 d. 全局DISPLAY地址 9.如果活动记录中没有DISPLAY表，则说明b。 a. 程序中不允许有递归定义的过程 b. 程序中不允许有嵌套定义的过程 c. 程序中既不允许有嵌套定义的过程，也不允许有递归定义的过程 d. 程序中允许有递归定义的过程，也允许有嵌套定义的过程 10.关于必经结点的二元关系，下列叙述中不正确的是 D 。 a．满足自反性b．满足传递性c．满足反对称性d．满足对称性11.构造编译程序应掌握 D 。 a．源程序b．目标语言 c．编译方法d．以上三项都是 12.词法分析器的输出结果是__C___。 A．单词的种别编码B．单词在符号表中的位置 C．单词的种别编码和自身值D．单词自身值 13.文法G：S→xSx|y所识别的语言是 C 。 a. xyx b. (xyx)* c. x n yx n(n≥0) d. x*yx* 14.同心集的合并有可能产生新的归约/归约冲突 15.四元式之间的联系是通过 B 实现的。 a.指示器 b.临时变量 c.符号表 d.程序变量 16.优化可生成_____的目标代码。 A. 运行时间较短 B．占用存储空间较小 C．运行时间短但占用内存空间大D．运行时间短且占用存储空间小
编译原理复习资料
第3章文法和语言 第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} 第 11题 令文法 G[E]为： E→T|E+T|E-T T→F|T*F|T/F F→(E)|i 证明 E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。答案： 此句型对应语法树如右，故为此文法一个句型。 或者：因为存在推导序列: E=>E+T=>E+T*F，所 以E+T*F句型 此句型相对于E的短语有:E+T*F；相对于 T的短语 有 T*F 直接短语为：T*F 句柄为：T*F 第 13题 一个上下文无关文法生成句子abbaa的推导树如下： (1)给出串abbaa最左推导、最右推导。 (2)该文法的产生式集合 P可能有哪些元素？ (3)找出该句子的所有短语、直接短语、句柄。 A S a S B B B A S a
《编译原理》课后习题答案第三章 答案： (1)串abbaa最左推导: S=>ABS=>aBS=>aSBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa 最右推导： S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>abbaa (2)产生式有：S→ABS |Aa|ε A→a B→SBB|b abbaa aaabbaa ? 可能元素有：ε aa ab (3)该句子的短语有： a是相对 A的短语 ε是相对 S的短语 b是相对 B的短语 εbb是相对 B的短语 aa是相对 S的短语 aεbbaa是相对 S的短语 直接短语有：a ε b 句柄是：a
编译原理课程设计
编译原理： 编译原理是计算机专业的一门重要专业课，旨在介绍编译程序构造的一般原理和基本方法。内容包括语言和文法、词法分析、语法分析、语法制导翻译、中间代码生成、存储管理、代码优化和目标代码生成。编译原理是计算机专业设置的一门重要的专业课程。编译原理课程是计算机相关专业学生的必修课程和高等学校培养计算机专业人才的基础及核心课程，同时也是计算机专业课程中最难及最挑战学习能力的课程之一。编译原理课程内容主要是原理性质，高度抽象。 编译原理课程设计： 《编译原理课程设计》是2007年11月浙江大学出版社出版的图书，作者是冯雁、鲁东明、李莹。 内容简介： 本书围绕着编译技术的基本原理和方法，以模拟程序设计语言SPL的编译器的设计和实现为主线，结合词法分析、语法分析、语义分析、代码生成、代码优化、错误处理等各个基本模块，对原理和实现方法进行了详细分析。该编译器可接受SPL的程序，并将其翻译成汇编语言程序，最终实现汇编语言到8086/8088机器语言的翻译。本书为编译技术等相关课程的实验提供了参考。在附件中还提供了三类不同类型和难度的实验题，可供课程实验选择。 第1章引论： 1.1本书介绍 1.2SPL语言的特点及实验安排
1.2.1SPL语言的特点 1.2.2SPL语言编译器的主要结构1.2.3实验安排 1.3平台的选择和介绍 1.3.1LEX简介 1.3.2YACC简介 第2章词法分析： 2.1词法分析器的基本框架 2.2词法分析器的基本原理 2.2.1DFA的构造和实现 2.2.2词法分析的预处理 2.2.3实现词法分析器的注意要点2.3词法分析器的实现 2.3.1SPL语言单词属性字 2.3.2SPL词法分析器的输入和输出2.3.3SPL词法分析器的分析识别第3章语法分析： 3.1语法分析的基本框架 3.1.1上下文无关文法 3.1.2语法分析过程 3.1.3语法分析过程中的数据结构3.2语法分析的基本方法
编译原理考试试题与答案(汇总)
《编译原理》考试试题及答案（汇总） 一、是非题（请在括号，正确的划√，错误的划×）（每个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．( ) 代码外提