3.2是非判断，对下面的陈述，正确的在陈述后的括号内写T，否则写F。
(1)有穷自动机接受的语言是正则语言。（）
(2)若r1和r2是Σ上的正规式，则r1|r2也是。（）
(3)设M是一个NFA，并且L(M)＝{x,y,z}，则M的状态数至少为4个。（）
(4)令Σ＝{a,b}，则Σ上所有以b为首的字构成的正规集的正规式为b*(a|b)*。（）
(5)对任何一个NFA M，都存在一个DFA M'，使得L(M')=L(M)。（）
(6)对一个右线性文法G，必存在一个左线性文法G'，使得L(G)=L(G')，反之亦然。（）
答案
(1) T (2) T (3) F
(4) F (5) T (6) T
3.3描述下列各正规表达式所表示的语言。
(1) 0(0|1)*0
(2) ((ε|0)1*)*
(3) (0|1)*0(0|1)(0|1)
(4) 0*10*10*10*
(5) (00|11)*((01|10)(00|11)*(01|10)(00|11)*)*
答案
(1) 以0开头并且以0结尾的，由0和1组成的符号串。
(2) {α|α∈{0,1}*}
(3) 由0和1组成的符号串，且从右边开始数第3位为0。
(4) 含3个1的由0和1组成的符号串。{α|α∈{0,1}+，且α中含有3个1 }
(5) {α|α∈{0,1}*,α中0和1为偶数}
3.4对于下列语言分别写出它们的正规表达式。
(1) 英文字母组成的所有符号串，要求符号串中顺序包含五个元音。
(2) 英文字母组成的所有符号串，要求符号串中的字母依照词典顺序排列。
(3) Σ={0,1}上的含偶数个1的所有串。
(4) Σ={0,1}上的含奇数个1的所有串。
(5) 具有偶数个0和奇数个1的有0和1组成的符号串的全体。
(6) 不包含子串011的由0和1组成的符号串的全体。
(7) 由0和1组成的符号串,把它看成二进制数，能被3整除的符号串的全体。
答案
(1) 令Letter表示除这五个元音外的其它字母。
((letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter))*
(2) A*B*....Z*
(3) (0|10*1)*
(4) (0|10*1)*1
(5) [分析]
设S是符合要求的串，|S|=2k+1 (k≥0）。
则S→S10|S21，|S1|=2k (k>0），|S2|=2k (k≥0）。
且S1是{0,1}上的串，含有奇数个0和奇数个1。
S2是{0,1}上的串，含有偶数个0和偶数个1。
考虑有一个自动机M1接受S1，那么自动机M1如下：
和L(M1)等价的正规表达式，即S1为：
((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*
类似的考虑有一个自动机M2接受S2，那么自动机M2如下：
和L(M2)等价的正规表达式，即S2为：
((00|11)|(01|10)(00|11)*(01|10))*
因此，S为：
((00|11)|(01|10)(00|11)*(01|10))*(01|10)(00|11)*0|
((00|11)|(01|10)(00|11)*(01|10))*1
(6)1*|1*0(0|10)*(1|ε)
(7)接受w的自动机如下：
对应的正规表达式：(1(01*0)1|0)*
3.6给出接受下列在字母表{0,1}上的语言的DFA。
(1) 所有以00结束的符号串的集合。
(2) 所有具有3个0的符号串的集合。
答案
(a) DFA M=({0，1}，{q0，q1，q2}，q0，{q2}，δ)
其中δ定义如下:
δ（q0，0）=q1δ（q0，1）=q0
δ（q1，0）=q2δ（q1，1）=q0
δ（q2，0）=q2δ（q2，1）=q0
(b)正则表达式: 1*01*01*01*
DFA M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，δ)
其中δ定义如下:
δ（q0，0）=q1δ（q0，1）=q0
δ（q1，0）=q2δ（q1，1）=q1
δ（q2，0）=q3δ（q2，1）=q2
δ（q3，1）=q3
3.7构造等价于下列正规表达式的有限自动机。
(1)10|（0|11）0*1
(2)((0|1)*|(11))*
答案
(1)DFA M=({0，1}，{q0，q1，q2，q3}，q0，{q3}，δ)
其中δ定义如下:
(2)δ（q0，0）=q1δ（q0，1）=q2
(3)δ（q1，0）=q1δ（q1，1）=q3
(4)δ（q2，0）=q3δ（q2，1）=q1
(5)
(6)(2) DFA M=({0，1}，{q0}，q0，{q0}，δ)
(7)其中δ定义如下:
(8)δ（q0，0）=q0δ（q0，1）=q0
(9)
3.8给定右线性文法G：
S->0S|1S|1A|0B
A->1C|1
B->0C|0
C->0C|1C|0|1
试求一个于G等价的左线性文法G'
3.9试对于下列正规表达式使用证明定理3。5的构造算法构造非确定的有限自动机。请给出每个自动机在处理输入符号串ababbab的过程中的动作序列。
(1) (a|b)*
(2) (a*|b*)*
(3) ((ε|a)b*)*
3.10转换练习3.9中的每个 NFA 为 DFA 。并给出每个DFA在处理输入符号串ababbab的过程中的动作序列。
3.11试把练习3.10中得到的DFA的状态给以最小化。
答案
(1),(2),(3)的DFA M相同，化简结果为：
(4)
3.12我们可以证明两个正规表达式是等价的，如果它们的最小状态DFA是相同的（除了状态的名字以外）。利用这一结论，请说明下列正规表达式都是等价的。
(1) (a|b)*
(2) (a*|b*)*
(3) ((ε|a)b*)*
答案
根据3.11的结果知这几个正规表达式是等价的。
3.13对于下列正规表达式构造最小状态的DFA。
(1) (a|b)*a(a|b)
(2) (a)b)*a(a|b)(a|b)
5．对如下文法：
G[S]：S → a b S | a a B | a d
B → b b B | b
分别给出句子abaabbb和ad的句柄
句子ad的语法分析树为：
句子abaabbb 的语法分析树为:
所以句子abaabbb 的句柄是b ；句子ad 的句柄是ad .
二、（10分）说明如下文法是否是LL （
1）文法，若不是，将其转换为LL （1）文法。最后给出该文法的
LL （1）分析表。 G [A]： A → B e
B → B b | a
文法中有左递归，不是LL(1)文法。 转换为 G ′ ： A → B e B → a B ′ B ′→b B ′ | λ Predict(A → B e) ={ a } Predict(B → a B ′) ={ a } Predict(B ′→b B ′) ={ b }
Predict(B ′→λ ) ={ e } LL(1)分析表:
4. 给出识别正则表达式(（a|bc）*d)+的NFA 。
5．已知文法G[S]：S → S；G│G
G → G(T)│ H
H → a │ (S)
T → T+S │ S
找出句型：a(T+S)；H；(S)的短语、简单短语和句柄。
短语: a, T+S, a(T+S) , H , a(T+S);H , (S)
简单短语：a , T+S , H , (S) 句柄是a .
6．已知文法G[S]为：
S→AB | bC A→b | λ
B→aD | λC→AD | b
D→aS | c
对其每一个非终级符求First集和Follow集。
First (S) = { b , a , λ }
First (A) = { b , λ }
First (B) = { a , λ }
First (C) = { b , a , c }
First (D) = { a , c }
Follow (S) = { # }
Follow (A) = { a , c , #}
Follow (B) = { # }
Follow (C) = { # }
Follow (D) = { # }
二、（10分）设有文法G[A]: A → iB*e
B → SB|ε
S → [eC]|.i
C → eC|ε
判定该文法是否为LL(1)文法？若是则给出它的LL(1)分析表，否则说明理由。
先计算各个产生式的Predict集：
Predict (A-> iB*e)={ i };
Predict (B-> SB) ={ [ , .}
Predict (B->ε ) ={ * }
Predict (S->[eC]) ={ [ }
Predict (S->. i) ={ . }
Predict (C-> eC) ={ e }
Predict (C->ε ) ={ ] }
因为Predict集没有冲突，所以是LL(1)文法。
LL(1)分析表如下：
1、证明下面文法是LL(1)的但不是SLR(1)文法
S→AaAb|BbBa A→εB→ε
解：对于产生式S→AaAb|BbBa 来说
FIRST(AaAb)∩FIRST(BbBa)={a}∩{b}=Φ而A，B∈V N仅有一条候选式。
因此，这个文法是LL(1)的。
下面构造这个文法的识别活前缀的DFA。
I0= {S'→·S, S→·AaAb, S→·BbBa, A→·, B→·}
I1= {S'→S·}
I2= {S→A·aAb}
I3= {S→B·bBa}
I4= {S→Aa·Ab, A→·}
I5= {S→Bb·Ba, B→·}
I6= {S→AaA·b}
I7= {S→BbB·a}
I8= {S→AaAb·}
I9= {S→BbBa·}
由于FOLLOW(A)=FOLLOW(B)={a, b}
因此项目集I0中存在归约－归约冲突。在I0状态下，当输入符号是a或是b时，不知用A→ε还是B→ε进行归约。故此文法不是SLR(1)的。但是，此文法是LR(1)的。
五、已知文法G[S]，其产生式如下：S→(L)|a L→L，S|S
从G[S]中消除左递归，并为之构造一个非递归预测分析器LL(1)分析表。请说明在句子(a，(a，a))上的分析器的动作。
（20分）解：将所给文法消除左递归得G'：S →(L)|a L →SL' L'→，SL' | ε
实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：根据文法G'有
FIRST(s) = { ( , a ) FOLLOW(S) = { } , ', ' , $ }
FIRST(L) = { ( , a ) FOLLOW(L) = { } } FIRST(L’) = { ', ' }FOLLOW(L’) = { } }
按以上结果，构造预测分析表M如下：
文法G’是LL(1)的，因为它的LL(1)分析表不含多重定义入口。
预测分析器对输入符号串(a, (a, a))做出的分析动作如下：
例5.3的文法G3[S] 为：
S→aA
S→d
A→bAS
A→ε
不难看出由定义5.3可得：
SELECT(S→aA)={a}
SELECT(S→d)={d}
SELECT(A→bAS)={b}
SELECT(A→ε)={a,d,# }
所以SELECT(S→aA)∩SELECT(S→d)={a}∩{d}=
SELECT(A→bAS)∩SELECT(A→ε)={b}∩{a,d,# }=
由定义5.4知例5.3文法是LL(1)文法，所以可用确定的自顶向下分析。
而对例5.5文法G5[S]为：
S→aAS
S→b
A→bA
A→ε
则SELECT(S→aAS)={a}
SELECT(S→b)={b}
SELECT(A→bA)={b}
SELECT(A→ε)={a,b}
所以SELECT(S→aAS)∩SELECT(S→b)={a}∩{b}=
SELECT(A→bA)∩SELECT(A→ε)={b}∩{a,b}≠
因此，例5.5文法不是LL(1)文法，因而也就不可能用确定的自顶向下
表达式文法为：
E→E+T|T
T→T*F|F
F→i|(E)
构造步骤：
(1)判断文法是否为LL(1)文法
4.5 已知文法G[S]，其产生式如下：S→(L)|a L→ L，S|S 从G[S]中消除左递归，并为之构造一个非递归预测分析器LL(1)分析表。请说明在句子(a，(a，a))上的分析器的动作。
解：将所给文法消除左递归得G'：S →(L)|a L → SL' L'→ ，SL' | ε
实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合控制，下面构造预测分析表：
根据文法G'有
FIRST(s) = { ( , a )FOLLOW(S) = { ) , ', ' , $ }
FIRST(L) = { ( , a )FOLLOW(L) = { ) }
FIRST(L’) = { ', ' }FOLLOW(L’) = { ) }
按以上结果，构造预测分析表M如下：
文法G’是LL(1)的，因为它的LL(1)分析表不含多重定义入口。预测分析器对输入符号串(a,
(a, a))做出的分析动作如下：
4.6 对于练习4.1的文法，构造它的LL(1)分析表。
解：从练习4.1得到文法的产生式如下：R → R '|' T | T T → TF | F
F → F* | C C → (R)| a | b
①消除上面文法中的左递归
R → TR' R' → '|' TR' | ε
T → FT' T' → FT' | ε
F → CF' F → *F' | ε
C → (R) | a | b
②计算FIRST(α)和FOLLOW(A)
③构造LL(1)分析表。
4.9 对于文法G[S]，其产生式如下S→(L)|a (4.22)L→L,S|S
(1)给出句子(a，((a，a)，(a，a)))的一个最右推导，并指出右句型的句柄。
(2)按照(a)的最右推导，说明移进-归约分析器的工作步骤。
解：(1) S =>(L)=>(L, S)=>(L,(L))=>(L,(L,S))=>(L,(L,(L)))=>(L,(L,(L,S))) =>(L,(L,(L,a)))=>(L,(L,(S,a)))=>(L,(L,(a,a)))=>(L,(S,(a,a)))
=>(L,((L),(a,a)))=>(L,((L,S),(a,a)))=>(L,((L,a),(a,a)))=>(L,((S,a),(a,a)))
=>(L,((a,a),(a,a)))=>(S,((a,a),(a,a)))=>(a,((a,a),(a,a)))
右句型的句柄为每个右句型中用下划线标识出的部分。
(2) 对于(a)的最右推导，移进－规约分析器的工作步骤如下：
4.11 下列文法是否为SLR(1)文法？若是，请构造相应的分析表。若不是，请说明理由。
(a)S→Sab|bR R→S|a
解：该文法的拓广文法G'为
(0) S' → S(1) S → Sab
(2) S → bR(3) R → S
(4) R → a
其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:
I0= {S'→·S, S→·Sab, S→·bR}I1= {S'→S·, S→S·ab}
I2= {S→b·R, R→·S, R→·a, S→·Sab, S→·bR}I3= {S→Sa·b}I4= {S→bR·}
I5= {R→S·, S→S·ab}I6= {R→a·}I7= {S→Sab·}
求FOLLOW集：FOLLOW(S')={＄} FOLLOW(R)=FOLLOW(S)={a,＄}
在I5中，出现移进－归约冲突，且FOLLOW(R)∩{a}={a}因此，此文法不是SLR(1)文法。
b)S→aSAB|BA A→aA|B B→b
解：该文法的拓广文法G'为
(0) S' → S(1) S → aSAB
(2) S → BA(3) A → aA
(4) A → B(5) B → b
其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:
I0= {S'→·S, S→·aSAB, S→·BA, B→·b}I1= {S'→S·}I2= {B→b·}
I3= {S→a·SAB, S→·aSAB, S→·BA, B→·b}I4= {S→B·A, A→·aA, A→·B, B→·b}
I5 = {S→aS·AB, A→·aA, A→·B, B→·b}I6 = {S→aSA·B, B→·b}
I7= {A→a·A, A→·aA, A→·B, B→·b}I8= {A→B·}I9= {S→BA·}I10= {S→aSAB·}
I11= {A→aA·}
求FOLLOW集：FOLLOW(S')={＄} FOLLOW(S)={a,b,＄} FOLLOW(A)={a,b,＄} FOLLOW(B)={a,b,＄}
4.12 证明下面文法是SLR(1)文法，并构造其SLR分析表。
E→E+T|T T→TF|F F→F*|a|b
解：该文法的拓广文法G'为
(0) E' → E(1) E → E+T
(2) E → T(3) T → TF
(4) T → F(5) F → F*
(6) F → a(7) F → b
其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:
I0 = {E'→·E, E→·E+T, E→·T, T→·TF, T→·F, F→·F*,F→·a, F→·b}
I1= {E'→E·, E→E·+T}I2 = {E→T·, T→T·F, F→·F*, F→·a, F→·b}
I3= {T→F·, F→F·*}I4= {F→a·}I5= {F→b·}
I6= {E→E+·T, T→·TF, T→·F, F→·F*, F→·a, F→·b}I7 = {T→TF·, F→F·*}I8 = {F→F*·}
I9= {E→E+T·, T→T·F, F→·F*, F→·a, F→·b}
求FOLLOW集： FOLLOW(E)={＋, ＄} FOLLOW(T)={＋, ＄, a, b}
FOLLOW(F)={＋, ＄, a, b, *}
构造的SLR分析表如下：
显然，此分析表无多重定义入口，所以此文法是SLR文法。
4.13 下面文法属于哪类LR文法？试构造其分析表。S→(SR|a R→,SR|)
解：该文法的拓广文法G'为
(0) S' → S(1) S → (SR
(2) S → a(3) R → ,SR
(4) R → )
构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:I0= {S'→·S, S→·(SR, S→·a}
I1= {S'→S·}I2= {S→(·SR, S→·(SR, S→·a}I3= {S→a·}I4= {S→(S·R, R→·,SR, R→·)}
I5= {S→(SR·}I6= {R→)·}I7= {R→,·SR, S→·(SR, S→·a}
I8= {R→,S·R, R→·,SR, R→·)}I9= {R→,SR·}
每个LR(0)项目集中没有冲突。因此，此文法是LR(0)文法。其分析表如下：
4.14 设文法G为S→A A→BA|εB→aB|b
(1)证明它是LR(1)文法。 (2)构造它的LR(1)分析表。 (3)给出输入符号串abab的分析过程。解：(1) 构造其拓广文法G'的产生式为
(0) S' → S(1) S → A
(2) A → BA(3) A → ε
(4) B → aB(5) B → b
构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:
I0= { [S'→·S, $], [S→·A, $], [A→·BA, $], [A→·, $],[B→·aB, a/b/$], [B→·b, a/b/$]} I1= {[S'→S·, $]}I2= {[S→A·, $]}
I3= {[A→B·A, $], [A→·BA, $], [A→·, $],[B→·aB, a/b/$], [B→·b, a/b/$]}
I4= {[B→b·, a/b/$]}I5= {[B→a·B, a/b/$], [B→·aB, a/b/$], [B→·b, a/b/$]} I6= {[A→BA·, $]}I7= {[B→aB·, a/b/$]}
该文法的LR(1)项目集规范族中没有冲突，所以该文法是LR(1)文法。
(2)构造LR(1)分析表如下：
以上分析表无多的定义入口，所以该文法为LR(1)文法。
(3)对于输入串abab，其分析过程如下：
4.15 为下面的文法构造LALR(1)分析表S→E E→E+T|T T→(E)|a
解：其拓广文法G'：
(0) S' → S(1) S → E
(2) E → E+T(3) E → T
(4) T → (E)(5) T → a
构造其LR(1)项目集规范族和goto函数(识别活前缀的DFA)如下:
I0= {[S’→·S, $], [S→·E, $], [E→·E+T, $/+], [E→·T, $/+],[T→·(E), $/+], [T→·a, $/+]} I1= {[S’→S·, $]}I2= {[S→E·, $], [E→E·+T, $/+]}I3= {[E→T·, $/+]}
I4= {[T→(·E), $/+], [E→·E+T, )/+], [E→·T, )/+], [T→·(E), )/+], [T→·a, )/+]}
I5= {[T→a·, $/+]}I6= {[E→E+·T, $/+], [T→·(E), $/+], [T→·a, $/+]}
I7= {[T→(E·), $/+], [E→E·+T, )/+]}I8= {[E→T·, )/+]}
I9= {[T→(·E), )/+}, [E→·E+T, )/+], [E→·T, )/+], [T→·(E), )/+], [T→·a, )/+]}
I10= {[T→a·, )/+]} I11= {[E→E+T·, $/+]}I12= {[T→(E)·, $/+]}
I13= {[E→E+·T, )/+], [T→·(E), )/+], [T→·a, )/+]}I14= {[T→(E·), )/+], [E→E·+T, )/+]} I15= {[E→E+T·, )/+]}I16= {[T→(E)·, )/+]}
合并同心的LR(1)项目集，得到LALR的项目集和转移函数如下：
I0= {[S’→·S, $], [S→·E, $], [E→·E+T, $/+], [E→·T, $/+], [T→··(E), $/+], [T→·a, $/+]}
I1= {[S’→S·, $]}I2= {[S→E·, $], [E→E·+T, $/+]}I3,8= {[E→T·, $/+/)]}
I4,9 = {[T→(·E), $/+/)], [E→·E+T, )/+], [E→·T, )/+], [T→·(E), )/+], [T→·a, )/+]}
I5,10= {[T→a·, $/+/)]}I6,13= {[E→E+·T, $/+/)], [T→·(E), $/+/)], [T→·a, $/+/)]}
I7,14= {[T→(E·), $/+/)], [E→E·+T, )/+]}I11,15= {[E→E+T·, $/+/)]}
I12,16= {[T→(E) ·, $/+/)]}
LALR分析表如下：br>
4.16 考虑文法G[S]，其产生式如下S→AS | b A→SA | a
(1)构造文法G[S]的LR(0)项目集规范族及相应的DFA。
(2)如果把每一个LR(0)项目看成一个状态，并从每一个形如B→α·Xβ的状态出发画一条标识为X的箭弧到状态B→αX·β,而且从每一个形如B→α·Aβ的状态出发画标记为ε的箭弧到所有形如A→·γ的状态。这样就得到了一个NFA。说明这个NFA与(a)的DFA是等价的。(3)构造文法的SLR分析表。
(4)对于输入串bab，给出SLR分析器所作出的动作。
(5)构造文法的LR(1)分析表和LALR分析表。
解：(1)其拓广文法G'：
(0) S' → S(1) S → AS
(2) S → b(3) A → SA
(4) A → a
构造其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下:
I0= {S'→·S, S→·AS, S→·b, A→·SA, A→·a}
I1= {S'→S·, A→S·A, A→·SA, A→·a, S→·AS, S→·b }
I2= {S→A·S, S→·AS, S→·b, A→·SA, A→·a }I3 = {A →a·}I4= {S→b·}
I5= {A→SA·, S→A·S, S→·AS, S→·b, A→·SA, A→·a }
I6= {A→S·A, A→·SA, A→·a, S→·AS, S→·b}
I7= {S→AS·, A→S·A, A→·SA, A→·a, S→·AS, S→·b}
一、填空题|（每题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．将编译程序分成若干个“遍”是为了_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）简述编译程序的概念及其构成 答：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：产生式集合(有限)。
一、填空题（每空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
2010-2011第一学期期末试题《山东理工大学》 一．（15） 1.乔姆斯基把文法分成__4__种类型，在编译原理中用来描述程序设计语言词法结构的___文法，用来描述程序设计语言语法结构的是______文法。 2.一个上下文无关文法G包括四个组成部分：一组终结符号，一组______，一个开始符号以及一组______。 3.自上而下语法分析法会遇到的主要问题有______和______。 4.最右推导也称______，最右推导的逆过程称为最左归约，也称为______。 5.一个文法符号的______属性是通过语法树中它的文结点和/或兄结点的相应文法符号和属性来计算的，而______属性是通过语法树中它的子结点的属性之值来计算的。 6.常用的两种动态存贮分配方法是______动态分配和______动态分配。 7.在PASCAL语言中，为了在过程的嵌套调用过程中实现对非局部名字的访问，可以采用______和活动记录，或______和活动记录的方式。 二．（15） 1.请画出编译程序的总框图。 2.请给出表达式(a+b)*c+c/d的后缀式，并将其表示成三元式、四元式和间接三元式。 3.设文法G(s):S→(A)|a A→A+s|s，请构造各非终结符的FIRSTVT集合和LASTVT 集合。 三．（10） 将下列语句翻译成四元式序列（假定地址从100开始） While(a>b and a
《编译原理》模拟试题一 一、是非题（请在括号内，正确的划√，错误的划×）（每个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．简单优先文法允许任意两个产生式具有相同右部。 (×) 二、选择题(请在前括号内选择最确切的一项作为答案划一个勾，多划按错论)(每个4分，共40分) 1．一个编译程序中，不仅包含词法分析，_____，中间代码生成，代码优化，目标代码生成等五个部分。 A．( ) 语法分析B．( )文法分析C．( )语言分析D．( )解释分析 2．词法分析器用于识别_____。 A．( ) 字符串B．( )语句 C．( )单词 D．( )标识符 3．语法分析器则可以发现源程序中的_____。 A．( ) 语义错误 B．( ) 语法和语义错误 C．( ) 错误并校正D．( ) 语法错误 4．下面关于解释程序的描述正确的是_____。
(1) 解释程序的特点是处理程序时不产生目标代码 (2) 解释程序适用于 COBOL 和 FORTRAN 语言 (3) 解释程序是为打开编译程序技术的僵局而开发的 A．( ) (1)(2) B．( ) (1)C．( ) (1)(2)(3) D．( ) (2)(3) 5．解释程序处理语言时 , 大多数采用的是_____方法。 A．( ) 源程序命令被逐个直接解释执行 B．( ) 先将源程序转化为中间代码 , 再解释执行 C．( ) 先将源程序解释转化为目标程序 , 再执行 D．( ) 以上方法都可以 6．编译过程中 , 语法分析器的任务就是_____。 (1) 分析单词是怎样构成的 (2) 分析单词串是如何构成语句和说明的 (3) 分析语句和说明是如何构成程序的 (4) 分析程序的结构 A．( ) (2)(3) B．( ) (2)(3)(4) C．( ) (1)(2)(3) D．( ) (1)(2)(3)(4) 7．编译程序是一种_____。 A. ( ) 汇编程序B．( ) 翻译程序 C．( ) 解释程序 D．( ) 目标程序 8．文法 G 所描述的语言是_____的集合。 A. ( ) 文法 G 的字母表 V 中所有符号组成的符号串 B．( ) 文法 G 的字母表 V 的闭包 V* 中的所有符号串 C．( ) 由文法的开始符号推出的所有终极符串 D. ( ) 由文法的开始符号推出的所有符号串 9．文法分为四种类型，即0型、1型、2型、3型。其中3型文法是_____。 A. ( ) 短语文法 B．( ) 正则文法 C．( ) 上下文有关文法 D．( ) 上下文无关文法 10．一个上下文无关文法 G 包括四个组成部分，它们是：一组非终结符号，一组终结符号，一个开始符号，以及一组 _____。 A．( ) 句子B．( ) 句型 C．( ) 单词 D．( ) 产生式 三、填空题(每空1分，共10分)
编译原理考试题及答案汇总 一、选择 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____。
一． 填空题（每空2分，共20分） 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-6为单选题，7-8为多选题，每问2分，共20分） 1. 一个上下文无关文法G 包括四个组成部分：一组终结符，一组非终结符，一个（ ），以及一组 （ ）。 A ． 字符串 B ． 产生式 C ． 开始符号 D ． 文法 2.程序的基本块是指（ ）。 A ． 一个子程序 B ． 一个仅有一个入口和一个出口的语句 C ． 一个没有嵌套的程序段 D ． 一组顺序执行的程序段，仅有一个入口和一个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于（ ）分析方法。 A ． 自左向右 B ． 自顶向下 C ． 自底向上 D ． 自右向左 4．在通常的语法分析方法中，（ ）特别适用于表达式的分析。 A ． 算符优先分析法 B ． LR 分析法 C ． 递归下降分析法 D ． LL （1）分析法 5．经过编译所得到的目标程序是（ ）。 A ． 四元式序列 B ． 间接三元式序列 C ． 二元式序列 D ． 机器语言程序或汇编语言程序 6． 一个文法所描述的语言是（ ）；描述一个语言的文法是（ ）。 A ． 唯一的 B ． 不唯一的 C ． 可能唯一，也可能不唯一 7． 如果在文法G 中存在一个句子，当其满足下列条件（ ）之一时，则称该文法是二义文法。 A ． 其最左推导和最右推导相同 B ． 该句子有两个不同的最左推导 C ． 该句子有两个不同的最右推导 D ． 该句子有两棵不同的语法树
《编译原理》期末考试复习题 一、是非题（请在括号内，正确的划√，错误的划×）（每个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．一个句型中的最左简单短语称为该句型的___句柄__。
南京工业大学继续教育学院编译原理期末考试试卷 (2012-2013学年) A卷 一、选择题（每题2分，共20分） 得分 1. 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符，一个_____，以及一组产生式。 A．字符串 B．运算符号 C．开始符号 D．文法 2.程序的基本块是指_____。 A．一个子程序 B．一个仅有一个入口和一个出口的语句 C．一个没有嵌套的程序段 D．一组顺序执行的程序段，仅有一个入口和一 个出口 3. 高级语言编译程序常用的语法分析方法中，递归下降分析法属于_____分析方法。 A．自左向右 B．自顶向下 C．自底向上 D．自右向左 4．经过编译所得到的目标程序是_____。 A．四元式序列 B．间接三元式序列 C．二元式序列 D．机器语言程序或汇编语言程序 5．运行阶段的存储组织与管理的目的是_____。 ①提高编译程序的运行速度②节省编译程序的存储空间 ③提高目标程序的运行速度④为运行阶段的存储分配做准备 A. ①② B. ②③ C. ③④ D. ④②6．词法分析器的输出结果是_____。 A．( ) 单词的种别编码B．( ) 单词在符号表中的位置C．( ) 单词的种别编码和自身值D．( ) 单词自身值 7．正规式M 1 和M 2 等价是指_____。
A．( ) M1和M2的状态数相等B．( ) M1和M2的有向边条数相等 C．( ) M1和M2所识别的语言集相等D．( ) M1和M2状态数和有向边条数相等 8．文法G：S→xSx|y所识别的语言是_____。 A．( ) xyx B．( ) (xyx)* C．( ) xnyxn(n≥0) D．( ) x*yx* 9．语言是_____。 A．句子的集合B．产生式的集合 C．符号串的集合D．句型的集合 10．编译程序前三个阶段完成的工作是 A．词法分析、语法分析和代码优化 B．代码生成、代码优化和词法分析 C．词法分析、语法分析、语义分析和中间代码生成 D．词法分析、语法分析和代码优化 二、名词解释（每题2分，共20分） 得分 1.最左推导： 2.语法： 3.文法： 4.基本块： 5.语法制导翻译： 6.短语： 7.规范句型：
编译原理 一、(5×6分)回答下列问题： 1．什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？ 2．什么是句柄？什么是素短语？ 3．划分程序的基本块时，确定基本块的入口语句的条件是什么？ 4．运行时的DISPLAY 表的内容是什么？它的作用是什么？ 5．对下列四元式序列生成目标代码： A:=B*C D:=E+F G:=A+D H:=G*2 其中，H 是基本块出口的活跃变量， R0和R1是可用寄存器 二、(8分)设∑={0，1}上的正规集S 由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该正规集的DFA 。 三、(6分)写一个文法使其语言为L(G)={ a n b m a m b n | m,n ≥1}。 四、(8分)对于文法G(E): E →T|E+T T →F|T* F F →(E)|i 1. 写出句型(T*F+i)的最右推导并画出语法树。 2. 写出上述句型的短语，直接短语、句柄和素短语。 五、(12分)设文法G(S)： ( |*)B B |B A A A |SiA S A →+→→ 1．构造各非终结符的FIRSTVT 和LASTVT 集合； 2．构造优先关系表和优先函数。 六、(9分)设某语言的do-while 语句的语法形式为 S → do S (1) While E 其语义解释为： 真 假 S (1)的代码 E 的代码
针对自下而上的语法分析器，按如下要求构造该语句的翻译模式： (1) 写出适合语法制导翻译的产生式； (2) 写出每个产生式对应的语义动作。 七、(8分)将语句if (A
2011～ 2012 学年第 1 学期期末考试试卷答案 《编译原理》（共 4 页） （考试时间： 2011 年 12 月 25 日） 一、选择题（每题 1 分，共 10 分） 1.B 2.D 3.A 4.D 5.D 6.C 7.B 8.C 9.D 10.B 二、简答题（每题 5 分，共 20 分） 1．何谓二义性文法？试举一例说明。 答：若文法G 的一个句子对应有两棵或两棵以上不同的推导树，则称该句子是 二义性的。产生二义性句子的文法称为二义性文法，否则该文法是无二义性的。 例子：给定文法G[）是上下文无关文法，产生式集合P 中任意一个产生式应具有什么样的形式？若G 是正则文法呢？ 答：上下文无关文法的产生式形式为： A →α，其中， A ∈ V N，α∈（ V N∪V T）* 正则文法产生式形式为： N，a∈V T A→，或→ （右线性文法）其中，A,B ∈V aBA a A→Ba，或 A → a（左线性文法）其中， A,B ∈ V N， a∈V T 三、推导题（共70 分） 1．对于文法 G[S]：
2、写出表达式a＋b*(c-d)/e的逆波兰式和三元序列。 3、写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。 4、已知文法G(S)及相应翻译方案 S→aAb {print “1”} S→a {print “2”} A→AS {print “3”} A→c {print “4”} 输入acab, 输出是什么 5、已知文法G(S) S→bAa A→(B | a B→Aa) 写出句子b(aa)b的规范归约过程。 6、已知文法G[S] S→S*aF | aF | *aF F→+aF | +a 消除文法左递归。 1、设文法G(S): S→^ | a | (T) T→T,S | S ⑴消除左递归； ⑵构造相应的FIRST和FOLLOW集合； ⑶构造预测分析表 2.语句if E then S (1) 改写文法，使之适合语法制导翻译； (2) 写出改写后产生式的语义动作。 4.设某语言的for语句的形式为 for i:＝E(1) to E(2) do S 其语义解释为 i:＝E(1) LIMIT:＝E(2) again: if i＜＝LIMIT then Begin S; i:＝i＋1 goto again End; （1）写出适合语法制导翻译的产生式； （2）写出每个产生式对应的语义动作。 7.已知文法G(S) S→a | ^ | (T) T→T,S | S (1) 给出句子(a,(a,a))的最左推导； (2) 给出句型((T,S),a)的短语, 直接短语，句柄。 8.对于C 语言do S while E语句 (1)改写文法，使之适合语法制导翻译；
(2)写出改写后产生式的语义动作。 9.已知文法G(S) S→aAcBe A→Ab| b B→d (1)给出句子abbcde的最左推导及画出语法树； (2)给出句型aAbcde的短语、素短语。 10.设文法G(S): S→(T) | aS | a T→T,S | S ⑴消除左递归和提公共左因子； ⑵构造相应的FIRST和FOLLOW集合； ⑶构造预测分析表。 12.已知文法G(S) E→E+T | T T→T*F| F F→(E)| i (1) 给出句型(i+i)*i+i的最左推导及画出语法树； (2) 给出句型(E+T)*i+F 的短语，素短语和最左素短语。 答案： (1)消除左递，文法变为G’[S]： S→^ | a | (T)' T→ST’ | S T’→,ST’ |ε 此文法无左公共左因子。 (2)构造相应的FIRST和FOLLOW集合： FIRST(S)={a, ^, (}，FOLLOW(S)={#, ,, )} FIRST(T)={a, ^, (} ，FOLLOW(T)={}} FIRST(T’)={,, ε} ，FOLLOW(F)={)} (3) C→if E then S→CS(1) (2) C→if E then {BACK, NXQ); :=} S→CS(1) {:=MERG, S(1). Chain)} 4. (1) F→for i:=E(1) to E(2) do S→FS(1) (2)F→for i:=E(1) to E(2) do {GEN(:=, E(1).place, _, entry(i)); :=entry(i);
一、单项选择题(共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．L0?L1?L2?L3 B．L3?L2?L1?L0 C．L3=L2?L1?L0D．L0?L1?L2=L3 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．词法分析
《编译原理》考试试题及答案（汇总） 一、是非题（请在括号，正确的划√，错误的划×）（每个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、将编译程序分成若干个“遍”是为了( B ) A．提高程序的执行效率 B. 使程序的结构更加清晰 C．利用有限的机器内存并提高机器的执行效率 D．利用有限的机器内存但降低了机器的执行效率 2、不可能是目标代码的是( D ) A．汇编指令代码 B．可重定位指令代码 C．绝对指令代码 D．中间代码 3、词法分析器的输入是( B ) A．单词符号串 B．源程序 C．语法单位 D．目标程序 4、编译程序中的语法分析器接受以 c 为单位的输入，并产生有关信息供以后各阶段使用。 可选项有：a、表达式 b、产生式 c、单词 d、语句 5、高级语言编译程序常用的语法分析方法中，递归下降分析法属于 b 分析方法。 可选项有：a、自左至右 b、自顶向下 c、自底向上 d、自右向左 6、已知文法G[E]：E→TE’ E’ →+TE’∣ε T→FT’ T’ →*FT’∣ε F→（E）∣id 求：FOLLOW（F）=（1） d ， FIRST（T’）=（2） b 可选项有： a、｛*，+｝ b、｛*，ε｝ c、｛+,#，）｝ d、｛*，+，#，）｝ e、｛#，）｝ f、｛*，+，#，id｝ 7、中间代码生成时所遵循的是( C ) A．语法规则 B．词法规则 C．语义规则 D．等价变换规则 8、编译程序是对( D ) A．汇编程序的翻译 B．高级语言程序的解释执行 C．机器语言的执行 D．高级语言的翻译 9、词法分析应遵循( C ) A．语义规则 B．语法规则 C．构词规则 D．等价变换规则 10、词法分析器的输出结果是( C ) A．单词的种别编码 B．单词在符号表中的位置 C．单词的种别编码和属性值 D．单词属性值 11、正规式M1和M2等价是指( C ) A．M1和M2的状态数相等 B．M1和M2的有向弧条数相等
1解释程序适用于COBOL 和FORTRAN 语言。(×) 2算符优先关系表不一定存在对应的优先函数。 3对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。 4正规文法产生的语言都可以用上下文无关文法来描述。 5确定的自动机以及不确定的自动机都能正确地识别正规集。(√) 6构造LR分析器的任务就是产生LR分析表。(√) 7编译程序是对高级语言程序的解释执行。(× ) 8静态数组的存储空间可以在编译时确定。(×) 9一个语义子程序描述了一个文法所对应的翻译工作。(×) 10编译程序与具体的机器有关,与具体的语言无关。(× ) 11编译程序是对汇编程序的翻译。（错） 12基本块内的优化为删除多余运算，删除无用赋值(对) 13基本块内的优化为代码外提，归纳变量（错） 14采用自上而下分析，必须消除左递归。 问答 1.编译程序和解释程序有哪些区别？举例说明。 答:编译程序与解释程序的主要区别是：编译程序将源程序翻译成目标程序后在执行该目标程序；而解释程序则逐条读出源程序中的语句并解释执行，即在解释程序的执行过程中并不产生目标程序。典型的解释型高级语言是BASIC语言。 2.适合采用静态存储分配的程序设计语言应有哪些限制？ 答：①数据实体所需空间在编译时能确定②运行时每个数据对象只能有一个实例 ③数组的上下界是常量④过程调用不允许递归⑤不能动态建立数据实体 3.什么是扫描器？扫描器的功能是什么？ 答：词法分析是编译的第一个阶段，其任务是：从左至右逐个字符地对源程序进行扫描，产生一个个单词符号，把字符串形式的源程序改造成为单词符号串形式的中间程序。执行词法分析的程序称为词法分析程序，也称为词法分析器或扫描器。词法分析器的功能是输入源程序，输出单词符号。 4.何谓嵌套过程语言运行时的DISPLAY表？它的作用是什么？ 1.写一个文法，使其语言是奇数集，且每个奇数不以0开头。 2.解：文法G(N)： N→AB|B A→AC|D B→1|3|5|7|9 D→B|2|4|6|8 C→0|D 3..2.写一个文法使其语言为偶数集，且每个偶数不以0开头。 解：文法G（S）： S→AB|B|A0 A→AD|C B→2|4|6|8 C→1|3|5|7|9|B D→0|C 2.写一文法，使其语言是偶正整数的集合,要求:(1)允许0打头(2)不允许0打头。 解：(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S) P: S->PD|D P->NP|N D->0|2|4|6|8 N->0|1|2|3|4|5|6|7|8|9 (2)G[S]=({S,P,R,D,N,Q },{0,1,2,…,9},P,S) P: S->PD|P0|D P->NR|N R->QR|Q D->2|4|6|8 N->1|2|3|4|5|6|7|8|9 Q->0|1|2|3|4|5|6|7|8|9