前言

在詞法分析過程中，如果將每類單詞都看作一種語言，則大多數(shù)單詞詞法可以用正則文法來描述。 除了正則文法外，正則表達(dá)式也可以相應(yīng)的用來描述單詞，正則文法和正則表達(dá)式的能力相同，且可以互相轉(zhuǎn)化。正則表達(dá)式比正則文法更直觀，有時(shí)首選正則表達(dá)式來表示正則語言。

一、正則文法

1.定義

正則文法在這篇文章（編譯原理-文法的定義與分類）中有所講解，在此處再稍微講述一遍：

• 正則文法G = (V，T，P，S)中，對(duì)∀α —> β∈P，α β均具有形式A —> w或A —> wB(A —> w或A —> Bw)，其中A，B∈V，w∈T+。
• 正則文法描述T上的正則語言。

2.例子

例子：詞法分析中標(biāo)識(shí)符的文法：

二、正則表達(dá)式

1.定義

定義：設(shè)∑是一個(gè)字母表，則∑上的正則表達(dá)式及其所表示的正則語言可遞歸地定義如下：

⑴ Ø是∑上的一個(gè)正則表達(dá)式，它表示空集；

⑵ ε是∑上的一個(gè)正則表達(dá)式，它表示語言{ε}；

⑶ 對(duì)于∀a(a∈∑)，a是∑上的一個(gè)正則表達(dá)式，它表示的正則語言是{a}；

⑷ 假設(shè)r和s都是∑上的正則表達(dá)式，它們表示的語言分別為L(zhǎng)®和L(s)，則：

( r )也是∑上的正則表達(dá)式，它表示的語言為L(zhǎng)( r )；
(r|s)也是∑上的正則表達(dá)式，它表示的語言為L(zhǎng)( r )∪L(s)；（并操作）
(r•s)也是∑上的正則表達(dá)式，它表示的語言為L(zhǎng)( r )L(s)；（連接操作）
(r*)也是∑上的正則表達(dá)式，它表示的語言為(L( r ))*；（克林閉包操作）

⑸ 使用上述規(guī)則構(gòu)造的表達(dá)式是∑上的正則表達(dá)式。

2.例子

例子：詞法分析中標(biāo)識(shí)符的正則表達(dá)式表達(dá)：

三、轉(zhuǎn)換規(guī)則

1.正則文法轉(zhuǎn)換為正則表達(dá)式

具體轉(zhuǎn)換步驟為：

1.根據(jù)正則文法G構(gòu)造正則表達(dá)式聯(lián)立方程組。

假設(shè)正則文法G是右線性的，其每個(gè)產(chǎn)生式的右部只含有一個(gè)終結(jié)符，則有如下方程式構(gòu)造規(guī)則：

2.解聯(lián)立方程組，求等價(jià)的正則表達(dá)式r。

用代入消元法逐個(gè)消去方程組中除開始符號(hào)S外的其他變量，最后即可得到關(guān)于開始符號(hào)S的解。

代入消元規(guī)則如下：

求得結(jié)果。如果最后得到的關(guān)于S的方程式為如下形式，S=α1|α2|…|αh則將方程式右邊所有其中仍然含有語法變量的αi(1≤i≤n)刪除，得到的結(jié)果就是與G等價(jià)的正則表達(dá)式。如果任意的αi(1≤i≤n)均含有語法變量，則Ø就是與G等價(jià)的正則表達(dá)式。

2.正則表達(dá)式轉(zhuǎn)換為正則文法

給定正則表達(dá)式r，按如下方法構(gòu)造正則定義式，并逐步將其轉(zhuǎn)換成正則文法。

引入開始符號(hào)S，從如下正則定義式開始：

S—>r

按如下規(guī)則將S—>r分解為新的正則定義式，在分解過程中根據(jù)需要引入新的語法變量。

四、轉(zhuǎn)換例子

1.正則文法轉(zhuǎn)換為正則表達(dá)式

過程：

2.正則表達(dá)式轉(zhuǎn)換為正則文法

例1.標(biāo)識(shí)符定義的轉(zhuǎn)換：

(1).引入 S
(2).S→ (|)*
(3).分解為
S→ A
A→(|)A|ε

例2.(a|b)*a(a|b)(a|b)

轉(zhuǎn)換成正則文法：
(1).S->Aa|Ab
(2).A->Ba|Bb
(3).B->Ca
(4).C->Ca|Cb|ε

總結(jié)

正則表達(dá)式與正則文法等價(jià)：
對(duì)任意一個(gè)正則文法，存在一個(gè)定義同一語言的正則表達(dá)式；
對(duì)任意一個(gè)正則表達(dá)式，存在一個(gè)定義同一語言的正則文法。

到此這篇關(guān)于編譯原理-正則文法與正則表達(dá)式的相互轉(zhuǎn)化的文章就介紹到這了,更多相關(guān)正則文法轉(zhuǎn)正則表達(dá)式內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論