在電腦科學中,正則文法是產生式規則取下述形式的一種形式文法(N, Σ, P, S):
- A -> a ,此處的A是N中的非終結符號,a是Σ中的終結符號;
- A -> aB,此處的A和B是N中的非終結符號,a是Σ中的終結符號;
- C -> ε,此處的C是N中的非終結符號。
下面給出一個正則文法的例子:
文法G = (N, Σ, P, S),其中N = {S, A},Σ = {a, b, c},S是起始符號,P包含下述規則:
- S -> aS
- S -> bA
- A -> ε
- A -> cA
這個文法描述的語言也可以用正則表達式a*bc* 來表達。
正則文法描述的語言構成了正則語言類,正則語言類中的語言也可以由有限狀態自動機或正則表達式來表達。