编译原理

在词法分析过程中，如果将每类单词都看作一种语言，则大多数单词词法可以用正则文法来描述。 除了正则文法外，正则表达式也可以相应的用来描述单词，正则文法和正则表达式的能力相同，且可以互相转化。正则表达式比正则文法更直观，有时首选正则表达式来表示正则语言。

正则文法在这篇文章（编译原理-文法的定义与分类）中有所讲解，在此处再稍微讲述一遍：

例子：词法分析中标识符的文法：

定义：设∑是一个字母表，则∑上的正则表达式及其所表示的正则语言可递归地定义如下： ⑴ Ø是∑上的一个正则表达式，它表示空集； ⑵ ε是∑上的一个正则表达式，它表示语言{ε}； ⑶ 对于∀a(a∈∑)，a是∑上的一个正则表达式，它表示的正则语言是{a}； ⑷ 假设r和s都是∑上的正则表达式，它们表示的语言分别为L®和L(s)，则：

⑸ 使用上述规则构造的表达式是∑上的正则表达式。

例子：词法分析中标识符的正则表达式表达：

具体转换步骤为：

根据正则文法G构造正则表达式联立方程组。 假设正则文法G是右线性的，其每个产生式的右部只含有一个终结符，则有如下方程式构造规则：

解联立方程组，求等价的正则表达式r。 用代入消元法逐个消去方程组中除开始符号S外的其他变量，最后即可得到关于开始符号S的解。 代入消元规则如下：

求得结果。 如果最后得到的关于S的方程式为如下形式， S=α1|α2|…|αh 则将方程式右边所有其中仍然含有语法变量的αi(1≤i≤n)删除，得到的结果就是与G等价的正则表达式。 如果任意的αi(1≤i≤n)均含有语法变量，则Ø就是与G等价的正则表达式。

给定正则表达式r，按如下方法构造正则定义式，并逐步将其转换成正则文法。 引入开始符号S，从如下正则定义式开始： S—>r 按如下规则将S—>r分解为新的正则定义式，在分解过程中根据需要引入新的语法变量。

过程：

例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|ε

正则表达式与正则文法等价： 对任意一个正则文法，存在一个定义同一语言的正则表达式； 对任意一个正则表达式，存在一个定义同一语言的正则文法。