昨天刚刚完备了
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) 阅读(2616)
评论(2) 编辑 收藏 引用 所属分类:
VL++3.0开发纪事