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所接受
对于∑*中的任何字α，若存在一条从初态到某一终态的通路，且这条通路上所有弧的标
b
S
U
V
Q
a
b
b
a
,
b
a 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, # }
a b d e#
S S→RT S→RT S→RT S→eT
T T→DR T→DRε
RεεT→DRε
D D→a D→bd
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) ={ *, +, ), #}
i + * ( ) #
E E→TE'E→TE'
E'E'→+TE'E'→εE'→ε
T T→FT'T→FT'
T'T'→εT'→*FT'T'→εT'→ε
F F→i F→(E)
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)的间接三元式表示如右图间接代码
(1)
(2)
(3)
(1)
(4)
(5)
三元式表
OP ARG1
ARG2
(1) + A B
(2) * (1) C
(3) := X (2)
(4) ↑ D (1)
(5) := Y (4)
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一个最小有限状态自动机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．目标代码生成
编译原理期末总结复习 编译原理期末总结复习 篇一： 一、简答题 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.词法分析阶段的功能是什么？ 答： 逐个读入源程序字符并按照构词规则切分成一系列单词 任务：读入源程序，输出单词符号 —滤掉空格，跳过注释、换行符 —追踪换行标志，指出源程序出错的行列位置 —宏展开，…… 10.什么是符号表？ 答：符号表在编译程序工作的过程中需要不断收集、记录和使用源程序中一些语法符号 的类型和特征等相关信息。这些信息一般以表格形式存储于系统
《编译原理》课程复习 五、计算题： 1、考虑下面程序 ………… Var a：integer； Procedure S(X)； Var X：integer； Begin a：＝a＋1； X：＝a＋X End； Begin a：＝5； S(a)； Print(a) End． 试问：若参数传递方式分别采取传名和传值时，程序执行后输出a的值是什么？ 答：传名：a＝12 传值：a＝6 2、写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。 逆波兰表示： abc*＋ab＋/d－ 三元式序列： ①(*，b，c) ②(＋，a，①) ③(＋，a，b) ④(/，②，③) ⑤(－，④，d) 3、已知文法G(S) S→a|∧|(T) T→T，S|S 写出句子((a，a)，a)的规范归约过程及每一步的句柄。 句型归约规则句柄 ((a，a)，a)S→a a ((S，a)，a)T→S S ((T，a)，a)S→a a ((T，S)，a)T→T，S T，S ((S)，a)T→S S ((T)，a)S→S(T)(T) (S，a)T→S S (T，a)S→a a
(T，S)T→T，S T，S (T)S→(T)(T) S 4、写一个文法，使其语言是奇数集，且每个奇数不以0开头。 解：文法G(N)： N→AB|B A→AC|D B→1|3|5|7|9 D→B|2|4|6|8 C→0|D 5、设文法G(S)： S→(L)|a S|a L→L，S|S (1) 消除左递归和回溯； (2) 计算每个非终结符的FIRST和FOLLOW； (3) 构造预测分析表。 解：S→(L)|aS’ S’→S|ε L→SL’ L’→SL’|ε FIRST)S)＝{(，a}FOLLOW(S)＝{#，，，)} FIRST(S’)＝{，a,ε}FOLLOW(S’)＝{#，，，)} FIRST(L)＝{(，a}FOLLOW(L)＝{ )} FIRST(L’)＝{，，ε}FOLLOW(L’)＝{ }} 6、While a＞0 ∨b＜0do Begin X：＝X＋1； if a＞0 then a：＝a－1 else b：＝b＋1 End； 翻译成四元式序列。 解： (1) (j＞，a，0，5) (2) (j，－，－，3) (3) (j＜，b，0，5) (4) (j，－，－，15) (5) (＋，×，1，T1) (6) (：＝，T1，－，×) (7) (j＞，a，0，9) (8) (j，－，－，12) (9) (－，a，1，T2) (10) (：＝，T2，－，a) (11) (j，－，－，1) (12) (＋，b，1，T3)
1》编译程序的框架图与功能块：（1）画出编译程序的总体结构，并简述各部分的主要功能：七个部分（2）编译程序的结构分为几个阶段，各阶段的任务是什么？ 答 编译程序总框架 （1）词法分析器，又称扫描器，输入源程序，进行词法分析，输出单词符号。 （2）语法分析器，简称分析器，对单词符号串进行语法分析（根据语法规则进行推导或规约），识别出各类语法单位，最终判断输入串是否构成语法上正确的“程序”。 （3）语义分析与中间代码产生器，按照语义规则对语法分析器归约出（或推导出）的语法单位进行语义分析并把它们翻译成一定形式的中间代码。 （4）优化器，对中间代码进行优化处理。 （5）目标代码生成器，把中间代码翻译成目标程序。 （6）表格管理，登记源程序的各类信息，编译各阶段的进展状况。 （7）出错管理，把错误信息报告给用户。 编译程序的结构分为五个阶段：（1）词法分析.任务是：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个的单词（亦称单词符号或简称符号），如基本字，标识符，常熟，算符和界符。 （2）。语法分析，任务是：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位（语法范畴）。 （3）语义分析与中间代码产生。任务：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。 （4）优化。任务在于对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。 （5）目标代码生成。任务是：把中间代码（或优化出理之后）变换成特定机械上的低级语言代码。 2》．重要概念： a. 编译程序：是指能够把源语言程序转换成逻辑上等价的目标语言程序的一个程序。 b. 单词符号：是语言的基本组成成分，是人们理解和编写程序的基本要素，是语言中具有独立意义的最基本结构，它一般包括：基本字、标识符、常数、运算符和界符等 c. 中间代码：是一种含义明确，便于处理的记号系统，它通常独立于具体的硬件。 d. 遍：就是对源程序或源程序的中间结果从头到尾扫描一次，并作有关的加工处理，生成新的中间结果或目标程序。
1.编译程序的工作过程一般可包括词法分析、语法分析、语义分析、中间代码产生与优化 和目标代码生成等几个阶段，同时还有表格管理和出错处理。 2.LEX是用于词法分析的工具，Y ACC是用于语法分析的工具。 3.解释程序和编译程序的区别在于是否生成目标代码。 4.任一文法终结符集合和非终结符集合的交集是空集。 5.描述程序设计语言语法的BNF方法中，“：：=”表示定义为，“|”表示或，[W]表示W 可出现0或1次，｛W｝表示W可出现n（n≥0）次。 6.已知文法G[G]: S→aSb|ab|ε，该文法描述的语言L(G)=｛a n b n|n≥0｝。 7.单词的描述工具有正规文法、正规式和有穷自动机，他们之间存在等价性。 8.高级程序设计语言的单词通常分为五类，它们是关键字、标识符、常数、运算符和界符。 9.正则式中的“|“表示或，“*”表示闭包。 10.自顶向下语法分析方法会遇到的主要问题有回溯，以及左递归带来的无限循环。 11.算符优先分析法每次归约当前句型的最左素短语，规范归约中每次归约的是当前句型的 句柄。 12.对文法G[G]: S→a|b|cTc，T→S|TdS而言，FIRSTVT(T)=｛a,b,c,d｝。 13.活前缀是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。 14.对文法G[G]: E→E*T|T, T→T+i|i的句子1+2*8+6进行归约后的结果为42（23，42）。 15.在LR(0),SLR(1),LR(1),LALR(1),四种文法中，描述能力最强的是LR(1)。 1.0型文法中每条规则左部至少包含一非终结符（√）。 2.3型文法一定是2型、1型、0型文法（√）。 3.对无二义性文法而言，无论最左推导还是最右推导，同一个句子的语法树是一样的。 4.若一个文法是递归的，则其语言中句子的个数必定是无穷个。（√） 5.文法规则右部的符号一定是终结符。（×） 6.语法树描述的是一个文法。（×） 7.若G是正则文法，则G一定是上下文无关文法。（√） 8.正则文法、正则式和有限自动机三者都是描述正则集的有力工具，它们的描述能力是等价的。（√） 9.LL（1）分析法必须要求原文法不含左公因子和左递归。（√） 10.对于LR(0)文法，我们可直接从它的项目集规范族和活前缀识别自动机的状态转换函数GO构造了LR分析表。（√） 1.BNF是一种广泛采用的描述（文法）的工具。 2.无符号常数的识别和拼数工作通常在（词法分析）阶段完成。 3.“运算符与运算对象类型不匹配”属于（语义错误） 4.将汇编语言程序翻译成机器可以执行的目标程序的工作由（汇编程序）完成。 5.在汇编过程中，汇编程序能够找到的错误包括（全部语法错误和部分语义错位） 6.由“非终结符→符号串”形式的规则构成的文法是（2型文法） 7.关于短语和句柄，正确的叙述为（直接短评才可能是句柄） 8.同正则式a*b*等价的文法是（G3:S→aS|Sb|ε） 9.文法G[S]:S→xSy|y所描述的语言是（x^nyx^n(n>=0)） 10.若G为一文法，Vt是该文法的终结符号集合，L(G)和Vt^*之间的关系是（L(G)是Vt^* 的子集） 11.有限自动机能够识别（正则文法）
复习汇总 一、第一章概述 1.文法与自动机的等价 1)0型文法—图灵机 2)1型文法—线性有界非确定图灵机 3)2型文法—非确定下推自动机 4)3型文法—有限状态自动机 2.编译技术的应用 1)语法制导的结构化编辑器 2)程序格式化工具 3)软件测试工具 4)程序理解工具 5)高级语言的翻译工具 6)等等 3.从面向机器的语言到面向人类的语言（结合第二章第9小点理解） 1)面向机器的语言：机器指令，汇编语言 2)面向人类的语言：通用程序设计语言，数据查询语言，形式化描述 语言（正规式,产生式）等等。 4.各语言的分类（结合第二章第9小点理解） 1)过程式语言，面向对象语言：通用程序设计语言。 2)函数语言：面向特点领域的，递归特性。例如LISP语言 3)说明性，非算法式语言：LEX/YACC,SQL。 4)脚本式语言：Shell语言 5.语言之间的转换（李静PPT41） 1)高级语言之间的转换一般称为预处理或转换。 2)高级语言翻译成汇编语言或机器语言称之为编译。 3)把汇编语言翻译成机器语言称之为汇编。 4)将一个汇编语言程序汇编为可在另一台机器上运行的机器指令称之
为交叉汇编。 5)把机器语言翻译成汇编语言称之为反汇编。 6)把汇编语言翻译成高级语言称之为反编译。 6.编译器和解释器 1)编译器 ●源程序的翻译和翻译后的程序的运行是两个不同的阶段。 ◆编译阶段：用户输入源程序，经过编译器的处理，生成目标 程序。 ◆目标程序的运行阶段：根据要求输入数据，得出结果。 2)解释器（凡是可以采用编译器的地方均可以采用解释器） ●解释器把翻译和运行结合到一起，编译一段源程序，紧接着就执 行它。这种方式称为解释。 7.解释器的优点（对比与编译器） 1)具有较好的动态特性。 2)具有较好的移植特性。 8.解释器的缺点（对比于编译器） 1)相比于编译器需花费大量的时间。 2)占用更多的内存空间。 9.编译器的工作阶段（结合第二章6小点红色部分理解） 1)源程序->词法分析器->语法分析器->语义分析器->中间代码生成器-> 代码优化器->目标代码生成器->目标代码 2)工作过程中的每个阶段均采用了符号表管理器，出错处理器。10.编译器各阶段的工作过程（结合第二章6小点红色部分理解） 1)源程序通过词法分析器翻译成记号流，记号流通过语法分析产生语 法树，然后根据语法树来进行适当的语义处理，语义分析产生符号 表和中间代码。 2)符号表的格式：标识符，类型，分配的地址。 3)中间代码的格式：操作符，左操作数，右操作数，结果。 4)中间代码的优化：传值的代码可以省略。
1、编译程序：是一种程序，它把用高级语言写的源程序作为数据接收，经过翻译转换产生 面向机器的代码作为输出。编译程序产生目标文件。 2、解释程序：是一种语言处理程序,它对源程序逐个语句地进行分析,根据每个语句的含义 执行语句指定的功能。广义上讲,编译程序和解释程序都属于翻译程序,但它们的翻译方式不同,解释程序是边翻译解释边执行不产生目标代码输出源程序的运行结果。而编译程序只负责把源程序翻译成目标程序输出与源程序等价的目标程序,而目标程序的执行任务由操作系统来完成即只翻译不执行。 3、解释程序：是一种程序，它的输入是某种语言的一系列语句，而他的输出则是另一种语 言的一系列语句。 4、源程序：源语言编写的程序称为源程序。 5、目标程序：目标语言书写的程序称为目标程序。 6、编译程序的前端： 机无关。通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段。某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。 7、后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目 标代码生成，以及相关出错处理和符号表操作。 8、遍：是对源程序或其等价的中间语言程序从头到尾扫视，并完成规定任务的过程，生成 新的中间结果或目标程序。第一遍：语法分析器处于核心地位。第二遍：局部优化。第三遍：全局优化。第四遍：目标代码生成。 9、一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？ 答案：一个典型的编译程序通常包含8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。其各部分的主要功能简述如下。 词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。 语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。 中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。 目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。 10、表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是造表、查表的工作过程。需要指出的是，这里的“表格管理程序”并不意味着它就是一个独立的表格管理模块，而是指编译程序具有的表格管理功能。 错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发现的错误进行适当的校正（修复），目的是使编译程序能够继续向下进行分析和处理。 10、二义性：如果对于某文法的一个句子存在两棵不同的语法树，则该句子是二义性的。而该文法是二义性文法。 11、文法定义：文法G定义为四元组（V N，V T，P，S）。 其中V N 为非终结符集；V T 为终结符；P为产生式集合，产生式左部是V N 和V T 的并集的元素且至少包含一个非终结符，产生式右部也是V N 和V T 并集的元素；V N、V T 和P是非空有
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
第一章： 编译过程的六个阶段：词法分析，语法分析，语义分析，中间代码生成， 代码优化，目标代码生成 解释程序：把某种语言的源程序转换成等价的另一种语言程序——目标语言程序，然后再执 行目标程序。解释方式是接受某高级语言的一个语句输入，进行解释并控制计算机执行，马上得到这句的执行结果，然后再接受下一句。 编译程序：就是指这样一种程序，通过它能够将用高级语言编写的源程序转换成与之在逻辑 上等价的低级语言形式的目标程序(机器语言程序或汇编语言程序)。 解释程序和编译程序的根本区别：是否生成目标代码 第三章： Chomsky 对文法中的规则施加不同限制，将文法和语言分为四大类： ） 0型文法（PSG ） 0型语言或短语结构语言 文法 Ｇ的每个产生式α→β中：若α∈Ｖ*ＶN Ｖ*, β∈(ＶN ∪ＶT)* ， 则 Ｇ是0型文法，即短语结构文法。 1型文法（CSG ） 1型语言或上下文有关语言 在0型文法的基础上：若产生式集合中所有|α|≤|β|，除Ｓ→ε(空串)外， 则Ｇ是１型文法,即：上下文有关文法 另一种定义： 文法G 的每一个产生式具有下列形式：αA δ→αβδ，其中α、δ∈V*，A ∈VN ，β∈V+； ( 2型文法（CFG ） 2型语言或上下文无关语言 文法Ｇ的每个产生式A →α，若A ∈ＶN ,α∈(ＶN ∪ＶT)*，则Ｇ是２型法，即：上下文无关文法。 3型文法（RG ） 3型语言或正则(正规)语言 若Ａ、Ｂ∈ＶN ，ａ∈ＶT 或 ， ' 右线性文法：若产生式为Ａ→ａＢ或Ａ→ａ 左线性文法：若产生式为 Ａ→Ｂａ或Ａ→ａ 都是３型文法（即：正规文法） 最左（最右）推导 在推导的任何一步α β，其中α、β是句型，都是对α中的最左（右）非终结符 进行替换 规范推导：即最右推导。 规范句型：由规范推导所得的句型。 } 句子的二义性（这里的二义性是指语法结构上的。） 文法G[S]的一个句子如果能找到两种不同的最左推导(或最右推导)，或者存在两棵不同的语法树，则称这个句子是二义性的。 文法的二义性 一个文法如果包含二义性的句子，则这个文法是二义文法，否则是无二义文法。 短语 若S * αA δ且 A +β，则称β是句型αβδ相对于非终结符A 的短语。 简单短语（直接短语） 2型文法 1型文法 0型文法 3型文
《编译原理》复习资料 1、编译程序的总体结构分为、、、和五部分。 2、构造一个编译程序的三要素是：_______________，_________________，____________________。 3、被编译的语言为A语言，编译的最终结果为B语言代码，编写编译程序的语言为C语言。那么，_______语言为源语言，_____语言为宿主语言，_________语言为目标语言。 4、设文法G(S)： S→aS|Sb|a|b，则文法G(S)所识别语言的正规式为_________________________。 5、设有文法G(S)： S→Sab|bR R→S|a G(S)的语言L(G(S))={_____________________}。 6、设文法G[V]： V→aaV|bc 该文法所对应的语言L(G)=_________________。 7、C语言中表达式a + + + + + + + = 1，词法分析后，能识别出的单词个数是_______。 8、设有文法G（S为开始符号）： S→Ap|Bq A→a|cA B→b|dB FIRST(Ap)=｛_____________｝。 9、设有文法G[S]: S→AB|bb|bAC A→ε|b B→ε|aC C→aS|c 则FIRST(S)=｛_____________｝,FOLLOW(A)=｛___________｝。 10、一个LR分析器的逻辑结构包括_______________、________________和 __________________三部分。 11、被编译的程序成为_____________。 12、设字母表A=｛0｝，A*=｛____________________｝。 13、程序设计语言的单词符号一般分为：关键字、___________、___________、______________和界限符等。 14、设有文法G(S)： S→AB|bC A→ε|b B→ε|aD C→AD|b D→aS|c 则FOLLOW(A)={_____________________},FIRST(S)={_____________}。 15、设文法G[S]： S→Pab|bP P→b|ε
《编译原理》常见题型 一、填空题 1、编译程序的工作过程一般可以划分为词法分析，语法分析，语义分析，中间代码生成，目标代码生成等几个基本阶段。 2、若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。 3、编译方式与解释方式的根本区别在于是否生成目标代码。 5、对编译程序而言，输入数据是源程序，输出结果是目标程序。 7、若源程序是用高级语言编写的，目标程序是机器语言程序或汇编程序，则其翻译程序称为编译程序。 8、一个典型的编译程序中，不仅包括词法分析、语法分析、中间代码生成、代码优化、目标代码生成等五个部分，还应包括表格处理和出错处理。其中，词法分析器用于识别单词。 10、一个上下文无关文法所含四个组成部分是一组终结符号、一组非终结符号、一个开始符号、一组产生式。 12、产生式是用于定义语法成分的一种书写规则。 13、设G[S]是给定文法，则由文法G所定义的语言L(G)可描述为 L(G)＝{x│ S * ?x，x∈V T*} 。 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、在使用高级语言编程时，首先可通过编译程序发现源程序的全部语法错误
第一章引论 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} 从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 ε
《编译原理》复习题集 1．名词解释 短语 句柄 文法 上下文无关文法 LL（1）文法 LR（1）文法 语法分析 无环路有向图(DAG) 后缀式 语法制导翻译 遍 局部优化 词法分析 语法分析 语义分析 源语言 源程序 目标语言 中间语言（中间表示） 2．简答题 (1)编译程序和高级语言有什么区别? (2)编译程序的工作分为那几个阶段? (3)简述自下而上的分析方法。 (4)目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？ (5)何谓优化？按所涉及的程序范围可分为哪几级优化？ (6)简述代码优化的目的和意义。 3．叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图。 ( 1 | 01 )* 0* 4．Pascal语言无符号数的正规定义如下： num→digit+ (.digit+)? (E(+|-)? digit+)? 其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。5．画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。 6．用状态转换图表示接收(a|b)*aa的确定的有限自动机。 7．处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状
态转换图。 8．某操作系统下合法的文件名为 device:name.extension 其中第一部分（device:）和第三部分（.extension）可缺省，device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。 9．构造一个DFA，它接受∑={0, 1}上0和1的个数都是偶数的字符串。 10．设有非确定的有自限动机 NFA M=({A，B，C}，{0，1}，δ，{A}，{C})，其中：δ(A，0)={C} δ (A，1)={A，B} δ (B，1)={C} δ (C，1)={C}。请画出状态转换距阵和状态转换图。 11．设L⊆ {a,b,c}* 是满足下述条件的符号串构成的语言： (1)若出现a ，则其后至少紧跟两个c ； (2)若出现b ，其后至少紧跟一个c 。 试构造识别L 的最小化的DFA ，并给出描述L 的正规表达式。 12．写出字母表∑ = {a, b}上语言L = {w | w的最后两个字母是aa或bb}的正规式，并画出接受该语言的最简DFA。 13．有穷自动机M接受字母表∑＝{0,1}上所有满足下述条件的串：串中至少包含两个连续的0或两个连续的1。请写出与M等价的正规式。 14．有正规式b*abb*(abb*)* ， (1) 构造该正规式所对应的NFA(画出状态转换图) 。 (2) 将所求的NFA 确定化(画出确定化的状态转换图)。 (3) 将所求的NFA 最小化. (画出最小化后的状态转换图)。 15．求出下列文法所产生语言对应的正规式. S→bS|aA A→aA|bB B→aA|bC|b C→bS|aA 16．给出与下图的NFA等价的正规式。 17．把下面的NFA确定化。
1已知有限自动机如图 0.1 (1)以上状态转换图表示的语言有什么特征 (2)写出其正规式. (3)构造识别该语言的确定有限自动机DFA. ［答案］ (1)至少含有两个连续的1的0，1组合 ⑵(0 I 1)*11 (0 I 1)* ⑶ 0 1 A A AB AB A ABC ABC AC ABC AC AC ABC 重新命名，令AB为B、ABC为C、AC为D 0 1
DFA: 2.试构造与下列文法G[S]等价的无左递归文法G[S]: S—Sal Nb I c N—Sd I Ne I f ［答案］ S—Sa I Nb I c N—Ne I Sd I f 消除N—Ne I Sd I f左递归： N—SdN I fN '③ N —eN‘ I £④ 代入S—Sa I Nb I c： S—Sa I SdN b fN b c
消除S—Sa I SdN b I fN^ bl c 左递归: S—fN‘ bS'l cS ①
S'—aS' dN‘ bS' & ② 3．考虑下面文法G1: S—a IAI (T) T—T, S I S 消去G1 的左递归。然后对每一个终结符，写出不带回溯的递归子程序。 ［答案］ S—a IAI (T) T—ST' T,ST' I & Void match(token t) { if (lookahead==t) lookahead=nexttoken; else error( ); } void S( ) { if (lookahead=='a') match(‘a'); else if (lookahead==A ' match( ‘ ' else if (lookahead=='(') { match(‘(');
编译原理复习题及答案一、选择题 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)