如何快速而準確地判斷一門語言的語法（或部分語法）屬於哪個Chomsky Hierarchy？

01-13

一般來說基本沒有語言是type3或者type4的。對於你的語言，你把它用type2的語法寫出來，然後看看這個語法是不是可以幫你解決所有錯誤（譬如說int變數不能賦值給一個char*之類的——如果你認為這是語法的話——這個type1可以做到），如果不行，那他多半是type1的。type0就牛逼了，不過手寫type1文法幾乎是一件不可能完成的事情，所以我覺得你只需要判斷他是不是上下文有關的就好了。

剛才想了想，C++應該就是type0的，因為他有圖靈完備的模板元編程，而且還有很多技巧可以產生只有圖靈完備的「檢查程序」才能查出來的錯誤，譬如說int x[用constexpr函數算出來的值]……

謝謝邀請。

事實上，這個問題是沒法回答的。因為喬姆斯基的理論是針對一般語言的，而題目限定里沒有說過是什麼語言場景。我的專業是程序設計語言，所以只能說程序設計語言。

目前可見的大部分程序設計語言中，通常是二型文法（上下文無關文法），附帶少量簡單的一型文法元素（上下文有關文法）。之所以是二型而非三型，因為我們的文法需要實現遞歸結構。比如下面的 if 語句。

if (cond) { ...} else { if (cond2) {} }

某些特定的語言要素，比如 Python 中作為代碼塊的空白縮進，屬於上下文有關文法，但因為語義足夠簡單，並不需要完備的一型文法分析，只需要對相關的部分做一些標註即可。

不過有一點希望大家注意：語法有時和語義掛鉤，但語義並不決定語法。比較典型的例子是 Perl 的 $_。它在不同上下文里含義區別極大，但那是程序生成邏輯的問題，於語法分析階段，卻並無特定處理。

檢查一個語言是否為type 3 (regular) 或者 type 2 (context-free) 可以用相應的pumping lemma. 打字好慢，直接截屏貼圖了……

目前好像沒有直接的定理可以用來分辨一個語言是否是type 1 (context-sensitive)。