昨天剛剛完備了
Vczh Library++3.0對于基本的分析器的支持。分析器主要有兩部分組成，第一部分是語法分析器。這個分析器通過程序員直接寫在C++里面的語法來分析一個輸入。第二部分是詞法分析器，這是通過實現一個正則表達式引擎來完成的。為了讓分析其更加靈活，分析器使用模板來寫，輸入只要滿足一定的接口就可以了。
Vczh Library++3.0內置字符串輸入、迭代器輸入和列表輸入。于是在單元測試里面就寫了兩段代碼來分析一個四則運算式子，第一個沒有詞法分析器，第二個用了詞法分析器。
我們先來分析一下四則運算式子的一般做法。總的來說我們會先寫一個不包含左遞歸的文法：
1 FACTOR = NUM | ( EXP )
2 TERM = FACTOR (MUL FACTOR)*
3 EXP = TERM (ADD TERM)*
從EXP開始，我們就可以將一個四則運算式子的結構表達出來了。我們先用
Vczh Library++3.0提供的庫，通過直接分析輸入的字符串來拆解一個四則運算式子并將其結果計算出來：
首先我們需要一個函數，這個函數輸入兩個整數和一個字符（代表操作符）來計算出結果。當然因為分析其本身的要求，操作符和右操作數是一個pair：
1 int cal(const int& first, const ParsingPair<wchar_t, int>& second)
2 {
3 int result=first;
4 switch(second.First())
5 {
6 case L'+':
7 result+=second.Second();
8 break;
9 case L'-':
10 result-=second.Second();
11 break;
12 case L'*':
13 result*=second.Second();
14 break;
15 case L'/':
16 result/=second.Second();
17 break;
18 }
19 return result;
20 }
接下來，我們要在C++里面寫一個文法：
1 typedef Rule<StringInput<wchar_t>, int> _Rule;
2 typedef Node<StringInput<wchar_t>, int> _Node;
3
4 _Rule FACTOR, TERM, EXP;
5 FACTOR = rgx(L"/d+")[wtoi] | (ch(L'(')>>EXP<<ch(L')'));
6 TERM = lrec(FACTOR + *(chs(L"*/") + FACTOR), cal);
7 EXP = lrec(TERM + *(chs(L"+-") + TERM), cal);
是不是比較直觀捏。現在來解釋一下里面的內容。
首先對于FACTOR = rgx(L"/d+")[wtoi] | (ch(L'(') >> EXP << ch(L')'));，我們知道這其實就是FACTOR = NUM | ( EXP )。這里rgx是一個正則表達式的輸入檢查，如果輸入的字符串是整數那么就走左邊的，如果輸入的第一個字符是括號就走右邊的。a >> b << c的意思是輸入必須是先a后b后c，然后拋棄a和c的分析結果只留下b。這個很好理解，分析完我們只需要那個EXP不需要兩個括號的。a[b]的意思是把a的分析結果用b函數轉換一下。rgx的結果自然是一個字符串，會告訴你輸入的整數究竟是什么，然后通過函數wtoi將字符串轉換成整數。
剩下兩條都比較像。我們知道左遞歸的寫法是：TERM = FACTOR | TERM MUL FACTOR，因為我的分析器不能直接支持左遞歸，所以需要一個變換：TERM = FACTOR (MUL FACTOR)*，但是這樣計算函數寫起來會很麻煩，所以我提供了一個lrec組合子將非左遞歸的模式在計算完成之后，重新轉成左遞歸，然后調用那個cal函數。因此cal函數才需要三個參數，如果不用lrec的話，cal將是一個整數，還有一個操作符和整數的列表，寫起來比較麻煩。
最后就剩下分析了：
1 {
2 Types<StringInput<wchar_t>>::GlobalInfo info;
3 StringInput<wchar_t> input=L"(1+2)*(3+4)";
4 ParsingResult<int> result=EXP.Parse(input, info);
5 TEST_ASSERT(result);
6 TEST_ASSERT(result.Value()==21);
7 TEST_ASSERT(info.errors.Count()==0);
8 }
9 {
10 TEST_ASSERT(EXP.Parse(L"(10+20)*(30+40)", false)==2100);
11 }
Vczh Library++3.0提供了兩種分析方法，分別對于需要知道詳細的錯誤信息和不需要知道詳細的錯誤信息來做。如果程序員可以假定輸入正確，或者說不需要報告那么詳細的輸入錯誤信息的話，使用第二種方法就行了，一行代碼搞定。
那么接下來看第二種。第二種我們走傳統道路，先詞法分析后語法分析。詞法分析把輸入分成了5種記號，分別是整數、左括號、右括號、加法和乘法，用正則表達式來描述：
1 typedef Rule<TokenInput<RegexToken>, int> _Rule;
2 typedef Node<TokenInput<RegexToken>, RegexToken> _Node;
3
4 List<WString> tokens;
5 tokens.Add(L"/d+");
6 tokens.Add(L"/(");
7 tokens.Add(L"/)");
8 tokens.Add(L"/+|-");
9 tokens.Add(L"/*|//");
10
11 RegexLexer lexer(tokens.Wrap());
12
13 _Node NUM=tk(0);
14 _Node OPEN=tk(1);
15 _Node CLOSE=tk(2);
16 _Node ADD=tk(3);
17 _Node MUL=tk(4);
因此我們的cal函數就要變一變了，同時還要提供一個tval函數將RegexLexer分析出的一個記號RegexToken轉成整數：
1 int tcal(const int& first, const ParsingPair<RegexToken, int>& second)
2 {
3 int result=first;
4 int value=second.Second();
5 switch(*second.First().reading)
6 {
7 case L'+':
8 result+=value;
9 break;
10 case L'-':
11 result-=value;
12 break;
13 case L'*':
14 result*=value;
15 break;
16 case L'/':
17 result/=value;
18 break;
19 }
20 return result;
21 }
22
23 int tval(const RegexToken& input)
24 {
25 return wtoi(WString(input.reading, input.length));
26 }
至此剩下的都差不多了。我相信看懂了第一種做法的人可以直接看懂第二種做法，因為只是換了一個輸入類型而已，剩下的內容都是一樣的：
1 _Rule FACTOR, TERM, EXP;
2 FACTOR = NUM[tval] | (OPEN >> EXP << CLOSE);
3 TERM = lrec(FACTOR + *(MUL + FACTOR), tcal);
4 EXP = lrec(TERM + *(ADD + FACTOR), tcal);
5
6 {
7 WString code=L"(1+2)*(3+4)";
8 List<RegexToken> tokens;
9 CopyFrom(tokens.Wrap(), lexer.Parse(code));
10 Types<TokenInput<RegexToken>>::GlobalInfo info;
11 TokenInput<RegexToken> input(&tokens[0], tokens.Count());
12 ParsingResult<int> result=EXP.Parse(input, info);
13 TEST_ASSERT(result);
14 TEST_ASSERT(result.Value()==21);
15 TEST_ASSERT(info.errors.Count()==0);
16 }
17 {
18 WString code=L"(10+20)*(30+40)";
19 List<RegexToken> tokens;
20 CopyFrom(tokens.Wrap(), lexer.Parse(code));
21 TokenInput<RegexToken> input(&tokens[0], tokens.Count());
22 TEST_ASSERT(EXP.Parse(input, false)==2100);
23 }
這里需要注意的是由于lexer.Parse返回的記號里面只保存了wchar_t*，所以變量code有必要存活下來，不然那個指針就會被釋放掉。此法的過程還是比較麻煩的，要多寫四行。這里并沒有過濾空格，如果需要過濾空格的話，用一下linq：
1 bool DiscardBlank(const RegexToken& token)
2 {
3 //如果token有定義返回true，空格沒有定義會返回false。
4 return token.token!=-1;
5 }
然后把CopyFrom那行改成：CopyFrom(tokens.Wrap(),
lexer.Parser(code)>>Where(DiscardBlank));就完了。linq萬歲！
至此兩種方法就介紹完了，上面的測試代碼和分析器的源代碼都可以在
Vczh Library++3.0找到。
posted on 2010-03-06 21:02
陳梓瀚(vczh) 閱讀(2636)
評論(2) 編輯 收藏 引用 所屬分類:
VL++3.0開發紀事