編譯原理3.3.1 正規(guī)式

1、第三章 詞法分析3.1 對于詞法分析器的要求3.2 詞法分析器的設(shè)計3.3 正規(guī)表達式和自動機3.4 詞法分析器的自動產(chǎn)生3.3 正規(guī)表達式和自動機3.3.1 正規(guī)式和正規(guī)集3.3.2 確定有限自動機3.3.3 非確定有限自動機3.3.4 正規(guī)文法與有限自動機的等價性3.3.5 正規(guī)式與有限自動機的等價性3.3.6 確定有限自動機的化簡正規(guī)語言確定化最小化正規(guī)式正規(guī)文法自動機3.3.1 正規(guī)式和正規(guī)集1、正規(guī)式的引入2、正規(guī)式和正規(guī)集的定義 3、兩個正規(guī)式等價的定義 4、正規(guī)式服從的代數(shù)規(guī)律1、正規(guī)式的引入正則表達式，正規(guī)表達式, RERegular Expression 正規(guī)式正規(guī)集正規(guī)文法

2、正規(guī)語言正規(guī)語言是VT*上的正規(guī)集L(G) VT* 單詞描述工具2 、正規(guī)式和正規(guī)集的定義 設(shè)字母表為, 輔助字母表= | * ( ) 正規(guī)式正規(guī)集 a a (1)(2): 語言的字母表 VT (3) 假定U和V都是上的正規(guī)式， 他們所表示的正規(guī)集分別為L(U)和L(V) (4) 僅由有限次使用上述三步驟而定義的表達式才是上的正規(guī)式，僅由這些正規(guī)式表示的字集才是上的正規(guī)集 規(guī)定算符的優(yōu)先順序()*| 正規(guī)式a a|bab(a|b)(a|b)a*(a|b)* 正規(guī)集aa, bab aa, ab, ba, bb , a, aa, aaa, , a, b, aa, ab 所有由a和b組成的串 補充例

3、 : 令=a，b ， 上的正規(guī)式和相應(yīng)的正規(guī)集例 3.1 =a，b P47 ba*ba*上所有以b為首,后面跟任意多個a的符號串a(chǎn)(a|b)*aa,b*上所有以a為首的符號串(a|b)*(aa|bb)(a|b)*a,b*aa,bba,b* 上所有含有兩個相繼a或兩個相繼b的符號串例 3.2 =A,B,0,1 P47 (A|B)(A|B|0|1)*A,BA,B,0,1*上 標識符的全體(0|1)(0|1)*0,10,1*上 數(shù)的全體補充例: =0,9,a,z,A,Z 正規(guī)式 d = 0|1|9正規(guī)式 l = a|z|A|Z整數(shù)的集合: dd* (dd* = d+)標識符的集合: l(l|d)*3、兩個正規(guī)式等價的定義若兩個正規(guī)式U和V表示的正規(guī)集相同,則說U和V等價，寫作U=V例a|b b|a b(ab)* (ba)* b (a|b)* (a* |b* )* 4、正規(guī)式服從的代數(shù)規(guī)律U,V,W為正規(guī)式 U|V=V|U U|(V|W)=(U|V) | W (UV)W=U(VW) U(V|W)=UV|UW ， (V|W)U=VU|WU U=U=U P47補充：正規(guī)式服從的代數(shù)規(guī)律r|r=r r*=|r|rr|(r*)* = r*=0 1 2 n 補充例：定義無符號數(shù)的正規(guī)式 =d .e+