式。考虑满足条件的字符串中的1：在串的开始部分可以有0个或多个1，串的尾部也可以有0个或多个1，但串的中间只要出现1则至少在两个以上，所以满足条件的正规表达式为1*(0∣111*)*1*。 5 解： （1）、图（a）中为一个NFA，所以需要先对它进行确定化，得到DFA，然后再对DFA进行最小化。
首先进行确定化，如下两个表所示：
所求的DFA如下图所示：
1 0 S 0A 1 1 B
状态 a b {0} {0，1} {1} {0，1} {0，1} {1} {1} {0} ? 状态 a b 0 1 2 1 1 2 2 0 6
根据状态转换矩阵得到如下图所示的DFA：
a b a 2 0 1 b a 题意，该DFA接受的字符串由0和1组成，并且每个1的后面都有0直接跟在右边，因此，可以将该字符串理解为由0和10构成的串，则相应的正规表达式就是(0︱10)*。 第二步：构造NFA。首先得出下图：
化简后的DFA为：
X (0︱10)* Y
a b a 然后对上图进行分解后得到如下图所示的NFA。
2
2 0 1 X ε 1 ε 0 （2）、题中所给即为一个DFA，不需要确定化，只对它进行最小化即可。
首先将状态划分为两个集合{{0，1}，{2，3，4，5}}。有{0，1}a={1}，{0，1}b={2，4}和{2，3，4，5}a={1，3，0，5}，{2，3，4，5}b={2，3，4，5}，所以可以进一步划分为{{0，1}，{2，4}，{3，5}}，然后有{0，1}a={1}，{0，1}b={2，4}，{2，4}a={1，0}，{2，4}b={3，5}，{3，5}a={3，5}，{3，5}b={2，4}。因此，最后划分结果是{{0，1}，{2，4}，{3，5}}。
最小化后的DFA如下图所示：
a ba bb 0 第三步：确定化，得到DFA。确定化结果如表14.1所列；给状态编号，得到表14.2所示的状态转换矩阵：
a 1 2
0 6解：第一步：写出正规表达式。根据状态 0 {1，Y} {1，Y} {1，Y} 0 1 1 1 1 {2} {2} ? 1 2 2 {X，1，Y} {1，Y} {2} 状态 0 1 2 表14.1 状态转换矩阵 表14.2 新的状态转换矩阵
7
根据状态转换矩阵得到DFA如下图所示：
0 1 1 2
第四步：对该DFA进行最小化。其分析过程如下：
{0，1}，{2}
{0，1}0={1}，{0，1}1={2} {0，1}，{2}
最小化后的DFA如图所示，该DFA即为所求。
0 1 0 0 0 0 0 1 2 0 1 0 1 1 0 1 0 3 0 4 1 还可以对上图的DFA进行化简，状态3和4可以合并，化简后的DFA如下图所示：
0，1 0 0 0 1 S A 1 0 B T 1 1 1
对状态转换图进行确定化，得到状态转换矩阵：
状态 {S} {S，B} {S，A} {S，B，C，Z} {S，A，C，Z}
状态 0 1 2 3 4
1 3 1 3 3
不难看出，该DFA接受的语言是{0，1}0 上包含00或11的字符串。根据化简后的1 DFA，我们可以写出相应的左线性文法G’： {S，B} {S，A} T0∣T1 {S，B，C，Z} T→A0∣{SB1，∣A} A→B0∣{S，B} {S0 ，A，C，Z} {S，B，C，Z} B→A1∣{S1 ，A，C，Z} 卷 A，C，Z} {S，B，C，Z} 编译原理F{S，1、考虑下面的文法G1： 0 1 S→a∣∧∣2 (T) T→T，S∣S 2 （1）消去G1的左递归。然后对每个非4 终结符，写出不带回溯的递归子程序。
4 （2）经改写后的文法是否是LL(1)的？
4 给出它的预测分析表。 （2）计算每个非终结符的FIRST集合和FOLLOW集合：
FIRST（S）={a，∧，( } FIRST（T）={a，∧，( } FIRST（T’）={，，ε}
8
给状态编号，得到新的状态转换矩阵： 根据状态转换矩阵获得DFA如下：
FOLLOW（S）={ )，’，’，#} FOLLOW（T）={ ) } FOLLOW（T’）={ ) }
从而可见改造后的文法符合LL(1)文法的充分必要条件，所以是LL(1)的。
该文法的预测分析表 S T T’ a S->a T->S T’ ^ S->^ T->S T’ ( S->(T) T->S T’ （1） （2）
（3） （4）
2、对下面的文法G： E→TE’ E’→+E∣ε T→FT’ T’→T∣ε F→PF’
F’→*F’∣ε P→(E)∣a∣b∣∧
计算这个文法的每个非终结符
的FIRST和FOLLOW。
（1） 证明这个文法是LL(1)的。
构造它的预测分析表。
构造它的递归下降分析程序。
3、下面文法中，哪些是LL(1)的，说明
理由。 （1）、 S→Abc A→a∣ε B→b∣ε （2）、 S→Ab A→a∣B∣ε B→b∣ε
（1）
（3）、
（2） S→ABBA
A→a∣ε
（3） B→b∣ε
（4） （4）、
S→aSe∣B
B→bBe∣C C→cCe∣d 4、对下面文法： Expr→-Expr Expr→(Expr)∣Var ExprTail→-Expr∣ε Var→id VarTail ) , # VarTail→(Expr) ∣ε （、构造LL(1) 1） 分析表。 （2）、给出对句子id--id((id))T’->ξ T->,S T’ 的分析过程。
1、令文法G1为 E→E+T∣T T→T*F∣F F→(E)∣i
证明E+T*F是它的一个句型，指出这个
句型的所有短语，直接短语和句柄。 2、考虑下面的表格结构文法G2： S→a∣∧∣(T) T→T，S∣S
给出(a，(a，a))和(((a，a)，
∧，(a))，a)的最左和最右推导。
指出(((a，a)，^，(a))，a)的规范归约及
每一步的句柄。根据这个规范归约，给出“移进-归约”的过程，并给出它的语法树自下而上的构造过程。 3、（1）计算练习2文法G2的FIRSTVT和LASTVT。
（2）计算G2的优先关系。G2是一个算符优先文法吗？
（3）给出输入串（a，（a，a））的算符优先分析过程。 4、考虑文法： S→AS︱b A→SA︱a
列出这个文法的所有LR(0)项
目。
构造这个文法的LR(0)项目集
规范族及识别活前缀的DFA。
这个文法是SLR的吗？若是，
构造出它的SLR分析表。
这个文法是LALR或LR(1)的
9
吗？ F卷答案 1答：解：
（1）按照T、S的顺序消除左递归，得到文法：?
G’(S)
S→a∣∧∣(T) T→ST’
T’→，ST’ ∣ε
对于非终结符S,T, T’的递归子程序如下：
Procedure S; Begin
If sym = ‘a’ or sym = ‘^’
Then advance
Else if sym = ‘(‘ （2） Then begin Advance ; T;
If sym = ’)’
Then advance Else error End Else error Ends;
Procedure T; Begin
S; T’; Ends;
Procedure T’ Begin
If sym = ‘,’ Then begin
Advance ; S; T’ Ends ends; 2解： （3）1） 计算每个非终结符的FIRST集
合和FOLLOW集合如下：
FIRST（E）={(，a，b，∧} FIRST（E’）={+，ε} FIRST（T）={(，a，b，∧}
FIRST（T’）={(，a，b，∧，ε} FIRST（F）={(，a，b，∧} FIRST（F’）={*，ε} FIRST（P）={(，a，b，∧}
FOLLOW（E）={#，)} FOLLOW（E’）={#，)} FOLLOW（T）={+，)，#} FOLLOW（T’）={+，)，#}
FOLLOW（F）={(，a，b，∧，+，)，#} FOLLOW（F’）={(，a，b，∧，+，)，#}
FOLLOW（P）={*，(，a，b，∧，+，)，#}
本文法是LL ( 1 )文法。 证明： 通过观察可知文法中不含有
左递归，满足LL (1)文法定义的第一个条件。
考虑下列产生式：
E’→+E∣ε T’→T∣ε F’→*F’∣ε P→(E)∣a∣b∣∧ 因为： FIRST（+E）∩FIRST（ε）={+}∩{ε}=? FIRST（E’）∩FOLLOW（E’）={+}∩{#，)}= ?
FIRST（T）∩FIRST（ε）={(，a，b，∧}∩{ε}=?
FIRST（T’）∩FOLLOW（T’）={(，a，b，∧}∩{+，)，#}=?
FIRST（*F’）∩FIRST（ε）={*}∩{ε}=?
FIRST（F’）∩FOLLOW（F’）={*}∩{(，a，b，∧，+，)，#}= ? FIRST（（E））∩FIRST（a）∩FIRST（b）∩FIRST（∧）= ?
所以该文法是LL(1)文法。
构造其预测分析表：
10
（