編譯原理練習三答案(共5頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上練習三9、考慮下面上下文無關(guān)文法：S>SS*|SS+|a（1）表明通過此文發(fā)如何生成串a(chǎn)a+a*,并為該串構(gòu)造推導樹。（2）該文法生成的語言是什么？答:（1）S=>SS*=>SS+S*=>aS+S*=>aa+S*=>aa+a*S=>SS*=>SS*S*=>SS*S*S*=>=>S(S*)=>Sa*(S*)=>aa*a*(S*)=>=>S(a*)=>SS+(a*)=>SS+S+(a*)=>SS+S+S+(a*)=>=>S(S+)(a*)=>a(S

2、+)(a*)=>aa+(S+) (a*)=>aa+a+(S+) (a*)=>a(a+)(a*)所以該文發(fā)生成的語言是：L1= a(a+)(a*)|n,m>=110、文法S->S(S)S|（1）生成的語言是什么？（2）該文發(fā)是二義的嗎？說明理由。答：（1）S=>S(S)S=>S(S(S)S)S=>=>S(S(S)S)S=>S(S)S(S(S)S)S=>S(S)S(S)S(S(S)S)S=>=>(S(S)S(S(S)S)S=>(S(S)S(S(S)S)S(S)S=>(S(S)S(S(S)S)S(S)S(S)S

3、=>=>(S(S)S(S(S)S) (S(S)S所以該文法生成的就是嵌套的括號。（2）由上面推導過程可知該語法可以構(gòu)成不同的語法樹，所以它是二義的。11、令文法GE為：E->T|E+T|E-TT->F|T*F|T/FF->(E)|i證明E+T*F是它的一個句型，指出這個句型的所有短語，直接短語和句柄。答：因為E=>E+T=>E+T*F，所以E+T*F是它的一個句型。因為E=>E+T=>E+T*F，所以該句型相對于E的短語有：E+T*F因為T-> T*F，所以該句型相對于T的短語有：T*F直接短語為：T*F句柄為：T*F13、一個上下文

4、無關(guān)文法生成句子abbaa的推導樹如下：（1） 給出該句子相應的最左推導，最右推導。（2） 該文法的產(chǎn)生式集合P可能有哪些元素？（3） 找出該句子的所有短語，簡單短語，句柄。答：（1） 最右推導：S=>ABS=>ABAa=>ABaa=>ASBBaa=>ASBbaa=>ASbbaa=>Abbaa=>Abbaa=>abbaa最左推導：S=>ABS=>aBS=>aSBBS=>aBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa（2） 產(chǎn)生式包括：S->ABS|Aa|

5、B->b|SBB A->a該文法的產(chǎn)生式集合P可能有 S=>S=>Aa=>aaS=>ABS=>aBS=>abS=>ab =>abS=>ABS=>ABAa=>aBAa=>abAa=>abaaS=>ABS=>ASBBS=>AAaBBS=>aAaBBS=>aaaBBS=>aaabBS=>aaabbS=>aaabb=>aaabb所以有 aa ab abaa aaabb （3）因為產(chǎn)生式包括：S->ABS|Aa| B->b|SBB A->aS=

6、>，是相對S的短語。S=>Aa=>aa，aa是相對S的短語。S=>ABS=>aBS=>aSBBS=>aBBS=>aBBS=>abBS=>abbS=>abbAa=>abbaa，abbaa是相對S的短語。A=>a，a是相對A的短語。B=>b，b是相對B的短語。B=>SBB=>BB =>bB=>bb，bb是相對B的短語。直接短語有：a，b，句柄：a14、給出生成下述語言的上下文無關(guān)文法：（1）abab|n,m>=0答：S->ASBS S->ASB S-> A->a

7、 B->bS=>ASBS=>aSBS=>aSbS=>aASBbS=>aaSbBS=>aaSbbS=>aaASbbBS=>aaaSbbBS=>aaaSbbbS=>=>aSbS=>abS=>abS=>abASB=> abaSB=> abaSb=>abaASBb=>abaaSBb=>abaaSbb=>=> abaSb=> abab=> abab推導得：L1=abab|n,m>=0（2）1010|n,m>=0答：S->1S0 S->A A->0A1 A->S=>1S0=>11S00=>