編譯原理-文法的定義與分類

前言

語言是一定的群體用來信息交流的工具 ，而信息交流的基礎是需要按照共同約定的生成規(guī)則和理解規(guī)則去生成句子和理解句子。計算機的語言具有嚴格的語法、語義，易于形式化的特征。程序設計語言經過形式化提取后可以得到以下內容：

程序設計語言(Programming Language)：組成程序的所有語句的集合。

程序(Program)：滿足語法規(guī)則的語句序列。

語句(Sentence) ：滿足語法規(guī)則的單詞序列。

單詞(Token) ：滿足詞法規(guī)則的字符串。

語言的描述形式——文法，對于單詞和語句有不同的概念：

詞法——單詞
單詞的組成規(guī)則
描述方法：BNF范式、正規(guī)式

語法——語句
語句的組成規(guī)則
描述方法：BNF范式、語法(描述)圖

一、文法的定義

以賦值語句為例，首先進行如下四個定義：
非終結符號集V =
{<賦值語句>，<左部量>，<右部表達式>，<簡單變量>，<下標變量>，<運算符>}
終結符號集T =
{a , b, c, m[1], m[2], m[3], +, -}
語法規(guī)則集P =
{<賦值語句> —> <左部量>=<右部表達式> ，……}
開始符號S = <賦值語句>

按照上述定義，則文法G的形式化定義為誒一個四元組：

Ｇ=(Ｖ，T，Ｐ，Ｓ)

Ｖ：非終結符(Variable )集
每個非終結符稱為一個語法變量（成分）——代表某個語言的各種子結構。

T：終結符(Terminal)集。
語言的句子中出現(xiàn)的字符，Ｖ∩T = 空集

Ｓ：開始符號(Start Symbol)，S∈Ｖ
代表文法所定義的語言，至少在產生式左側出現(xiàn)一次。

Ｐ：產生式(Product)集合。

二、文法的分類

根據(jù)語言結構的復雜程度（形式語言）（涉及文法的復雜程度、分析方法的選擇、反映文法描述語言的能力）可以分為以下四種語言：
0型文法 (即：短語結構文法)
1型文法 (即：上下文有關文法)
2型文法 (即：上下文無關文法)
3型文法 (即：正規(guī)文法)

0.短語結構語言(PSL)

如果G滿足文法定義的要求，則Ｇ是０型文法（短語結構文法PSG: Phrase Structure Grammar ）。

1.上下文有關文法(CSG)

如果對于任意α —>β∈P，均有 **|β|≥|α|**成立，則稱Ｇ為１型文法。即：上下文有關文法（CSG——Context Sensitive Grammar）

2.上下文無關文法(CFG)

如果對于任意α —>β∈P，均有|β|≥|α|，并且α∈V成立，則稱G為２型文法，即：上下文無關文法(CFG: Context Free Grammar)（CFG能描述程序設計語言的多數(shù)語法成分）。

3.正規(guī)文法(RG)

設A、B∈V，a∈T+
右線性(Right Linear)文法：A→aB或A→a
左線性(Left Linear)文法：A→Ba或A→a
都是３型文法(正規(guī)文法 Regular Grammar -RG)
其中左線性文法和右線性文法等價，只是識別句子的方向不同。

正規(guī)文法與正則表達式的相互轉化.

三、判斷以下文法的類別

G1: S —> 0 | 1 | 00 | 11 （正則文法）
G2: S —> A | B | AA | BB, A —> 0, B —> 1 （上下文無關文法）
G3: S —> 0 | 1 | 0A | 1B, A —> 0, B —> 1 （正則文法）
G4: S —> A | B | BC, A —> 0, B —> 1,C —> 21, C —> 11, C—> 2 （上下文無關文法）
G5: S —> 0 | 0S （正則文法）
G6: S —> ε | 0S （短語結構文法）
G7: S —> ε | 00S111 （短語結構文法）
G8: A —> aS | bS | cS | a | b | c （正則文法）
G9: S —> 0A | 1B | 2C | 0SA | 1SB | 2SC
0A —> A0 1A —> A1
2A —> A2 0B —> B0
1B —> B1 2B —> B2
0C —> C0 1C —> C1
2C —> C2
（上下文有關文法）
G10: S —> aT | bT | cT
T —> ε | a | b | c | 0 | 1 | 2 | 3 | aT | bT | cT | 0T | 1T | 2T | 3T （短語結構文法）

總結

G = (V，T，P，S)是一個文法,α→β ∈ P

• G是0型文法，L(G)是0型語言；
• |α|≤|β|:G是1型文法，L(G)是1型語言(除Ｓ→ε);
• α∈Ｖ : G是2型文法，L(G)是2型語言;
• A→aB或A→a: G是右線性文法，L(G)是3型語言
  A→Ba或A→a : G是左線性文法，L(G)是3型語言

四種文法之間的關系是將產生式作進一步限制而定義的。

四種文法之間的逐級“包含”關系如下：

到此這篇關于詳解文法的定義與分類(編譯原理)的文章就介紹到這了,更多相關文法的定義與分類內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！