文档介绍：3. 文法: S->MH|a H ->LSo| ε K ->dML| ε L ->eHf M->K|bLM 
判断 G 是否为 LL(1) 文法,如果是,构造 LL(1) 分析表。 解:各符号的 FIRST 集和 FOLLOW集为: 
        
各产生式SELECT集为: 
 SELECT S->MH {d,b,e,#,o} S->a {a} H ->LSo {e} H ->ε {#,f,o} K ->dML {d} K ->ε {e,#,o} L ->eHf {e} M->K {d,e,#,o} M-> bLM {b} 
 
预测分析表 
 
由于预测分析表中无多重入口,所以可判定文法是 LL(1)的
已知文法为:A ->aAd|aAb| ε      判断该文法是否是 SLR(1) 文法,若是构造相应分析表
,并对输入串 ab# 给出分析过程。
解:增加一个非终结符 S/后,产生原文法的增广文法有: S'->A A ->aAd|aAb|ε 下面构造它的 LR(0)项目集规范族为:     
 
 
从上表可看出,  状态 I0 和 I2 存在移进- 归约冲突,该文法不是 LR(0)文法。对于 I0 来说有:    FOLLOW(A)∩{a}={b,d,#}∩{a}=Φ ,所以在 I0 状态下面临输入符号为 a 时移进,为 b,d,#时   归约,为其他时报错。对于 I2 来说有也有与 I0 完全相同的结论。这就是说,以上的移 - 归冲突是可以解决的,因此该文法是 SLR(1)文法。   其 SLR(1)分析表为:
 
 
 
对输入串 ab#给出分析过程为: 
 
 
 
对给定正规式b*(d|ad)(b|ab)+,构造其NFA M;
解答:首先用A+=AA*改造正规式得:b*(d|ad)(b|ab)(b|ab)*;其次,构造该正规式的NFA M,如图3-6-7所示。
 
试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。 
解: w a b + c d e 10 - / + 8 + * + 
构造下述文法  G[S] 的自动机:  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的重复输入,所以上图只是NFA,面将它确定化: 下表由子集法将NFA转换为 DFA:  
]
  由上表可知DFA
(a+b)/(a-b-(a+b*c)的三元序列及四元序列。
解:(1)三元式:①(+,a,b)②(-,a,b)③(/,①,②)④(*,b,c)⑤(+,a,④) ⑥(-,③,⑤)(2)四元式: ①(+,a,b