资源描述：
《编译原理习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章：习题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根据：Page289，变量table:array[0..txmax]ofrecord结构体以及block函数得到下表，而表中各部分的含义，见教材Page18,Page19NameKinkVal/LevelAdrSizexvariabl
2、e030yvariable040pprocedur010avariable130qprocedur134sprocedur170cvariable230dvariable240rprocedur200第三章文法和语言5.写一文法，使其语言是偶正整数的集合要求：(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,…,9},P,S)P:SàPD
18、P0
19、
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：<表达式>::=<项>
43、<表达式>+<项>
44、<表达式>-<项><项>::=<因子>
45、<项>*<因子>
46、<项>/<因子><因子>::=(<表达式>)
47、i。试给出下述表达式的推导及语法树。(1)i;(2)(i)(3)i*i;(4)i*i+i;(5)i+(i+i);(6)i+i*i。解：(1)v=<表达式>=><项>=><因子>=>i=w(2)v=<表达式>=><项>=><因子>=>(<表达式>)=>(<项>)=>(
48、<因子>)=>(i)=w(3)v=<表达式>=><项>=><项>*<因子>=><因子>*<因子>=>i*i=w(4)v=<表达式>=><表达式>+<项>=><项>+<项>=><项>*<因子>+<项>=><因子>*<因子>+<因子>=>i*i+i=w(5)v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<因子>=>i+(<表达式>)=>i+(<表达式>+<项>)=>i+(<项>+<项>)=>i+(<因子>+<因子>)=>i+(i+i)=w(6)v=<表达式>=><表达式>+<项>=><项>+<项>=><因子>+<项>=>i+<项>=>i+
49、<项>*<因子>=>i+<因子>*<因子>=>i+i*i=w语法树见下图:7.为句子i+i*i构造两棵语法树，从而证明下述文法G[<表达式>]是二义的。<表达式><项><因子>i<表达式><项><因子>(<表达式>)<项><因子>i<表达式><项><项>*<因子><因子>ii<表达式><表达式>+<项><项><项>*<因子><因子>ii<因子>i<表达式><表达式>+<项><项><因子>i<因子>(<表达式>)<表达式>+<项><项><因子>i<因子>i<表达式><表达式>+<项><项><因子>i<项>*<因子><因子>ii(1)i(2)(i)(3)i*i
50、(4)i*i+i(5)i+(i+i)(6)i+i*i<表达式>::=i
51、(<表达式>)
52、<表达式><运算符><表达式><运算符>::=+
53、-
54、*
55、/解：为句子i+i*i构造的两棵语法树如下：<表达式><表达式>+<表达式>i<表达式>*<表达式>ii<表达式><表达式>*<表达式><表达式>+<表达式>iii所以，该文法是二义的。8.习题1中的文法G[S]是二义的吗？为什么？答：是二义的。因为对于句子abc可以有两种不同的生成树，即：S=>Ac=>abc和S=>aB=>abc11.令文法G[E]为：EàT
56、E+T
57、E-TTàF
58、T*F
59、T/FFà(E)
60、i
61、证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。解：可为E+T*F构造一棵语法树（见下图），所以它是句型。EE+TT*F从语法树中容易看出，E+T*F的短语有：T*F是句型E+T*F的相对于T的短语，也是相对于规则TàT*F的直接短语。E+T*F是句型E+T*F的相对于E的短语。句型E+T*F的句柄（最左直接短语）是T*F。12.下述文法G[E]生成的语言是什么？给出该文法的一个句子，该句子至少含五个终结符，构造该句子的语法树。证明：是G[]的句型，并指出该句型的所有短语、直接短语和句柄。<
62、E>à
63、à
