1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？
答
编译程序总框架
（1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。
（2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。
（3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。
（4）优化器，对中间代码进行优化处理。
（5）目标代码生成器，把中间代码翻译成目标程序。
（6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。
（7）出错管理，把错误信息报告给用户。
编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。
（2）。语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。
（3）语义分析与中间代码产生。任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。
（4）优化。任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。
（5）目标代码生成。任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。
2》．重要概念：
a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。
b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等
c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。
d. 遍：就是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。
e. 上下文无关文法（CFG）：它所定义的语法范畴（或语法单位）完全独立于这种范畴可能出现的环境之外，不宜描述自然语言。自然语言中，句子和词等往往与上下文紧密相关
f. LL（K）分析法：第一个L表示从左到右扫描输入串，第二个L表示最左推导，K表示分析时每一步需要向前查看K个符号。
g. LR分析法：L表示从左到右扫描输入串,R表示构造一个最右推导的逆过程。
h. 算符优先法：就是定义算符之间的某种优先关系，借助于这种关系寻找“可归约串”和进行归约。
i. 属性文法：是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值“（称为属性），对于文法的每个产生式都配备了一组属性的计算规则（称为语义规则）。
3》.有哪些存储分配策略，并叙述何时用何种存储分配策略？
答：有静态与动态存储分配策略。动态的存储分配策略包括栈式动态分配策略与堆式动态分配策略。静态分配策略在编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变。栈式动态分配策略在运行时把存储器作为一个栈进行管理，运行时，每当调用一个过程，它所需要的存储空间就动态地分配于栈顶，一旦退出，她所占空间就予以释放。堆式动态分配策略在运行时把存储器组织成堆结构，以便用户关于存储空间的申请与归还（回收），凡申请者从堆中分给一块，凡释放者退回给堆。
4》.编译过程中可进行的优化如何分类？最常用的代码优化技术有哪些？
答：根据优化涉及范围与程序范围可以分为：局部优化，循环优化和全局优化。
最常用的代码优化技术有：删除公共子表达式，复写传播，删除无用代码，代码外提，强度削弱和删除归纳变量。
5》.一个编译程序的代码生成要着重考虑哪些问题？
答：代码生成器的设计要着重考虑目标代码的质量问题，而衡量目标代码的质量主要从占用空间和执行效率两个方面综合考虑。
【代码生成要着重考虑两个问题：1）.如何使生成的目标代码较短 2.）如何充分利用计算机的寄存器。（减少目标代码中访问存储单元的次数。）这两个问题都直接影响目标代码的执行速度】
6》．语言和文法的转换的例题
(1). 文法G2：S→bA，A→aA∣a
解：推导过程S?bA?ba
S?bA?baA?baa
…
S?bA?baA?…?ba…a
归纳得出：L(G2)={ba^n︱n≥1}
(2).文法G3：S→AB，A→aA∣a，B→bB∣b
解：推导过程S?AB?ab
S?AB?aAB?aAb?aab?a^2b
S?AB?abB?abb?ab^2
…
归纳得出L(G3)={a^mb^n︱m,n≥1}
(3).若已知文法G6(A)： A → c|Ab 请给出G6(A)的语言?
解答::L(G6)={c，cb，cbb，?} 以c开头，后继若干个b
(4).若已知文法G8(S)：S→aSBE S→aBE
EB→BE aB→ab bB→bb bE→be eE→ee
请给出G8(S)的语言?
解答: S →a S BE S →aaB EB E (S →aBE)
S →a aB BEE (EB →BE) S →aa bB EE (aB →ab) S →aab bE E (bB →bb) S →aabb eE (bE →be) S →aabbee (eE →ee)
L(G8)={ a^nb^ne^n | n ≥1}, 上下文有关文法
(5)给出生成下述语言的上下文无关文法：（1）{ a^nb^na^mb^m| n ，m>=0} （2）{ 1^n0^m1^m0^n| n ，m>=0}
? G1(S)
S →AA A →aAb|ε
? G2(S)
S →1S0|A A →0A1|ε
7》.有限自动机
（1）DFA 举例 DFA M = ({0,1,2,3},{a,b},f,0,{3}) f 定义如下：
f(0,a)=1 f(0,b)=2 f(1,a)=3 f(1,b)=2 f(2,a)=1 f(2,b)=3 f(3,a)=3
f(3,b)=3
（2）.
证明t=baab 被下图的DFA 所接受
对于∑*中的任何字α，若存在一条从初态到某一终态的通路，
且这条通路上所有弧的标
a
记符连接成的字等于α，则称α为DFA M所识别（或接受）
证法一：∵a,b∈∑∴baab∈∑*
f(S,baab) = f(f(S,b),aab) = f(V,aab) = f(f(V,a),ab) = f(U,ab) = f(f(U,a),b) = f(Q,b) =
Q。Q属于终态,故得证
证法二：根据上述状态转换图，可以构造确定有限自动机DFA M＝〈{S,U,V,Q}，{a,b}，FM，S，{Q}〉
其中，FM 是DFA M的状态转换函数，定义如下：
FM （S,a）＝U FM （S,b）＝V
FM （U,a）＝Q FM （U,b）＝V
FM （V,a）＝U FM （V,b）＝Q
FM （Q,a）＝Q FM （Q,b）＝Q
∵a,b∈∑∴baab∈∑*
由题意可知：对于t＝baab，DFA M存在一条经过S、V、U、Q和Q的通路，
使得该通路上所有弧的标记符连接成的字等于t
因此，t 被DFA M所接受
（2）：下图是一个NFA的状态转换图，请将其转化为一个DFA。
●
解：采用NFA确定化算法（或子集法）。
状态集合I的ε-闭包表示为ε-closure(I)。
状态集I中任何状态S经任意条ε弧而能到达的状态集S∈ε-closure(I)。
状态集合I的a弧转换表示为move(I,a)，定义为状态集合J，其中：J是所有那些可从I 中的某一状态经过一条a弧而到达的状态的全体。
Ia = move(I,a) = ε-closure(J)。
因此得出上表。
根据上述NFA的状态转换图及其确定化过程，可以构造与它等价的DFA M。
DFA M ＝〈{S,A,B,C,D,E,F}，{a,b}，FM ，S ，{C,D,E,F}〉 这个DFA M 的状态转换图
见下图所示。
其中 S={i,1,2} A={1,2,3} B={1,2,4} C={1,2,3,5,6,f} D={1,2,4,5,6,f} E={1,2,4,6,f} F={1,2,3,6,f}
FM 是DFA M 的状态转换函数，定义如下： FM （S,a ）＝A FM （S,b ）＝B FM （A,a ）＝C FM （A,b ）＝B FM （B,a ）＝A FM （B,b ）＝D FM （C,a ）＝C FM （C,b ）＝E FM （D,a ）＝F FM （D,b ）＝D FM （E,a ）＝F FM （E,b ）＝D FM （F,a ）＝C FM （F,b ）＝E 8》．语法分析
1．文法G[V]： V →N | N[E] E →V | V+E N →i
是否为LL(1)文法？若不是，如何改造成LL(1)文法？ 解：LL(1)文法的基本条件是不含左递归和回溯（公共左因子），而G[V]中含有回溯，所以先消除回溯得到文法G ’[V]： G ’[V]： V →NV ’ V ’→ε|[E]V ’ E →VE ’ E ’→ε|+EE ’ N →i 由LL(1)文法的充要条件可证 G ’[V]是LL(1)文法 2.文法G[s]: S →BA A →BS|d B →aA|bS|c
证明文法G 是LL(1)文法 ，构造LL(1)分析表，写出句子adccd 的分析过程
解：一个LL(1)文法的充要条件是对每一个非终结符A 的任何两个不同产生式A →α|β，有下面的条件成立：FIRST(α)∩FIRST(β)=Φ， 若β* ε, 则有FIRST(α)∩FOLLOW(A)=Φ对于文法G[s]: S →BA A →BS|d B →aA|bS|c
FIRST 集FIRST(B)={a, b, c}; FIRST(A)={a, b, c, d};FIRST(S)={a, b, c}。 FOLLOW 集 FOLLOW(S)={#}
对S →BA 有 FIRST(A)\{ε}加入FOLLOW(B)，即FOLLOW(B)={a, b, c, d } 对A →BS 有FIRST(S)\{ε}加入FOLLOW(B)，即FOLLOW(B)={a, b, c, d } 对B →aA 有FOLLOW(B)加入FOLLOW(A)，即FOLLOW(A)={a, b, c, d } 对B →bS 有FOLLOW(B)加入FOLLOW(S)，即FOLLOW(S)={#, a, b, c, d } 由A →BS|d 得FIRST(BS) ∩FIRST(d) = { a, b, c } ∩{d} = Φ
由B →aA|bS|c 得FIRST(aA)∩FIRST(bS)∩FIRST(c)={a}∩{b}∩{c}= Φ
由于文法G[s]不存在形如 β→ε的产生式，故无需求解形如FIRST(α)∩FOLLOW(A)的值也即，文法G[S]是一个LL(1)文法 由G[s]：S →BA A →BS|d B →aA|bS|c 的 FIRST(B)={a, b, c}; FOLLOW(B)={a, b, c, d };
b
FIRST(A)={a, b, c, d}; FOLLOW(A)={a, b, c, d };
FIRST(S)={a, b, c}。FOLLOW(S)={#, a, b, c, d }
在分析表的控制下，句子adccd的分析过程如下：
3．对于文法G(E)：E→TE'E'→+TE' | εT→FT'T'→*FT' | εF→(E) | i
构造每个非终结符的FIRST和FOLLOW集合FIRST(E) ={ (, i } FOLLOW(E) ={ ), # } FIRST(E')={+,ε} FOLLOW(E')={ ), # } FIRST(T) ={ (, i } FOLLOW(T) ={ +, ), # } FIRST(T')={*,ε} FOLLOW(T')={ +, ), # } FIRST(F) ={ (, i } FOLLOW(F) ={ *, +, ), #}
把FOLLOW(A)中的所有符号作为A的同步符号
4．已知文法G[S]：S→eT | RT T→DR | εR→dR | εD→a | bd 构造该文法的LL(1)分析表。
F IRST(S), FIRST(T), FIRST(R), FIRST(D)
FOLLOW(S),FOLLOW (T),FOLLOW (R),FOLLOW (D)
LL(1)分析表
解：FIRST(S) = { a, b, d, e, ε } FOLLOW(S) = { # }
FIRST(T) = { a, b, ε } FOLLOW(T) = { # } FIRST(R) = { d, ε }
FOLLOW(R) = { a, b, # } FIRST(D) = { a, b } FOLLOW(D) = { d, # }
5．例：文法G[E]：E →E+T |T T →T*F | F F →(E) | id
考虑文法G[E]上的句子id1+id2*id3 。给出其最右推导和分析树，并根据分析树指出句子中的短语、直接短语和句柄
从E1推导可得到id1+id2*id3
id1+id2*id3是句型id1+id2*id3相对于E1的短语
id1+id2不是句型id1+id2*id3中相对于任何非终结符的短语
因为找不到任何一个非终结符，它的子树中的所有叶子构成id1+id2
短语以非终结符为根的子树中所有从左到右排列的叶子
?
?E1 ? E2+id2*id3? T2+id2*id3 ? F1+id2*id3? id1+id2*id3
id1是相对于非终结符E2、T2和F1的短语
相对于F1的直接短语，也是句柄
6.例4.2 文法: E→E＋T | T T→T*F | F F→(E) | i
经消去直接左递归后变成：E→TE'E'→+TE' | ε
T→FT'T'→*FT' | εF→(E) | i
7.例: 对于文法G(E)
E→TE'E'→+TE' | ε
T→FT'T'→*FT' | ε
F→(E) | i
构造每个非终结符的FIRST和FOLLOW集：
FIRST(E) ={ (, i } FOLLOW(E) ={ ), # }
FIRST(E')={+,ε} FOLLOW(E')={ ), # }
FIRST(T) ={ (, i } FOLLOW(T) ={ +, ), # }
FIRST(T')={*,ε} FOLLOW(T')={ +, ), # }
FIRST(F) ={ (, i } FOLLOW(F) ={ *, +, ), #}
T→FT'; T'→*FT' | ε; FOLLOW(T') ∈FOLLOW(F)
8.例: 对于文法G(E)
E→TE'E'→+TE' | εT→FT'T'→*FT' | εF→(E) | i
构造每个非终结符的FIRST和FOLLOW集合：
FIRST(E) ={ (, i } FOLLOW(E) ={ ), # } FIRST(E')={+,ε} FOLLOW(E')={ ), # } FIRST(T) ={ (, i } FOLLOW(T) ={ +, ), # } FIRST(T')={*,ε} FOLLOW(T')={ +, ), # }
FIRST(F) ={ (, i } FOLLOW(F) ={ *, +, ), #}
9.文法G[V]：V→N | N[E] E→V | V+E N→i
是否为LL(1)文法？若不是，如何改造成LL(1)文法？
解：LL(1)文法的基本条件是不含左递归和回溯（公共左因子），而G[V]中含有回溯，所以先消除回溯得到文法G’[V]：
G’[V]：V→NV’V’→ε|[E]V’
E→VE’E’→ε|+EE’N→i
由LL(1)文法的充要条件可证:G’[V]是LL(1)文法
11.已知文法G[S]：S→eT | RT T→DR | εR→dR | εD→a | bd
构造该文法的LL(1)分析表。FIRST(S), FIRST(T), FIRST(R), FIRST(D)
FOLLOW(S),FOLLOW (T),FOLLOW (R),FOLLOW (D) LL(1)分析表
解：FIRST(S) = { a, b, d, e, ε } FOLLOW(S) = { # } FIRST(T) = { a, b, ε } FOLLOW(T) = { # } FIRST(R) = { d, ε } FOLLOW(R) = { a, b, # }
FIRST(D) = { a, b } FOLLOW(D) = { d, # }
9》。中间语言形式
常用的中间语言：a.后缀式表示法 b.图表示法：DAG 抽象语法树
三地址代码：三元式四元式间接三元式
1.abc+*等价a*(b+C)
表达式x+y≤z ∨a＞0 ∧(8+z) ＞3 的逆波兰表示为xy+z≤a0＞8z+3＞∧∨
表达式﹁A∨﹁（C∨﹁D）的逆波兰表示为A﹁CD﹁∨﹁∨
表达式a ∧ b ∨ c ∧(b ∨x=0 ∧c) 的逆波兰表示为ab∧cbx0=c∧∨∧∨表达式（A∨B）∧（C∨﹁D∧E）的逆波兰表示为AB∨CD﹁E∧∨∧
一个带有四个域的记录结构，这四个域分别称为op, arg1, arg2及result
例：a:=b*-c+b*-c 的四元式
op arg1 arg2 result
(0) uminus c T1
(1) * b T1 T2
(2) uminus c T3
(3) * b T3 T4
(4) + T2 T4 T5
(5) := T5 a
2.例：a:=b*-c+b*-c 的三元式
三个域：op、arg1和arg2
op arg1 arg2
(0) uminus c
(1) * b (0)
(2) uminus c
(3) * b (2)
(4) + (1) (3)
(5) assign a (4)
3.例如，语句X:=(A+B)*C;
Y:=D↑(A+B)的间接三元式表示如右图间接代码
(2)
(3)
三元式表
OP ARG1
ARG2
(1) + A B
(2) * (1) C
(3) := X (2)
4．表达式-a+b*c+d+(e*f)/d*e，如果优先级由高到低依次为-、+、*、/，且均为左结合，则其后缀式为a-b+cd+ef*+*de*/
5.如果优先级由高到低依次为-、+、*、$（乘幂），且均为右结合，则表达式2+3-2+2*2*1$2$3-3-2+1的后缀式为232-2++21**2332--1+$$
6.如果某表达式的后缀式为ab+cd+*，则其中缀形式的表达式为(a+b) * (c+d)
7.请将表达式-(a+b)*(c+d)-(a+b)分别表示成三元式、间接三元式和四元式序列
解：
三元式间接三元式
(1) (+ a, b) 间接三元式序列间接码表
(2) (+ c, d) (1) (+ a, b)(1)
(3) (* (1), (2)) (2) (+ c, d)(2)
(4) (- (3), /) (3) (* (1), (2))(3)
(5) (+ a, b) (4) (- (3), /) (4)
(6) (- (4), (5)) (5) (- (4), (1))(1)
（5）
四元式
(1) (+, a, b, t1) (2) (+, c, d, t2)
(3) (*, t1, t2, t3) (4) (-, t3, /, t4)
(5) (+, a, b, t5)(6) (-, t4, t5, t6)
必考题：构造一个DFA，它接收Σ={a,b}上所有满足下述条件的字符串：字符串中的每个a 都有至少有一个b直接跟在其右边。
解：由题意可得其正规式为（b*abb*）*,画出相应的DFM.
仅供参考,如有什么不对的地方尽请谅解
编译原理考试题及答案汇总一、选择 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.编译程序的步骤和任务： 1）词法分析：从左到右一个字符一个字符地读入源程序，对构成源程序的字符流进行扫描和分解，从而识别出一个个单词。 2）语法分析：是在词法分析基础上将单词序列分解成各类语法短语(比如程序、语句、表达式等），通过语法分析确定整个输入串是否构成一个语法上正确的程序。 3）语义分析：是审查源程序有无语义错误，为代码生成阶段收集类型信息。 4）中间代码产生：将源程序变成一种易于翻译成目标代码的内部表示形式。 5）代码优化：对前阶段生成的中间代码进行变换或改造，使生成的目标代码更为高效6）目标代码生成：把中间代码变换成特定机器上的绝对指令代码或可重定位的指令代码或汇编指令代码。 2.前端和后端的概念，试问前端通常包括那些阶段，后端包括那些阶段？ 答：前端只依赖于源语言，与目标机无关。编译程序的前端通常包括词法分析程序、语法分析程序、语义分析程序、中间代码生成程序及相关的表格管理程序和出错处理程序。后端是指编译器中依赖于目标机器的部分,只与中间代码有关。通常包括目标代码生成程序、代码优化程序以及相关的表格管理程序和出错处理程序。 遍（PASS)：对输入文件（源程序或其等价的中间语言程序）从头到尾扫视，完成预定处理的过程。 一个多遍的编译程序较之一遍的编译程序可能少占内存，逻辑结构可能清晰些，但效率相对可能差点 3.程序的正确与否：结构上的语法规则，语义上的语义规则。 翻译程序：汇编，解释，编译。 4.解释程序及其与编译程序的比较 解释程序功能：源程序+初始数据=计算结果 解释与编译的区别： 工作模式：这是根本区别，编译把源程序翻译成目标代码，而解释直接得到计算结果，不生成目标代码。 存储区内容：编译方式翻译和执行分开，解释方式翻译和执行同时并允许修改源程序，因此二者存储组织不同。 效率：解释慢于编译，很多语言两种方式都有。 标识符：=表达式 第三章：文法和语言 1.文法的直观概念：一组判定规则。 在实践中，文法不包含多余产生式。 2.文法G定义为四元组（VT，VN ,S, P ），其中： VT是一个非空有穷终结符号集合； VN是一个非空有穷的非终结符号集合，且VT∩VN＝Φ； P是一个产生式的非空有穷集合（注意：产生式左部至少含有一个非终结符）； S VN ，称为开始符号，且S至少必须在某个产生式的左部出现一次。 通常用V表示VN∪ VT,V称为文法G的字母表或字汇表. 3.句型、句子：设文法G，如果符号串x是从识别符号推导出来的，即S→x,x∈V*，则称x 是一个句型。仅含终结符号的句型是一个句子。 4.语言：语言 L(G）是由文法G产生的所有句子所组成的集合。 5文法的类型：逐渐对产生式施加限制四种类型：0型，1型，2型，3型
一、填空题|（每题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)
翻译程序:把一种语言程序转换成另一种语言程序，且在功能上是相同的这样的程序。 编译程序：把高级语言转换成低级语言，且在功能上是相同的这样的程序。 解释程序：边解释边执行源程序的程序。区别：编译程序有中间代码，而解释程序没有。编译过程的五个阶段： 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分，共10分； 二、单选题：每题2分，共20分； 三、应用题：每小题6分，共48分； 四、综合分析题：每小题11分，共22分。 【知识点】 1.编译程序的整个过程从逻辑上依次分为哪6个阶段，其中还涉及哪2个重要工作。 2.语法分析有哪两大类方法？ 3.编译程序和解释程序的概念，二者最主要的区别是？ 4.句柄的定义。 5.什么是规范推导？ 6.语言、句型、句子的定义。 7.LR分析法中的项目类型定义（待约项目、移入项目、归约项目）。 8.中间代码和目标代码区别。 9.文法与正则表达式所描述的语言及句子。 10.如何判断自动机（状态转换图）所能识别的字符串。 11.中间代码生成时主要依据什么规则？ 12.根据给定文法，通过推导，画出指定句子的语法树。
13.自底向上的语法分析过程中，构造LR分析表时可能会面临的两种冲突。 14.判断源程序中出现的某类错误可能在编译的哪个阶段被发现。 15.词法分析及语法分析的输入输出是什么？ 16.0、1、2、3型文法的定义、别名及描述能力强弱排名。 17.证明给定文法是二义性的（参考第二章课后练习）。 18.消除文法的左递归及提取公共左因子。 19.给定一个文法和该文法的句型，要求写出句型的最左推导、画出语法分析树、指出短语、简单短 语、句柄（参考第二章课后练习及课件中的例题）。 20.根据有限自动机的定义（五元组），给出其状态转换矩阵和状态转换图。 21.画出按照给定翻译模式分析某句子时所产生的分析树，分析其输出结果（参考第六章课后练习及 课件中的例题）。 22.针对给定的语言构造一个文法G，然后判断该文法类型（0、1、2、3型）（参考第二章课后练习）。 23.根据有限自动机M的定义（五元组），画出M的状态转换图，并说明它所识别或接受的语言是 什么（参考课件第三章例题）。 24.给出一个复合表达式，写出该表达式的三元式和四元式（如：-a*(b+c)/d）。 25.判断某语法制导定义在给定输入下的输出结果，分析文法产生的语言，指出语法制导定义功能。 26.已知文法及其LR分析表，给出对该文法某个句子的分析过程。（参考例题及习题） 27.给定一个文法，消除其左递归和提取左公因子，求所有非终结符的FIRST和FOLLOW集，构造 该文法的LL(1)分析表，根据分析表给出某句子的分析过程（参考第四章课后练习）。
编译原理期末复习 鉴于编译原理马上就要期末考试，我将手中集中的一些资料上的题目进行了整理归类，每种类型题目给出了所涉及到的基本知识，然后对每类题目中的第一道例题进行了做法进行了讲解，剩下的例题请给大家作为练习，答案也都给出，希望对大家复习有所帮助，最后由于时间很紧，整理的有些仓促，整理中难免有遗漏或错误，请大家见谅。 注：下面出现的字母中，若无特别说明，小写英文字母为终结符，大写英文字母为非终结符，希腊字母为终结符与非终结符的任意组合。 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：产生式集合(有限)。
编译原理的复习提纲 1.编译原理=形式语言+编译技术 2.汇编程序： 把汇编语言程序翻译成等价的机器语言程序 3.编译程序： 把高级语言程序翻译成等价的低级语言程序 4.解释执行方式： 解释程序，逐个语句地模拟执行 翻译执行方式： 翻译程序，把程序设计语言程序翻译成等价的目标程序 5.计算机程序的编译过程类似，一般分为五个阶段： 词法分析、语法分析、语义分析及中间代码生成、代码优化、目标代码生成 词法分析的任务： 扫描源程序的字符串，识别出的最小的语法单位（标识符或无正负号数等） 语法分析是： 在词法分析的基础上的，语法分析不考虑语义。语法分析读入词法分析程序识别出的符号，根据给定的语法规则，识别出各个语法结构。 语义分析的任务是检查程序语义的正确性，解释程序结构的含义，语义分析包括检查变量是否有定义，变量在使用前是否具有值，数值是否溢出等。
语法分析完成之后，编译程序通常就依据语言的语义规则，利用语法制导技术把源程序翻译成某种中间代码。所谓中间代码是一种定义明确、便于处理、独立于计算机硬件的记号系统，可以认为是一种抽象机的程序 代码优化的主要任务是对前一阶段产生的中间代码进行等价变换，以便产生速度快、空间小的目标代码 编译的最后一个阶段是目标代码生成，其主要任务是把中间代码翻译成特定的机器指令或汇编程序 编译程序结构包括五个基本功能模块和两个辅助模块 6.编译划分成前端和后端。 编译前端的工作包括词法分析、语法分析、语义分析。编译前端只依赖于源程序，独立于目标计算机。前端进行分析 编译后端的工作主要是目标代码的生成和优化后端进行综合。独立于源程序，完全依赖于目标机器和中间代码。 把编译程序分为前端和后端的优点是： 可以优化配置不同的编译程序组合，实现编译重用，保持语言与机器的独立性。 7.汇编器把汇编语言代码翻译成一个特定的机器指令序列 第二章 1.符号，字母表，符号串，符号串的长度计算P18，子符号串的含义，符号串的简单运算XY，Xn， 2.符号串集合的概念，符号串集合的乘积运算，方幂运算，闭包与正闭包的概念P19，P20A0 ={ε} 3.重写规则，简称规则。非xx（V
第八节习题一、单项选择题 1、将编译程序分成若干个“遍”是为了 b 。 a．提高程序的执行效率 b．使程序的结构更加清晰 c．利用有限的机器内存并提高机器的执行效率 d．利用有限的机器内存但降低了机器的执行效率 2、构造编译程序应掌握 d 。 a．源程序b．目标语言 c．编译方法d．以上三项都是 3、变量应当 c 。 a．持有左值b．持有右值 c．既持有左值又持有右值d．既不持有左值也不持有右值 4、编译程序绝大多数时间花在 b 上。 a．出错处理b．词法分析 c．目标代码生成d．管理表格 5、 d 不可能是目标代码。 a．汇编指令代码b．可重定位指令代码 c．绝对指令代码d．中间代码 6、使用 a 可以定义一个程序的意义。 a．语义规则b．词法规则 c．产生规则d．词法规则 7、词法分析器的输入是 a 。 a．单词符号串b．源程序 c．语法单位d．目标程序 8、中间代码生成时所遵循的是- d 。 a．语法规则b．词法规则 c．语义规则d．等价变换规则 9、编译程序是对 d 。 a．汇编程序的翻译b．高级语言程序的解释执行 c．机器语言的执行d．高级语言的翻译 10、语法分析应遵循 b 。 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 二、多项选择题
《编译原理》总复习-07级 第一章编译程序的概述 （一）内容 本章介绍编译程序在计算机科学中的地位和作用，介绍编译技术的发展历史，讲解编译程序、解释程序的基本概念，概述编译过程，介绍编译程序的逻辑结构和编译程序的组织形式等。 （二）本章重点 编译（程序），解释（程序），编译程序的逻辑结构。 （三）本章难点 编译程序的生成。 （四）本章考点 全部基本概念。 编译程序的逻辑结构。 （五）学习指导 引论部分主要是解释什么是编译程序以及编译的总体过程。因此学习时要对以下几个点进行重点学习：翻译、编译、目标语言和源语言这几个概念的理解；编译的总体过程：词法分析，语法分析、语义分析与中间代码的生成、代码优化、目标代码的生成，以及伴随着整个过程的表格管理与出错处理。 第三章文法和语言课外训练 （一）内容 本章是编译原理课程的理论基础，主要介绍与课程相关的形式语言的基本概念，包括符号串的基本概念和术语、文法和语言的形式定义、推导与归约、句子和句型、语法分析树和二义性文法等定义、文法和语言的Chomsky分类。 （二）本章重点 上下文无关文法，推导，句子和句型，文法生成的语言，语法分析树和二义性文法。（三）本章难点 上下文无关文法，语法分析树，文法的分类。 （四）本章考点 上下文无关文法的定义。 符号串的推导。 语法分析树的构造。 （五）学习指导 要构造编译程序，就要把源语言用某种方式进行定义和描述。学习高级语言的语法描述是学习编译原理的基础。上下文无关文法及语法树是本章学习的重点。语法与语义的概念；程序的在逻辑上的层次结构；文法的定义，文法是一个四元组：终结符号集，非终结符号集，开始符号、产生式集；与文法相关的概念，字符，正则闭包，积（连接），或，空集，产生式，推导，直接推导，句子，句型，语言，最左推导，最右推导（规范推导）；学会用文法来描述语言及通过文法能分析该文法所描述的语言；语法树及二义性的概念、能通过画语法树来分析一个文法描述的语言是否具有二义性；上下文无关文法的定义和正规文法的定义，能判断一个语言的文法是哪一类文法。 附训练试题：
《编译原理》期末考试复习题 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） ×1．计算机高级语言翻译成低级语言只有解释一种方式。() ×2．在编译中进行语法检查的目的是为了发现程序中所有错误。() √3．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。 () ×4．正则文法其产生式为 A->a ， A->Bb, A,B∈VN ， a 、b∈VT 。 () √5．每个文法都能改写为 LL(1) 文法。 () √6．递归下降法允许任一非终极符是直接左递归的。 () ×7．算符优先关系表不一定存在对应的优先函数。 () ×8．自底而上语法分析方法的主要问题是候选式的选择。 () ×9．LR 法是自顶向下语法分析方法。 () ×10．简单优先文法允许任意两个产生式具有相同右部。 () 三、填空题(每空1分，共10分) 1．编译程序的工作过程一般可以划分为词法分析,语法分析,语义分析,中间代码生成,代码优化等几个基本阶段,同时还会伴有__ ___和 ___ _。 表格管理出错处理_ 2．若源程序是用高级语言编写的,__ __是机器语言程序或汇编程序,则其翻译程序称为 __ __ 。 _目标程序_编译程序 3．编译方式与解释方式的根本区别在于__ __。 是否生成目标代码_ 4．对编译程序而言,输入数据是__ __, 输出结果是__ ___。 _源程序目标程序
5．产生式是用于定义__ __的一种书写规则。 _语法成分 6．语法分析最常用的两类方法是___ __和__ __分析法。 自上而下_自下而上 四、简答题（20分） 1. 什么是句子？什么是语言 ? 答：(1)设G是一个给定的文法，S是文法的开始符号，如果S x(其中x∈VT*),则称x是文法的一个句子。 (2)设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为：L(G)＝{x│S x,x∈VT*} 。 一、是非题（请在括号内，正确的划√，错误的划×）（每个2分，共20分） ×1．对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。() ×2．甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同。() √3．递归下降分析法是自顶向上分析方法。() ×4．产生式是用于定义词法成分的一种书写规则。() √5．LR 法是自顶向下语法分析方法。() √6．在SLR （1 ）分析法的名称中，S的含义是简单的。() ×7．综合属性是用于“ 自上而下” 传递信息。() ×8．符号表中的信息栏中登记了每个名字的属性和特征等有关信息，如类型、种属、所占单元大小、地址等等。() ×9．程序语言的语言处理程序是一种应用软件。() ×10．解释程序适用于COBOL 和FORTRAN 语言。() 三、填空题(每空1分，共10分) 1．一个句型中的最左简单短语称为该句型的___句柄__。
一、填空题（每空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
一、简答题 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 A.提高程序的执行效率 B.使程序的结构更加清晰 C.利用有限的机器内存并提高机器的执行效率 D.利用有限的机器内存但降低了机器的执行效率 2、构造编译程序应掌握（）。D A.源程序 B.目标语言 C.编译方法 D.以上三项都是 3、变量应当（）。C A.持有左值 B.持有右值 C.既持有左值又持有右值 D.既不持有左值也不持有右值 4、编译程序绝大多数时间花在（）上。D A.出错处理 B.词法分析 C.目标代码生成 D.管理表格 5、（）不可能是目标代码。D A.汇编指令代码 B.可重定位指令代码
C.绝对指令代码 D.中间代码 6、编译程序是对（）。D A.汇编程序的翻译 B.高级语言程序的解释执行 C.机器语言的执行 D.高级语言的翻译 7、正规式M1和M2等价是指（）。C A.M1和M2的状态数相等和M2的有象弧条数相等 和M2所识别的语言集相等和M2状态数和有象弧条数相等 8、如果文法G是无二义的，则它的任何句子（）。A A.最左推导和最右推导对应的语法树必定相同。 B.最左推导和最右推导对应的语法树可能相同。 C.最左推导和最右推导必定相同。 D.可能存在两个不同的最左推导，但它们对应的语法树相同。 9、文法G：S→S+T|T T→T*P|P P→(S)|i 句型P+T+i的短语有（）B A.i，P+T B. P，P+T，i，P+T +i +T + i D. P，P+T，i
10、产生正规语言的文法为（）。D 型型型型 11、文法G：S→b|?|(T) T→T?S|S 则FIRSTVT(T)=() C A.{b，?，(} B.{b，?，)} C.{b，?，(，?} D.{b，?，)，?} 12、给定文法：A→bA | cc，下面的符号串中，为该文法句子的是（）。A cc bcbc bcbcc ④bccbcc ⑤bbbcc 可选项有： A. B.④⑤ C.④ D.④⑤ 13、采用自上而下分析，必须（）。C A.消除左递归 B.消除右递归 C.消除回溯 D.提取公共左因子 14、由文法的开始符经0步或多步推导产生的文法符号序列是（）。C A.短语 B.句柄 C.句型 D.句子 15、后缀式ab+cd+/可用表达式（）来表示。B
编译原理学习心得 编译原理学习心得1 编译程序在计算机科学与技术的发展历史中发挥了巨大作用，是计算机系统的核心支撑软件。而“编译原理”这门课程一直以来是国内外大学计算机相关专业的重要课程。因为它的知识结构贯穿程序设计语言、系统环境以及体系结构，能以相对的视角体现从软件到硬件以及软硬件协同的整机概念。其理论基础又涉及形式语言与自动机、数据结构与算法等计算机学科的许多重要方面，为联系计算机科学理论和计算机系统的典范。 虽然编译原理这门课程在大多数的人里认为枯燥无味，学起来就像看天书一样。然而学习这门课程还是有一定的好处的。比如可以更加容易的理解在一个语言种哪些写法是等价的，哪些是有差异的，可以更加客观的比较不同语言的差异，并且学习新的语言的效率也会更加高，语言转换也会更加游刃有余。 不学“编译原理”这门课程的话，自己的编程思想会很浅显。而且编程也只仅仅停留在编程上，无法深入理解其中的原理。 学习编译原理的话，从文法、正规式、NFA与DFA的定义，下手，要用心动脑去体会 编译原理学习心得2
从联系最紧密的操作系统来说吧，你写多线程/多进程的程序就得和操作系统的知识打交道。写多线程得加锁吧，临界区、死锁的四个条件之类的标准的操作系统的内容吧(不得不吐槽一下，某国内一线电商干了三年的程序猿，写多线程居然不知道加锁，也是醉了)。进程间通信的几种方式什么管道、socket、共享内存等，这也是操作系统的内容吧。文件系统，这也是经常要打交道的东西。还有内存什么的，你做Android 开发，这些里边有很多东西都在系统层面被封装好了，但是你要是不知道原理，一旦出了错根本无从调试，况且你该不会打算写一辈子写Android 就是填逻辑吧。 然后，是编译原理，普通的程序猿是接触不到编译器或者虚拟机的开发的。但是这并不意味着编译原理就用不到。说个最常见的读取配置文件，只要你的配置文件有自定义的语法，你就要用编译原理的东西。还有类似于自动生成代码啦、正则表达式啦这些都算是编译原理的内容。你既然是写Java 的不了解虚拟机怎么可以，最基本的字节码总是需要能看懂的吧，分析一些疑难杂症的时候字节码还是很有用的。 最后，是计算机原理，如果只是做应用开发的话计算机原理其实不必要掌握的多深入，但是一些基本的概念还是要清楚的。比如寄存器、缓存、中断什么的，关键的时候可以帮助你调试。在一些对性能要求非常高的场合，也是很有作用的。此外，学了
选择： 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．运行时间短且占用存储空间小
一、简答题 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.语言概念：语言是人类所特有的用来表达意思、交流思想的工具，是一种特殊的社会现象，由语 音、词汇、语法、语义构成一个系统。语言包括口语和书面形式。 课本P1：语言是人们交流思想的工具，人们通过语言来描述事物，表达自己思想。 2.语言的分类及各类特点 自然语言:人与人之间交流信息的一种语言。动物之间通过动物语言交流信息。 数理语言：以数理逻辑、集合论和统计数学来描述的一种语言。 例如，用计算机进行几何定理的证明就得以数理语言形式进行描述。 程序设计语言：是人和计算机进行信息交流的一种语言，它遵循一定的语法和语义的规则，而编 译程序的功能正是：○1讨论语法，检查程序正确性○2讨论语义，生成目标代码 程序设计语言的分类及特点： 1)机器语言(第一代语言)：由机器指令构成的语言称机器语言，即用二进制编码组成。（如 01110101） 特点：○1费时费事○2难懂容易错○3只能在一种型号计算机上运行○4可以直接在计算 机上运行 2)汇编语言(第二代语言:50年代初期出现)：用容易记忆的符号来代替机器指令中操作码和 地址码的一种语言.（如:ADD 代表“+” SUB代表“-” MOV代表“传递”） 特点：优点——(1)程序直观容易阅读；(2)编程工作量相对小； 缺点——(1)只能在一种型号机器上运行；(2)不能直接在计算机上运行。 3)高级程序设计语言(第三代语言:50年代中期提出)：高级程序设计语言是一种面向过程 或者面向对象的语言，不面向机器，用一些符号或者数字对求解的问题或者现实世界进行描述。 特点：a) 直观、易写、易读、工作量小 b) 不依赖于具体的机器 c) 便于程序交流 d) 不可直接在计算机上运行，经编译程序编译成机器语言后方可运行 4)超高级程序设计语言(第四代语言):只需指出所求问题、输入数据及输出形式，就能得到 输出结果，无需对算法和计算过程描述的语言。 特点:a) 语言功能强，效率高，使用方便； b) 开发应用系统修改方便、维护容易； c) 系统复杂，不但要编译还要生成程序。 3.三种翻译程序的定义 解释程序：将高级语言写的源程序作为输入数据，但并不产生目标程序，而是边解释边执行源程序 本身的一种程序。 编译程序：是将高级语言写的源程序翻译成目标语言（汇编语言、机器语言）的程序。这种翻译过程 称为编译。 编译系统：目标程序，再加上运行系统（如服务子程序、动态分配程序、装配程序等）就可获得计算 结果，整个系统称为编译系统。 汇编程序：把汇编语言写的源程序翻译成机器语言的目标程序，这个翻译过程称为汇编。 4.编译基本过程 编译过程基本包括以下几个步骤：1.词法分析 2.语法分析 3.语义分析 4.中间代码生成 5.修饰优 化 6.生成目标程序
考试题型：填空24%简答4*4=16%+解答4*15=6 Chapter 1 重要概念 1?什么编译程序？P3 答：编译程序的主要功能是把用高级语言编写的源程序翻译为等 价的目标程序。 2. 编译程序的工作过程？（6个阶段）P4 1、词法分析程序2、语法分析程序3、语义分析程序4、中间代码生成5、代码优化程序6、目标代码生成 （不做优化是4个阶段，5、6不要） 4. 执行高级语言编写的程序：（编译执行、解释执行） 1）按编译方式在计算机上执行用高级语言编写的程序，一般须 经过两个阶段。第一个阶段称为编译阶段，其任务是由编译程序将源程序编译为目标程序，若目标程序不是机器代码，而是汇编语言程序，则尚需汇编程序再行汇编为机器代码程序；第二阶段称为运行阶段，其任务是在目标计算机上执行编译阶段所得到的
目标程序。 2）用高级语言编写的程序也可以通过解释程序来执行。解释程序也以源程序作为它的输入，它与编译程序的主要区别是在解释程序的执行过程中不产生目标程序，而是解释执行源程序本身。缺点：这种边翻译边执行的方式工作效率很低，但由于解释程序 的结构比编译程序简单，且占用内存较少，在执行过程中也易于在源程序一级对程序进行修改，因此一些规模较小的语言，如BASIC,也常采用此种方式。 5. P11第一段 编译程序的各部分之间的关系，是指他们之间的逻辑关系，而不一定是执行时间上的先后顺序，事实上，可按不同的执行流程来组织上述各部分的工作，这在很大程度上依赖与编译过程中对源程序扫描的遍数，以及如何划分各遍扫描所进行的工作。此处所说的“遍”，是指对源程序或其内部表示从头到尾扫视一次，并进行有关的加工处理工作。 （执行过程：单遍扫描、多遍扫描（大多数）） Chapter 2前后文无关文法和语言 1. 文法和语言的形式定义 产生语言就是制定出有限个规则（文法），借助于它们，就能产生出此语言的全部句子。 2. 文法规则四要素: