本文鏈接：https://blog.csdn.net/Helloyongwei/article/details/79638785
字母表與符號串
在介紹字母表和符號串之前晾咪，讓我們來看看下面的例子：
A = {a, b, c, …, A, B, C, …}
B = {0, 1}
C = {0, 1, 2, …, 8, 9}
由集合A中的元素任意組合可以得到英文單詞， 由集合B中的任意元素組合可以得到二進制數(shù)據(jù)，由C中的任意元素可以得到非負整數(shù)。
上例中媳搪， 每個集合就可以看成一個字母表得湘， 集合中的元素就是符號， 字母表通常用大寫的字母表示办素。由字母表中的元素互相組合生成的串就叫符號串， 我們也常稱為字符串或串祸穷。
下面給出字母表和符號串的相關(guān)定義：

字母表是符號的非空有窮集合性穿， 符號是語言中最基本的不可再分單位。
符號串是字母表中符號組成的有窮序列
不含任何符號的串稱為空串雷滚， 記作 ε
字母表上的符號以某種規(guī)則構(gòu)成的串稱為句子

為了便于研究季二， 通常我們將大寫字母A，B揭措，C等表示集合胯舷， a，b绊含，c等表示符號桑嘶， α，β 等表示符號串躬充， 又是也會加上下標逃顶。

聯(lián)結(jié)
聯(lián)結(jié)是符號串集的乘積， 聯(lián)結(jié)還是一個串集充甚。
串集A={α1以政，α2，…}伴找，B={β1盈蛮，β2，…}技矮，則聯(lián)結(jié)AB={αβ| α∈ A且β∈ B}抖誉，假設(shè)A有n個元素， B有m個元素衰倦，則聯(lián)結(jié)AB就有n×m個元素袒炉。
聯(lián)結(jié)具有以下性質(zhì)（設(shè)A有m個元素）：

串集自身的乘積稱作串集的方冪
A0={ε}A0={ε} 且 |An|=mn|An|=mn
字母表A的n次方冪是字母表A上所有長度為n的串集
閉包與正閉包
假設(shè)有字母表A， 則閉包為
A?=A0∪A1∪A2∪A3∪A4....
A?=A0∪A1∪A2∪A3∪A4....

正閉包為:
A?=A1∪A2∪A3∪A4....
A?=A1∪A2∪A3∪A4....
樊零，
正閉包即為:
A??ε
A??ε
字母表上的語言是字母表正閉包的子集

文法（重點）
文法是用來描述語言的語法成分結(jié)構(gòu)構(gòu)造的形式規(guī)則我磁， 我們通常用G表示。

語法成分由句子和構(gòu)成句子的單詞組成
語言由句子組成

我們首先來看一個文法：

N→ ND|D
D→ 0|1
上面的文法中有兩條規(guī)則（1和2）， 由這兩條文法規(guī)則組成了文法夺艰。由文法可以推導出形如1011的二進制句子：
N → ND
→ NDD
→ NDDD
→ 1DDD
→ 10DD
→ 101D
→ 1011

同樣叛溢， 上面的文法也可以推出句子101111， 10101等二進制數(shù)劲适。上例中， N厢蒜，D只要想推就能推出下一步霞势， 因此我們把N，D叫做非終結(jié)符斑鸦。而0愕贡，1不能推出任何東西，我們叫做終結(jié)符巷屿。推導的過程是從N開始的固以， N就是開始符號。推導的每一步可以得到一個產(chǎn)生式嘱巾。從文法推導出句子的過程可以叫做推導憨琳，推導的逆過程叫做規(guī)約。
看完示例后我們給這些概念相關(guān)定義旬昭。

非終結(jié)符
規(guī)則的左部符號篙螟， 通常用VN 表示。

終結(jié)符
在規(guī)則的右部问拘， 它是語言不可再分的單位遍略，組成句子的基本單位， 常用VT 表示骤坐。

開始符號
為非終結(jié)符绪杏，又稱為識別符號， 常用S表示纽绍。

產(chǎn)生式
定義符號串之間關(guān)系的一組規(guī)則蕾久， 形如A→ α，文法規(guī)則是產(chǎn)生式拌夏， 產(chǎn)生式不一定是文法規(guī)則腔彰。

推導
由文法開始符號開始推導， 用產(chǎn)生式的右部取代產(chǎn)生式的左部辖佣， 直到推到終結(jié)符號為止霹抛。

推導分為最左推導和最右推導， 最左推導每次替換式子的最左邊卷谈， 最右替換每次推導式子的最右邊杯拐。

規(guī)約
規(guī)約是句子通過文法規(guī)則將產(chǎn)生式的左部取代右部， 直到規(guī)約到非中介符為止。

規(guī)約也分為最左規(guī)約和最右規(guī)約端逼。 最左規(guī)約和最右推導互為逆過程朗兵，同樣，最右規(guī)約和最左推導互為逆過程顶滩。

句型余掖，句子，語言
句型是從文法的開始符號S開始礁鲁， 每步推導（包括0步推導）所得到的的字符串α 盐欺，記作S??α，α∈(VN∪VT)S??α仅醇，α∈(VN∪VT) 冗美。
句子是僅含有終結(jié)符的句型。
語言由S開始通過1步及以上推導所得句子的集合析二， 記作L(G), L(G)={S?+α粉洼，α∈V?T}L(G)={S?+α，α∈VT?}
文法的遞歸定義
在文法規(guī)則中叶摄， 非終結(jié)符的定義包含了非終結(jié)符本身属韧， 這樣的定義稱之為遞歸定義。
在前面所講的例子中N→ ND|D 就是遞歸定義蛤吓，因為在此規(guī)則中N還可以推導出N挫剑。
若文法中有遞歸定義， 則一定要有出口柱衔， 否則定義的規(guī)則就是無效的樊破。加入不定義一個出口，那么就永遠推導不完唆铐，也就推導不出句子哲戚。
還是上面的例子， 雖然N→ ND|D 是遞歸定義艾岂， 但是D→ 0|1 給出了出口顺少， 那么此文法就是有效的。

文法和語言的形式定義（重點）
Chomsky將文法定義為四元組 G=(VN王浴，VT脆炎，P，S)G=(VN氓辣，VT秒裕，P，S)钞啸， 其中VNVN表示非終結(jié)符的集合几蜻，VTVT 表示終結(jié)符的集合喇潘， P表示產(chǎn)生式的有窮集合， S表示開始符號梭稚。
文法具體又可以分為0型文法颖低， 1型文法， 2型文法弧烤，3型文法忱屑。下面的說明中V=VN∪VTV=VN∪VT 。

0型文法：P中的產(chǎn)生式α?βα?β, 其中α∈V+α∈V+ 并至少含有一個非終結(jié)符暇昂，β∈V?β∈V?
1型文法：P中的產(chǎn)生式α?βα?β莺戒， 除可能有S?εS?ε 外均有|β|≥|α||β|≥|α| 。 若有S?εS?ε 话浇，規(guī)定S不得出現(xiàn)在產(chǎn)生式的右部。
1′1′ 型文法（等價于1型文法）：P中的產(chǎn)生式α?βα?β闹究， 除可能有S?εS?ε 外有αAβ?αRβαAβ?αRβ 幔崖，其中α，β∈V?α渣淤，β∈V? 且 A∈VN赏寇，R∈V+A∈VN，R∈V+
2型文法：P中的產(chǎn)生式具有形式A?βA?β 价认， 其中A∈VN嗅定，β∈V?A∈VN，β∈V?
3型文法：P中的產(chǎn)生式具有形式A?αβ用踩，A?αA?αβ渠退，A?α 或者 A?Bα，A?αA?Bα脐彩，A?α 碎乃， 其中A，B∈VN惠奸，α∈V?TA梅誓，B∈VN，α∈VT? 佛南。
0型文法又叫做短語文法或無限制文法梗掰， 識別0型語言的自動機稱為圖靈機（TM）。
1型文法又稱為上下文有關(guān)文法或者長度增加文法嗅回， 通過線性界限自動機（LBA）識別及穗。
2型文法稱為上下文無關(guān)文法，記作CFG（Context-Free Grammar）绵载， 通過下推自動機（PDA）識別申尼。
3型文法稱為正規(guī)文法桦山，記作RG（Regular Grammar）峭跳， 通過有限狀態(tài)自動機識別。

我們通常研究上下文無關(guān)文法和正規(guī)文法丸氛， 因為程序設(shè)計語言的語法和詞法規(guī)則主要與2型文法和3型文法有關(guān)。

語法樹
語法樹用來描述句子的結(jié)構(gòu), 這讓我們在語法分析時更直觀的感受文法. 語法樹還可以用來判斷文法二義性, 若一個句子具有二義性, 那么其語法樹至少有兩個.
假設(shè)某二型文法
S→aB,A→a,A→bAA,B→aBBS→aB,A→a,A→bAA,B→aBB
S→bA,A→aS,B→bS,B→bS→bA,A→aS,B→bS,B→b
可通過最左推導產(chǎn)生的句子為aabbab:
S→aB→aaBB→aabSB→aabbAB→aabbaB→aabbabS→aB→aaBB→aabSB→aabbAB→aabbaB→aabbab
產(chǎn)生如下的語法樹,:

由語法樹我們引進五個術(shù)語:

子樹:語法樹中除了葉子結(jié)點以外的任意結(jié)點連同它所有的子孫結(jié)點構(gòu)成的一課子樹.
修剪子樹: 剪去除子樹根以外的其余部分, 該子樹根稱為一個新的葉子結(jié)點.
句型: 樹的根節(jié)點所能推出的任意串都為句型
短語: 子樹的葉子結(jié)點從左到右連成的串, (短語是相對句型而言的)
4.1 簡單短語: 短語是某子樹經(jīng)過一步推導得來的, 稱為該子樹的簡單短語, 也叫直接短語
句柄: 句型中的最左邊簡單短語
在上例中, aabbab的句型, 短語, 簡單短語, 句柄分別為:
句型: aabbab (這是一個句子, 句子是特殊的短語, 具體請看上文)
短語: a, ba, bba, abbab, aabbab (共有5個)
簡單短語: a, b
句柄: a

版權(quán)聲明：本文為CSDN博主「CSDN認證用戶」的原創(chuàng)文章著摔，遵循CC 4.0 by-sa版權(quán)協(xié)議缓窜，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/Helloyongwei/article/details/79638785