哈工大编译原理习题及答案

(r*)*=r*={ε,r,rr,rrr,?} 所以四者是等价的。

(2)（rs）*r表示的正规式集是{ε,rs,rsrs,rsrsrs,?}r ={r,rsr,rsrsr,rsrsrsr,?} r(sr)* 表示的正规式集是r{ε,sr,srsr,srsrsr,?} ={ r,rsr,rsrsr,rsrsrsr,?} 所以两者等价。 18 写成方程组 S=aT+aS(1) B=cB+c(2) T=bT+bB(3) 所以B=c*cT=b*bc*c S=a*ab*bc*c

?

G1:

S=aA+B(1) B=cC+b(2) A=abS+bB (3) C=D(4) D=bB+d(5)

把（4）（5）代入（2），得B＝c(bB+d)+b=cbB+cd+b 得B=(cb)*(cd|b),代入（3）得 A=abS+b(cb)*(cd|b)把它打入（1）得 S=a(abS+b(cb)*(cd|b))+ (cb)*(cd|b) =aabS+ab(cb)*(cd|b) + (cb)*(cd|b) =(aab)*( ab(cb)*(cd|b)| (cb)*(cd|b)) G2:

S=Aa+B (1) A=Cc+Bb (2) B=Bb+a(3) C=D+Bab(4) D=d(5)

可得 D=dB=ab*C=ab*ab|bA=(ab*ab|b)c + ab*b S=(ab*ab|b)ca+ab*ba +ab* =(ab*ab|b)ca| ab*ba| ab* 20

? ?

识别此语言的正规式是S=?LABEL?d(d|,d)*; 从略。

21 从略。 22 构造NFA

其余从略。

23 下面举一个能够识别1,2,3,10,20,100的例子，读者可以推而广之。 %{

#include #include

#include #define ON1 #define TW 2 #define THRE 3 #define TE 10 #define TWENT 20 #define HUNDRE 100 #define WHITE9999 %}

upper[A-Z] %%

ONEreturn ON; TWOreturn TW; THREEreturn THRE; TENreturn TE; TWENTYreturn TWENT; HUNDREDreturn HUNDRE; \\\nreturn0; %%

main(int argc,char *argv[]) {

int c,i=0;

char tmp[30]; if (argc==2) {

if ((yyin=fopen(argv[1],\{

printf(\} }

while ((c=yylex())!=0) {

switch(c) { case ON: c=yylex();

if (c==0) goto {i+=1;label;} c=yylex(); if (c==HUNDRE) i+=100; else i+=1; break;

case TW:c=yylex(); c=yylex(); if (c==HUNDRE)