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)构造预测分析表：
a ^ ( ) , # S S→a S→^ S→(T)' T T→ST’ T→ST’ T→ST’ T’ T’→ε T’→,ST’ 2. (1)
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); LIMIT:=Newtemp;
GEN(:=, E(2).place, _, LIMIT); Q:=NXQ; :=q;
GEN(j≤, entry(i), LIMIT, q+2) :=NXQ;
GEN(j, _, _, 0)} S→FS(1)
{BACKPATCH(S(1).chain, NXQ);
GEN(+, , 1, ; GEN(j, _, _, ; := }
7. 最左推导
S=(T)=>(T,S)=>(S,S)=>(a,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a,a)) 短语 ((T,S),a) (T,S),a (T,S) T,S a 直接短语 T,S a 句柄 T,S
9.(1) S=>aAcBe=>AAbcBe=>abbcBe=>abbcde
(2) 短语: aAbcde, Ab, d 素短语: Ab, d 10.(1) S →(L) | aS’ S’→S |ε L→SL’
L’→,SL’ |ε
(2) FIRST(S)={a, (} FIRST(S’)={a, (, ε} FIRST(L)={a, (} FIRST(L’)={,, ε}
FOLLOW(S)={,, ), #} FOLLOW(S’)={,, ), #} FOLLOW(L)={ )} FOLLOW(L’)={ )}
(3)
( ) a , # S S →(L) S → aS’ S’ S’→S S’→ε S’→S S’→ε S’→ε L L→SL’ L→SL’ L’→,SL’ L’
L’→ε 12.(1) E=>E+T=>T+T=>T*F+T=>F*F+T=>(E)*F+T=>(E+T)*F+T=>(T+T)*F+T
=>(F+T)*F+T=>(i+T)*F+T=>(i+F)*F+T=>(i+i)*F+T=>(i+i)*i+T
=>(i+i)*i+F=>(i+i)*i+i
(2) 短语 i, F, E+T, (E+T), (E+T)*i, (E+T)*i+F 素短语 i, E+T
最左素短语 E+T
《编译原理》期末试题（二）
对于函数f2，由于局部变量x的作用域只是函数体的一部分，不会出现上述问题，因而编译器不报错。
6、正规式ba(bba) b体现的特点是，每个a的左边都有若干b，除非a是第一个字母。该正规式定义的语言是：至少含一个a，但不含子串aa的所有a和b的串集。最简DFA如下：
7、 消除左递归后的文法： B 1 B
B 0 B | 1 B | 相应的翻译方案如下：
B 1 {B.i := 1 }B{ := B.val} B 0 {B := B.i 2 } B | 1 {B := B.i 2 +1} B | {B.val := B.i}
1
{B.val := B}
1
{B.val := B}
《编译原理》期末试题（三）
2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。 答：逆波兰式： abc*bd*+:=
3、对于文法G(S):
S bMbM (L|aL Ma）
答：1） SbMbb(Lbb(Ma)b
b2） 短语: Ma)， (Ma)， b(Ma)b
(SMbTLMa)直接短语: Ma) 句柄: Ma)
三、 设有字母表{a，b}上的正规式R=(ab|a)*。
解：（1）
（2）将（1）所得的非确定有限自动机确定化
ε a b -0 1 1 3 12 2 1 +3
（3）对（2）得到的DFA化简，合并状态0和2 为状态2：
（4）令状态1和2分别对应非终结符B和A
G: A→aB|a|ε； B→aB|bA|a|b|ε；可化简为：G: A→aB|ε；B→aB|bA|ε 四、 设将文法G改写成等价的LL(1)文法，并构造预测分析表。
G：S→S*aT|aT|*aT； T→+aT|+a
解：消除左递归后的文法G’: S→aTS’|*aTS’
S’→*aTS’|ε
T→+aT|+a
提取左公因子得文法G’’: S→aTS’|*aTS’
S’→*aTS’|ε T→+aT’
T’→T|ε
Select(S→aTS’)={a} Select(S→*aTS’)={*}
Select(S→aTS’)∩Select(S→*aTS’)=Ф Select(S’→*aTS’)={*}
Select(S’→ε)=Follow(s’)={#}
Select(S’→*aTS’)∩Select(S’→ε)= Ф Select(T→+aT’)={+}
Select(T’→T)=First(T) ={+} Select(T’→ ε)=Follow(T’)={*,#}
Select(T’→T)∩Select(T’→ε)= Ф 所以该文法是LL(1)文法。 预测分析表：
* + a # S →*aTS’ →aTS’ S’ →*aTS’ →ε →T +aT’ T’ → ε
→T → ε 6设文法G 为：
S→A；A→BA|ε；B→aB|b
解：（1）拓广文法G’：(0) S’→S (1) S→A (2) A→BA(3) A→ε(4) B→aB (5)
B→b ； FIRST(A) = {ε, a, b}；FIRST(B) = {a, b} 构造的DFA 如下:
项目集规范族看出，不存在冲突动作。∴该文法是LR(1)文法。
（2）
LR(1)分析表如下：
(3)输入串abab 的分析过程为：
五、 对文法G(S)：S → a | ^ | (T)；T → T，S | SFIRSTVT(S){a,^,(} 答：(1) FIRSTVT(T){,,a,^,(}
LASTVT(S){a,^,)}LASTVT(T){,,a,^,)}
a ^ ( ) , # a > > > ^ > > > ( < < < = <
) (2) 是算符优先文法，因为任何两个终结符之间至多只
有一种优先关系。（2分）
(3) 给出输入串(a,a)#的算符优先分析过程。
> > > , < < < > > # < < 步骤 栈 当前输入剩余输动作 字符 入串 < = 1 # ( a,a# #<( 移进 2 #( a ,a)# (, 归约 4 #(N , a)# (<, 移进 5 #(N, a )# ,) 归约 7 #(N,N ） # ,>) 归约 8 #(N ) # (=) 移进 9 #(N) # )># 归约 10 #N # 接受 五、设有文法G[A]： A→BCc | gDB B→bCDE |ε C→DaB | ca D→dD |ε E→gAf | c (1) 计算该文法的每一个非终结符的 FIRST集和FOLLOW集； (2) 试判断该文法是否为LL（1）文法。（15） FIRST FOLLOW A B C D A,b,c,d,g A,c,d b C,d,g A,c,d A,b,c,g D E C,g 是LL（1）文法。 2．对于文法G[S]：SAB，AAa|bB，Ba|Sb求句型baSb的全部短语、直接短语和句柄 S B S b A 句型baSb的语法树如图五(2)所示。 b B a 解：baSb为句型baSb的相对于S的短语，ba为句型baSb的相对于A的短语，Sb为句型baSb的相对于B的短语，且为直接短语，a为句型baSb的相对于B的短语，且为直接短语和句柄。 3．设有非确定的有自限动机NFA M=({A，B，C}，{0，1}，，{A}，{C})，其中： (A，0)={C} (A，1)={A，B} (B，1)={C} (C，1)={C}。请画出状态转换距阵和状态转换图。 解：状态转换距阵为： 0 1 A C A，B B C C C 状态转换图为 ABC1七 已知文法G为: （0） S′→ S S → aAd S → bAc S → aec S → bed A → e （1） （2） （3） （4） （5） 试构造它的LR（1）项目集、可归前缀图和LR（1）分析表。 I0: I：S′→【】【答案：】 构造LR(1)分析表 如下： 二、设={0，1} 上的正规集 S由倒数第二个字符为 1 的所有字符串组成，请给出该字集 对应的正规式，并构造一个识别该正规集的 DFA。(8分 ) 答： 构造相应的正规式：(0|1)*1(0|1) (3分) NFA: (2分) 1 1 1 0 0 确定化：(3分) I I0 I1 {0,1,2} {1,2} {1,2,3} {1,2} {1,2} {1,2,3} {1,2,3} {1,2,4} {1,2,3,4} {1,2,4} {1,2} {1,2,3} {1,2,3,4} {1,2,4} {1,2,3,4} 0 1 0 1 0 0 0 1 1 1 四、对于文法G(E): (8分) ET|E+T TF|T*F F(E)|i 1. 写出句型(T*F+i)的最右推导并画出语法树。 E2. 写出上述句型的短语，直接短语、句柄和素短语。 T F(E)答： 1. (4分) E+TETF(E) (E+T) (E+F) (E+i) (T+i) (T*F+i) TT*FFi2. (4分) 短语：(T*F+i), T*F+i, T*F, i 直接短语：T*F, i 句柄：T*F 素短语：T*F, i 九、(9分) 设已构造出文法G(S)： (1) S BB aB b的LR分析表如下 (2) B (3) B ACTION GOTO 状态 a b # S B 0 s3 s4 1 2 1 acc 2 s6 s7 5 3 s3 s4 8 4 r3 r3 5 r1 6 s6 s7 9 7 r3 8 r2 r2 9 r2 假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。 答： 步骤 状态 符号 输入串 0 0 # abab# 1 03 #a bab# 2 034 #ab ab# 3 038 #aB ab# 4 02 #B ab# 5 026 #Ba b# 6 0267 #Bab # 7 0269 #BaB # 8 025 #BB # 9 01 #S # acc 1. 设有如下文法G（S），试消除其左递归。 G（S）：S—>Ac|c A—>Bb|b B—>Sa|a 解：S→abcS′|bcS′|cS′, S′→abcS′| 2. 试构造与下面G（S）等价的无左递归的文法。 G（S）：S—>Sa|Nb|c N—>Sd|Ne|f 解：S→fN′bS′|cS′, S′→aS′|dN′bS′|, N′→eN′| 3. 设有文法G（S）： S—>aBc|bAB A—>aAb|b B—>b|ε ①求各产生式的FIRST集，FOLLOW(A)和FOLLOW(B),以及各产生式的SELECT集。 ②构造LL(1)分析表，并分析符号串baabbb是否是。 解：（1）FIRST(aBc)={a}, FIRST(bAB)={b} FIRST(aAb)={a}, A→b: FIRST(A→b)={b}, B→b: FIRST(b) = {b}, FIRST(ε)={ε} FOLLOW(A)={b, #}, FOOLOW(B)={c, #} SELECT(S→aBc)={a}, SELECT(S→bAB) ={b}, SELECT(A→aAb)={a}, SELECT(A→b)={b}, SELECT(B→b)={b}, SELECT(B→)={c, #} 因此，所得的LL(1)分析表如表A-4所示。 表A-4 LL(1)分析表 输入 VN a 输入符号 b c # S S→aBc S→bAB A A→aAb A→b B B→b B→ B→ （2）分析符号串baabbb成功，baabbb是该文法的句子，如图A-16所示。 步骤 符号栈 输入串 所用的产生式 1 #S baabbb# SbAB 2 3 4 5 6 7 #BAb #BA #BbAa #BbA #BbbAa #BbbA baabbb# aabbb# AaAb aabbb# abbb# AaAb abbb# bbb# Ab bbb# bb# b# # # Bε 成功 8 #Bbbb 9 #Bbb 10 #Bb 11 #B 12 # 图A-16 识别串baabbb的过程 4. 已知文法G(S)： S—>a|(T) T—>T,S|S ①给出句子((a,a),a)的最左推导并画出语法树；②给出句型(T,a,(T))所有的短语、直接短语、素短语、最左素短语、句柄和活前缀。 解 ：（1）最左推导：S (T) (T,S) (S,S) (a,S)(a,(T))(a,(T,S))(a,(S,S))(a,(a, S))(a,(a,a)) 语法树：如图A-16所示。 S( T )T , SSa( T )T , SSaa 图A-16 (a,(a,a))的语法树 （2）句型(T, a, (T))的短语、直接短语、素短语、最左素短语、句柄、活前缀及语法树（图A-17）。 短语：a || T,a || (T) || T , a , (T) || (T , a , (T)) 直接短语：a || (T) 素短语：a || (T) 最左素短语：a 句柄：a 活前缀： || ( || (T || (T , || (T , a S( T )T , ST , S( T )a 图A-17 (T,a,(T))的语法树 I1: S′S· SaAbI2: Sa· Sa·Ab A·1A0 A·I4: SaA·b AI8: SaAb· I9: A1A·0 01I5: A1·A0 A·1A0 A·1I12: A1A0· I0: S′·S S·a S·aAb S·b S·bBa BbI3: Sb· Sb·Ba B·1B0 B·I6: SbB·a aBI10: SbBa· I11: B1B·0 011I7: B1·B0 B·1B0 B·I13: B1B0· 项目集族和DFA 1、w a b + c d e 10 - / + 8 + * + 2、abcd-*e/+ 3、abc+e*bc+f/+:= 4、4231 5、句子b(aa)b的规范归约过程： 步骤 符号栈 输入串 动作 0 # aa)b# b(预备 1 #b aa)b# (移进 2 #b( aa)b# 移进 3 #b(a a)b# 移进 4 #b(A # a)b归约 5 #b(Ma # )b移进 6 #b(Ma) b# 移进 7 #b(B b# 归约 8 #bA b# 归约 9 #bAb # 移进 10 #S # 接受 6、消除左递归 S→aFS’ | *aFS’ S’→*aFS’ | ε F→+aF | +a 因篇幅问题不能全部显示，请点此查看更多更全内容
Copyright © 2019- huatuo0.com 版权所有 湘ICP备2023021991号-1
违法及侵权请联系：TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务