--第三章有限自動(dòng)機(jī)與詞法分析器

1、第三章第三章 有窮自動(dòng)有窮自動(dòng)機(jī)與詞法分析器機(jī)與詞法分析器任課教師任課教師王養(yǎng)廷王養(yǎng)廷1 正則表達(dá)式正則表達(dá)式n基本概念基本概念字母表：它是非空有限集合，其中的字母表：它是非空有限集合，其中的元素稱(chēng)為字母（或符號(hào)），一般使用元素稱(chēng)為字母（或符號(hào)），一般使用表示。表示。 例如：例如： =a,b,c,.,z符號(hào)串：符號(hào)的有限序列符號(hào)串：符號(hào)的有限序列 例如：例如：a, ab, cda 、表示空串表示空串 區(qū)分區(qū)分和和1 正則表達(dá)式（續(xù)）正則表達(dá)式（續(xù)）符號(hào)串長(zhǎng)度：符號(hào)串中包含符號(hào)符號(hào)串長(zhǎng)度：符號(hào)串中包含符號(hào)的個(gè)數(shù)，使用的個(gè)數(shù)，使用|表示符號(hào)串表示符號(hào)串的長(zhǎng)的長(zhǎng)度度 例如：例如：| a |=1, |

2、 abc |=3, | |=0符號(hào)串的連接：符號(hào)串的連接：、是符號(hào)串，是符號(hào)串，為符號(hào)串為符號(hào)串和和的連接的連接 例如：例如： =aa, =bb, =aabb = = 1 正則表達(dá)式（續(xù)）正則表達(dá)式（續(xù)） 符號(hào)串的乘積：符號(hào)串的乘積：A、B是符號(hào)串的集合，則是符號(hào)串的集合，則AB定義為符號(hào)串定義為符號(hào)串A和和B的乘積。的乘積。AB=| A, B，若，若為空集，則為空集，則A=A=A。 例如：例如：A=ab, cd, B=12,34，則，則AB=ab12, ab34, cd12, cd34 符號(hào)串集合的方冪：設(shè)符號(hào)串集合的方冪：設(shè)A是符號(hào)串的集合，是符號(hào)串的集合，則稱(chēng)則稱(chēng)Ai為符號(hào)串的方冪為符號(hào)

3、串的方冪 A0= A1=A Ak=AA.A(k個(gè)個(gè))1 正則表達(dá)式（續(xù)）正則表達(dá)式（續(xù)） 符號(hào)串的正閉包：設(shè)符號(hào)串的正閉包：設(shè)A是符號(hào)串的集合，則是符號(hào)串的集合，則稱(chēng)稱(chēng)A+ 是符號(hào)串的正閉包是符號(hào)串的正閉包 A+= A1 A2 A3 . 例如：例如：A=a, A+=a,aa,aaa,. 符號(hào)串的星閉包：設(shè)符號(hào)串的星閉包：設(shè)A是符號(hào)串的集合，則是符號(hào)串的集合，則稱(chēng)稱(chēng)A* 是符號(hào)串的星閉包是符號(hào)串的星閉包 A+= A0 A+ 例如：例如：A=a, A*=, a,aa,aaa,. 問(wèn)題問(wèn)題 A=a, b，A的正閉包和星閉包是什么的正閉包和星閉包是什么1 正則表達(dá)式（續(xù)）正則表達(dá)式（續(xù)）n正則符號(hào)串集

4、：用正則符號(hào)串集：用RSS表示，定義為：表示，定義為： 字母表字母表的任何子集的任何子集空集空集 若若A A、B B是是RSS,RSS,則則ABAB是是RSSRSS若若A A、B B是是RSS,RSS,則則ABAB是是RSSRSS若若A A、B B是是RSS,RSS,則則A A* *是是RSSRSS1 正則表達(dá)式（續(xù)）正則表達(dá)式（續(xù)）n正則表達(dá)式正則表達(dá)式 設(shè)設(shè)是給定字符集，則每個(gè)是給定字符集，則每個(gè)上的正則表達(dá)式將定義上的正則表達(dá)式將定義上的一個(gè)字符串集。若用上的一個(gè)字符串集。若用RE表示表示的正則表達(dá)式，的正則表達(dá)式，則用則用L(RE ) 表示表示RE所表示的正則集，則所表示的正則集，則R

5、E的定義的定義及含義如下：及含義如下： 是正則表達(dá)式，即是正則表達(dá)式，即 R E，其中，其中L()= 是正則表達(dá)式，即是正則表達(dá)式，即 R E，其中，其中L()=a a是正則表達(dá)式，即是正則表達(dá)式，即 a RE ，其中，其中L(a)=a 設(shè)設(shè)A和和B是正則表達(dá)式，即是正則表達(dá)式，即A RE ，B RE ,則有則有 (A) R E， L(A)=L(A) A|B R E ， L(A|B)=L(A) | L(B) AB R E ， L(AB)=L(A) L(B) A* R E ， L(A*)=L(A)*1 正則表達(dá)式（續(xù)）正則表達(dá)式（續(xù)）算符優(yōu)先級(jí)算符優(yōu)先級(jí) 冪運(yùn)算冪運(yùn)算 連接連接 選擇選擇 a*b

6、|c =(a*)b) | c擴(kuò)充擴(kuò)充RE A+ R E ， L(A+)=L(A)+ A? R E ， L(A?)=L(A) chchi i-ch-chk k R E 表示（表示（ chchi i |chchi+1i+1 | chchk k ） abc R E 表示（表示（ a| b| c ） chchi i-ch-chk k chchj j-ch-chl l表示表示chchi i-ch-chk k | chchj j-ch-chl l正則表達(dá)式（續(xù)）正則表達(dá)式（續(xù)）正則表達(dá)式的性質(zhì)：正則表達(dá)式的性質(zhì)：P48 A|B =B|A |的可交換性的可交換性 A|(B|C)=(A|B)|C |的可結(jié)合性的可結(jié)合性 A(BC)=(AB)C 連接的可結(jié)合性連接的可結(jié)合性 A(B|C)=AB|AC 連接的可分配性連接的可分配性 (A|B)C=AC|BC 連接的可分配性連接的可分配性 A*=A* 冪的等價(jià)性?xún)绲牡葍r(jià)性正則表達(dá)式（續(xù)）正則表達(dá)式（續(xù)）正則表達(dá)式示例正則表達(dá)式示例 假設(shè)：假設(shè)：D=0,1,9, L=az, AZ D+ D+. D+ L(D|L)舉例舉例 (a|bc)*d)+ (0|1)* (2|3)+)|0011正則表達(dá)式（續(xù)）正則表達(dá)式（續(xù)）n實(shí)例實(shí)例aa | baba*a*b*(a|b)*(ab)*a+a(b|c)a+(