编译原理习题课剖析.ppt

习题课 令文法G[E]为: E→T?E+T?E-T T→F?T*F?T/F F→(E)?i证明E+T*F是它的句型,指出这个句型的所有短语、直接短语和句柄 E?E+T?E+T*F 短语： E+T*F和T*F 直接短语： T*F 句柄： T*F E E + T T * F 一个上下文无关文法生成的句子abbaa的推导树如图。（1）给出该句子的相应的最左推导和最右推导（2）该文法的产生式集合P可能有哪些元素？（3）找出该句子的所有的短语、简单短语、句柄。 S?ABS?aBS?aSBBS ?a?BBS ?a?bBS?a?bbS?a?bbAa?a?bbaa 最左推导 最右推导略 产生式集合： S→ABS B→SBB S→Aa S→? B→b A→a 短语、句柄 S A B S a S B B A a ? b b a 习题解答 7．给文法G[S]： S?aA|bQ A?aA|bB|b B?bD|aQ Q?aQ|bD|b D?bB|aA E?aB|bF F?bD|aE|b 构造相应的最小的DFA。 由于从S出发任何输入串都不能到达状态E和F，所以，状态E，F为多余的状态，不予考虑。 a Z S A D Q B b b b a b a b b b a a 简化产生式后生成的NFA I Ia = ε-closure(MoveTo(I,a)) Ib = ε-closure(MoveTo(I,b)) 1[S] 2[A] 3[Q] 2[A] 2[A] 4[B,Z] 3[Q] 3[Q] 5[D,Z] 4[B,Z] 3[Q] 6[D] 5[D,Z] 2[A] 7[B] 6[D] 2[A] 7[B] 7[B] 3[Q] 6[D] 因为4,5状态包含Z,所以都是终态,1,2,3,6,7都是非终态; 1态输入b后为3,是非终态;2和3输入b后为4和5是终态,所以1和2,3是不同的状态; 2和3是相同等价状态;4和5是等价状态;6何是等价状态; 所以,最后剩下:1,2,4,6四个状态. a 6 2 b a a 1 b a b b 4 最小化的DFA 1 2 4 3 7 6 a b b a a 5 b a b a b a b b a 8.给出下述文法所对应的正规式 S?0A|1B A?1S|1 B?0S|0 将 A?1S|1 和 B?0S|0 分别代入 S?0A|1B 得: S=01S|01 S=10S|10 得产生式:S=01S|10S|01|10 化简得: S=(01|10) S | (01|10) S=(01|10)*(01|10) 得正规式: (01|10)*(01|10) 将图4.18的DFA最小化，并用正规式描述它所识别的语言： a 7 2 b c b d b 1 3 4 c 6 a a b b d 5 b 因为6，7是DFA的终态，其他是非终态，可将状态集分成两个子集：P1={1，2，3，4，5}，P2={6，7}。 由于F(6,b)=F(7,b)=6,而6，7又没有其他输入，所以6，7等价。 由于F(3,c)=F(4,c)=3,F(3,d)=F(4,d)=5,F(3,b)=6,F(4,b)=7,而6，7等价，所以3,4等价。 由于F(1,b)=F(2,b)=2,F(1,a)=3,F(2,a)=4,而3，4等价，所以1,2等价。 由于状态5没有输入字符b,所以与1，2，3，4都不等价。 综上所述，上图DFA的状态可最细分解为：P={{1，2}，{3，4}，{5}，{6，7}}。 a b b 1 3 c 6 b d 5 a 最小化后的DFA 该DFA用正规式表示为： b*a(c|da)*bb* 习题解答 2．对下面的文法G： E?TE’ E’?+E|ε T?FT’ T’?T|ε F?PF’ F’?*F’|ε P?(E)|a|b|^ 计算这个文法的每个非终结符的FIRST集和FOLLOW集。 证明这个方法是LL(1)的。 构造它的预测分析表。 S为文法开始符号，#一定是FOLLOW（S）元素 设A ??B?是一个产生式，则First(?)的非空元素 属于FOLLOW（B） 如果??*ε，则FOLLOW（A）的元素就要加入到 FOLLOW（B）中，因为： D ??1A?1 A ??B? 两个产生式，在推导过程中，可能会出现这样的句型 S?*…?1A?1… ? *…?1?B??1…? *…?1?B?1… 计算每个非终结符的FIRST和FOLLOW集合 非终结符 FIRST集合 FOLLOW集合 E (,a,b,^ ),# E’ +,ε ),# T (,a,b,^ +,),# T‘ (,a,b,^,ε +,),# F (,a,b,^ (,a,b,^,+,),# F’ *,ε