應該如何理解「上下文無關文法」？

01-06

學編譯原理，詞法分析階段學的挺順利。可是進入到語法分析後，一直涉及到一個概念就是上下文無關文法。搜了一些資料，全部都是數據公式解釋的，看不明白。
有人可以通俗的解釋下這個概念嗎？

上下文無關文法就是說這個文法中所有的產生式左邊只有一個非終結符，比如：

S -&> aSb

S -&> ab

這個文法有兩個產生式，每個產生式左邊只有一個非終結符S，這就是上下文無關文法，因為你只要找到符合產生式右邊的串，就可以把它歸約為對應的非終結符。

比如：

aSb -&> aaSbb

S -&> ab

這就是上下文相關文法，因為它的第一個產生式左邊有不止一個符號，所以你在匹配這個產生式中的S的時候必需確保這個S有正確的「上下文」，也就是左邊的a和右邊的b，所以叫上下文相關文法。

上下文無關文法（Context-Free Grammar）就是下推自動機（Pushdown Automata）能夠識別的文法。跟有限狀態自動機（DFA/NFA）相比，多了個棧，有了棧就有了遞歸能力，可以識別括弧表達式（DFA/NFA沒有遞歸能力）

另外CFG也是有歧義的，甚至有的CFG不存在無歧義表示法。某樓回答錯誤。

所有CFG都可以轉成Chomsky Normal Form然後用CYK演算法識別，某答案已經提到了。不過感覺CYK對CFG的理解並不是很有幫助，還是把Chomsky Hierarchy中幾種語言對應的自動機掌握，看看下推自動機比有限狀態機多了什麼、比圖靈機缺了什麼，有助於弄清CFG本質。

拋磚引玉，試著用漢語來解釋一下。比如這個帖子（用「本來」一詞造句，看看誰造的比較有水平。）裡面讓大家用本來造句，結果有這樣的句子：

本來這個進球就是違例的，但你不肯承認也沒辦法

我有一本來自美國的花花公子雜誌

拿我的筆記本來

如果漢語是上下文無關文法的話，那我們任何時候看見「本來」兩個字，都可以把它規約為一個詞。可惜漢語不是上下文無關文法，所以「本來」能否歸約為一個詞，要看它的上下文是什麼。上面的三個例子中，第一句里的「本來」可以規約為一個詞：

（（本來）（（（這個）（進球））（就）（是）（違例的））），（（但）（（你）（不肯）（承認）（也）（沒辦法）））

但後面兩句都不行。後面的兩句大約應該這樣規約：

（我）（有）（（（一本）（來自）（美國）（的））（花花公子雜誌））

（拿）（（我的）（筆記本））（來）

看到問題突然想到的思路，不一定對。可以進一步參考這個Context-free grammar，Context-sensitive grammar。總之，我覺得不從學編譯的角度思考，而是從自然語言的角度思考更容易理解一些。

在我看來上下文無關的文法是指，文法中不存在aAc-&>B aAb -&>C這種情況，即在推導過程中A的產生式體選擇不受A左右的文法符號串影響（即abc）

就是可以等價轉換成 Chomsky normal form 的文法，想明白這個最基本的形式基本就理解CF文發了。

想了解更多推薦看以下關於Context-free語言的部分：

J.E. Hopcroft, R. Motwani, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley 2001.

舉個例子。C的語法其實不是CFG，所以要看上下文的。比如說

T *x;

這是定義一個T的指針並命名為x，還是T乘x?

參見這個：The context sensitivity of C"s grammar

大家分析得真好,其實百科說的很清楚了: V 總可以被字串 w 自由替換，而無需考慮字元 V 出現的上下文

我也一直糾結於「上下文無關」這個詞的理解，總是想不明白到底是跟什麼東西「無關」。忽然有一天醍醐灌頂。

這種文法一般可以畫作樹形。這裡的「上下文」應該指的是某一個節點的兄弟節點！就是說任何一個節點想往下推，只看它自己就行了，跟他的兄弟節點無關。

也就是說，不會存在這種情況：

單獨的a推出mn；

bac卻禁止推出bmnc，只能推出pq；

dae也不能推出dmne，只會推出rst……

等等。

任何時候看到a，就可以無腦替換成mn，不用管它的兄弟們。a的上級推出了bac也好，dae也好，@*^$*iudfuiidffa￥oiu$#op7%iuf……也好，不影響。一定能推出bmnc、dmne、@*^$*iudfuiidffmn￥oiu$#op7%iuf……

這三個例子里的b和c，d和e；@*^$*iudfuiidff和￥oiu$#op7%iuf……就是a的上和下文！

再編一個規整點的例子。

比如英譯漢！規定文法是friend-&>朋友，ship-&>船。那如果是上下文無關的無腦推方法的話，friendship-&>朋友船！船你MEI啊，友誼的小船嗎？說翻就翻！

應該是上下文有關文法。

friend-&>朋友，ship-&>船，friendship-&>友誼。推的時候得看看人家兄弟節點是啥了。

不能無腦替了哦。

PS：這裡隱含了另一個例子：friend也不能推出「fri結束」！哈哈。

其實舉片語更完美，因為是多個單詞，更像是從上面推下來的。

watch-&>觀看，out-&>外面，watch out-&>觀看外面？NO！是留意。

PS2：突然感覺，某些翻譯軟體出的令人啼笑皆非的差錯，是不是就是上下文無關無腦推了呢？

PS3：暴漫熊貓中英文那套表情包，很多都是」上下文無關「無腦翻產生的笑果吧？（另一些可以說是多種情況選錯了）【手動滑稽】

」無鴨梨「。這個要看的情況多了，甚至得看好長一段，考慮發言的環境是網路還是現實，才能確定是真的說沒有鴨梨了，還是」無壓力「。

博大精深。

不請自來，給自己留個答案，出自離散數學及其應用中的表格：

圖中1類文法是上下文有關文法，2類是上下文無關文法，3類是正則文法。

產生式左邊是個非終結符右邊是一堆東西那一堆東西的長度至少比左邊的長

無歧義，不存在多義詞，多義詞就需要上下文確定含義。

詞法分析結果唯一

語法分析結果唯一（語法樹唯一）