學(xué)習(xí)編譯原理Time06 ~ 正規(guī)式

單詞的描述工具-正規(guī)式 ：多數(shù)程序設(shè)計語言的單詞的語法均可用正規(guī)文法來表示。

正規(guī)式（regular expression也叫正則表達(dá)式）：正規(guī)式是定義正規(guī)集的數(shù)學(xué)工具，是說明單詞的模式(pattern)的一種表示法，用它描述單詞符號時一般比正規(guī)文法更簡潔。正規(guī)式和正規(guī)集 (即其描述的語言) 的定義可以用遞歸的形式給出。

正規(guī)式運算規(guī)律 :

設(shè)r,s,t為正規(guī)式，則它們滿足如下運算規(guī)律：

r|s=s|r

r|(s|t)=(r|s)|t

(rs)t=r(st):交換律

r(s|t)=rs|rt; (s|t)r=sr|tr :分配律

εr=r ; rε=r : ε是 “連接”的恒等元素

r|r=r : “或”的抽取律

例 : 令∑={a,b},則∑上的正規(guī)式和相應(yīng)正規(guī)集為

正規(guī)式	正規(guī)集
a	{a}
a|b	{a,b}
ab	{ab}
(a|b)(a|b)	{aa,ab,ba,bb}
a*	{ε ,a,aa,..,n個a的串}
(a|b)*	{ε ,a,aa, ……n個a的串}{ε ,a,b,aa,ab,bb ……所有由 a和b組成的串}
(a|b)* (aa|bb)(a|b)*	∑上所有含有兩個相繼的a或兩個相繼的b組成的串},例如：aaaa、bbaabb、abbaaa

例 : 令∑={a，d}

其中a代表字母,d代表數(shù)字，則∑上的正規(guī)式 r=a(a|d) * 定義的正規(guī)集為{a,aa,ad,add,……}， 即：字母(字母|數(shù)字) * ,它表示的正規(guī)集中的每個元素的模式是“字母打頭的字母數(shù)字串”,也就是多數(shù)程序語言中標(biāo)識符的詞法規(guī)則.

記錄

點點滴滴的筆記

歡迎關(guān)注，共同學(xué)習(xí)

小浩筆記