资源描述：
《清华大学软件学院编译原理课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、THSS341001622010/4301Chap.3形式语言初步(II)王朝坤chaokun@tsinghua.edu.cnOutlineTHSS341001622010/4301•RE•RG~RE•CFG语法树•二义性•句型分析•文法化简•文法推断2EXAMPLESofRegularExpressionsTHSS341001622010/4301L={A,B,C,D}E={1,2,3}A
2、B
3、C
4、D=L(A
5、B
6、C
7、D)(A
8、B
9、C
10、D)=L2(A
11、B
12、C
13、D)*=L*(A
14、B
15、C
16、D)((A
17、B
18、C
19、D
20、)
21、(1
22、2
23、3))=L(LÈE)3AlgebraicPropertiesofRETHSS341001622010/4301AXIOMDESCRIPTIONr
24、s=s
25、r
26、iscommutativer
27、(s
28、t)=(r
29、s)
30、t
31、isassociative(rs)t=r(st)concatenationisassociativer(s
32、t)=rs
33、rtconcatenationdistributesover
34、(s
35、t)r=sr
36、trer=reistheidentityelementforconcatenati
37、onre=rr*=(r
38、e)*relationbetween*ander**=r**isidempotent(幂等)4RegularExpressionExamplesTHSS341001622010/43011.AllStringsthatstartwith“tab”orendwith“bat”:tab(A
39、…
40、Z
41、a
42、…
43、z)*
44、(A
45、…
46、Z
47、a
48、....
49、z)*batletter→A
50、…
51、Z
52、a
53、…
54、ztabletter*
55、letter*bat1.AllUppercaseStringsinwhichdi
56、gits1,2,3existinascendingnumericalorder:(A
57、…
58、Z)*1(A
59、…
60、Z)*2(A
61、…
62、Z)*3(A
63、…
64、Z)*letter→A
65、…
66、Zletter*1letter*2letter*3letter*5从正规式到正规文法THSS341001622010/4301对å上的正规式r,存在一个RG=(VN,VT,P,S)：L(G)=L(r)初始，VT=å,SÎVN,生成正规产生式S®r(R.1)对形如A®r1r2的正规产生式：A®r1BB®r2BÎVN(R.2)对形如A®r*r1
67、的正规产生式：A®rAA®r1(R.3)对形如A®r1½r2的正规产生式:A®r1A®r2不断应用(R.x)做变换，直到每个产生式右端至多有一个VN6例r=a(a½d)*THSS341001622010/4301(1)S®a(a½d)*(2)S®aAA®(a½d)*(3)A®(a½d)AA®e(4)A®aA½dA(5)A®aAA®dAVT={a,d}VN={S}{S,A}G[s]:S®aAA®eA®aA7A®dA从正规文法到正规式THSS341001622010/4301对G=(VN,VT,P,S),存在一个
68、å=VT上的正规式r:L(r)=L(G)A®xB,B®y形成正规式A=xyA®xA½y形成正规式A=x*yA®x½y形成正规式A=x½y8从正规文法到正规式（例）THSS341001622010/4301G[s]:S®aA
69、aA®aA½a½dA½dA®(a½d)A½(a½d)A®(a½d)*(a½d)S=a(a½d)*(a½d)½a=a((a½d)*(a½d)½e)=a((a½d)+½e)R=a(a½d)*9上下文无关文法及其语法树THSS341001622010/4301上下文无关文法有足够的能力描述程序设
70、计语言的语法结构语法树---句型推导的直观表示10句型推导THSS341001622010/4301G[E]：E→E+T
71、TT→T*F
72、FF→(E)
73、aEÞE+TÞT+TÞF+TÞa+TÞa+T*FÞa+F*FÞa+a*FÞa+a*aEÞE+TÞE+T*FÞE+T*aÞE+F*aÞE+a*aÞT+a*aÞF+a*aÞa+a*aEÞE+TÞT+TÞT+T*FÞF+T*FÞF+F*FÞa+F*FÞa+F*aÞa+a*a11规范推导规范句型THSS341001622010/4301句型推导的分类最左（最右）推导：—
74、在推导的任何一步αÞβ，其中α、β是句型，都是对α中的最左（右）非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型句型推导的直观表示语法树12语法树THSS341001622010/4301设G=(VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树/推导树/派生树：1.根结点的标号是文法的开始符号S2.每个内部结点的标号为A，且A∈VN3.每个叶结点
