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

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

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

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

4、：用正則符號串集：用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è)是給定字符集，則每個是給定字符集，則每個上的正則表達(dá)式將定義上的正則表達(dá)式將定義上的一個字符串集。若用上的一個字符串集。若用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)先級算符優(yōu)先級 冪運(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* 冪的等價性冪的等價性正則表達(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+(