如何定義上下文無(wú)關(guān)文法？

上下文無(wú)關(guān)文法（Content-Free Grammar, CFG）

在計(jì)算機(jī)科學(xué)中，一個(gè)形式文法 G = (N, ∑, P, S) 稱(chēng)之為上下文無(wú)關(guān)的，如果它的產(chǎn)生式規(guī)則都取如下的形式：V -> w ，這里 V∈N ，w∈(N∪∑)* 。上下文無(wú)關(guān)文法取名為“上下文無(wú)關(guān)”的原因就是因?yàn)樽址?V 總可以被字串 w 自由替換，而無(wú)需考慮字符 V 出現(xiàn)的上下文。一個(gè)形式語(yǔ)言是上下文無(wú)關(guān)的，如果它是由上下文無(wú)關(guān)文法生成的（條目上下文無(wú)關(guān)語(yǔ)言）。

上下文無(wú)關(guān)文法重要的原因在于它們擁有足夠強(qiáng)的表達(dá)力來(lái)表示大多數(shù)程序設(shè)計(jì)語(yǔ)言的語(yǔ)法；實(shí)際上，幾乎所有程序設(shè)計(jì)語(yǔ)言都是通過(guò)上下文無(wú)關(guān)文法來(lái)定義的。另一方面，上下文無(wú)關(guān)文法又足夠簡(jiǎn)單，使得我們可以構(gòu)造有效的分析算法來(lái)檢驗(yàn)一個(gè)給定字串是否是由某個(gè)上下文無(wú)關(guān)文法產(chǎn)生的。例子可以參見(jiàn) LR 分析器和 LL 分析器。

BNF （巴克斯-諾爾范式）經(jīng)常用來(lái)表達(dá)上下文無(wú)關(guān)文法。

文法規(guī)則使用相似的表示法。名字用斜體表示（但它是一種不同的字體，所以可與正則表達(dá)式相區(qū)分）。豎線仍表示作為選擇的元符號(hào)。并置也用作一種標(biāo)準(zhǔn)運(yùn)算。但是這里沒(méi)有重復(fù)的元符號(hào)（如正則表達(dá)式中的星號(hào)*），稍后還會(huì)再講到它。表示法中的另一個(gè)差別是現(xiàn)在用箭頭符號(hào)“→”代替了等號(hào)來(lái)表示名字的定義。這是由于現(xiàn)在的名字不能簡(jiǎn)單地由其定義取代，而需要更為復(fù)雜的定義過(guò)程來(lái)表示，這是由定義的遞歸本質(zhì)決定的。

同正則表達(dá)式類(lèi)似，文法規(guī)則是定義在一個(gè)字母表或符號(hào)集之上。在正則表達(dá)式中，這些符號(hào)通常就是字符，而在文法規(guī)則中，符號(hào)通常是表示字符串的記號(hào)。我們利用C中的枚舉類(lèi)型定義了在掃描程序中的記號(hào)；為了避免涉及到特定實(shí)現(xiàn)語(yǔ)言（例如C）中表示記號(hào)的細(xì)節(jié)，就使用了正則表達(dá)式本身來(lái)表示記號(hào)。此時(shí)的記號(hào)就是一個(gè)固定的符號(hào)，如同在保留字 while 中或諸如+或: =這樣的特殊符號(hào)一樣，對(duì)于作為表示多于一個(gè)串的標(biāo)識(shí)符和數(shù)的記號(hào)來(lái)說(shuō)，代碼字體為斜體，這就同假設(shè)這個(gè)記號(hào)是正則表達(dá)式的名字（這是它經(jīng)常的表示）一樣。