《2015年期中测试答案》由会员分享，可在线阅读，更多相关《2015年期中测试答案（7页珍藏版）》请在金锄头文库上搜索。
1、11、给出文法 G(S) （8 分）aQbcPcSS|（1）它是乔姆斯基哪一型文法？答：文法是乔姆斯基 2 型文法，即上下文无关文法。（2）它生成的语言是什么？ 1,0|)( kjibcaGLjkji2、已知语言 L，试构造相应文法。 （8 分）（1） 0,|)(mncn答： G(S): |bBaS（2）L(G)= a 2n+1 |n0答：G(S): 或|SA|aA3、构造以下正规式相应的 NFA，再确定化，并最小化（12 分）（a|ba) *答：过程如下2四、 请给出与下面自动机等价的正规表达式。 （7 分）0 1 a 943ba2aab3456 7 a8baaaaaaaa答：*)(|()b
2、ab3五、已知文法 G（S）:SS*aP| aP|*aP，P+aP|+a(1) 将文法 G（S）改写为 LL(1)文法 G(S);(2) 求出每个非终结符的 FIRST 集合和 FOLLOW 集合，写出文法G（S ）的预测分析表。 （15 分）解：消除左递归 aPS|*| 提取公因子后： |* PaSFIRST,FOLLOW 集：FIRST(S)=a,* FOLLOW(S)=#FIRST(P)=+ FOLLOW(P)=*,#FIRST(S)=*, FOLLOW(S)=#FIRST(P)=+, FOLLOW(P)= *,#4六 、文法 G(S)：S bTc S a T RR R/SR S该文法是
3、不是算符优先文法？请构造算符优先关系表并证实。 （15 分）5七、文法 GS，其产生式如下 fSePdcbaS|（1）是不是 LL(1)文法。（2）是不是 SLR(1)文法。请予以证实。要求构造识别活前缀的 DFA.(20 分）6八、 已知文法 GS及其 LR 分析表如下，请给出字符串 baba#的分析过程。(15 分)GS: (1) S DbB (2) Dd (3) D 7(4) Ba (5) B Bba (6) B文法 GS的 LR 分析表ACTION GOTO状态b d a # S B D0 R3 S3 1 21 acc2 S43 R24 R6 S5 R6 65 R4 R46 S7 R17 S88 R5 R50
