這些日子花了不少時間在一個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語法分析算法的支持。