前言

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

一、正則文法

1.定義

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

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

2.例子

例子：詞法分析中標識符的文法：

二、正則表達式

1.定義

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

⑴ Ø是∑上的一個正則表達式，它表示空集；

⑵ ε是∑上的一個正則表達式，它表示語言{ε}；

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

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

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

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

2.例子

例子：詞法分析中標識符的正則表達式表達：

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

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

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

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

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

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

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

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

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

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

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

引入開始符號S，從如下正則定義式開始：

S—>r

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

四、轉(zhuǎn)換例子

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

過程：

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

例1.標識符定義的轉(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é)

正則表達式與正則文法等價：
對任意一個正則文法，存在一個定義同一語言的正則表達式；
對任意一個正則表達式，存在一個定義同一語言的正則文法。

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

最新評論