資源描述:
《編譯原理習(xí)題解答》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、編譯原理習(xí)題解答頁30/30第二章:習(xí)題2-4Table表varx,y;procedurep;vara;procedureq;varb;beginb:=10;end;procedures;varc,d;procedurer;vare,f;begincallq;end;begincallr;end;begincalls;end;begincallp;end根據(jù):Page289,變量table:array[0..txmax]ofrecord結(jié)構(gòu)體以及block函數(shù)得到下表,而表中各部分的含義,見教材Page18,Page19Na
2、meKinkVal/LevelAdrSizexvariable030yvariable040pprocedur010avariable130qprocedur134sprocedur170cvariable230dvariable240rprocedur200編譯原理習(xí)題解答頁30/30第三章文法和語言5.寫一文法,使其語言是偶正整數(shù)的集合要求:(1)允許0打頭(2)不允許0打頭解:(1)G[S]=({S,P,D,N},{0,1,2,…,9},P,S)P:SàPD
3、DP->NP
4、NDà0
5、2
6、4
7、6
8、8N->0
9、1
10、2
11、3
12、
13、4
14、5
15、6
16、7
17、8
18、9(2)G[S]=({S,P,R,D,N,Q},{0,1,2,…,9},P,S)P:SàPD
19、P0
20、DP->NR
21、NR->QR
22、QDà2
23、4
24、6
25、8N->1
26、2
27、3
28、4
29、5
30、6
31、7
32、8
33、9Q->0
34、1
35、2
36、3
37、4
38、5
39、6
40、7
41、8
42、96.已知文法G:<表達(dá)式>::=<項(xiàng)>
43、<表達(dá)式>+<項(xiàng)>
44、<表達(dá)式>-<項(xiàng)><項(xiàng)>::=<因子>
45、<項(xiàng)>*<因子>
46、<項(xiàng)>/<因子><因子>::=(<表達(dá)式>)
47、i。試給出下述表達(dá)式的推導(dǎo)及語法樹。(1)i;(2)(i)(3)i*i;(4)i*i+i;(5)i+(i+i);(
48、6)i+i*i。解:(1)v=<表達(dá)式>=><項(xiàng)>=><因子>=>i=w(2)v=<表達(dá)式>=><項(xiàng)>=><因子>=>(<表達(dá)式>)=>(<項(xiàng)>)=>(<因子>)=>(i)=w(3)v=<表達(dá)式>=><項(xiàng)>=><項(xiàng)>*<因子>=><因子>*<因子>=>i*i=w(4)v=<表達(dá)式>=><表達(dá)式>+<項(xiàng)>=><項(xiàng)>+<項(xiàng)>=><項(xiàng)>*<因子>+<項(xiàng)>=><因子>*<因子>+<因子>=>i*i+i=w(5)v=<表達(dá)式>=><表達(dá)式>+<項(xiàng)>=><項(xiàng)>+<項(xiàng)>=><因子>+<因子>=>i+(<表達(dá)式>)=>i+(<表達(dá)式>+<項(xiàng)
49、>)=>i+(<項(xiàng)>+<項(xiàng)>)=>i+(<因子>+<因子>)=>i+(i+i)=w(6)v=<表達(dá)式>=><表達(dá)式>+<項(xiàng)>=><項(xiàng)>+<項(xiàng)>=><因子>+<項(xiàng)>=>i+<項(xiàng)>=>i+<項(xiàng)>*<因子>=>i+<因子>*<因子>=>i+i*i=w語法樹見下圖:編譯原理習(xí)題解答頁30/307.為句子i+i*i構(gòu)造兩棵語法樹,從而證明下述文法G[<表達(dá)式>]是二義的。<表達(dá)式><項(xiàng)><因子>i<表達(dá)式><項(xiàng)><因子>(<表達(dá)式>)<項(xiàng)><因子>i<表達(dá)式><項(xiàng)><項(xiàng)>*<因子><因子>ii<表達(dá)式><表達(dá)式>+<項(xiàng)><項(xiàng)><項(xiàng)>*
50、<因子><因子>ii<因子>i<表達(dá)式><表達(dá)式>+<項(xiàng)><項(xiàng)><因子>i<因子>(<表達(dá)式>)<表達(dá)式>+<項(xiàng)><項(xiàng)><因子>i<因子>i<表達(dá)式><表達(dá)式>+<項(xiàng)><項(xiàng)><因子>i<項(xiàng)>*<因子><因子>ii(1)i(2)(i)(3)i*i(4)i*i+i(5)i+(i+i)(6)i+i*i<表達(dá)式>::=i
51、(<表達(dá)式>)
52、<表達(dá)式><運(yùn)算符><表達(dá)式><運(yùn)算符>::=+
53、-
54、*
55、/解:為句子i+i*i構(gòu)造的兩棵語法樹如下:<表達(dá)式><表達(dá)式>+<表達(dá)式>i<表達(dá)式>*<表達(dá)式>ii<表達(dá)式><表達(dá)式>*<表達(dá)式><表
56、達(dá)式>+<表達(dá)式>iii所以,該文法是二義的。編譯原理習(xí)題解答頁30/308.習(xí)題1中的文法G[S]是二義的嗎?為什么?答:是二義的。因?yàn)閷?duì)于句子abc可以有兩種不同的生成樹,即:S=>Ac=>abc和S=>aB=>abc11.令文法G[E]為:EàT
57、E+T
58、E-TTàF
59、T*F
60、T/FFà(E)
61、i證明E+T*F是它的一個(gè)句型,指出這個(gè)句型的所有短語、直接短語和句柄。解:可為E+T*F構(gòu)造一棵語法樹(見下圖),所以它是句型。EE+TT*F從語法樹中容易看出,E+T*F的短語有:T*F是句型E+T*F的相對(duì)于T的短語,也是
62、相對(duì)于規(guī)則TàT*F的直接短語。E+T*F是句型E+T*F的相對(duì)于E的短語。句型E+T*F的句柄(最左直接短語)是T*F。12.下述文法G[E]生成的語言是什么?給出該文法的一個(gè)句子,該句子至少含五個(gè)終結(jié)符,構(gòu)造該句子的語法樹。證明:是G[]的句