C/C++ 的語法是 LL(1) 語法嗎？

01-05

按照C/C++的語言規範，是否可以構造出符合LL(1)的上下文無關文法，以應用LL(1)分析演算法建立抽象語法樹？

C++ 語法根本不是 context-free。AA bb(cc); 這句話根據八百萬行之前的定義不同，AST 天壤之別。

補充： @陳碩提到了 C 也不是 context-free。不過「X* y;」可能是 C 里唯一的例子。而這個例子只要簡單的查一下 X 的類型就行。這個例子更像 Python 的縮進：縮進本身導致了 Python 不是 context-free，但是只要做一個簡單的預處理就能變成 context-free。而 C++「AA bb(cc);」本身可以是對一個新名稱 bb 的 declaration，無法通過簡單的判定 AA 的類型來決定。所以 C++ 的語法複雜程度和 C 不是一個層次的。

C 語言的語法也不是 context-free，它有 the 「typedef-name: identifier」 problem。比如 X* y; 可以是乘法表達式語句，也可以是定義 y 為指向 X 的指針。(T)*p, 可以是把 *p 強制轉型為 T，也可以是乘法表達式。

The context sensitivity of C"s grammar

C++貌似不能，維基百科上有記述

http://en.wikipedia.org/wiki/C%2B%2B

It is relatively difficult to write a good C++ parser with classic parsing algorithms such as LALR(1).

[29]

This is partly because the C++ grammar is not LALR. Because of this, there are very few tools for analyzing or performing non-trivial transformations (e.g., refactoring) of existing code. One way to handle this difficulty is to choose a different syntax. More powerful parsers, such as GLR parsers, can be substantially simpler (though slower).

Parsing C++ is even undecidable!

即使預處理後的C++代碼也不是上下文無關。

例子: f&(a)

這個需要在parse到此處時，知道f的類型才能正確模擬C++的語義。

不是上下文無關文法，比如變數沒定義不能使用。

上下文相關是通過編譯時的符號表解決的。