THSS341001622010/4301Chap.3形式语言初步(II)王朝坤chaokun@tsinghua.edu.cnOutlineTHSS341001622010/4301•RE•RG~RE•CFG语法树•二义性•句型分析•文法化简•文法推断2EXAMPLESofRegularExpressionsTHSS341001622010/4301L={A,B,C,D}E={1,2,3}A|B|C|D=L(A|B|C|D)(A|B|C|D)=L2(A|B|C|D)*=L*(A|B|C|D)((A|B|C|D)|(1|2|3))=L(LÈE)3AlgebraicPropertiesofRETHSS341001622010/4301AXIOMDESCRIPTIONr|s=s|r|iscommutativer|(s|t)=(r|s)|t|isassociative(rs)t=r(st)concatenationisassociativer(s|t)=rs|rt(s|t)r=sr|trconcatenationdistributesover|er=rre=reistheidentityelementforconcatenationr*=(r|e)*relationbetween*ander**=r**isidempotent(幂等)4RegularExpressionExamplesTHSS341001622010/43011.AllStringsthatstartwith“tab”orendwith“bat”:tab(A|…|Z|a|…|z)*|(A|…|Z|a|....|z)*batletter→A|…|Z|a|…|ztabletter*|letter*bat1.AllUppercaseStringsinwhichdigits1,2,3existinascendingnumericalorder:(A|…|Z)*1(A|…|Z)*2(A|…|Z)*3(A|…|Z)*letter→A|…|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®rr1的正规产生式：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®aAA®dA7从正规文法到正规式THSS341001622010/4301对G=(VN,VT,P,S),存在一个å=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|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上下文无关文法有足够的能力描述程序设计语言的语法结构语法树---句型推导的直观表示10句型推导THSS341001622010/4301G[E]：E→E+T|TT→T*F|FF→(E)|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句型推导的分类最左（最右）推导：—在推导的任何一