「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 的BtYaccKelbt都是為了 C++ 這麼複雜的語言而生,據我所知兩者還未有 production 等級的 C++ parser,不過已經示範了這樣的技術在 C++ 上是可行的。
    • 至於 LL(*) 方面,我對 ANTLR 抱有一定程度的期望,但也沒聽說有成熟的實作。
    • Scalpel嘗試運用 Boost.Spirit/Wave 實作 C++ 靜態分析器,完成度未知。

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

novus 發表在 痞客邦 PIXNET 留言(0) 人氣()