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

前言

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

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

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

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

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

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

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

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

一、文法的定義

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

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

Ｇ=(Ｖ，T，Ｐ，Ｓ)

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

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

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

Ｐ：產(chǎn)生式(Product)集合。

二、文法的分類

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

0.短語結(jié)構(gòu)語言(PSL)

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

1.上下文有關(guān)文法(CSG)

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

2.上下文無關(guān)文法(CFG)

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

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

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

正規(guī)文法與正則表達(dá)式的相互轉(zhuǎn)化.

三、判斷以下文法的類別

G1: S —> 0 | 1 | 00 | 11 （正則文法）
G2: S —> A | B | AA | BB, A —> 0, B —> 1 （上下文無關(guān)文法）
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 （上下文無關(guān)文法）
G5: S —> 0 | 0S （正則文法）
G6: S —> ε | 0S （短語結(jié)構(gòu)文法）
G7: S —> ε | 00S111 （短語結(jié)構(gòu)文法）
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
（上下文有關(guān)文法）
G10: S —> aT | bT | cT
T —> ε | a | b | c | 0 | 1 | 2 | 3 | aT | bT | cT | 0T | 1T | 2T | 3T （短語結(jié)構(gòu)文法）

總結(jié)

G = (V，T，P，S)是一個(gè)文法,α→β ∈ 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型語言

四種文法之間的關(guān)系是將產(chǎn)生式作進(jìn)一步限制而定義的。

四種文法之間的逐級“包含”關(guān)系如下：

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

最新評論