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 ：

）