编译原理-复习.doc

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

3.写出表达式(a+b)/(a-b-(a+b*c)的三元序列及四元序列。
解：（1）三元式：①（＋，a，b）②（－，a，b）③（/，①，②）④（*，b，c）⑤（＋，a，④） ⑥（－，③，⑤）（2）四元式： ①（＋，a，b，T1）②（－，a，b，T2）③/，T1，T2，T3）④（*，b，c，T4）⑤（＋，a，T4，T5）⑥（－，T3，T5，T6）

4.写一个文法使其语言为偶数集，且每个偶数不以0开头。
解：文法G（S）：S→AB|B|A0A→AD|CB→2|4|6|8C→1|3|5|7|9|BD→0|C
5.设文法G（S）：S→S＋aF|aF|＋aFF→*aF|*a （1）消除左递归和回溯；
（2）构造相应的FIRST和Follow集合。
1） S->aFS'|＋aFS
'S'->＋aFS'|ε
F->*aF'
F'->F|ε
（2） FIRST（S）＝｛a，+｝FOLLOW（S）＝｛＃｝FIRST（S'）＝｛+，ε｝FOLLOW（S'）＝｛＃｝FIRST（F）＝｛*｝FOLLoW（F）＝（+，＃｝FIRST（F'）＝｛*，ε｝FOLLOW（+，＃｝五.计算题（10分）
已知文法为：S->a|^|(T) T->T,S|S 构造它的LR(0)分析表。
解：加入非终结符S'，方法的增广文法为：
S'->S
S->a
S->^
S->(T)
T->T,S
T->S
下面构造它的LR(0)项目集规范族为：

从上表可看出,不存在移进-归约冲突以及归约归约冲突，该文法是LR(0)
文法。从而有下面的LR(0)分析表：