资源描述:
《编译原理 复习》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、3. 文法: S->MH
2、a H ->LSo
3、 ε K ->dML
4、 ε L ->eHf M->K
5、bLM 判断 G 是否为 LL(1) 文法,如果是,构造 LL(1) 分析表。 解:各符号的 FIRST 集和 FOLLOW集为: 各产生式SELECT集为: SELECT S->MH {d,b,e,#,o} S->a {a} H ->LSo {e} H ->ε {#,f,o} K ->dML {d} K ->ε {e,#,o} L ->eHf {e} M->K {d,e,#,o} M-> bLM
6、{b} 预测分析表 由于预测分析表中无多重入口,所以可判定文法是 LL(1)的已知文法为:A ->aAd
7、aAb
8、 ε 判断该文法是否是 SLR(1) 文法,若是构造相应分析表,并对输入串 ab# 给出分析过程。解:增加一个非终结符 S/后,产生原文法的增广文法有: S'->A A ->aAd
9、aAb
10、ε 下面构造它的 LR(0)项目集规范族为: 从上表可看出, 状态 I0 和 I2 存在移进- 归约冲突,该文法不是 LR(0)文法。对于 I0 来说有: FOLLOW(A)∩{a}={b,d
11、,#}∩{a}=Φ ,所以在 I0 状态下面临输入符号为 a 时移进,为 b,d,#时 归约,为其他时报错。对于 I2 来说有也有与 I0 完全相同的结论。这就是说,以上的移 - 归冲突是可以解决的,因此该文法是 SLR(1)文法。 其 SLR(1)分析表为: 对输入串 ab#给出分析过程为: 对给定正规式b*(d
12、ad)(b
13、ab)+,构造其NFAM;解答:首先用A+=AA*改造正规式得:b*(d
14、ad)(b
15、ab)(b
16、ab)*;其次,构造该正规式的NFAM,如图3-6-7所示。 试为表达式 w+
17、(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。 解: w a b + c d e 10 - / + 8 + * + 构造下述文法 G[S] 的自动机: S->A0 A->A0
18、S1
19、0 该自动机是确定的吗?若不确定,则对它确定化。 解:由于该文法的产生式S->A0,A->A0
20、S1中没有字符集VT的输入,所以不是确定的自动机。 要将其他确定化,必须先用代入法得到它对应的正规式。把S?A0代入产生式A?S1有:A=A0
21、A01
22、0=A(0
23、01)
24、0=0(0
25、01)*。 代入S->A0有该文法
26、的正规式:0(0
27、01)*0,所以,改写该文法为确定的自动机为: 由于状态A有3次输入0的重复输入,所以上图只是NFA,面将它确定化: 下表由子集法将NFA转换为DFA: ] 由上表可知DFA3.写出表达式(a+b)/(a-b-(a+b*c)的三元序列及四元序列。解:(1)三元式:①(+,a,b)②(-,a,b)③(/,①,②)④(*,b,c)⑤(+,a,④)⑥(-,③,⑤)(2)四元式:①(+,a,b,T1)②(-,a,b,T2)③/,T1,T2,T3)④(*,b,c,T4)⑤(+,a,T4,T5)⑥(-,T3
28、,T5,T6)4.写一个文法使其语言为偶数集,且每个偶数不以0开头。解:文法G(S):S→AB
29、B
30、A0A→AD
31、CB→2
32、4
33、6
34、8C→1
35、3
36、5
37、7
38、9
39、BD→0
40、C5.设文法G(S):S→S+aF
41、aF
42、+aFF→*aF
43、*a(1)消除左递归和回溯;(2)构造相应的FIRST和Follow集合。1)S->aFS'
44、+aFS'S'->+aFS'
45、εF->*aF'F'->F
46、ε(2)FIRST(S)={a,+}FOLLOW(S)={#}FIRST(S')={+,ε}FOLLOW(S')={#}FIRST(F)={
47、*}FOLLoW(F)=(+,#}FIRST(F')={*,ε}FOLLOW(+,#}五.计算题(10分)已知文法为:S->a
48、^
49、(T)T->T,S
50、S构造它的LR(0)分析表。解:加入非终结符S',方法的增广文法为:S'->SS->aS->^S->(T)T->T,ST->S下面构造它的LR(0)项目集规范族为:从上表可看出,不存在移进-归约冲突以及归约归约冲突,该文法是LR(0)文法。从而有下面的LR(0)分析表: