資源描述：
《上下文無關(guān)文法與上下文有關(guān)文法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、上下文無關(guān)文法形式語言理論中一種重要的變換文法，用來描述上下文無關(guān)語言，在喬姆斯基分層中稱為2型文法。由于程序設(shè)計(jì)語言的語法基本上都是上下文無關(guān)文法，因此應(yīng)用十分廣泛。簡(jiǎn)介上下文無關(guān)文法（Context-FreeGrammar,CFG） 在計(jì)算機(jī)科學(xué)中，若一個(gè)形式文法G=(N,Σ,P,S)的產(chǎn)生式規(guī)則都取如下的形式：V->w，則稱之為上下文無關(guān)的，其中V∈N，w∈(N∪Σ)*。上下文無關(guān)文法取名為“上下文無關(guān)”的原因就是因?yàn)樽址鸙總可以被字串w自由替換，而無需考慮字符V出現(xiàn)的上下文。一個(gè)形式語言是上下文無關(guān)的，如果它是由上
2、下文無關(guān)文法生成的﹙條目上下文無關(guān)語言﹚?！ ∩舷挛臒o關(guān)文法重要的原因在于它們擁有足夠強(qiáng)的表達(dá)力來表示大多數(shù)程序設(shè)計(jì)語言的語法；實(shí)際上，幾乎所有程序設(shè)計(jì)語言都是通過上下文無關(guān)文法來定義的。另一方面，上下文無關(guān)文法又足夠簡(jiǎn)單，使得我們可以構(gòu)造有效的分析算法來檢驗(yàn)一個(gè)給定字串是否是由某個(gè)上下文無關(guān)文法產(chǎn)生的。例子可以參見第10頁，共8頁LR分析器和LL分析器?！ NF﹙巴克斯-諾爾范式﹚經(jīng)常用來表達(dá)上下文無關(guān)文法。 文法規(guī)則使用相似的表示法。名字用斜體表示（但它是一種不同的字體，所以可與正則表達(dá)式相區(qū)分）。豎線仍表示作為選擇
3、的元符號(hào)。并置也用作一種標(biāo)準(zhǔn)運(yùn)算。但是這里沒有重復(fù)的元符號(hào)（如正則表達(dá)式中的星號(hào)*），稍后還會(huì)再講到它。表示法中的另一個(gè)差別是現(xiàn)在用箭頭符號(hào)“→”代替了等號(hào)來表示名字的定義。這是由于現(xiàn)在的名字不能簡(jiǎn)單地由其定義取代，而需要更為復(fù)雜的定義過程來表示，這是由定義的遞歸本質(zhì)決定的。 第10頁，共8頁 同正則表達(dá)式類似，文法規(guī)則是定義在一個(gè)字母表或符號(hào)集之上。在正則表達(dá)式中，這些符號(hào)通常就是字符，而在文法規(guī)則中，符號(hào)通常是表示字符串的記號(hào)。我們利用C中的枚舉類型定義了在掃描程序中的記號(hào)；為了避免涉及到特定實(shí)現(xiàn)語言（例如C）中表示記號(hào)
4、的細(xì)節(jié)，就使用了正則表達(dá)式本身來表示記號(hào)。此時(shí)的記號(hào)就是一個(gè)固定的符號(hào)，如同在保留字while中或諸如+或:=這樣的特殊符號(hào)一樣，對(duì)于作為表示多于一個(gè)串的標(biāo)識(shí)符和數(shù)的記號(hào)來說，代碼字體為斜體，這就同假設(shè)這個(gè)記號(hào)是正則表達(dá)式的名字（這是它經(jīng)常的表示）一樣?！ ∩舷挛臒o關(guān)文法的卻利用了與正則表達(dá)式中極為類似的命名慣例和運(yùn)算，二者的主要區(qū)別在于上下文無關(guān)文法的規(guī)則是遞歸的（recursive）。例子例子1 一個(gè)簡(jiǎn)單的上下文無關(guān)文法的例子是：S->aSb
5、ε。這個(gè)文法產(chǎn)生了語言{anbn:n≥0}。不難證明這個(gè)語言不是正規(guī)的?！ ?/p>
6、例子2 這個(gè)例子可以產(chǎn)生變量x,y,z的算術(shù)表達(dá)式： S->T+S
7、T-S
8、T T->T*T
9、T/T
10、(S)
11、x
12、y
13、z 例如字串"(x+y)*x-z*y/(x+x)"就可以用這個(gè)文法來產(chǎn)生?！ 〉?0頁，共8頁例子3 字母表{a,b}上a和b數(shù)目不相等的所有字串可以由下述文法產(chǎn)生： S->U
14、V U->TaU
15、TaT V->TbV
16、TbT T->aTbT
17、bTaT
18、ε 這里T可以產(chǎn)生a和b數(shù)目相等的所有字串，U可以產(chǎn)生a的數(shù)目多于b的數(shù)目的所有字串，V可以產(chǎn)生a的數(shù)目少于b的數(shù)目的所有字串。范式每一個(gè)不
19、生成空串的上下文無關(guān)文法都可以轉(zhuǎn)化為等價(jià)的Chomsky范式或Greibach范式。這里兩個(gè)文法等價(jià)的含義指它們生成相同的語言。 由于Chomsky范式在形式上非常簡(jiǎn)單，所以它在理論和實(shí)踐上都有應(yīng)用。比如，對(duì)每一個(gè)上下文無關(guān)語言，我們可以利用Chomsky范式構(gòu)造一個(gè)多項(xiàng)式算法，用它來判斷一個(gè)給定字串是否屬于這個(gè)語言﹙CYK算法﹚。同態(tài)映射下的性質(zhì)第10頁，共8頁對(duì)任意正整數(shù)n,令…，an}，Σ'n={a'1，…，a'n},定義喬姆斯基變換文法G=(Σ，V，S，P)為(Σn∪Σ'n,S,S,P={S→,S→SaiSa'iS
20、
21、1≤i≤n})。這個(gè)文法生成的語言稱為代克集。如果把a(bǔ)i看作開括號(hào)，把a(bǔ)'i看作相應(yīng)的閉括號(hào)，則n維代克集Dn就是由幾種不同的括號(hào)對(duì)組成的配對(duì)序列之集合。例如,a1a2a2a'2a2a'1和a1a'1a2a'2a1a'1都屬于D2，用括號(hào)表示時(shí)可以寫成（〔（）〕）和（）〔〕（）。 代克集是把正則語言族擴(kuò)大成上下文無關(guān)語言族的工具。對(duì)任一上下文無關(guān)語言L,必存在兩個(gè)同態(tài)映射h1和h2，以及一個(gè)正則語言R，使L=h2【h1(D2)∩R】,其中D2是二維代克集，反之亦然?！ 「M(jìn)一步，上下文無關(guān)語言族是包含D2，且在同態(tài)、逆同
22、態(tài)和與正則語言相交三種代數(shù)運(yùn)算下封閉的最小語言族。加上乘積和乘冪閉包兩種運(yùn)算后，此結(jié)論仍真。文法形式和文法的相似性在兩種符號(hào)置換的意義下(終結(jié)符和非終結(jié)符分別替換),許多文法之間有著相似性。把一組彼此相似的文法抽象成一個(gè)更高級(jí)的形式體系，就叫作文法形式。迄今，文法形式的研究主要集中在上下文
