Arsenal詞法分析器

目標(biāo)組件：

• 可配置的詞法分析器
• 可配置的LR-Parser
• Ray: 類C的中間語(yǔ)言
• 匯編器
• 相關(guān)設(shè)計(jì)，測(cè)試工具

已完成組件：

• 可配置的詞法分析器
• 可配置的LR-Parser，支持SLR(1),LALR(1)
• 文法設(shè)計(jì)工具
  1. BNF Compiler,生成SLR(1),LALR(1)分析表
  2. 內(nèi)建錯(cuò)誤處理
  3. 實(shí)時(shí)觀測(cè)語(yǔ)法及其分析樹(shù)
  4. 實(shí)時(shí)報(bào)告分析表，沖突，F(xiàn)irst Follow集合以及左遞歸，左因子

目錄結(jié)構(gòu)：

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

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

用法：

1. 在Grammar Designer中，選項(xiàng)Tools->Generate->Template會(huì)根據(jù)當(dāng)前詞法和語(yǔ)法規(guī)則，自動(dòng)生成一份調(diào)用Arsenal庫(kù)的.c模板.

詞法分析部分：

1. 例子 ：請(qǐng)參考./misc/grammar/中的例子.
2. 技 術(shù)細(xì)節(jié): 基于NFA的Pseudo-Parallel正則表達(dá)式引擎，支持正向預(yù)搜索，逆向預(yù)搜索，貪婪，非貪婪，循環(huán)等操作，支持SINGLELINE IGNORECASE模式，不支持MULTILINE，"^" "$"永遠(yuǎn)匹配整個(gè)輸入的首尾，但是擴(kuò)展了關(guān)鍵字"\B" "\E"以便匹配行首尾，"."在默認(rèn)不匹配"\n",SINGLELINE下匹配所有字符。

語(yǔ)法分析部分：

• 目 標(biāo)： 在最開(kāi)始我并沒(méi)有想把這兩樣?xùn)|西通用化，僅僅想做一個(gè)比較精簡(jiǎn)的基于遞歸下降技術(shù)的類C解釋器（應(yīng)該會(huì)去掉很多晦澀的C語(yǔ)法支持），但是在實(shí)踐過(guò)程中，我 發(fā)現(xiàn)需要一些工具，例如便于實(shí)時(shí)設(shè)計(jì)和修正文法以及觀測(cè)此文法接受的語(yǔ)言和其具體語(yǔ)法樹(shù)（包括錯(cuò)誤處理之后的）等等，因此才決定實(shí)現(xiàn)一個(gè)可配置的LR分析 器。另外，一個(gè)被常問(wèn)到的問(wèn)題是，自己寫(xiě)一個(gè)類似yacc的庫(kù)有什么用處？我只能說(shuō)，這個(gè)東西可以輕易的改裝成任何我需要的東西，不論是對(duì)UI的友好程度 還是線程安全性以及其執(zhí)行時(shí)的解釋性質(zhì)，至少很難拿yacc做個(gè)像樣的設(shè)計(jì)工具出來(lái)。

• 實(shí)現(xiàn)：
  1. 實(shí)現(xiàn)簡(jiǎn)單的說(shuō)就是個(gè)LR理論的瘦封裝，生成Action和Goto表，之后每個(gè)產(chǎn)生式注冊(cè)一個(gè)語(yǔ)義動(dòng)作，收集節(jié)點(diǎn)，自底向上最終生成一顆AST。

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

• 優(yōu)先級(jí)，結(jié)合性：同樣和yacc的準(zhǔn)則類似，優(yōu)先選擇移入，每條產(chǎn)生式的優(yōu)先級(jí)默認(rèn)是其最右終結(jié)符號(hào)，也可以單獨(dú)指定產(chǎn)生式的優(yōu)先級(jí)以及結(jié)合性。例如：

%left '+', '-';

%left '*', '/', '%';

%right UMINUS;

E -> E '+' E | E '-' E | E '*' E | E '/' E | E '%' E | '-' E %prec UMINUS | '(' E ')';

這里，配置起來(lái)的 前兩條產(chǎn)生式的優(yōu)先級(jí)結(jié)合性是其最右終結(jié)符，也就是'+' '-', 之后三條是'*' '/' '%' ,在

E -> '-' E %prec UMINUS

中，其優(yōu)先級(jí)結(jié)合性取自符號(hào)UMINUS，而最后一個(gè)

E->'(' E')'

的優(yōu)先級(jí)為默認(rèn)的，默認(rèn)為0和無(wú)結(jié)合性。

• 實(shí)例：先簡(jiǎn)單說(shuō)下具體用法，因?yàn)椴捎玫氖潜眚?qū)動(dòng)的Shift-Reduce Parser，所以Parser的接口提供了一個(gè)名為PSR_AddToken的函數(shù)，每次調(diào)用處理一個(gè)詞法值，直到移入它，此函數(shù)返回，當(dāng)EOI被接受 后，此Parser狀態(tài)為接受狀態(tài)，所以實(shí)用中是詞法分析器調(diào)用語(yǔ)法分析器。關(guān)于語(yǔ)法樹(shù)的構(gòu)建實(shí)際上是靠針對(duì)每條產(chǎn)生式注冊(cè)一個(gè)相關(guān)的Action- Handler來(lái)完成的，詳情請(qǐng)參考實(shí)例：./Arsenal/Tools/grammar_config.c,里面實(shí)現(xiàn)一個(gè)完整的基于Arsenal的 語(yǔ)法配置程序.一個(gè)完整的應(yīng)用Arsenal的例子是./Tools/GrammarDesigner/,一個(gè)基于MFC的文法設(shè)計(jì)工具，可以用其觀測(cè)大 部分文法的具體語(yǔ)法樹(shù)。基于時(shí)間關(guān)系，文檔也不可能寫(xiě)的相當(dāng)詳細(xì)，而且代碼還處于不斷的修改中，所以有人對(duì)其有興趣的話可以聯(lián)系我。

• 錯(cuò) 誤報(bào)告： 這是個(gè)不太好設(shè)計(jì)的部分，暫時(shí)權(quán)宜之計(jì)是在AR_Init中注冊(cè)統(tǒng)一的error以及print handler，并由統(tǒng)一的AR_error和AR_printf調(diào)用，在AR_printf假設(shè)UI共享同一個(gè)終端，另外每個(gè)子模塊例如lex_t被創(chuàng) 建出來(lái)時(shí)需要注冊(cè)一個(gè)ioctx_t;例如：

 
typedef void    (AR_STDCALL *AR_error_func_t)(int_t level, const wchar_t *msg, void *ctx);
typedef void    (AR_STDCALL *AR_print_func_t)(const wchar_t *msg, void *ctx);


typedef struct __arsenal_io_context_tag
{
                AR_error_func_t on_error;
                AR_print_func_t on_print;
                void                    *ctx;
}arIOCtx_t;

在需要報(bào)告錯(cuò)誤時(shí)，lex_t內(nèi)部會(huì)調(diào)用例如：

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

等等，暫時(shí)限于我對(duì)此類軟件的理解，只能如此設(shè)計(jì)。

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

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

聯(lián)系方式:

1. Email：[email protected]
2. GTalk: [email protected]
3. QQ : 2070341