這些日子花了不少時間在一個c語言的語法分析程序上，這個程序要能識別變量、函數的定義、聲明和引用，簡而言之就是找出sourceinsight所能提供的信息（比si還要精確）。
分析代碼和編譯代碼一樣，都要做語法分析。但是因為分析代碼不做預處理，所以就會遇到一些麻煩，比如處理一些定義的稀奇古怪的宏，無法判斷一個identifier是變量還是類型。這么一來，嚴格的用C語言語法來分析代碼就沒法通過。
考慮到這個問題，一開始決定用lex作詞法分析，生寫語法分析。進行到中間，代碼復雜度越來越高，感覺力不從心。又決定通過修改標準的C語言語法規(guī)則，用bison（yacc的GNU實現）來完成語法分析。
所謂“工欲善其事，必先利其器”，bison在做語法分析上，果然很方便。但是很快就遇到上面所說的問題：不做預處理，無法得到一個token的類型。標準的yacc支持的是LALR語法，LALR語法只預讀一個token，無法解決這個問題。
好在GNU的Yacc實現bison支持GLR語法，GLR沒有只預讀一個token的限制，它用狀態(tài)分裂來解決無法判斷token類型的問題。采用GLR，寫語法規(guī)則就基本上沒有什么限制了。
但是GLR有個問題，它用狀態(tài)分裂解決問題，如果所有分裂的狀態(tài)只有一個能分析成功，那自然OK；如果不能，就叫產生了ambiguity（不確定），分析就失敗了。
解決ambiguity，可以用%dprec來指定規(guī)則的優(yōu)先級。當兩個狀態(tài)發(fā)生ambiguity時，根據它們對應的reduce規(guī)則的優(yōu)先級，選擇優(yōu)先級高的那個狀態(tài)。
但還有一類ambiguity的情況，用%dprec也沒發(fā)解決。那就是兩個產生ambiguity的狀態(tài)它們對應的reduce規(guī)則是同一條。這類問題很棘手，我只好采用重寫規(guī)則來避免。但這就導致規(guī)則的可讀性很差，而且往往是解決一個ambiguity又引入另外一個。
無奈，往bison的mail list里發(fā)了一封信求救，第二天收到一哥們回信，信中說：
“用merge啊。我也遇到過類似的問題。”
merge是啥呢？merge就正好是處理上面這類問題的，相當于把多個狀態(tài)合并。因為是比較新的特性，在bison的文檔里并沒有很明顯的提及。
這樣，用bison分析c代碼就基本沒有問題了;)
備注
Flex:詞法分析器
Bison:語法分析器
GNU bison是一個自由軟件，用于自動生成語法分析器程序，實際上可用于所有常見的操作系統。Bison把LALR形式的上下文無關文法描述轉換為可做語法分析的C或C++程序。在新近版本中，Bison增加了對GLR語法分析算法的支持。
