其實(shí)
Vczh Library++3.0提供的parser combinator并不能大量減少語法分析器的代碼量，其實(shí)真正降低的是語法分析器的復(fù)雜程度。當(dāng)你想比較快速的完成一個(gè)功能的時(shí)候，有兩種代碼量差不多的設(shè)計(jì)，一種實(shí)現(xiàn)起來比較難并且調(diào)試起來很慘，一種實(shí)現(xiàn)起來比較簡(jiǎn)單而且基本不用怎么調(diào)試，那相對(duì)來說肯定會(huì)選擇后一種方法了。除非你純粹是想獲得鍛煉。
使用parser combinator開發(fā)語法分析器的時(shí)候，你可以直接往C++里面寫EBNF語法，當(dāng)然語法的具體形式因?yàn)槭艿紺++語言本身的限制我做了一點(diǎn)點(diǎn)修改，譬如說A*和A+只好寫成*A和+A，A B只好寫成A + B、A>>B或者A<<B了。
空明流產(chǎn)跟我抱怨說boost::spirit編譯速度奇慢（據(jù)說要一個(gè)多小時(shí)，不知道是不是他機(jī)器太爛……）而且容易出現(xiàn)C1060 compiler is out of heap space的錯(cuò)誤，相比之下我在用我自己開發(fā)的parser combinator的時(shí)候，我一個(gè)充滿語法的cpp文件只需要一秒多一點(diǎn)（Thinkpad R61i, Vista Home Basic, 3G內(nèi)存），而且不會(huì)出現(xiàn)C1060這種離譜的錯(cuò)誤。至少從這個(gè)程度上來說，開發(fā)boost::spirit的人應(yīng)該是有很大的C++潔癖癥，才會(huì)把好好地一個(gè)parser combinator折騰成那個(gè)樣子。
我是用的文法模型是帶類型修飾的文法，從文法的類型只能看出文法最終給你什么數(shù)據(jù)，而不是文法他本身是怎么寫的。Vczh Library++2.0的parser combinator采用了后面一中的做法，據(jù)說boost::spirit也是這么做的，不過奇怪的是舊的parser combinator也沒出現(xiàn)那兩種錯(cuò)誤，取而代之是VC++經(jīng)常抱怨我一個(gè)表達(dá)式的類型簽名超過了4000個(gè)字符（囧）。于是
Vczh Library++3.0的parser combinator做了一點(diǎn)修改。
假設(shè)你一條文法A的結(jié)果是node<input, type>，第二條文法B的結(jié)果是node<input, string>，那么A+B的結(jié)果就是node<input, pair<type, string>>。這是什么意義呢？我們看表達(dá)文法type name semicolon的意思，大概可以理解為他可以接受“int a;”的這種語句。首先由于C++的限制我們替換成type + name + semicolon，其次由于那個(gè)semicolon，也就是分號(hào)，其實(shí)僅僅是語法的要求而不是語法樹的一個(gè)必須成分，因此改成type + name << semicolon。這樣的話，這個(gè)文法依舊會(huì)要求輸入的字符串分別是一個(gè)類型、一個(gè)名字和一個(gè)分號(hào)，但是返回的結(jié)果就自動(dòng)把分號(hào)給忽略掉了。那么我們?nèi)绾伪硎疽粋€(gè)同時(shí)包含type和name的類型呢？因?yàn)槲姆ú豢赡芴婺銊?chuàng)建一個(gè)struct，所以就定義了一個(gè)泛型的pair來表達(dá)。于是type + name << semicolon的結(jié)果類型就是node<input, pair<type, string>>了。這里input代表輸入的記號(hào)列表的類型。
上面是新的parser combinator的做法，舊的parser combinator（據(jù)說也是boost::spirit的做法）的類型表示方法比較BT：當(dāng)你有文法type : node<input, type>，string : node<input, string>和semicolon : node<input, token>的話，那么type + name << semicolon的類型會(huì)變成：
1 discard_right<input, sequence<input, node<input, type>, node<input, string>>, node<input, token>>
寫成這樣大概就可以理解什么是“文法他本身是怎么寫的”了吧。
舊的parser combinator的好處是C++為每一個(gè)文法生成了一個(gè)類型，雖然代碼會(huì)膨脹一點(diǎn)但是執(zhí)行過程會(huì)很快，只不過缺點(diǎn)比較多。第一個(gè)當(dāng)然是類型太多VC++編譯器會(huì)崩潰（C1060 compiler is out of heap space），第二個(gè)是編譯時(shí)間過長，第三個(gè)是當(dāng)你的文法比較長的時(shí)候，類型簽名可能會(huì)超過VC++給你的限制，然后就會(huì)出現(xiàn)奇怪的問題。所以我在
Vczh Library++3.0的parser combinator就是用了一個(gè)新的做法，也就是僅保留文法的結(jié)果類型，所以也就不得不引入虛函數(shù)了。因?yàn)橐粋€(gè)文法node<input, type>有非常多種組合可能，在結(jié)構(gòu)上沒辦法表現(xiàn)出來，所以必須使用虛函數(shù)。
在聽了
空明流產(chǎn)的抱怨之后，我去搜了一下使用boost::spirit的人的反應(yīng)，好像都是遇到了那兩個(gè)嚴(yán)重的問題。幸好我喜歡造車輪，不然的話也許也會(huì)深陷地獄了。不過boost::spirit還是提供了解決辦法的，就是把你的長的文法拆開成短的。寫過編譯器的人都會(huì)知道，這么做的嚴(yán)重后果就是你的分析器變成一團(tuán)亂麻，根本不知道自己在寫什么，不僅不可能有我
上一篇文章描寫的優(yōu)美結(jié)果，更不可能把
NativeX的分析器寫成下面這個(gè)樣子了：
1 primitive = TRUE[ToTrue] | FALSE[ToFalse]
2 | ACHAR[ToAChar] | WCHAR[ToWChar]
3 | ASTRING[ToAString] | WSTRING[ToWString]
4 | FLOAT[ToFloat] | DOUBLE[ToDouble]
5 | NULL_VALUE[ToNull]
6 | INTEGER[ToInteger]
7 ;
8 reference = ID[ToReference];
9
10 exp0 = primitive
11 | reference
12 | RESULT[ToResult]
13 | (CAST + (LT >> type << GT) + (OPEN_BRACE >> exp << CLOSE_BRACE))[ToCastExpression]
14 ;
15 exp1 = lrec(exp0 + *(
16 (OPEN_ARRAY + exp0 << CLOSE_ARRAY)
17 | (OPEN_BRACE + list(opt(exp + *(COMMA >> exp)))[UpgradeArguments] << CLOSE_BRACE)
18 | ((DOT | POINTER) + reference)
19 | (INCREASE | DECREASE)[UpgradePostfix]
20 ), ToPostUnary);
21 exp2 = exp1 | ((INCREASE | DECREASE | BIT_AND | MUL | SUB | BIT_NOT | NOT) + exp1)[ToPreUnary];
22 exp3 = lrec(exp2 + *((MUL | DIV | MOD) + exp2), ToBinary);
23 exp4 = lrec(exp3 + *((ADD | SUB) + exp3), ToBinary);
24 exp5 = lrec(exp4 + *((SHL | SHR) + exp4), ToBinary);
25 exp6 = lrec(exp5 + *((LT | GT | LE | GE) + exp5), ToBinary);
26 exp7 = lrec(exp6 + *((EQ | NE) + exp6), ToBinary);
27 exp8 = lrec(exp7 + *(BIT_AND + exp7), ToBinary);
28 exp9 = lrec(exp8 + *(XOR + exp8), ToBinary);
29 exp10 = lrec(exp9 + *(BIT_OR + exp9), ToBinary);
30 exp11 = lrec(exp10 + *(AND + exp10), ToBinary);
31 exp12 = lrec(exp11 + *(OR + exp11), ToBinary);
32 exp = lrec(exp12 + *((OP_ASSIGN | ASSIGN) + exp12), ToBinary);
33
34 primType = (FUNCTION + type + (OPEN_BRACE >> list(opt(type + *(COMMA >> type))) << CLOSE_BRACE))[ToFunctionType]
35 | (PRIM_TYPE | ID)[ToNamedType]
36 ;
37 type = lrec(primType + *(MUL | (OPEN_ARRAY >> INTEGER << CLOSE_ARRAY)), ToDecoratedType);
38
39 statement = SEMICOLON[ToEmptyStat]
40 | (exp + SEMICOLON)[ToExprStat]
41 | (VARIABLE + type + ID + opt(ASSIGN >> exp) << SEMICOLON)[ToVarStat]
42 | (IF + (OPEN_BRACE >> exp << CLOSE_BRACE) + statement + opt(ELSE >> statement))[ToIfStat]
43 | (BREAK << SEMICOLON)[ToBreakStat]
44 | (CONTINUE << SEMICOLON)[ToContinueStat]
45 | (EXIT << SEMICOLON)[ToReturnStat]
46 | (OPEN_STAT + list(*statement) << CLOSE_STAT)[ToCompositeStat]
47 | (DO + statement + (WHILE >> OPEN_BRACE >> exp << CLOSE_BRACE << SEMICOLON))[ToDoWhileStat]
48 | (LOOP + statement)[ToLoopStat]
49 | (WHILE + (OPEN_BRACE >> exp << CLOSE_BRACE) + statement + opt(WHEN >> OPEN_BRACE >> exp << CLOSE_BRACE << SEMICOLON))[ToWhileStat]
50 | (FOR + list(*statement) + (WHEN >> OPEN_BRACE >> exp << CLOSE_BRACE) + (WITH >> list(*statement)) + (DO >> statement))[ToForStat]
51 ;
52
53 declaration = (VARIABLE + type + ID + opt(ASSIGN >> exp) << SEMICOLON)[ToVarDecl]
54 | (TYPE + ID + (ASSIGN >> type) << SEMICOLON)[ToTypedefDecl]
55 | (STRUCTURE + ID << SEMICOLON)[ToStructPreDecl]
56 | (STRUCTURE + ID + (OPEN_STAT >> *(type + ID << SEMICOLON) << CLOSE_STAT))[ToStructDecl]
57 | (FUNCTION + type + ID + (OPEN_BRACE >> plist(opt((type + ID) + *(COMMA >> (type + ID)))) << CLOSE_BRACE) + statement)[ToFuncDecl]
58 ;
59
60 unit = ((UNIT >> ID << SEMICOLON) + list(opt(USES >> (ID + *(COMMA >> ID)) << SEMICOLON)) + list(*declaration))[ToUnit];
啊，簡(jiǎn)直就跟EBNF沒什么區(qū)別啊。
當(dāng)前的進(jìn)度可以在
Vczh Library++3.0的頁面上看到。
posted on 2010-03-20 23:49
陳梓瀚(vczh) 閱讀(4573)
評(píng)論(2) 編輯 收藏 引用 所屬分類:
VL++3.0開發(fā)紀(jì)事