编译原理作业20150515(答案)概要.doc

第3章作业【编辑人：陈芳芳】 写一文法，使其语言是偶正整数的集合。要求： （1）允许0打头； （2）不允许0打头。 【解】： 允许0打头且含0的偶正整数集合的文法为： N—(0|D|E)N|(E|0) D—1|3|5|7|9 E—2|4|6|8 (2) 不允许0打头的偶正整数集合的文法为： R—(D|E)N|E N—(0|D|E)N|(E|0) D—1|3|5|7|9 E—2|4|6|8 (3) 允许0打头的偶正整数集合的文法为： S—0S|R R—(D|E)N|E N—(0|D|E)N|(E|0) D—1|3|5|7|9 E—2|4|6|8 2.一个上下文无关文法生成句子abbaa的推导树如下： S A B S a S B B A a ? b b a （1）给出该句子的相应的最左推导，最右推导。 （2）该文法的产生式集合P可能有哪些元素？ （3）找出该句子的所有短语，简单短语，句柄。 【解】： （1）最左推导： S=ABS=aBS=aSBBS=aBBS=abBS=abbS=abbAa=abbaa 最右推导： S=ABS=ABAa=ABaa=ASBBaa=ASBbaa=ASbbaa=Abbaa=abbaa (2) 产生式集合P： S—ABS | Aa| ? A—a B—SBB | b (3) 短语：a , ? , b , bb , aa , abbaa 直接短语：a , ? , b 句柄：a 3、给出生成下述语言的上下文无关文法： (1){anbnambm | n, m = 0} (2){1n0m1m0n | n, m = 0} 【解】： （1）S—AA A—aAb | ? （2）S—1S0 | A A—0A1 | ? 第4章课后作业 构造一个状态数最小的DFA，它接受∑={0,1}上所有倒数第二个字符为1的字符串。（编辑：张超） 解： ① 构造正规式：（0│1）* 1（0│1） ② 由正规式构造NFA： ③ NFA转化为DFA ： T0=ε－closure（{0}）={0} 用子集构造法求DFA状态，T0为初态，T2，T3为终态。 状态 ε－closure（move（Ti，0）） ε－closure（move（Ti，1）） T0={0} {0} {0,1} T1={0,1} {0,2} {0,1,2} T2={0,2} {0} {0,1} T3={0,1,2} {0,2} {0,1,2} 用0,1,2,3代表T0，T1，T2，T3，得到如下DFA ： ④最小化DFA ： P0=（{0,1}，{2,3}） P1=（{0}，{1}，{2}，{3}） ∴无等价状态。 ∵ 没有找到多余状态，∴ 无多余状态。 ∴ 上图为最小化的DFA。 2、将下图的NFA确定化为DFA，并最小化。（编辑：张超） 解：用子集构造法求DFA状态，T0为初态，T3为终态。 状态 ε－closure（move（Ti，a）） ε－closure（move（Ti，b）） T0={X，1，2} {1，2} {1，2，3} T1={1，2} {1，2} {1，2，3} T2={1，2，3} {1，2，Y} {1，2，3} T3={1，2，Y} {1，2} {1，2，3} 用0,1,2,3代表T0，T1，T2，T3，得到如下DFA ： 最小化： ①{0，1，2} {3} ②{0，1} {2} {3} ③{0，1} {2} {3} 0和1是等价的，∴ 得到最小化的DFA 如下 ： 第5-7章课后作业（含答案） 1、将文法G[S] 改写为等价的G′[S]，使G′[S]不含左递归和左公共因子。G[S]： S→bSAe|bA A→Abd | dc | a 【解】： G[S]：S→bS’ S’→SAe|A A→(dc|a)A’ A’ →bd A’ |ε 2、有文法G[S]：S→ABf A→BbS|e B→dAg|ε 证明文法G是LL(1)文法，并构造预测分析表 【解】： ①计算FIRST、FOLLOW、SELECT集 产生式 FIRST FOLLOW SELECT 左部 右部 S ABf d b e # g d f d b e A