這些日子花了不少時(shí)間在一個(gè)c語言的語法分析程序上，這個(gè)程序要能識別變量、函數(shù)的定義、聲明和引用，簡而言之就是找出sourceinsight所能提供的信息（比si還要精確）。

分析代碼和編譯代碼一樣，都要做語法分析。但是因?yàn)榉治龃a不做預(yù)處理，所以就會遇到一些麻煩，比如處理一些定義的稀奇古怪的宏，無法判斷一個(gè)identifier是變量還是類型。這么一來，嚴(yán)格的用C語言語法來分析代碼就沒法通過。

考慮到這個(gè)問題，一開始決定用lex作詞法分析，生寫語法分析。進(jìn)行到中間，代碼復(fù)雜度越來越高，感覺力不從心。又決定通過修改標(biāo)準(zhǔn)的C語言語法規(guī)則，用bison（yacc的GNU實(shí)現(xiàn)）來完成語法分析。

所謂“工欲善其事，必先利其器”，bison在做語法分析上，果然很方便。但是很快就遇到上面所說的問題：不做預(yù)處理，無法得到一個(gè)token的類型。標(biāo)準(zhǔn)的yacc支持的是LALR語法，LALR語法只預(yù)讀一個(gè)token，無法解決這個(gè)問題。

好在GNU的Yacc實(shí)現(xiàn)bison支持GLR語法，GLR沒有只預(yù)讀一個(gè)token的限制，它用狀態(tài)分裂來解決無法判斷token類型的問題。采用GLR，寫語法規(guī)則就基本上沒有什么限制了。

但是GLR有個(gè)問題，它用狀態(tài)分裂解決問題，如果所有分裂的狀態(tài)只有一個(gè)能分析成功，那自然OK；如果不能，就叫產(chǎn)生了ambiguity（不確定），分析就失敗了。

解決ambiguity，可以用%dprec來指定規(guī)則的優(yōu)先級。當(dāng)兩個(gè)狀態(tài)發(fā)生ambiguity時(shí)，根據(jù)它們對應(yīng)的reduce規(guī)則的優(yōu)先級，選擇優(yōu)先級高的那個(gè)狀態(tài)。

但還有一類ambiguity的情況，用%dprec也沒發(fā)解決。那就是兩個(gè)產(chǎn)生ambiguity的狀態(tài)它們對應(yīng)的reduce規(guī)則是同一條。這類問題很棘手，我只好采用重寫規(guī)則來避免。但這就導(dǎo)致規(guī)則的可讀性很差，而且往往是解決一個(gè)ambiguity又引入另外一個(gè)。

無奈，往bison的mail list里發(fā)了一封信求救，第二天收到一哥們回信，信中說：

“用merge啊。我也遇到過類似的問題。”

merge是啥呢？merge就正好是處理上面這類問題的，相當(dāng)于把多個(gè)狀態(tài)合并。因?yàn)槭潜容^新的特性，在bison的文檔里并沒有很明顯的提及。

這樣，用bison分析c代碼就基本沒有問題了;)

備注

Flex:詞法分析器

Bison:語法分析器

GNU bison是一個(gè)自由軟件，用于自動生成語法分析器程序，實(shí)際上可用于所有常見的操作系統(tǒng)。Bison把LALR形式的上下文無關(guān)文法描述轉(zhuǎn)換為可做語法分析的C或C++程序。在新近版本中，Bison增加了對GLR語法分析算法的支持。

GNU bison基本兼容Yacc，并做了一些改進(jìn)。它一般與flex一起使用。