novus log

「C++ 是 context-free 嗎？」這是我在很長一段時間裡，分別在 stackoverflow.com 等許多地方都看過的問題。類似的問題還有其他變形，有時主角換成別的程式語言，或者變成「...是否為 context-sensitive」等等。

我發覺這類問題似乎具有某種雞同鴨講和鬼打牆的傾向，有些參與者沒有先釐清概念、用詞也不統一，以致於耗費大量篇幅卻難以觸及重點，反而顯示出許多人對於形式語言充滿誤解。我甚至看過一些人拿某某程式語言不是 context-free 做為不喜歡某某語言的理由，但是他很明顯沒有搞懂 context-free 的意義。

攤開 C++ 的規格書，裡面有一份詳盡的文法，其中每條 production rule 左邊都只有一個 non-terminal，所以是 context-free grammar (CFG)。這裡要注意的是「ISO C++ 規格書附的文法」並不是形式語言意義上「C++ 語言的生成文法」，因為「ISO 規格書附的文法」所生成的字串不保證滿足所有 C++ 語言規範。

以下為了方便區隔「和語言等效的生成文法」，所以特別將規格書上的這份文法稱為 syntax。 照這裡的定義，我們可以說 C++ 的 syntax 確實是 context-free。（我知道有些情境下提及 syntax check、syntactically correct 時涵蓋範圍不僅於此，只是一時也找不到其他合用的名詞，所以暫且使用這裡的定義吧。）

但是有很多資訊並沒有被編入 C++ syntax 當中，舉例來說，ISO 規格書附的文法並沒有包含 one-definition rule，沒告訴你使用前要宣告...... 像下面這條 production rule 規定了函數宣告或定義時的參數列形式：

parameter-declaration-list:
    parameter-declaration
    parameter-declaration-list, parameter-declaration

但是光這樣一條規則，沒有辦法限制呼叫函數時參數數量要與宣告時一致。因為以上這些限制不屬於 syntax 的一部分，而是被混雜在好幾百頁的語意描述當中。

想一下，如果將 one-definition rule、使用前須宣告、函數參數數量匹配等規範都納入考量，會是什麼光景？從自動機的角度來看，有沒有辦法設計一個 nondeterministic pushdown automaton (NPDA) 來判別任一給定的字串屬不屬於合法的 C++ 程式；又或者從生成文法的角度來看，有沒有辦法設計一個 CFG生成所有合法的 C++ 字串？

畢竟 C++ 語言太複雜，這裡不提供嚴謹的分析。從直覺上來看，像這種使用者可以自訂識別符號、又要重複使用識別符號的文字排列規則，大概都超出 NPDA 的計算能力之外，因為 NPDA 只能用 stack 儲存可變資訊。CFG 或 NPDA 甚至無法處理像L = { ww | w 屬於 {a, b}* }這麼簡單的符號重複；對了，如果你會用 pumping lemma 證這題而且夠無聊的話，也可以用同樣的手法證明 XML 的 <w> </w> 標籤配對不是 context-free。

包含 C++ 和 XML 在內，一般人舉得出來的程式語言常常可以發現類似的機制，所以可以說許多程式語言本質上都不是 context-free。但是這根本不是什麼大問題，人們習慣將問題分解成許多層級，一個層級只解決一部分相對簡單的問題。在實作時，程式語言設計者還是能用 CFG 寫出一份完整的 syntax，然後將那些無法用 CFG 表達的資訊塞到語意規範裡面。就算在實作 parser 時需要重寫部分文法，也只會使文法變得更精確且適於實作而已。

總結前面所述，我們可以得到兩個結論：

1. C++ 的 syntax 是 context-free。
2. C++ 語言本身不是 context-free；雖然我沒做過嚴謹的分析，但我猜大部分的程式語言本質上都不是 CFL。

回到原點，我假設當一個人發起「某語言是否為 context-free 嗎」這樣的討論串時，目的是想得知處理某個語言所需的計算能力是否高於另一些語言，這也是發展形式語言與自動機理論的主要動機。

這樣的話，討論「某個程式語言本質上是否為 CFL」並不是一個很好的切入點，因為 parser 實作者並非在這個層級上思考與解決問題，而且 parsing 的目的在於決定正確的 syntax tree，這和為了探討抽象理論而生的「生成」或「判別」問題已經有了差別。即使能得到一些理論上正確的結論，對於實務卻沒有太大的幫助。這個量尺會將 XML 和 C++ 都歸到 non-context-free，儘管經驗告訴我們處理這兩種語言的難度頗具差異。

據我觀察，有些人之所以會產生 C++ 非 context-free 這樣的印象，應該是源於 parse C++ 非常依賴語意此一特質。

foo * x;        // 宣告指標？ 乘法運算子？
bar < u > y;    // template？ 比較運算子？

應該不難想像，上面兩道 statement 各自滿足兩條以上的文法推導途徑，而不同的文法推導途徑則會產生截然不同的 syntax tree。至於要選擇哪一條文法推導途徑，則取決於至目前為止所收集到的語意資訊 -- foo、x、bar、u、y 這些識別符號到底屬於什麼？

有些人將這樣的現象稱之為「context sensitivity」，以英文詞義來說當然沒有問題，但意義已經不同於形式語言分類所說的 context-sensitive language (CSL)，只是在描述 parser 的行為而已。我不太喜歡用 context sensitivity 來描述 parser 此一的行為，因為在討論 parsing 的語境中，總會有人產生這樣的誤解：「某些程式語言之所以比較不好處理，就是因為這些語言本質上屬於 CSL」。

對於這樣的誤解，有基本常識的人馬上就會發現一個語病：形式語言中的 CSL 並不代表 CFL 的反義，雖然語意依賴往往意味著語言包含無法用 CFG 規範的成分，但要怎麼知道這樣的語言會是 CSL，而非 recursive 或 recursively enumerable？其實到這裡已經沒必要再鑽牛角尖下去了，因為結論對實作沒有太大的意義，現實中的程式語言轉譯大都是靠 syntax directed translation -- 關鍵是 syntax。

C++ 和絕大多數程式語言一樣都有一份以 CFG 描述的 syntax，只不過 C++ 的 syntax 屬於 CFG 當中比較不友善的一類：C++ 的 syntax 存在 ambiguous，而且是無藥可救的那種；更棘手的是必須靠語意資訊以消除 ambiguous。

廣泛被使用的 LL(k)、LALR(k) 和 LR(k) parser 能力都不超過 Deterministic CFG (DCFG) -- 這是 unambiguous CFG 的真子集，這些 parser 期待只要讀入有限的語彙元素，就能毫無疑問的套上單一條文法生成規則。以這些演算法為基礎的 parser 產生器，先天上就不足以處理 ambiguous CFG。

實務上，這些 parser 產生器通常可以讓使用者指定某些靜態 policy 來排除 ambiguous。舉個最典型的例子，使用 LR 類 Parser 時，可以選擇 shift 優先於 reduce 來解決 dangling else 問題。另外，運算子的 associativity 也可算是這種靜態 policy 之一。但 C++ 需要依賴即時的語意資訊來選擇文法推導途徑，就不是這類靜態 policy 所能解決的。

另一個難題在於，為了解決語意依賴的現象，必須要有一些機制將目前所收集的語意資訊前饋到編譯前期、甚至是語彙分析階段，C++ 繁瑣的作用域和名稱查詢規則讓問題更雪上加霜。

由於 parsing 演算法先天上的不足，硬要做的話就只能靠後天努力。《Parsing Non-LR(k) Grammars with Yacc》這篇文章示範了一些技巧，讓基於 LALR(1) 的 yacc 也有機會處理非 LR(k) 的文法。在權衡利弊得失之後，有些情況下純手工打造的 parser 可能還比較容易維護，也有機會提供更多彈性。GCC 在很久以前就放棄用 parser 產生器，Clang front-end 也是純手工打造。

更強力的 parser 當然也存在，只是在時間或空間方面必須付出一定的代價，除錯也更複雜。其中一個很直覺的方案是在 LR 或 LL 加上 backtracking 機制。此外 LL(*) 有能力處理某種程度的 ambiguous，而 CYK、Earley、GLR 都可以處理完整的 CFG。理論上處理任意 CFG 最糟情況的時間複雜度為 O(n^3)，不過 GLR 在 DCFG 情況下也可以擁有 O(n) 的複雜度，與 LR 相當，較 CYK 和 Earley 略勝一籌。收集與傳遞所需的語意資訊仍然是使用者必須頭痛的地方，不過這些比較強力的 parser 通常可以靠後設的方法來解析語意，也緩解了語意資訊前饋的需求。

以上談的只是分析文字架構的部分，至於要執行完整的語意又是另一個故事了。

註記：

• 不知為什麼，總是有人在討論 CFL 判斷時刻意舉 ambiguous 的例子，事實上有一些 CFL 就是無藥可救的 ambiguous（Inherently ambiguous）。大致上的階層為：

  • CFL 可分成 ambiguous 和 unambiguous 兩類，而 deterministic CFL 又為 unambiguous CFL 的真子集。
  • LR(k) 能處理的語言相當於 DCFL。更強的演算法像 GLR、Earley、CYK 等等都可以處理整個 CFL。
  • 對所有常數 k，能用 LL(k) 處理的語言皆為 LR(k) 語言的真子集。至於 LL(*) 則和 LR(k) 互不相屬，LL(*) 可以處理某些 ambiguous CFL，但是卻無法處理某些 DCFL。
  • 一些常用的語言/文法階層關係：http://cs.stackexchange.com/questions/43/language-theoretic-comparison-of-ll-and-lr-grammars

• 我看過一些作者很口語化的使用 context sensitivity 來泛指各種脈絡上的依賴，閱讀時要注意，作者不一定在討論形式語言。當然，在不會引起誤解的語境講 context sensitive 並沒有什麼不妥，例如編譯器在進行 interprocedural optimization 時，也有一個名為 context-sensitive analysis 的分析法，應該就沒有什麼誤會的空間。

• 一些我目前所知道的 parser 自動產生技術應用於 C++ 的現況：

  • 目前由機器自動生成的 C++ parser 當中最成功的應該是 Elsa，由採用 GLR 的Elkhound所生成。現代的 GNU Bison 也支援 GLR，理論上也做得到，但是好像沒聽說有成熟的實作。
  • 基於 backtracking LR 的BtYacc和Kelbt都是為了 C++ 這麼複雜的語言而生，據我所知兩者還未有 production 等級的 C++ parser，不過已經示範了這樣的技術在 C++ 上是可行的。
  • 至於 LL(*) 方面，我對 ANTLR 抱有一定程度的期望，但也沒聽說有成熟的實作。
  • Scalpel嘗試運用 Boost.Spirit/Wave 實作 C++ 靜態分析器，完成度未知。

我認為上面提到的這些方法之所以還沒有成熟的實作，有很大的一部分原因是缺乏投入動機，而現有的手工 parser 又足以使用。這裡提供的資訊很可能已經落後，歡迎知道詳情的讀者補充。