清华大学：《编译原理》课程教学资源_第四章练习答案

练习参考答案 第1题 (1)允许0开头的偶正整数集合的文法 E->NTD T>NTD N->D)13|579 D->02468 (2)不允许0开头的偶正整数集合的文法 E->NTD T->FTG N->D13579 D->2468 F->N|0 G->D0

练习参考答案 第1题 (1)允许0开头的偶正整数集合的文法 E->NT|D T->NT|D N->D|1|3|5|7|9 D->0|2|4|6|8 (2)不允许0开头的偶正整数集合的文法 E->NT|D T->FT|G N->D|1|3|5|7|9 D->2|4|6|8 F->N|0 G->D|0

练习参考答案 第2题 可为句子a+a*a构造两个不同的最右推导: 最右推导1〈表达式〉→〈表达式〉〈运算符〉〈表达式 →〈表达式〉〈运算符〉a 〈表达式〉*a 〈表达式〉〈运算符〉〈表达式 →〈表达式〉〈运算符〉a*a 〈表达式〉+a*a a +aN 最右推导2〈表达式〉→〈表达式〉〈运算符〉〈表达式 〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式 〈表达式〉〈运算符〉〈表达式〉〈运算符〉a 〈表达式〉〈运算符〉〈表达式〉动a →〈表达式〉〈运算符〉a*a 〈表达式)+a*a

练习参考答案 第2题 可为句子a+a*a构造两个不同的最右推导: 最右推导1 〈表达式〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉a 〈表达式〉* a 〈表达式〉〈运算符〉〈表达式〉* a  〈表达式〉〈运算符〉a * a 〈表达式〉+ a * a  a + a * a 最右推导2 〈表达式〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉 〈表达式〉〈运算符〉〈表达式〉〈运算符〉a 〈表达式〉〈运算符〉〈表达式〉* a  〈表达式〉〈运算符〉a * a 〈表达式〉+ a * a  a + a * a

练习参考答案 第3题,GE|为: E→>E+T|E-T T->T*FT FF F->(EI 因为存在推导序列:E→E+T→E+TF所以 E+TF句型 句型E+TF的 短语有E+TF,T*F 直接短语有:TF 句柄为:T*F

练习参考答案 第3题，G[E]为: E->E+T|E-T T->T*F|T/F|F F->(E)|I 因为存在推导序列: E  E+T  E + T * F 所以 E+T*F句型 句型 E+T*F的 短语有:E+T*F,T*F 直接短语有:T*F 句柄为:T*F

第4题 练习参考答案 (1){a"b"ab叫n,m>=0 (2){10m1吗0叫n,m>=0} S->AA S->IS0JA A->aAble A->0A1|E 第5题, (1){a"b叫n,m>=1}的三型文法为 S->aA A->aAB B->bblb (2){ aback,m,k>=0}的三型文法为: A->aAB B->bBC C->cCa 第6题 R=(01|10)(0110)

第4题 练习参考答案 （1）{ a nb na mb m| n，m>=0} (2) { 1n0 m 1 m0 n | n，m>=0} S->AA S->1S0|A A->aAb|ε A->0A1|ε 第5题， (1){ a nb m|n,m>=1 }的三型文法为： S->aA A->aA|B B->bB|b (2){anb mc k |n,m,k>=0 }的三型文法为: A->aA|B B->bB|C C->cC|ε 第6题 R = (01 | 10) ( 01 | 10 )*