正則文法與正則運算式的相互轉化
- 前言
- 一、正則文法
- 1.定義
- 2.例子
- 二、正則運算式
- 1.定義
- 2.例子
- 三、轉換規則
- 1.正則文法轉換為正則運算式
- 2.正則運算式轉換為正則文法
- 四、轉換例子
- 1.正則文法轉換為正則運算式
- 2.正則運算式轉換為正則文法
- 總結
前言
在詞法分析程序中，如果將每類單詞都看作一種語言，則大多數單詞詞法可以用正則文法來描述， 除了正則文法外，正則運算式也可以相應的用來描述單詞，正則文法和正則運算式的能力相同，且可以互相轉化，正則運算式比正則文法更直觀，有時首選正則運算式來表示正則語言，
一、正則文法
1.定義
正則文法在這篇文章（編譯原理-文法的定義與分類）中有所講解，在此處再稍微講述一遍：
- 正則文法G = (V，T，P，S)中，對?α —> β∈P，α β均具有形式A —> w或A —> wB(A —> w或A —> Bw)，其中A，B∈V，w∈T+，
- 正則文法描述T上的正則語言，
2.例子
例子：詞法分析中識別符號的文法：
二、正則運算式
1.定義
定義：設∑是一個字母表，則∑上的正則運算式及其所表示的正則語言可遞回地定義如下：
⑴ ?是∑上的一個正則運算式，它表示空集；
⑵ ε是∑上的一個正則運算式，它表示語言{ε}；
⑶ 對于?a(a∈∑)，a是∑上的一個正則運算式，它表示的正則語言是{a}；
⑷ 假設r和s都是∑上的正則運算式，它們表示的語言分別為L?和L(s)，則：
- ( r )也是∑上的正則運算式，它表示的語言為L( r )；
- (r|s)也是∑上的正則運算式，它表示的語言為L( r )∪L(s)；（并操作）
- (r?s)也是∑上的正則運算式，它表示的語言為L( r )L(s)；（連接操作）
- (r*)也是∑上的正則運算式，它表示的語言為(L( r ))*；（克林閉包操作）
⑸ 使用上述規則構造的運算式是∑上的正則運算式，
2.例子
例子：詞法分析中識別符號的正則運算式表達：
三、轉換規則
1.正則文法轉換為正則運算式
具體轉換步驟為：
-
根據正則文法G構造正則運算式聯立方程組，
假設正則文法G是右線性的，其每個產生式的右部只含有一個終結符，則有如下方程式構造規則：
-
解聯立方程組，求等價的正則運算式r，
用代入消元法逐個消去方程組中除開始符號S外的其他變數，最后即可得到關于開始符號S的解，
代入消元規則如下：
-
求得結果，
如果最后得到的關于S的方程式為如下形式，
S=α1|α2|…|αh
則將方程式右邊所有其中仍然含有語法變數的αi(1≤i≤n)洗掉，得到的結果就是與G等價的正則運算式，
如果任意的αi(1≤i≤n)均含有語法變數，則?就是與G等價的正則運算式，
2.正則運算式轉換為正則文法
給定正則運算式r，按如下方法構造正則定義式，并逐步將其轉換成正則文法，
引入開始符號S，從如下正則定義式開始：
S—>r
按如下規則將S—>r分解為新的正則定義式，在分解程序中根據需要引入新的語法變數，
四、轉換例子
1.正則文法轉換為正則運算式
程序：
2.正則運算式轉換為正則文法
例1.識別符號定義的轉換：
(1).引入 S
(2).S→ (|)*
(3).分解為
S→ A
A→(|)A|ε
例2.(a|b)*a(a|b)(a|b)
轉換成正則文法：
(1).S->Aa|Ab
(2).A->Ba|Bb
(3).B->Ca
(4).C->Ca|Cb|ε
總結
正則運算式與正則文法等價：
對任意一個正則文法，存在一個定義同一語言的正則運算式；
對任意一個正則運算式，存在一個定義同一語言的正則文法，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/239092.html
標籤：其他