資源描述：
《編譯原理習(xí)題解》由會員上傳分享，免費(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,Page19NameKinkVal/LevelAdrSi
2、zexvariable030yvariable040pprocedur010avariable130qprocedur134sprocedur170cvariable230dvariable240rprocedur200編譯原理習(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、4
13、5
14、6
15、7
16、8
17、9(2)G[S]=({S,P,R,D,N,Q},{0,1,2
18、,…,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);(6)i+i*i。解：(1)v=<表達(dá)式>=><項(xiàng)>=><因子>=>i=w(2)v=<表達(dá)式>=><項(xiàng)>=><因子>=>(
48、<表達(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)>)=>i+(<項(xiàng)>+<項(xiàng)>)=>i+(<因子>+<因子>)=>i+(i+i)=w(6)v=<表達(dá)式>=><表達(dá)式>+<項(xiàng)>=><項(xiàng)>+<項(xiàng)>=><因子>+<項(xiàng)
49、>=>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)>*<因子><因子>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)>*<因子>
50、<因子>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á)式><表達(dá)式>+<表達(dá)式>iii所以，該文法是二義的。編譯原理習(xí)題解答頁30/308.習(xí)題1中的文法G[S]是二義的嗎？為什么？答：是二義的。因?yàn)閷τ诰渥觓bc可以有兩種不同的生成樹，即：S=>Ac=>abc和S=>aB=>abc11.令文法G[E
56、]為：EàT
57、E+T
58、E-TTàF
59、T*F
60、T/FFà(E)
61、i證明E+T*F是它的一個句型，指出這個句型的所有短語、直接短語和句柄。解：可為E+T*F構(gòu)造一棵語法樹（見下圖），所以它是句型。EE+TT*F從語法樹中容易看出，E+T*F的短語有：T*F是句型E+T*F的相對于T的短語，也是相對于規(guī)則TàT*F的直接短語。E+T*F是句型E+T*F的相對于E的短語。句型E+T*F的句柄（最左直接短語）是T*F。12.下述文法G[E]生成的語言是什么？給出該文法的一個句子，該句子至少含五個終結(jié)符，構(gòu)造該句子的語法樹。證明：是G[<
62、E>]的句
