📄 编译原理-课后习题.doc
字号:
<p>状态矩阵是：<span lang=EN-US><img width=237 height=150 id="_x0000_i1032"
src="编译原理-课后习题.files\a03-08.jpg"></span></p>
<p>记<span lang=EN-US>[S]=q0 [B]=q1 [A B]=q2 [S A]=q3 ,最小化和确定化后如图</span></p>
<p><span lang=EN-US><img width=497 height=148 id="_x0000_i1033"
src="编译原理-课后习题.files\a03-09.jpg"></span></p>
<p>（<span lang=EN-US>2）记 [S]=q0, [A]=q1,[B S]=q2 最小化和确定化后的状态转换图如下</span></p>
<p><span lang=EN-US><img width=435 height=93 id="_x0000_i1034"
src="编译原理-课后习题.files\a03-10.jpg"></span></p>
<p><span lang=EN-US>13 （1）将具有ε动作的NFA确定化后，其状态转换图如图：</span></p>
<p>记<span lang=EN-US> { S0,S1,S3}=q0 {S1}=q1 {S2 S3}=q2 {S3}=q3 </span></p>
<p><span lang=EN-US><img width=422 height=231 id="_x0000_i1035"
src="编译原理-课后习题.files\a03-11.jpg"></span></p>
<p><span lang=EN-US>(2) 记{S}=q0 {Z}=q1 {U R}=q2 {S X}=q3 {Y U R}=q4 {X S U}=q5
{Y U R Z}=q6 {Z S}=q7</span></p>
<p><span lang=EN-US><img width=615 height=258 id="_x0000_i1036"
src="编译原理-课后习题.files\a03-12.jpg"></span></p>
<p><span lang=EN-US>14（1）从略</span></p>
<p><span lang=EN-US>(2)化简后S0和S1作为一个状态，S5和S6作为一个状态。</span></p>
<p>状态转换图如图</p>
<p><span lang=EN-US><img width=427 height=246 id="_x0000_i1037"
src="编译原理-课后习题.files\a03-13.jpg"></span></p>
<p><span lang=EN-US>15从略。</span></p>
<p><span lang=EN-US>16从略。</span></p>
<ul type=disc>
<li class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;
mso-list:l1 level1 lfo3;tab-stops:list 36.0pt'><span lang=EN-US>(1) r*表示的正规式集是{ε,r,rr,rrr,…}
</span></li>
</ul>
<p><span lang=EN-US>(ε|r)*表示的正规式集是{ε, εε,…}∪{r,rr,rrr,…}={ε,r,rr,rrr,…}</span></p>
<p><span lang=EN-US>ε|rr*表示的正规式集是{ε,r,rr,rrr,…}</span></p>
<p><span lang=EN-US>(r*)*=r*={ε,r,rr,rrr,…}</span></p>
<p>所以四者是等价的。</p>
<p><span lang=EN-US>(2)（rs）*r表示的正规式集是{ε,rs,rsrs,rsrsrs,…}r
={r,rsr,rsrsr,rsrsrsr,…}</span></p>
<p><span lang=EN-US>r(sr)* 表示的正规式集是r{ε,sr,srsr,srsrsr,…} ={
r,rsr,rsrsr,rsrsrsr,…}</span></p>
<p>所以两者等价。</p>
<p><span lang=EN-US>18 写成方程组</span></p>
<p><span lang=EN-US>S=aT+aS(1)</span></p>
<p><span lang=EN-US>B=cB+c(2)</span></p>
<p><span lang=EN-US>T=bT+bB(3)</span></p>
<p>所以<span lang=EN-US>B=c*cT=b*bc*c</span></p>
<p><span lang=EN-US>S=a*ab*bc*c</span></p>
<ul type=disc>
<li class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;
mso-list:l2 level1 lfo4;tab-stops:list 36.0pt'><span lang=EN-US>G1: </span></li>
</ul>
<p><span lang=EN-US>S=aA+B(1) </span></p>
<p><span lang=EN-US>B=cC+b(2)</span></p>
<p><span lang=EN-US>A=abS+bB (3)</span></p>
<p><span lang=EN-US>C=D(4)</span></p>
<p><span lang=EN-US>D=bB+d(5)</span></p>
<p>把（<span lang=EN-US>4）（5）代入（2），得B＝c(bB+d)+b=cbB+cd+b 得B=(cb)*(cd|b),代入（3）得</span></p>
<p><span lang=EN-US>A=abS+b(cb)*(cd|b)把它打入（1）得</span></p>
<p><span lang=EN-US>S=a(abS+b(cb)*(cd|b))+ (cb)*(cd|b)</span></p>
<p><span lang=EN-US>=aabS+ab(cb)*(cd|b) + (cb)*(cd|b)</span></p>
<p><span lang=EN-US>=(aab)*( ab(cb)*(cd|b)| (cb)*(cd|b))</span></p>
<p><span lang=EN-US>G2:</span></p>
<p><span lang=EN-US>S=Aa+B (1)</span></p>
<p><span lang=EN-US>A=Cc+Bb (2)</span></p>
<p><span lang=EN-US>B=Bb+a(3)</span></p>
<p><span lang=EN-US>C=D+Bab(4)</span></p>
<p><span lang=EN-US>D=d(5)</span></p>
<p>可得<span lang=EN-US> D=dB=ab*C=ab*ab|bA=(ab*ab|b)c + ab*b</span></p>
<p><span lang=EN-US>S=(ab*ab|b)ca+ab*ba +ab*</span></p>
<p><span lang=EN-US>=(ab*ab|b)ca| ab*ba| ab*</span></p>
<p><span lang=EN-US>20</span></p>
<ul type=disc>
<li class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;
mso-list:l4 level1 lfo5;tab-stops:list 36.0pt'>识别此语言的正规式是<span lang=EN-US>S=’LABEL’d(d|,d)*;
</span></li>
<li class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;
mso-list:l4 level1 lfo5;tab-stops:list 36.0pt'>从略。 </li>
</ul>
<p><span lang=EN-US>21 从略。</span></p>
<p><span lang=EN-US>22 构造NFA</span></p>
<p><span lang=EN-US><img width=561 height=168 id="_x0000_i1038"
src="编译原理-课后习题.files\a03-14.jpg"></span></p>
<p>其余从略。 </p>
<p><span lang=EN-US>23 下面举一个能够识别1,2,3,10,20,100的例子，读者可以推而广之。</span></p>
<p><span lang=EN-US>%{</span></p>
<p><span lang=EN-US>#include <stdio.h></span></p>
<p><span lang=EN-US>#include <string.h></span></p>
<p><span lang=EN-US>#include <ctype.h></span></p>
<p><span lang=EN-US>#define ON1</span></p>
<p><span lang=EN-US>#define TW 2</span></p>
<p><span lang=EN-US>#define THRE 3</span></p>
<p><span lang=EN-US>#define TE 10</span></p>
<p><span lang=EN-US>#define TWENT 20</span></p>
<p><span lang=EN-US>#define HUNDRE 100</span></p>
<p><span lang=EN-US>#define WHITE9999</span></p>
<p><span lang=EN-US>%}</span></p>
<p><span lang=EN-US>upper[A-Z]</span></p>
<p><span lang=EN-US>%%</span></p>
<p><span lang=EN-US>ONEreturn ON;</span></p>
<p><span lang=EN-US>TWOreturn TW;</span></p>
<p><span lang=EN-US>THREEreturn THRE;</span></p>
<p><span lang=EN-US>TENreturn TE;</span></p>
<p><span lang=EN-US>TWENTYreturn TWENT;</span></p>
<p><span lang=EN-US>HUNDREDreturn HUNDRE;</span></p>
<p><span lang=EN-US>" "+|\treturn WHITE;</span></p>
<p><span lang=EN-US>\nreturn0;</span></p>
<p><span lang=EN-US>%%</span></p>
<p><span lang=EN-US>main(int argc,char *argv[])</span></p>
<p><span lang=EN-US>{</span></p>
<p><span lang=EN-US>int c,i=0;</span></p>
<p><span lang=EN-US>char tmp[30];</span></p>
<p><span lang=EN-US>if (argc==2)</span></p>
<p><span lang=EN-US>{</span></p>
<p><span lang=EN-US>if ((yyin=fopen(argv[1],"r"))==NULL)</span></p>
<p><span lang=EN-US>{</span></p>
<p><span lang=EN-US>printf("can't open %s\n",argv[1]);exit(0);</span></p>
<p><span lang=EN-US>}</span></p>
<p><span lang=EN-US>}</span></p>
<p><span lang=EN-US>while ((c=yylex())!=0)</span></p>
<p><span lang=EN-US>{</span></p>
<p><span lang=EN-US>switch(c)</span></p>
<p><span lang=EN-US>{</span></p>
<p><span lang=EN-US>case ON:</span></p>
<p><span lang=EN-US>c=yylex();</span></p>
<p><span lang=EN-US>if (c==0) goto {i+=1;label;}</span></p>
<p><span lang=EN-US>c=yylex();</span></p>
<p><span lang=EN-US>if (c==HUNDRE)</span></p>
<p><span lang=EN-US>i+=100;</span></p>
<p><span lang=EN-US>else i+=1;</span></p>
<p><span lang=EN-US>break;</span></p>
<p><span lang=EN-US>case TW:c=yylex();</span></p>
<p><span lang=EN-US>c=yylex();</span></p>
<p><span lang=EN-US>if (c==HUNDRE)</span></p>
<p><span lang=EN-US>i+=200;</span></p>
<p><span lang=EN-US>else i+=2;</span></p>
<p><span lang=EN-US>break;</span></p>
<p><span lang=EN-US>case TWENT: i+=20;</span></p>
<p><span lang=EN-US>break;</span></p>
<p><span lang=EN-US>case TE:i+=10;</span></p>
<p><span lang=EN-US>break;</span></p>
<p><span lang=EN-US>default:break;</span></p>
<p><span lang=EN-US>}</span></p>
<p><span lang=EN-US>}/*while*/</span></p>
<p><span lang=EN-US>label: printf("%d\n",i);</span></p>
<p><span lang=EN-US>return;</span></p>
<p><span lang=EN-US>}</span></p>
<p><span lang=EN-US>24 （1）Dn表示的正规集是长度为2n任意a和b组成的字符串。</span></p>
<ul type=disc>
<li class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;
mso-list:l0 level1 lfo6;tab-stops:list 36.0pt'>此正规式的长度是<span lang=EN-US>2n
</span></li>
<li class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;
mso-list:l0 level1 lfo6;tab-stops:list 36.0pt'>用来识别<span lang=EN-US>Dn的DFA至多需要2n＋1个状态。
</span></li>
</ul>
<p><span lang=EN-US>25 从略。</span></p>
<p><span lang=EN-US>26（1）由{}括住的,中间由任意个非{组成的字符串, 如{},{}},{a},{defg}等等。</span></p>
<p>（<span lang=EN-US>2）匹配一行仅由一个大写字母和一个数字组成的串，如A1,F8,Z2等。</span></p>
<p>（<span lang=EN-US>3）识别\r\n和除数字字符外的任何字符。</span></p>
<ul type=disc>
<li class=MsoNormal style='mso-margin-top-alt:auto;mso-margin-bottom-alt:auto;
mso-list:l6 level1 lfo7;tab-stops:list 36.0pt'>由<span lang=EN-US>’和’括住的，中间由两个’’或者非’和\n组成的任意次的字符串。如’’’’,
‘a’,’bb’,’def’，’’’’’’等等 </span></li>
</ul>
<p><span lang=EN-US>27O[Xx][0-9]*[a-fA-F]*|[0-9]+|(\’([a-zA-Z]|\\[Xx][0-7][0-7a-fA-F]|\\0[01][0-7][0-7]|\\[a-z])\’)</span></p>
<p><span lang=EN-US>28^[a-zA-Z_]+[0-9]*[a-zA-Z_]*</span></p>
<p><span lang=EN-US>29 参考程序如下：</span></p>
<p><span lang=EN-US>%{</span></p>
<p><span lang=EN-US>#include <stdio.h></span></p>
<p><span lang=EN-US>#include <string.h></span></p>
<p><span lang=EN-US>#include <ctype.h></span></p>
<p><span lang=EN-US>#define UPPER2</span></p>
<p><span lang=EN-US>#define WHITE3</span></p>
<p><span lang=EN-US>%}</span></p>
<p><span lang=EN-US>upper[A-Z]</span></p>
<p><span lang=EN-US>%%</span></p>
<p><span lang=EN-US>{upper}+returnUPPER;</span></p>
<p><span lang=EN-US>\t|" "+returnWHITE;</span></p>
<p><span lang=EN-US>%%</span></p>
<p><span lang=EN-US>main(int argc,char *argv[])</span></p>
<p><span lang=EN-US>{</span></p>
<p><span lang=EN-US>int c,i;</span></p>
<p><span lang=EN-US>if (argc==2)</span></p>
<p><span lang=EN-US>{</span></p>
<p><span lang=EN-US>if ((yyin=fopen(argv[1],"r"))==NULL)</span></p>
<p><span lang=EN-US>{</span></p>
<p><span lang=EN-US>printf("can't open %s\n",argv[1]);exit(0);</span></p>
<p><span lang=EN-US>}</span></p>
<p><span lang=EN-US>} </span></p>
<p><span lang=EN-US>while ((c=yylex())!=EOF)</span></p>
<p><span lang=EN-US>{</span></p>
<p><span lang=EN-US>if (c==2)</span></p>
<p><span lang=EN-US>{</span></p>
<p><span lang=EN-US>for (i=0;yytext[i];i++)</span></p>
<p><span lang=EN-US>printf("%c",tolower(yytext[i]));</span></p>
<p><span lang=EN-US>yytext[0]='\000';</span></p>
<p><span lang=EN-US>}</span></p>
<p><span lang=EN-US>if (c==3)</span></p>
<p><span lang=EN-US>printf(" ");</span></p>
<p><span lang=EN-US>else printf("%s",yytext);</span></p>
<p><span lang=EN-US>}</span></p>
<p><span lang=EN-US>return;</span></p>
<p><span lang=EN-US>}</span></p>
<p><span lang=EN-US>yywrap()</span></p>
<p><span lang=EN-US>{</span></p>
<p><span lang=EN-US>return ;</span></p>
<p><span lang=EN-US>}</span></p>
<p class=MsoNormal><span lang=EN-US>30 从略。 </span></p>
<p><span lang=EN-US> </span></p>
</div>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -