发布时间 : 星期四 文章编译原理期末复习题(含答案2011-5)更新完毕开始阅读
E->Aa(2)|Bb(3) A->cA(4)|d(5) B->cB|d
构造其LR（0）分析表并利用此分析表判断符号串acccd是否是该文法的句子。 8、对下列文法：
S’->S S->bRST S->bR R->dSa
R->e T->fRa T->f
(1)出非终结符的FIRST和FOLLOW的集合。 （2）构造该文法的SLR（1）分析表。
9、给定文法 G[S] ：
S → SaA | a A → AbS | b
⑴ 请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。 ⑵ 请构造该文法的 LR(0) 分析表。
⑶ 什么是 LR(0) 文法？该文法是 LR(0) 文法吗？为什么？ ⑷ 什么是 SLR(1) 文法？该文法是 SLR(1) 文法吗？为什么？
10、构造下列文法的LR（1）分析表，其中S’ 是文法的开始符号。
S’->S
S->Aa|dAb|Bb|dBa A->c B->c
11、对下面的文法G：
S’->bAAB|bA A->dSa|b B->cAa|c
（1）判断此文法是下列文法中的哪一种？并说明理由。 LR（0）、SLR（1）、LALR（1）、LR（1） （2）构造相应文法的项目集族和分析表。 12、对下面的文法G[S]：
(6)
(7)
S->aBc|bAB A->aAb|b B->b|ε
构造其LL（1）分析表，并利用符号栈分析符号串baabbb是否是该文法的句子。
13、对下面的文法G：
E->E+T|T T->T*F|F F->(E)|I
(1)构造其消除直接左递归后的文法G’；
（2）构造文法G’ 的LL（1）分析表，并利用符号栈分析符号串i1*i2+i3是否是该文法的句子。 14、对下面的文法G：
P->begind;Xend X->d;X|sY Y->;sY|ε
构造文法G’ 的LL（1）分析表 15、对下面的文法G：
E->TE’ E’->+E|ε T->FT’ T’->T|ε F->PF’ F’->*F’|ε P->(E)|a|b|Λ
(1)计算这个文法的每个非终结符的FIRST和FOLLOW集合； （2）证明这个文法是LL（1）的； （3）构造它的预测分析表； （4）构造它的递归下降分析程序。 16、对文法G(S)：
S ? S ? a T | a T | ? a T T ? ? a T | ? a
(1) 消除该文法的左递归和提取左公因子； (2) 构造各非终结符的FIRST和FOLLOW集合；
(3) 构造该文法的LL(1)分析表，并判断该文法是否是LL(1)的。 17、设字母表∑={ a，b}，给出∑上的一个正则式b*abb*(abb*)。 （1）构造该正则式所对应的NFA（画出转换图）； （2）将所求的NFA确定化（画出DFA的转换图）； （3）将所求出的DFA最小化（画出极小化后的转换图）； （4）该正则式所表示的正则集是什么？试用自然语言描述之。 18、设字母表∑={ a，b}，给出∑上的一个正则式（a *|b*）b(ba)*。 （1）构造该正则式所对应的NFA（画出转换图）； （2）将所求的NFA确定化（画出DFA的转换图）； （3）将所求出的DFA最小化（画出极小化后的转换图）；
19、设有语言 L= {α | α ∈ {0,1} + ，且α不以 0 开头，但以 00 结尾 } 。 ⑴ 试写出描述 L 的正规表达式；
⑵ 构造识别 L 的 DFA （要求给出详细过程，并画出构造过程中的 NDFA、DFA 的状态转换图，以及 DFA 的形式化描述 ) 。
20、设字母表∑={ a，b}，给出∑上的一个正则式（a|b）*（aa|bb）（a|b）*。 （1）构造该正则式所对应的NFA（画出转换图）； （2）将所求的NFA确定化（画出DFA的转换图）； （3）将所求出的DFA最小化（画出极小化后的转换图）；
21、设字母表∑={ a，b}，给出∑上的一个正则式（a|b）*a（a|b）。 （1）构造该正则式所对应的NFA（画出转换图）； （2）将所求的NFA确定化（画出DFA的转换图）； （3）将所求出的DFA最小化（画出极小化后的转换图）；
22、设有语言 L={ α | α∈ {0,1} + ，且α不以 0 开头，但以 00 结尾 } 。 ⑴试写出描述 L 的正规表达式；
⑵构造识别 L 的 DFA （要求给出详细过程，并画出构造过程中的 NDFA 、 DFA 的状态转换图，以及 DFA 的形式化描述 ) 。 答：（ 1 ）正规表达式： 1(0|1) * 00 （ 2 ）第一步：将正规表达式转换为 NDFA
第二步：将 NDFA 确定化为 DFA ：
造表法确定化（ 3 分） 确定化后 DFA M 的状态转换表 状态 输入 I 0 I 1 t 0 1 [S] — [A,D,B] q 0 — q 1 [A,D,B] [D,B,C] [D,B] 重新命名 q 1 q 2 q 3 [D,B,C] [D,B,C,Z] [D,B] q 2 q 4 q 3 [D,B] [D,B,C] [D,B] q 3 q 2 q 3 [D,B,C,Z] [D,B,C,Z] [D,B] q 4 q 4 q 3 DFA 的状态转换图
第三步：给出 DFA 的形式化描述
DFA M = （ { q 0 , q 1 , q 2 , q 3 , q 4 }, {0,1}, t, q 0 , { q 4 } t 的定义见 M 的状态转换表。
23、给定文法 G[S] ： S → SaA|a A → AbS|b
⑴请构造该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 。 ⑵请构造该文法的 LR(0) 分析表。
⑶什么是 LR(0) 文法？该文法是 LR(0) 文法吗？为什么？ ⑷什么是 SLR(1) 文法？该文法是 SLR(1) 文法吗？为什么？ 答： （1）拓广文法：
G[S′]: S′→ S ⑴ S → SaA ⑵ S → a ⑶ A → AbS ⑷ A → b ⑸
该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA ：
）