资源描述:
《编译原理基础——习题与上机题解答 教学课件 作者 刘坚 第1-5章第2章.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第2章“词法分析”习题解答2.1分别给出下述Pascal和C程序段的记号流形式。其中每个记号以有序对(记号类别,记号属性)的形式表示。例如:left+right的记号流应该是:(id,left)(op,+)(id,right)。程序段中的注释可以忽略。(1)Pascalfunctionmax(i,j:integer):integer;{returnmaximumofiandj}beginifi>jthenmax:=ielsemax:=jend;(2)Cintmax(i,j)inti,j;/*returnmaximumofiandj*/{returni>j?i
2、:j;}解:(1)Pascal类别属性类别属性(keyword,function)(id,max)(keysymbol,()(id,i)(keysymbol,,)(id,j)(keysymbol,:)(keyword,integer)(keysymbol,))(keysymbol,:)(keyword,integer)(keysymbol,;)(keyword,begin)(keyword,if)(id,i)(relation,>)(id,j)(keyword,then)(id,max)(assign,:=)(id,i)(keyword,else)(id,m
3、ax)(assign,:=)(id,j)(keyword,end)(keysymbol,;)(2)C类别属性类别属性(keyword,int)(id,max)(keysymbol,()(id,i)(keysymbol,,)(id,j)(keysymbol,))(keyword,int)(id,i)(keysymbol,,)(id,j)(keysymbol,;)(keysymbol,{)(keyword,return)(id,i)(relation,>)(id,j)(keysymbol,?)(id,i)(keysymbol,:)(id,j)(keysymbo
4、l,;)(keysymbol,})2.2用正规式描述习题2.1中的记号。 解:(1)Pascalkeyword=function
5、integer
6、begin
7、if
8、then
9、else
10、endid=char(char
11、digit)*(其中,char=[a–zA–Z],digit=[0–9])assign=:=keysymbol=(
12、)
13、,
14、:
15、;relation=>(2)Ckeyword=int
16、returnid=(_
17、char)(_
18、char
19、digit)*(其中char=[a–zA–Z],digit=[0–9])keysymbol=(
20、)
21、{
22、}
23、:
24、
25、?
26、;
27、,relation=>2.3令A、B、C是任意的正规式,证明下述关系成立:(1)A
28、A=A(2)(A*)*=A*(3)A*=ε
29、AA*(4)(AB)*A=A(BA)*证:(1)设正规式A表示的正规集为L(A)。 因为L(A
30、A)=L(A)∪L(A)=L(A)所以A
31、A=A(2)因为(A*)*=A**A**=A*所以(A*)*=A*(3)因为AA*=A+A*=A+
32、ε=ε
33、A+所以A*=ε
34、AA*(4)因为(AB)*=ε
35、AB
36、ABAB
37、ABABAB
38、…(BA)*=ε
39、BA
40、BABA
41、BABABA
42、…所以(AB)*A=(ε
43、AB
44、ABAB
45、ABAB
46、AB
47、…)A=A
48、ABA
49、ABABA
50、ABABABA
51、…=A(ε
52、BA
53、BABA
54、BABABA
55、…)=A(BA)*2.4写出下述语言的正规式描述。(1)由偶数个0和奇数个1构成的所有01串。(2)所有不含子串011的01串。(3)每个a后边至少紧随两个b的ab串。(4)C的形如/*…*/的注释。其中…代表不含*/的字符串。 解:(1)A1A
56、A0A1A0A其中,A=((00
57、11)
58、(10
59、01)(00
60、11)*(10
61、01))*。(2)1*(01
62、0)*(3)(b
63、abb)*(4)/*([^*]
64、**[^*/])****/2.5合法的日期表示有如下三种
65、形式,请给出描述日期的正规式。 年.月.日,如1992.08.12日月年,如12081992月/日/年,如08/12/1992解:digit=[0–9]year=(digit)(digit)(digit)(digit)month=0[1–9]
66、1[0–2]day=0[1–9]
67、[1–2][0–9]
68、3[0–1]date1=year.month.daydate2=daymonthyeardate3=month/day/yeardate=date1
69、date2
70、date32.6有NFA定义如下:N=(S={0,1},∑={a,b},s0=0,F={0},mo
71、ve={move(0,a)=0,move(0,a)=