前言

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

程式設計語言(Programming Language)：組成程式的所有陳述句的集合，
程式(Program)：滿足語法規則的陳述句序列，
陳述句(Sentence) ：滿足語法規則的單詞序列，
單詞(Token) ：滿足詞法規則的字串，

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

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

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

一、文法的定義

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

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

Ｇ = ( Ｖ， T ，Ｐ，Ｓ ) Ｇ = (Ｖ，T，Ｐ，Ｓ) Ｇ=(Ｖ，T，Ｐ，Ｓ)
Ｖ：非終結符(Variable )集
每個非終結符稱為一個語法變數（成分）——代表某個語言的各種子結構，

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

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

Ｐ：產生式(Product)集合，

二、文法的分類

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

0.短語結構語言(PSL)

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

1.背景關系有關文法(CSG)

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

2.背景關系無關文法(CFG)

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

3.正規文法(RG)

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

三、判斷以下文法的類別

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型語言

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

四種文法之間的逐級“包含”關系如下：
在這里插入圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/238590.html

標籤：其他

上一篇：C++性能之驚群問題

下一篇：PTA 8習題講解