编译原理_复习题.pdf

.word 可编辑.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)的.专业.专注.word 可编辑.已知文法为：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)分析表为：.专业.专注.word 可编辑.对输入 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+*+构造下述文法 GS 的自动机：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:.专业.专注.word 可编辑.由上表可知 DFA3.写出表达式(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）：SAB|B|A0AAD|CB2|4|6|8C1|3|5|7|9|BD0|C5.设文法 G（S）：SSaF|aF|aFF*aF|*a（1）消除左递归和回溯；（2）构造相应的 FIRST 和 Follow 集合。1）S-aFS|aFSS-aFS|F-*aFF-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-SS-aS-S-(T)T-T,ST-S下面构造它的 LR(0)项目集规范族为：.专业.专注.word 可编辑.从上表可看出,存在移进-归约冲突以及归约归约冲突，该文法是LR(0)文法。从而有下面的 LR(0)分析表：.专业.专注.