什麼編程語言是上下文無關的？

或者，更精確一點：哪些編程語言是由上下文無關語法定義的？什麼編程語言是上下文無關的？

從我收集的信息來看，由於諸如宏和模板之類的原因，C++沒有上下文。我的直覺告訴我，函數式語言可能沒有上下文，但我沒有任何硬數據來支持。

爲簡潔的例子外代表:-)

來源

2009-05-22 n3rd

爲什麼地球上這被認爲與編程無關？ – kajaco 2009-05-22 16:20:02

我對這個標籤不太確定，我想這不是真的關於編程本身的過程。但你是對的，我刪除了標籤。 – n3rd 2009-05-22 16:43:14

的集合，是語法正確的程序是免費的背景下，幾乎所有的語言。

對於幾乎所有語言而言，編譯的程序集都不是上下文無關的。例如，如果集合中的所有編譯C程序是免費的情況下，然後用常規的語言（也稱爲正則表達式），設置匹配

^int main\(void\) { int a+; a+ = a+; return 0; }$

將上下文所有編譯C程序的交叉免費的，但這顯然與語言a^kba^kba^k同名，這是衆所周知的而不是是上下文無關的。

來源

2009-05-22 15:37:22 Dave

+1的答案是正確的。接受的答案是誤導性的。 – 2010-02-23 20:27:45

如果有人希望看到證明語言{a^k b a^k b a^k b | k> = 0}不規則，請參閱Torben Mogensen的「編譯器設計基礎」一章2.10.2：http://www.diku.dk/~torbenm/Basics – 2013-07-16 18:49:50

hmm語法有效程序和語義有效程序之間的區別是誤導性的，因爲後者在上下文敏感的語法中（對編程語言感興趣的情況）被語法表達。說一個程序在語法上是有效的，因爲CFG可以接受它，這是錯誤的，因爲有效程序的語言要求條件限制只由CFG接受的字符串，這意味着它們不能被CFG描述。無論如何+1 – 2015-06-08 19:44:36

VHDL有些上下文敏感。

（谷歌：解析 - VHDL-IS-非常硬）

來源

2009-05-22 15:46:43

去一個免費的非上下文無關文法的最生動的例子，Perl的語法是，據我所知，turing-complete。

來源

2009-08-18 03:14:29

根據你對問題的理解，答案會改變。但是IMNSHO，正確的答案是所有現代編程語言實際上都是上下文敏感的。例如，沒有上下文無關文法只接受語法上正確的C程序。指向C語言的yacc/bison上下文無關語法的人員缺少了這一點。

來源

2011-08-02 06:50:53 starflyer

我認爲Haskell和ML支持上下文無關。對於Haskell，請參閱link。

來源

2012-06-22 07:39:11 RoboAlex

如果我理解你的問題，你正在尋找可以用上下文無關語法（cfg）來描述的編程語言，以便cfg生成所有有效的程序和唯一有效的程序。

我相信大多數（如果不是全部的話）現代編程語言因此不是上下文無關的。例如，一旦您擁有用戶定義的類型（在現代語言中很常見），您就會自動對上下文敏感。

驗證語法和驗證程序的語義正確性是有區別的。檢查語法是上下文無關的，而檢查語義的正確性不是（再次，在大多數語言中）。

但是，這並不意味着這種語言不能存在。例如，非類型lambda calculus可以使用上下文無關語法來描述，並且當然是圖靈完備的。

來源

2012-06-25 13:46:31 Ginandi

大多數現代編程語言都不是上下文無關的語言。作爲一個證明，如果我深入瞭解CFL的根源，其相應的機器PDA無法處理像{ww | w is a string}這樣的字符串匹配。所以大多數編程語言都需要這些

例子：

int fa; // w 
fa=1; // ww as parser treat it like this

來源

2013-04-01 14:51:32

什麼編程語言是上下文無關？ [...]

TL; DR：幾乎沒有，但Brainfuck和SKI combinator calculus兩種，由於它們的語法的簡單性。

較長的版本：通常，上下文無關文法（CFGS）僅用於大致指定語言的語法。必須區分句法正確的程序和程序編譯。最常見的是，編譯器將語言分析分爲語法分析，它們構建並驗證一段代碼的一般結構，並且語義分析驗證程序的含義。

如果使用「上下文無關語言」表示「...爲所有程序編譯」，那麼答案是：幾乎沒有。符合這項法案的語言幾乎沒有任何規則或複雜的功能（如變量的存在，空白敏感或類型系統）。

我的直覺告訴我，函數式語言可能是免費的上下文[...]

無論是語言是上下文與否無關，與它具有功能性。這只是一個語言規則和功能要解析多麼複雜的問題。

下面是命令式語言Brainfuck一個CFG：

Program → Instr Program | ε 
Instr → '+' | '-' | '>' | '<' | ',' | '.' | '[' Program ']'

而且這裏有一個CFG的功能SKI組合子演算：

Program → E 
E → 'S' E E E 
E → 'K' E E 
E → 'I' 
E → '(' E ')'

如果，另一方面，「上下文無關語言「只意味着」...所有程序都通過語法分析「，答案只是語法本身的複雜程度。有很多句法特徵很難或不可能用CFG單獨描述。通過向解析器添加額外的狀態來跟蹤計數器，查找表等，克服了其中的一些問題。的句法特徵

例子是不可能表達了CFG：

Indentation-和空白敏感的語言如Python和Haskell。跟蹤任意嵌套的縮進級別本質上是上下文敏感的，並且需要單獨的縮進級別計數器。（只允許固定級別的縮進將理論上通過複製每個縮進等級的語法來工作，但實際上這是不方便的。）
C Typedef Parsing Problem表示C語言程序在詞法分析過程中不明確，因爲如果某個東西是現有類型的常規標識符或typedef別名，它無法單獨從語法知道。
宏和基於模板的語言，如Lisp，C++，模板Haskell，Nim等等。由於語法在被解析時會發生變化，因此一種解決方案是將解析器變成自修改程序。正如對問題Is C++ context-free or context-sensitive?的回答所表達的，答案既不是。

句法特徵的一個例子是可能表現爲CFG，但往往不是：

通常情況下，運營商優先級和結合都不能直接在CFGS表示。例如，對於一小的表達式文法其中^結合不同於×更緊，和×結合不同於+更緊一個CFG，可能是這樣的：
```
E → E^E 
E → E × E 
E → E + E 
E → (E) 
E → num 
```
這CFG是ambiguous，然而，往往伴隨着一個precedence/associativity table說，例如結合最緊密，結合比+更緊密，結合是正確的，並且結合X和+。

優先級和關聯性可以用系統化的方式編碼到CFG中，這樣它就是明確的，只有在操作符正確行爲的地方纔會生成語法樹。上面語法的一個這樣的例子：
```
E₀ → EA E₁ 
EA → E₁ + EA 
EA → ε 
E₁ → EM E₂ 
EM → E₂ × EM 
EM → ε 
E₂ → E₃ EP 
EP →^E₃ EP 
E₃ → num 
E₃ → (E₀) 
```
但是曖昧CFGS +優先級/關聯表是常見的，因爲它們是更具有可讀性和因爲各種類型的LR parser發生器文庫可以通過eliminating shift/reduce conflicts產生更有效的解析器，而不是處理用明確的，更大尺寸的轉換語法。

從理論上講，所有有限的字符串都是常規語言，所以所有有限大小的合法程序都是規則的。由於常規語言是上下文無關語言的子集，所有有限大小的程序都是上下文無關的。爭論繼續，

雖然可以認爲它是一種語言只允許少於一百萬行的程序的可接受限制，但將一種編程語言描述爲常規語言是不切實際的：說明會太大。
- 託本Morgensen的Basics of Compiler Design, ch. 2.10.2

這同樣適用於CFGS。以不同的方式解決您的子問題一點點，

哪些編程語言由上下文無關文法定義？

大多數實際的編程語言是由它們的實現定義，對於真實世界的編程語言大多數語法分析器要麼是手寫或使用該擴展上下文解析解析器生成。不幸的是，找到您最喜歡的語言的確切CFG並不常見。當你這樣做的時候，通常是在Backus-Naur form（BNF）中，或者一個解析器規範，它很可能不是純粹的上下文無關的。從野生的語法規範的

例子：

來源

2013-07-16 20:18:45

什麼編程語言是上下文無關的？

回答

相關問題