09--第三章 有限自動機與詞法分析器.ppt

1、第三章 有窮自動機與詞法分析器,任課教師 王養(yǎng)廷,1 正則表達式,基本概念 字母表：它是非空有限集合，其中的元素稱為字母（或符號），一般使用表示。 例如： =a,b,c,.,z 符號串：符號的有限序列 例如：a, ab, cda 、表示空串 區(qū)分和,1 正則表達式（續(xù)）,符號串長度：符號串中包含符號的個數(shù)，使用|表示符號串的長度 例如：| a |=1, | abc |=3, | |=0 符號串的連接：、是符號串，為符號串和的連接 例如： =aa, =bb, =aabb = = ,1 正則表達式（續(xù)）,符號串的乘積：A、B是符號串的集合，則AB定義為符號串A和B的乘積。AB=| A, B，若為空

2、集，則A=A=A。 例如：A=ab, cd, B=12,34，則AB=ab12, ab34, cd12, cd34 符號串集合的方冪：設A是符號串的集合，則稱Ai為符號串的方冪 A0= A1=A Ak=AA.A(k個),1 正則表達式（續(xù)）,符號串的正閉包：設A是符號串的集合，則稱A+ 是符號串的正閉包 A+= A1 A2 A3 . 例如：A=a, A+=a,aa,aaa,. 符號串的星閉包：設A是符號串的集合，則稱A* 是符號串的星閉包 A+= A0 A+ 例如：A=a, A*=, a,aa,aaa,. 問題 A=a, b，A的正閉包和星閉包是什么,1 正則表達式（續(xù)）,正則符號串集：用RS

3、S表示，定義為： 字母表的任何子集 空集 若A、B是RSS,則AB是RSS 若A、B是RSS,則AB是RSS 若A、B是RSS,則A*是RSS,1 正則表達式（續(xù)）,正則表達式 設是給定字符集，則每個上的正則表達式將定義上的一個字符串集。若用RE表示的正則表達式，則用L(RE ) 表示RE所表示的正則集，則RE的定義及含義如下： 是正則表達式，即 R E，其中L()= 是正則表達式，即 R E，其中L()=a a是正則表達式，即 a RE ，其中L(a)=a 設A和B是正則表達式，即A RE ，B RE ,則有 (A) R E， L(A)=L(A) A|B R E ， L(A|B)=L(A)

4、| L(B) AB R E ， L(AB)=L(A) L(B) A* R E ， L(A*)=L(A)*,1 正則表達式（續(xù)）,算符優(yōu)先級 冪運算 連接 選擇 a*b|c =(a*)b) | c 擴充RE A+ R E ， L(A+)=L(A)+ A? R E ， L(A?)=L(A) chi-chk R E 表示（ chi |chi+1 | chk ） abc R E 表示（ a| b| c ） chi-chk chj-chl表示chi-chk | chj-chl,正則表達式（續(xù)）,正則表達式的性質(zhì)：P48 A|B =B|A |的可交換性 A|(B|C)=(A|B)|C |的可結(jié)合性 A(BC)=(AB)C 連接的可結(jié)合性 A(B|C)=AB|AC 連接的可分配性 (A|B)C=AC|BC 連接的可分配性 A*=A* 冪的等價性,正則表達式（續(xù)）,正則表達式示例 假設：D=0,1,9, L=az, AZ D+ D+. D+ L(D|L) 舉例 (a|bc)*d)+ (0|1)* (2|3)+)|0011,正則表達式（續(xù)）,實例 a a | b ab a* a*b* (a|b)* (ab)*,a+ a(b|c) a+(b|c)a* (a|