什麼是語境免費語法？

Question

有人可以向我解釋一個上下文無關語法是什麼嗎？在查看維基百科條目，然後查看正式語法中的維基百科條目之後，我完全置之不理，完全糊塗。有人會善意地解釋這些是什麼嗎？

我想知道這是因爲我希望研究分析，並就在旁邊，正則表達式引擎的侷限性。

我不知道，如果這些條款是直接相關的編程，或者如果他們更多地涉及普通語言學。如果是這樣的話，我很抱歉，如果是這樣的話，這可能會被移動？

Answer 1

上下文無關語法是滿足某些特性的語法。在計算機科學中，語法描述語言;具體來說，他們描述的是正式語言

正式語言只是一個字符串（符號序列...與字符串「編程」使用非常相似）的集合（對象集合的數學術語）。形式語言的一個簡單例子是長度爲3的所有二進制字符串{000，001，010，011，100，101，110，111}的集合。

語法的工作方式是定義轉換，您可以使用語法描述的語言構造字符串。文法將會說如何將一個開始符號（通常是S）轉換成一些符號串。給出一種語言的語法之前爲：

S -> BBB 
B -> 0 
B -> 1 

解釋這是說，S可被B和B可以通過0代替，和B可以通過1.更換所以的方式構造字符串010我們可以做S→BBB→0BB→01B→010

上下文無關語法只是一個語法，其中你正在替換的東西（箭頭的左邊）是一個語法單個「非終端」符號。非終結符號是您在語法中使用的任何符號，它們不能出現在最終字符串中。在上面的語法中，「S」和「B」是非終端符號，「0」和「1」是「終端」符號。像

S -> AB 
AB -> 1 
A -> AA 
B -> 0 

不規則，因爲它們包含像「AB - > 1」這樣的規則。

Answer 2

語言理論與計算理論有關。哪一個是計算機科學更哲學的一面，關於決定哪些程序是可能的，哪些是可能編寫的，哪些類型的問題是不可能編寫算法來解決的。

正則表達式是描述正則語言的一種方式。常規語言是一種可以由確定性有限自動機決定的語言。

你應該閱讀有限狀態機的文章：http://en.wikipedia.org/wiki/Finite_state_machine

和定期的語言： http://en.wikipedia.org/wiki/Regular_language

所有的正則語言是上下文無關語言，但也有上下文無關語言不屬於正規。上下文無關語言是由上下文無關語法或下推自動機接受的所有字符串的集合，其是具有單個堆棧的有限狀態機：http://en.wikipedia.org/wiki/Pushdown_automaton#PDA_and_Context-free_Languages

有更復雜的語言需要圖靈機（任何可能的程序你可以在你的計算機上寫）來決定一個字符串是否在使用該語言。

語言理論也是對P對NP問題，以及其他一些有趣的東西非常相關。

我的計算機科學導論高三的課本是在解釋這個東西不錯：介紹計算理論。由邁克爾Sipser。但是，花費160美元購買新產品並不是很大。也許你可以找到一份舊版本或在圖書館找到一份副本或者它可以幫助你。

編輯：

正則表達式和較高的語言課程的侷限性進行了研究一噸，在過去50年左右。你可能對正規語言的抽象引理感興趣。這是證明的手段是一定的語言不是正規：

http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages

如果語言不經常也可能是上下文無關，這意味着它可以通過上下文無關格拉默來描述，或可能甚至會出現在更高級的語言類中，您可以通過上下文無關語言的抽象引理來證明它不是上下文無關語言，它與正則表達式類似。

語言甚至可以是不可判定的，這意味着即使是圖靈機（可以編程您的計算機可以運行）不能進行編程，以決定是否字符串應該接受的語言或拒絕。

我認爲你最感興趣的部分是有限狀態機（既有確定性又有確定性），以查看正則表達式可以決定哪些語言，以及抽取引理來證明哪些語言不規則。

基本上，一種語言如果需要某種內存或計數能力的話是不規則的。例如，匹配括號的語言是不規則的，因爲機器需要記住它是否打開了括號以知道是否必須關閉它。

使用字母A和B至少包含三個B的所有字符串的語言是一個普通的語言：一個BA BA BA

使用字母a和b的所有字符串的語言包含更多的b比a的不規則。

而且你不應該所有的有限語言都是正規，例如：

所有字符串的語言少於50個字符使用含有較多的B的比的是普通的字母a和b，因爲它是有限的，我們知道它可以被描述爲（b | abb | bab | bba | aabbb | ababb | ...）等，直到列出所有可能的組合。