编译原理_复习题

1、.word可编辑.3.文法：S->MH|a H ->LSo| £ K ->dML| £ L->eHf M->K|bLM判断G是否为LL(1)文法，如果是，构造 LL(1)分析表。解：各符号的FIRST集和 FOLLOW为：FIRSTFOLLOWS通。M& Jb依兑。H他L一a4b岛口网K型他#各产生式SELEC磔为:SELECTS->MHdb 喇口S->aH ->LSoe锵WK->dMLK-速伯相。L ->eHf依M4KM-> bLMbSELECT S->MH d,b,e,#,o S->a

2、 a H ->LSo e H ->£ #,f,o K ->dML d K ->£ e,#,o L ->eHf e M->K d,e,#,o M-> bLM b预测分析表a0defb#S->MHM->K双双Hc £3lso'L->eHfK£->dML*>£由于预测分析表中无多重入口，所以可判定文法是LL(1)的专业.专注判断该文法是否是 SLR(1)文法，若是构造相应分已知文法为：A ->aAd|aAb| &析表,并对输入串ab#给出分析过程。解：增加一

3、个非终结符S/后，产生原文法的增广文法有：S'->A A - >aAd|aAb| e 下面构造它的LR(0)项目集规范族为：bd9AL：A今*AT/曲 AT德！ AaAbInS-HlitI S ->A-accU ATM Ad*今*出aAb RT*LLi A-*-aA*dImATaA*bI tlitI EATaAb*LtATM小从上表可看出，状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。对于I0来 说有： FOLLOW(A) a=b,d,# na=，所以在I0状态下面临输入符号为 a时移进，为b,d,#时 归约，为其他时报错。对于 I2来说有也有与I0完全

4、相同的结论。这 就是说，以上的移-归冲突是可以解决的，因此该文法是 SLR(1)文法。 其SLR(1)分析表为：GOTO*bdtAQs;a11cc2Srflr3力335St4r：r：r：於5HlririZi对输入串ab#给出分析过程为:1根湫oGOTO101:202lait3-8 _ J1023taibtS40234taAbIi；15L01Ji对给定正规式 b* (d|ad) (b|ab) +,构造其 NFA M;解答：首先用A+=AA*改造正规式得:b*(d|ad)(b|ab)(b|ab)*;其次，构造该正规式的 NFAM如图3-6-7所示。写出相应的逆波兰表示。试为表达式 w+(a+b)*

5、(c+d/(e-10)+8)解：w a b + c d e 10 - / + 8 + * +该自动机是确定的吗？若不确构造下述文法 GS 的自动机： S->A0 A->A0|S1|0 定，则对它确定化。解：由于该文法的产生式S->A0 , A->A0|S1中没有字符集VT的输入，所以不是确定的自动机。要将其他确定化，必须先用代入法得到它对应的正规式。把 S?A0代入产生式A?S1有：A=A0|A01|0=A(0|01)|0=0(0|01)*。 代入 S->A0 有该文法的正规式：0(0|01)*0 ，所以，改写该文法为确定的自动机为：由于状态A有3次输入0的重复输

6、入，所以上图只是 NFA面将它确定化：下表由子集法将NFA转换为DFA:II« -火心如色似加。力 0）Ik -机心suzfMQgAVBXBXCX,Y,ZcXy.zcXxzbx由上表可知DFA0,03 .写出表达式（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, T5, T6）4 .写一个文法使其语言为偶数集，且每个偶数不

7、以0开头。解：文法 G (S): Sf AB|B|A0KAD|CB2141618c - 1|3|5|7|9|BD 一0|C5 .设文法 G (S): S-S+ aF|aF| +aFF-*aF|*a(1)消除左递归和回溯；(2)构造相应的 FIRST和Follow集合。1) S->aFS'| +aFS'S'-> +aFS'| £F->*aF'F'- >F| £(2) FIRST (S) = a, + FOLLOW( S) = # FIRST (S') = +, e FOLLOW( S')

8、=# FIRST (F) = * FOLLoW(F) = (+,# FIRST (F') = *, e FOLLOW( + , #五.计算题(10分)已知文法为：S->aF|(T) T->T,S|S 构造它的LR(0)分析表。解：加入非终结符 S',方法的增广文法为：S'->SS->aS->AS->T->T,STS下面构造它的LR(0)项目集规范族为：从上表可看出，不存在移进-归约冲突以及归约归约冲突，该文法是LR（0）文法。从而有下面的LR（0）分析表：4、对文法G®0)S* T 4)A -*aU5分)1)S -"A5)B -*hBd2)S T6)B h3)A