詞法分析器 Arsenal

目標組件：

• 可配置的詞法分析器
• 可配置的LR-Parser
• Ray: 類C的中間語言
• 匯編器
• 相關設計，測試工具

已完成組件：

• 可配置的詞法分析器
• 可配置的LR-Parser，支持SLR(1),LALR(1)
• 文法設計工具
  1. BNF Compiler,生成SLR(1),LALR(1)分析表
  2. 內建錯誤處理
  3. 實時觀測語法及其分析樹
  4. 實時報告分析表，沖突，First Follow集合以及左遞歸，左因子
  5. 

目錄結構：

1. ./Arsenal/Lex : 詞法分析器;
2. ./Arsenal/Parser : 語法分析器.
3. ./Arsenal/Common : 公共庫函數.
4. ./Arsenal/Tools : 一些必要的工具，例如讀取語法分析配置文件的工具等等.
5. ./Tools/GrammarDesigner : 基于MFC的文法設計工具.
6. ./Prj : 各種編譯器的工程(除了VS2K8之外的工程僅是為了測試代碼的兼容性)
7. ./misc 一些測試用的文法以及工具和一部分語言的yacc版.
8. ./binary/x86/dll/release : 編譯后，生成的x86平臺下的dll release版，其余binary下結構與其類似,
9. ./temp/ 編譯器生成的臨時文件，例如obj等.

• 其中，./Arsenal/可支持所有目標平臺，./Tools下的GrammarDesigner，僅支持win x86 X64.本工程所有生成的二進制文件都放在./Arsenal/binary下。所有引用到MFC的DLL版本都需要安裝vs2k8發行包:VS2008_Redistributable_Package

用法：

1. 在Grammar Designer中，選項Tools->Generate->Template會根據當前詞法和語法規則，自動生成一份調用Arsenal庫的.c模板.

詞法分析部分：

1. 例子 ：請參考./misc/grammar/中的例子.
2. 技 術細節: 基于NFA的Pseudo-Parallel正則表達式引擎，支持正向預搜索，逆向預搜索，貪婪，非貪婪，循環等操作，支持SINGLELINE IGNORECASE模式，不支持MULTILINE，"^" "$"永遠匹配整個輸入的首尾，但是擴展了關鍵字"\B" "\E"以便匹配行首尾，"."在默認不匹配"\n",SINGLELINE下匹配所有字符。

語法分析部分：

• 目 標： 在最開始我并沒有想把這兩樣東西通用化，僅僅想做一個比較精簡的基于遞歸下降技術的類C解釋器（應該會去掉很多晦澀的C語法支持），但是在實踐過程中，我 發現需要一些工具，例如便于實時設計和修正文法以及觀測此文法接受的語言和其具體語法樹（包括錯誤處理之后的）等等，因此才決定實現一個可配置的LR分析 器。另外，一個被常問到的問題是，自己寫一個類似yacc的庫有什么用處？我只能說，這個東西可以輕易的改裝成任何我需要的東西，不論是對UI的友好程度 還是線程安全性以及其執行時的解釋性質，至少很難拿yacc做個像樣的設計工具出來。

• 實現：
  1. 實現簡單的說就是個LR理論的瘦封裝，生成Action和Goto表，之后每個產生式注冊一個語義動作，收集節點，自底向上最終生成一顆AST。

• 錯 誤處理：我采用的是和yacc相當類似的一種技術--error token，首先error作為保留終結符，當有錯誤發生時，直接檢索當前Action Table是否有可以移入error，如果有，則移入，否則，向上pop_stack，直到可以接受終結符error為止，此時parser狀態進入 error狀態，在此狀態下任何非法的輸入符號均被丟棄，直到移入了一個在error上合法的符號（這里并非是終結符，請看例子），此時恢復到正常狀態。 如果任何錯誤發生時直到parser-stack空為止都不能接受終結符error，則分析失敗，否則帶error的產生式會被當作正常產生式處理，可以 在規約時處理這條錯誤產生式。例如A -> error ';'；當有任何錯誤發生時，parser會移入error直到移入';'后才會恢復到正常狀態。同樣的道理， A -> error TERM; TERM -> ';';同樣可以接受，實際上和上面的error -> ';'相同，只不過先做一次';'到TERM的規約動作，當然 A->error同樣可以接受，只是錯誤狀態被傳遞到A之后的符號，也可以在分析中清除Error狀態，例如在某個ActionHandler中調 用PSR_ClearError(...);

• 優先級，結合性：同樣和yacc的準則類似，優先選擇移入，每條產生式的優先級默認是其最右終結符號，也可以單獨指定產生式的優先級以及結合性。 

這里，配置起來的 前兩條產生式的優先級結合性是其最右終結符，也就是 '+' '-', 之后三條是 '*' '/' '%' ,在

E -> '-' E %prec UMINUS

中，其優先級結合性取自符號UMINUS，而最后一個

E->'(' E')'

的優先級為默認的，默認為0和無結合性。

• 實例：先簡單說下具體用法，因為采用的是表驅動的Shift-Reduce Parser，所以Parser的接口提供了一個名為PSR_AddToken的函數，每次調用處理一個詞法值，直到移入它，此函數返回，當EOI被接受 后，此Parser狀態為接受狀態，所以實用中是詞法分析器調用語法分析器。關于語法樹的構建實際上是靠針對每條產生式注冊一個相關的Action- Handler來完成的，詳情請參考實例：./Arsenal/Tools/grammar_config.c,里面實現一個完整的基于Arsenal的 語法配置程序.一個完整的應用Arsenal的例子是./Tools/GrammarDesigner/,一個基于MFC的文法設計工具，可以用其觀測大 部分文法的具體語法樹。基于時間關系，文檔也不可能寫的相當詳細，而且代碼還處于不斷的修改中，所以有人對其有興趣的話可以聯系我。

• 錯 誤報告： 這是個不太好設計的部分，暫時權宜之計是在AR_Init中注冊統一的error以及print handler，并由統一的AR_error和AR_printf調用，在AR_printf假設UI共享同一個終端，另外每個子模塊例如lex_t被創 建出來時需要注冊一個ioctx_t; 

在需要報告錯誤時，lex_t內部會調用例如：

AR_error_ctx(io_ctx, AR_ERR_FATAL, "error = %ls", err_msg);

等等，暫時限于我對此類軟件的理解，只能如此設計。

• 移植：
  1. 因為此類程序對系統調用幾乎沒有依賴，所以移植起來相對簡單，這里比較棘 手的問題是在某些編譯器下缺乏對于wchar_t以及相關CRT庫函數的支持，所以所有被引用到的CRT函數已被隔離在common.h中，以AR_為前 綴，如果移植的平臺編譯器等不支持相關函數，在必要時可能要單獨實現一套。未來可能會把所有IO部分的CRT都重寫為獨立的版本，因為類似sprintf 一族的函數缺乏統一標準，暫時是移植方面(甚至是編譯器間)最大的麻煩。
  2. strconv.c提供了utf8到 (utf16&&utf32 非可變長標準）的相互轉換，這塊可以認為是平臺無關的，wchar_t無論是配合win32下utf16的雙字節或linux下utf32的4字節在本程 序中都不成為問題。此類程序和是字符集本身幾乎沒有關系，wchar_t換成unsigned int等等照樣可以完成任務，此模塊僅僅是為了讀取一些配置文件時使用。
  3. thread.c中提供了靠CAS指令實現的spinlock，以提供Arsenal庫在多線程環境下的安全初始化以及某些數據結構池的分配。
  4. 請留意基本數據類型的字長，例如int_t被定義為和目標平臺字長相同，而并非32bit，而其它相關數值類型都由其后綴決定，例如int8_t int16_t int32_t int64_t等。wchar_t尤其相關編譯器決定，所以永不少于16bit。
  5. 我 的主要開發工具是VS2K8，Arsenal由ANSI C編寫，在VS2K8下可以完美的編譯為x86,X64并通過測試,另外Prj目錄中有VC6和BCB6的工程，在vs2K8之外都僅僅是編譯通過，支持 gcc4.x版本，在ubuntu 8.04下編譯通過,暫時沒精力去做其它平臺或者編譯器的大量測試，而且，請注意，我不能保證最新代碼完全可以在ubuntu下編譯通過的，一般都是在核 心模塊有變化的時候才會做一次兼容性測試，所以只能盡可能的保證方便的移植。

• 一些問題：
  1. 這 種可配置的詞法和語法分析器本質上都是通過模式構建一個狀態機，就像不良的程序導致錯誤一樣，這里有些不良的文法會導致它們生成死循環，很遺憾我沒辦法在 編譯時檢測它們，一個詞法模式的例子是比如（{name1}|{name2}|^)+這種模式導致的死循環，很難在對表達式做語法分析時檢測并報告它們。 而語法分析器部分相對要好一些，但是存在一種可能，導致在用error 嘗試容錯的時候變成無窮reduce空Rule：首先嘗試shift error，之后reduce Epsilon,但是shift Epsilon之后的狀態并不能shift error，這里會彈出Epsilon，繼續嘗試shift error，這就是又一個死循環了。因為中間不一定存在多少reduce操作，所以幾乎沒辦法知道如何從這個循環跳出去。
  2. 另一個被常 提及的問題是，例如如何描述C語言的聲明和typedef等，例如typedef int int_t; int_t x;諸如此類，當type_specifier -> ID的會產生沖突的問題，這里的答案是沒有辦法，LALR(1)不具備這種能力，也許GLR是一種選擇.但GLR的問題是錯誤報告和容錯異常復雜，我還沒 找到一種足夠標準的做法。