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